Informatica Online Judge

  요리 [2278 / 08E6]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 6   Total Tried : 6


The Champion of this Problem (C++) : gs17044 - ms / 960byte
My Best Submission (C++) : N/A

[]

Background

세기의 주방장 이도연의 요리 철학은 남다르다. 그의 요리 철학은 “많이, 맛있게”로 요약할 수 있다.

그의 요리 철학은 그가 요리를 하는 방법에서 적나라하게 드러난다.

1. N개의 재료를 일렬로 늘어 놓는다.
2. 연속된 K개의 재료을 선택하고, 모두 한데 섞어 요리한다.
3. “많이”, 늘어놓은 재료들 중 K개를 선택할 때, 최대한 많은 재료들(즉, K가 최대이도록)을 선택할 것이다.
4. “맛있게”, 늘어놓은 재료들로 한 요리가 맛있어야한다. 요리의 맛은 각 재료들의 맛을 정수 로 표현할 때, 모든 재료의 값을 XOR한 값이다. 즉, i~(i+K-1)의 재료들을 사용했을 때 맛은 $a_i ⊕ a_{i+1} ⊕ ... ⊕ a_{i-K+1}$ 로 표현 가능하다. 이로써 만들어진 요리는 그만의 기준 X이상이 되어야한다.

주방장 이도연은 어젯밤, 불로만 매운맛을 먹은 여파로 재료 N개를 늘어놓고 병원에 실려갔다. 그의 철학대로, 그의 요리를 완성시켜주자!

Input

첫 번째 줄에는 늘어놓은 재료의 개수 N, 요리의 맛 기준인 음 아닌 정수 X가 공백으로 구분되어 주어진다.

두 번째 줄에는 늘어놓은 재료의 맛을 표현한 음이 아닌 정수 가 공백으로 구분되어 순서대로 주어진다.

[입력값의 정의역]

$1≤N≤300,000$
$0≤X≤2^{31}-1$
$0≤a_i≤2^{31}-1$

Output

가장 앞에 위치한 재료의 위치 i와 재료의 개수 K를 공백으로 구분하여 출력한다. 같은 답이 여러 개라면, i가 가장 작은 답을 출력한다. 만약, 불가능한 경우에는 “-1”(쌍따옴표 제외)를 출력한다.

IO Example

입력 예제 1
4 6
7 3 1 5

출력 예제 1
2 3

예제 설명
2번 위치부터 3개의 수를 XOR하면 6이므로 기준인 6을 넘는다. 이는 길이가 3이고, 이 길이를 넘게 선택하면서 기준을 넘는 연속된 재료는 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]