{"raw_statement":[{"iden":"statement","content":"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.\n\nVitya quickly understood all tasks of the teacher, but can you do the same?\n\nYou 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:\n\n*   Perform the bitwise addition operation modulo 2 (_xor_) of each array element with the number _x_.\n*   Find _mex_ of the resulting array.\n\n_Note that after each query the array changes._"},{"iden":"input","content":"First line contains two integer numbers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 3·105) — number of elements in array and number of queries.\n\nNext line contains _n_ integer numbers _a__i_ (0 ≤ _a__i_ ≤ 3·105) — elements of then array.\n\nEach of next _m_ lines contains query — one integer number _x_ (0 ≤ _x_ ≤ 3·105)."},{"iden":"output","content":"For each query print the answer on a separate line."},{"iden":"examples","content":"Input\n\n2 2\n1 3\n1\n3\n\nOutput\n\n1\n0\n\nInput\n\n4 3\n0 1 5 6\n1\n2\n4\n\nOutput\n\n2\n0\n0\n\nInput\n\n5 4\n0 1 5 6 7\n1\n1\n4\n5\n\nOutput\n\n2\n2\n0\n2"}],"translated_statement":[{"iden":"statement","content":"今天在课堂上，Vitya 学习了一个非常有趣的函数——_mex_。一个数列的 _mex_ 是指该序列中不存在的最小非负整数。例如，#cf_span[mex([4, 33, 0, 1, 1, 5]) = 2] 和 #cf_span[mex([1, 2, 3]) = 0]。\n\nVitya 迅速理解了老师的所有题目，但你能做到吗？\n\n给你一个包含 #cf_span[n] 个非负整数的数组，以及 #cf_span[m] 个查询。每个查询由一个数字 #cf_span[x] 描述，并按以下连续步骤进行：\n\n_注意：每次查询后数组会发生变化。_\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 3·105]）——数组元素个数和查询个数。\n\n下一行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[0 ≤ ai ≤ 3·105]）——数组的元素。\n\n接下来的 #cf_span[m] 行每行包含一个查询——一个整数 #cf_span[x]（#cf_span[0 ≤ x ≤ 3·105]）。\n\n对于每个查询，请在单独一行输出答案。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 3·105]）——数组元素个数和查询个数。下一行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[0 ≤ ai ≤ 3·105]）——数组的元素。每行接下来的 #cf_span[m] 行包含一个查询——一个整数 #cf_span[x]（#cf_span[0 ≤ x ≤ 3·105]）。"},{"iden":"output","content":"对于每个查询，请在单独一行输出答案。"},{"iden":"examples","content":"输入\n2 2\n1 3\n1\n3\n输出\n1\n0\n\n输入\n4 3\n0 1 5 6\n1\n2\n4\n输出\n2\n0\n0\n\n输入\n5 4\n0 1 5 6 7\n1\n1\n4\n5\n输出\n2\n2\n0\n2"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of array elements and queries, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the initial array of non-negative integers.  \nLet $ x_1, x_2, \\dots, x_m \\in \\mathbb{Z}_{\\ge 0} $ be the sequence of query values.  \n\nFor each query $ j \\in \\{1, \\dots, m\\} $:  \n- Let $ A^{(j)} $ denote the array state before the $ j $-th query.  \n- Let $ \\text{mex}(S) = \\min \\left( \\mathbb{Z}_{\\ge 0} \\setminus S \\right) $ for any finite set $ S \\subseteq \\mathbb{Z}_{\\ge 0} $.  \n- The query updates the array: $ A^{(j+1)} = A^{(j)} \\setminus \\{x_j\\} $ if $ x_j \\in A^{(j)} $, otherwise $ A^{(j+1)} = A^{(j)} $.  \n\n**Constraints**  \n1. $ 1 \\le n, m \\le 3 \\cdot 10^5 $  \n2. $ 0 \\le a_i \\le 3 \\cdot 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 0 \\le x_j \\le 3 \\cdot 10^5 $ for all $ j \\in \\{1, \\dots, m\\} $  \n\n**Objective**  \nFor each query $ j \\in \\{1, \\dots, m\\} $, compute and output:  \n$$\n\\text{mex}\\left( A^{(j)} \\right)\n$$  \nwhere $ A^{(1)} = A $, and $ A^{(j)} $ is updated by removing one occurrence of $ x_{j-1} $ from $ A^{(j-1)} $ for $ j \\ge 2 $.","simple_statement":null,"has_page_source":false}