CF1673E.Power or XOR?

The symbol $\wedge$ is quite ambiguous, especially when used without context. Sometimes it is used to denote a power ($a\wedge b = a^b$) and sometimes it is used to denote the XOR operation ($a\wedge b=a\oplus b$).

You have an ambiguous expression $E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$. You can replace each $\wedge$ symbol with either a $\texttt{Power}$ operation or a $\texttt{XOR}$ operation to get an unambiguous expression $E'$.

The value of this expression $E'$ is determined according to the following rules:

• All $\texttt{Power}$ operations are performed before any $\texttt{XOR}$ operation. In other words, the $\texttt{Power}$ operation takes precedence over $\texttt{XOR}$ operation. For example, $4\;\texttt{XOR}\;6\;\texttt{Power}\;2=4\oplus (6^2)=4\oplus 36=32$.
• Consecutive powers are calculated from left to right. For example, $2\;\texttt{Power}\;3 \;\texttt{Power}\;4 = (2^3)^4 = 8^4 = 4096$.

You are given an array $B$ of length $n$ and an integer $k$. The array $A$ is given by $A_i=2^{B_i}$ and the expression $E$ is given by $E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$. You need to find the XOR of the values of all possible unambiguous expressions $E'$ which can be obtained from $E$ and has at least $k$ $\wedge$ symbols used as $\texttt{XOR}$ operation. Since the answer can be very large, you need to find it modulo $2^{2^{20}}$. Since this number can also be very large, you need to print its binary representation without leading zeroes. If the answer is equal to $0$, print $0$.

符号 $\wedge$ 具有高度歧义性，尤其在缺乏上下文时。有时它表示幂运算（$a\wedge b = a^b$），有时则表示按位异或（XOR）运算（$a\wedge b=a\oplus b$）。

你有一个歧义表达式 $E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$。你可以将每个 $\wedge$ 符号替换为 $\texttt{Power}$ 运算或 $\texttt{XOR}$ 运算，从而得到一个无歧义的表达式 $E'$。

该表达式 $E'$ 的值由以下规则确定：

• 所有 $\texttt{Power}$ 运算均在任何 $\texttt{XOR}$ 运算之前执行。换言之，$\texttt{Power}$ 运算的优先级高于 $\texttt{XOR}$ 运算。例如，$4\;\texttt{XOR}\;6\;\texttt{Power}\;2=4\oplus (6^2)=4\oplus 36=32$。
• 连续的幂运算是从左到右依次计算的。例如，$2\;\texttt{Power}\;3 \;\texttt{Power}\;4 = (2^3)^4 = 8^4 = 4096$。

给定一个长度为 $n$ 的数组 $B$ 和一个整数 $k$。数组 $A$ 定义为 $A_i=2^{B_i}$，表达式 $E$ 定义为 $E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$。你需要求出所有可能的无歧义表达式 $E'$（这些 $E'$ 由 $E$ 得到，且其中至少有 $k$ 个 $\wedge$ 符号被用作 $\texttt{XOR}$ 运算）的值的异或和。由于答案可能非常大，你需要对 $2^{2^{20}}$ 取模。又因该模数本身也可能极大，你需输出其二进制表示（不含前导零）。若答案等于 $0$，则直接输出 $0$。

The first line of input contains two integers $n$ and $k$ $(1\leq n\leq 2^{20}, 0\leq k \lt n)$.

The second line of input contains $n$ integers $B_1,B_2,\ldots,B_n$ $(1\leq B_i \lt 2^{20})$.

输入的第一行包含两个整数 $n$ 和 $k$ $(1\leq n\leq 2^{20}, 0\leq k \lt n)$。

输入的第二行包含 $n$ 个整数 $B_1,B_2,\ldots,B_n$ $(1\leq B_i \lt 2^{20})$。

Print a single line containing a binary string without leading zeroes denoting the answer to the problem. If the answer is equal to $0$, print $0$.

输出一行，包含一个不含前导零的二进制字符串，表示该问题的答案。如果答案等于 $0$，则输出 $0$。

For each of the testcases $1$ to $3$, $A = {2^3,2^1,2^2} = {8,2,4}$ and $E=8\wedge 2\wedge 4$.

For the first testcase, there is only one possible valid unambiguous expression $E' = 8\oplus 2\oplus 4 = 14 = (1110)_2$.

For the second testcase, there are three possible valid unambiguous expressions $E'$:

• $8\oplus 2\oplus 4 = 14$
• $8^2\oplus 4 = 64\oplus 4= 68$
• $8\oplus 2^4 = 8\oplus 16= 24$

XOR of the values of all of these is $14\oplus 68\oplus 24 = 82 = (1010010)_2$.

For the third testcase, there are four possible valid unambiguous expressions $E'$:

• $8\oplus 2\oplus 4 = 14$
• $8^2\oplus 4 = 64\oplus 4= 68$
• $8\oplus 2^4 = 8\oplus 16= 24$
• $(8^2)^4 = 64^4 = 2^{24} = 16777216$

XOR of the values of all of these is $14\oplus 68\oplus 24\oplus 16777216 = 16777298 = (1000000000000000001010010)_2$.

For the fourth testcase, $A={2,2}$ and $E=2\wedge 2$. The only possible valid unambiguous expression $E' = 2\oplus 2 = 0 = (0)_2$.

对于测试用例 $1$ 至 $3$，有 $A = \{2^3,2^1,2^2\} = \{8,2,4\}$，且 $E=8\wedge 2\wedge 4$。

对于第一个测试用例，仅存在一种可能的有效无歧义表达式 $E' = 8\oplus 2\oplus 4 = 14 = (1110)_2$。

对于第二个测试用例，存在三种可能的有效无歧义表达式 $E'$：

• $8\oplus 2\oplus 4 = 14$
• $8^2\oplus 4 = 64\oplus 4= 68$
• $8\oplus 2^4 = 8\oplus 16= 24$

所有这些值的异或结果为 $14\oplus 68\oplus 24 = 82 = (1010010)_2$。

对于第三个测试用例，存在四种可能的有效无歧义表达式 $E'$：

• $8\oplus 2\oplus 4 = 14$
• $8^2\oplus 4 = 64\oplus 4= 68$
• $8\oplus 2^4 = 8\oplus 16= 24$
• $(8^2)^4 = 64^4 = 2^{24} = 16777216$

所有这些值的异或结果为 $14\oplus 68\oplus 24\oplus 16777216 = 16777298 = (1000000000000000001010010)_2$。

对于第四个测试用例，$A=\{2,2\}$，且 $E=2\wedge 2$。唯一可能的有效无歧义表达式为 $E' = 2\oplus 2 = 0 = (0)_2$。