Informatica Online Judge

  숙제 기계 [1966 / 07AE]

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


The Champion of this Problem (C++) : gs16106 - 40ms / 2019byte
My Best Submission (C++) : N/A

[gs16022]

Background

승한이는 확률과 통계 시간에 내준 숙제를 하기 위해 $N$개의 날 동안 한 개의 숙제를 했다.

$i$번째 날에 한 숙제는 $a_i$라고 하면, $0 ≤ a_i ≤ 300,000$ 이고 승한이는 바보이기 때문에 옛날에 했던 숙제를 또 할 수도 있다.

수업 날 선생님께서는 $0$ ~ $N$까지의 문제를 $0$부터 하나씩 검사해서 처음으로 승한이가 안 한 숙제의 번호를 알려준다. 숙제를 대충해 간 승한이는 결국 숙제 기계의 손을 빌리기로 했다.

$M$개의 숙제 기계는 각각 고유번호를 가지고 있는데, (승한이가 한 숙제들 번호) XOR (고유번호) 한 번호로 숙제를 바꾼다.

즉, 숙제 기계의 고유번호를 $X$라 하면 승한이의 숙제는 ($a_0~XOR~X$, $a_1~XOR~X$, ... $a_{N-1}~XOR~X$) 로 바뀐다.

이 때, 승한이는 $0$번째 숙제 기계부터 $M-1$번째 숙제 기계를 차례대로 사용하여 각 숙제 기계를 사용한 후에 선생님이 알려준 번호를 알고 싶어한다.

승한이를 도와 $i$번째 숙제기계를 사용한 이후 선생님이 알려준 값을 출력하자.

$i+1$번째 숙제 기계를 사용할 때의 숙제는 $i$번째 숙제 기계를 사용한 후의 상태임에 유의하라.

Input

첫 줄에 $N$, $M$이 입력된다. ($1 ≤ N, M ≤ 300,000$)
다음 줄에는 승한이가 처음에 한 숙제 $a_i$가 N 개 입력된다. ($0 <= a_i <= 300,000$)
3번째 줄부터 $M+2$번째 줄까지는 $i$번째 숙제 기계의 고유번호 $X_i$ 가 주어진다.
($0 <= X_i <= 300,000$)

Output

$i$번째 줄에 $i$번째 숙제 기계를 사용한 후의 선생님의 답을 출력하여라.

IO Example

입력 예제 1)
2 2
1 3
1
3

출력 예제 1)
1
0

예제 1 설명)
$1$번째 숙제 기계를 사용한 후에는 승한이의 숙제 목록이 $(1~XOR~1, 3~XOR~1) = (0, 2)$ 가 되므로 선생님의 답은 $1$이다.
$2$번째 숙제 기계를 사용한 후에는 승한이의 숙제 목록이 $(0~XOR~3, 2~XOR~3) = (3, 1)$ 이 되므로 선생님의 답은 $0$이다.

입력 예제 2)
4 3
0 1 5 6
1
2
4

출력 예제 2)
2
0
0

예제 2 설명)
$1$번째 숙제 기계를 사용한 이후 승한이의 숙제는 $(0~XOR~1, 1~XOR~1, 5~XOR~1, 6~XOR~1) = (1, 0, 4, 7)$ 이 되어 선생님의 값은 $2$가 된다.
$2$번째 숙제 기계를 사용한 이후 승한이의 숙제는 $(1~XOR~2, 0~XOR~2, 4~XOR~2, 7~XOR~2) = (3, 2, 6, 5) $가 되어 선생님의 값은 $0$이 된다.
$3$번째 숙제 기계를 사용한 이후 승한이의 숙제는 $(3~XOR~4, 2~XOR~4, 6~XOR~4, 5~XOR~4) = (7, 6, 2, 1)$이 되어 선생님의 값은 $0$이 된다.

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