Doremy’s IQ Solution Codeforces

Table of Contents

Doremy’s IQ Solution Codeforces

Doremy is asked to test nn contests. Contest ii can only be tested on day ii. The difficulty of contest ii is aiai. Initially, Doremy’s IQ is qq. On day ii Doremy will choose whether to test contest ii or not. She can only test a contest if her current IQ is strictly greater than 00.

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

  • if ai>qai>q, Doremy will feel she is not wise enough, so qq decreases by 11;
  • 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.

Input Doremy’s IQ Solution Codeforces

The input consists of multiple test cases. The first line contains a single integer tt (1t1041≤t≤104) — the number of test cases. The description of the test cases follows.

The first line contains two integers nn and qq (1n1051≤n≤1051q1091≤q≤109) — the number of contests and Doremy’s IQ in the beginning.

The second line contains nn integers a1,a2,,ana1,a2,⋯,an (1ai1091≤ai≤109) — the difficulty of each contest.

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

Output Doremy’s IQ Solution Codeforces

For each test case, you need to output a binary string ss, where si=1si=1 if Doremy should choose to test contest ii, and si=0si=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.

Example
input

Copy
5
1 1
1
2 1
1 2
3 1
1 2 1
4 2
1 4 3 1
5 2
5 1 2 4 3
output

Copy
1
11
110
1110
01111

Note Doremy’s IQ Solution Codeforces

In the first test case, Doremy tests the only contest. Her IQ doesn’t decrease.

In the second test case, Doremy tests both contests. Her IQ decreases by 11 after testing contest 22.

In the third test case, Doremy tests contest 11 and 22. Her IQ decreases to 00 after testing contest 22, so she can’t test contest 33.

 

For Solution

Click Here

Leave a Comment