"When we confide, our worries diminish. Half of the confider's sadness is transferred to the other person, and the other half is returned to the world with the sound waves. Thus, worries propagate through the crowd, becoming weaker and weaker until they vanish with the wind."

In Little I's small circle, there are $n$ people. The $i$-th person ($1 \le i \le n$) initially has a positive integer amount of worry $a_i$. To alleviate everyone's worries, Little I organizes a chat activity where the $n$ people sit in a row from left to right, ordered by their index from smallest to largest.

Time is limited; Little I can organize at most $k$ confiding sessions during the activity. In each session, a confider $p$ ($1 \le p \le n-1$) confides in the person to their right, $p+1$. This first causes $a_{p+1} \leftarrow a_{p+1} + \frac{1}{2} a_p$, and then $a_p \leftarrow 0$, where $\leftarrow$ denotes assignment. Little I can choose the confider for each session arbitrarily. Note that the person with index $n$ cannot confide in anyone else.

Little I wants to minimize everyone's worries, so he wants to know: after the activity, what is the minimum possible value of the maximum worry among all people?

You need to output the exact value of the answer. Specifically, the answer can always be written in the form $\frac{S}{2^n}$, where $S$ is a positive integer not exceeding $2^n \times (\max_{i=1}^n a_i)$. You need to output the binary representation of $S$.

Input

The input is read from standard input.

There are multiple test cases. The first line contains an integer $T$, representing the number of test cases. The following lines describe each test case.

For each test case, the first line contains two integers $n$ and $k$, representing the number of people and the upper limit on the number of confiding sessions, respectively. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, describing the initial worry value of each person.

Output

For each test case, output a single line containing a $01$ string representing the binary representation of $S$ from the most significant bit to the least significant bit. Your output should not have leading zeros.

Examples

Input 1

3
3 1
5 2 1
4 3
2 5 2 1
3 3
5 2 1

Output 1

100100
10100
10100

Note 1

For the first test case, the optimal strategy is to have the first person confide. The final worry values are $(0, 4.5, 1)$, so we output the binary representation of $4.5 \times 2^3 = 36$, which is 100100.

For the second and third test cases, the optimal strategy is to have the second person confide first, and then have the first person confide. The final worry values are $(0, 2.5, 2)$, so we output the binary representation of $2.5 \times 2^3 = 20$, which is 10100.

Input 2

(See the files confide/confide2.in in the contestant directory)

Output 2

(See the files confide/confide2.ans in the contestant directory)

Note 2

The answers for the seven test cases in this sample are $10, 10, 8, 5, 3.5, 2.75, 2.5$ respectively.

Subtasks

Let $\sum n$ denote the sum of $n$ over all test cases in a single test file. For all test cases, it is guaranteed that: $1 \le T \le 2 \times 10^4$ $1 \le n, \sum n \le 2 \times 10^4$, $1 \le k \le 10^9$ * $\forall 1 \le i \le n, 1 \le a_i \le 10^6$