E. Power or XOR?time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThe 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.InputThe first line of input contains two integers n and k (1\leq n\leq 2^{20}, 0\leq k < n).The second line of input contains n integers B_1,B_2,\ldots,B_n (1\leq B_i < 2^{20}).OutputPrint 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.ExamplesInput
3 2
3 1 2
Output
1110
Input
3 1
3 1 2
Output
1010010
Input
3 0
3 1 2
Output
1000000000000000001010010
Input
2 1
1 1
Output
0
NoteFor 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.
3 2
3 1 2

1110 
['bitmasks', 'combinatorics', 'math', 'number theory', '*2500']