304405: CF842D. Vitya and Strange Lesson

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Vitya and Strange Lesson

题意翻译

## 问题描述 mex 是一个序列中没有出现过的最小非负整数。 给出你一个长度为 $n$ 的非负整数序列以及 $m$ 个询问,每次询问先给你一个整数 $x$ ,然后: - 把序列中所有数异或上 $x$ - 输出序列的 mex 注意,在每个询问过后序列是发生变化的。 ## 输入格式 第一行 $n,m$ ($1 \leq n,m \leq 3 \times 10^5$ )。 下一行 $n$ 个整数 $a_i$ ($0 \leq a_i \leq 3\times 10^5$ )。 下 $m$ 行一行一个整数 $x$ ($0 \leq x \leq 3\times 10^5$ )。 ## 输出格式 对于每个询问输出你的答案并换行。

题目描述

Today at the lesson Vitya learned a very interesting function — mex. Mex of a sequence of numbers is the minimum non-negative number that is not present in the sequence as element. For example, $ mex([4,33,0,1,1,5])=2 $ and $ mex([1,2,3])=0 $ . Vitya quickly understood all tasks of the teacher, but can you do the same? You are given an array consisting of $ n $ non-negative integers, and $ m $ queries. Each query is characterized by one number $ x $ and consists of the following consecutive steps: - Perform the bitwise addition operation modulo $ 2 $ (xor) of each array element with the number $ x $ . - Find mex of the resulting array. Note that after each query the array changes.

输入输出格式

输入格式


First line contains two integer numbers $ n $ and $ m $ ( $ 1<=n,m<=3·10^{5} $ ) — number of elements in array and number of queries. Next line contains $ n $ integer numbers $ a_{i} $ ( $ 0<=a_{i}<=3·10^{5} $ ) — elements of then array. Each of next $ m $ lines contains query — one integer number $ x $ ( $ 0<=x<=3·10^{5} $ ).

输出格式


For each query print the answer on a separate line.

输入输出样例

输入样例 #1

2 2
1 3
1
3

输出样例 #1

1
0

输入样例 #2

4 3
0 1 5 6
1
2
4

输出样例 #2

2
0
0

输入样例 #3

5 4
0 1 5 6 7
1
1
4
5

输出样例 #3

2
2
0
2

Input

题意翻译

## 问题描述 mex 是一个序列中没有出现过的最小非负整数。 给出你一个长度为 $n$ 的非负整数序列以及 $m$ 个询问,每次询问先给你一个整数 $x$ ,然后: - 把序列中所有数异或上 $x$ - 输出序列的 mex 注意,在每个询问过后序列是发生变化的。 ## 输入格式 第一行 $n,m$ ($1 \leq n,m \leq 3 \times 10^5$ )。 下一行 $n$ 个整数 $a_i$ ($0 \leq a_i \leq 3\times 10^5$ )。 下 $m$ 行一行一个整数 $x$ ($0 \leq x \leq 3\times 10^5$ )。 ## 输出格式 对于每个询问输出你的答案并换行。

加入题单

上一题 下一题 算法标签: