## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Power or XOR? Solution | Codeforces Problem Solution 2022

E. Power or XOR?
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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 \dots \wedge {A}_{n}$. You can replace each $\wedge$ symbol with either a $\mathtt{\text{Power}}$ operation or a $\mathtt{\text{XOR}}$ operation to get an unambiguous expression ${E}^{\prime }$.

The value of this expression ${E}^{\prime }$ is determined according to the following rules:

• All $\mathtt{\text{Power}}$ operations are performed before any $\mathtt{\text{XOR}}$ operation. In other words, the $\mathtt{\text{Power}}$ operation takes precedence over $\mathtt{\text{XOR}}$ operation. For example, $4\phantom{\rule{thickmathspace}{0ex}}\mathtt{\text{XOR}}\phantom{\rule{thickmathspace}{0ex}}6\phantom{\rule{thickmathspace}{0ex}}\mathtt{\text{Power}}\phantom{\rule{thickmathspace}{0ex}}2=4\oplus \left({6}^{2}\right)=4\oplus 36=32$.
• Consecutive powers are calculated from left to right. For example, $2\phantom{\rule{thickmathspace}{0ex}}\mathtt{\text{Power}}\phantom{\rule{thickmathspace}{0ex}}3\phantom{\rule{thickmathspace}{0ex}}\mathtt{\text{Power}}\phantom{\rule{thickmathspace}{0ex}}4=\left({2}^{3}{\right)}^{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 \dots \wedge {A}_{n}$. You need to find the XOR of the values of all possible unambiguous expressions ${E}^{\prime }$ which can be obtained from $E$ and has at least $k$ $\wedge$ symbols used as $\mathtt{\text{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$.

Input

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

The second line of input contains $n$ integers ${B}_{1},{B}_{2},\dots ,{B}_{n}$ $\left(1\le {B}_{i}<{2}^{20}\right)$.

Output

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$.