A15191 | Doremy's IQ

Doremy is asked to test $n$ contests. Contest $i$ can only be tested on day $i$ . The difficulty of contest $i$ is $a_i$ . Initially, Doremy's IQ is $q$ . On day $i$ Doremy will choose whether to test contest $i$ or not. She can only test a contest if her current IQ is strictly greater than $0$ .

If Doremy chooses to test contest $i$ on day $i$ , the following happens:

- if $a_i>q$ , Doremy will feel she is not wise enough, so $q$ decreases by $1$ ;
- otherwise, nothing changes.

If she chooses not to test a contest, nothing changes.Doremy wants to test as many contests as possible. Please give Doremy a solution.

The input consists of multiple test cases. The first line contains a single integer $t$ ( $1\le t\le 10^4$ ) — the number of test cases. The description of the test cases follows.

The first line contains two integers $n$ and $q$ ( $1 \le n \le 10^5$ , $1 \le q \le 10^9$ ) — the number of contests and Doremy's IQ in the beginning.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$ ( $1 \le a_i \le 10^9$ ) — the difficulty of each contest.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$ .

For each test case, you need to output a binary string $s$ , where $s_i=1$ if Doremy should choose to test contest $i$ , and $s_i=0$ otherwise. The number of ones in the string should be maximum possible, and she should never test a contest when her IQ is zero or less.

If there are multiple solutions, you may output any.