mex
시간 제한1초메모리 제한512 MB
각 질의 x마다 수열의 모든 원소를 x로 XOR한 뒤 mex(수열에 없는 가장 작은 음이 아닌 정수)를 출력한다.
문제
mex는 어떤 수열에 포함되지 않은 수 중에서 가장 작은 음이 아닌 정수를 찾는 함수이다. 예를 들어, mex([1,2,3]) = 0, mex([5,0,1,1,4]) = 2, mex([0,5,2,1,5,0,1,2]) = 3이다.
크기가 N이고 음이 아닌 정수로 이루어진 수열 A와 M개의 쿼리가 주어진다. 쿼리는 정수 x로 이루어져 있고, 다음을 순서대로 수행해야 한다.
- 수열 A에 속한 각각의 원소를 x와 xor한다.
- mex(A)를 출력한다.
A의 원소를 x와 xor할 때, A의 원소의 값이 실제로 바뀐다고 가정한다.
입력
첫째 줄에 수열의 크기 N(1 ≤ N ≤ 300,000)과 쿼리의 개수 M(1 ≤ M ≤ 300,000)이 주어진다.
둘째 줄에 A1, A2, ..., AN (0 ≤ Ai ≤ 300,000)이 주어진다.
셋째 줄부터 M개의 줄에 쿼리를 나타내는 x(0 ≤ x ≤ 300,000)가 한 줄에 하나씩 주어진다.
출력
각 쿼리를 순서대로 수행하고, mex(A)를 출력한다.