B. Abu HatemCPC (Hard version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Note: This is the same as easy version in the ROUND 16 contest but in this version for each team you need to find out all possible ranks for the team. Also some constraints are different.

Abu Hatem has a very famous coffee shop. Sometimes, they play games, and it becomes very competitive. Abu Hatem is also very keen on shabab el7ara; he always takes care of them and wishes them all the best. For that reason, he decided to teach shabab el7ara competitive programming so they can get jobs in the best companies.

Also, Abu Hatem wants to create competitive and fun events, so he decided to organize a programming contest called AbuHatemCPC.

Ma2moon beik is not just 3meel from frensawi; he also works in a big tech company as a recruiter. One of the things he was thinking about when he entered Haret AlDabe3 was finding good and skilled programmers for his company.

So he decided to come to AbuHatemCPC to view the contest and see how shabab el7ara performed, as well as to headhunt skilled and smart contestants.

Ma2moon beik arrived at the contest just after it ended, and he saw the final scoreboard but without the results of the submissions in the blind hour.

AbuHatemCPC had 25 problems, and its duration was (4 + 1) hours. In the first 4 hours, the submission results were public to all contestants, but in the last hour, only the team that made the submission could see its result (whether it was accepted or not).

When Ma2moon beik saw the scoreboard, he could see, for each team, the number of problems they solved before the blind hour and their time penalty. He could also see, for each team, the submissions they made in the blind hour as pending submissions.

When revealing the results, they would use the contest resolver to show whether each pending submission was accepted or not.

Now, each pending submission has two possibilities: to be accepted or not. If it is accepted, it will increase the number of solved problems for that team by 1 and increase the time penalty by some known amount.

The rank of each team is equal to $$$1$$$ plus the number of teams that solved a strictly greater number of problems or solved the same number of problems with a strictly lower time penalty. (If two teams solved the same number of problems with the same time penalty, they would have the same rank.)

Now, Ma2moon beik is wondering, for each team, considering all possible outcomes of the pending submissions, what is the possible ranks this team can get. Can you help him?

Input

The first line will contain one integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, which is the number of test cases.

For each test case:

The first line will contain one integer $$$n$$$ $$$(1 \leq n \leq 100)$$$, which is the number of contestants.

Then, for each contestant, the input will contain two lines. For the $$$i_{th}$$$ contestant:

The first line will contain three integers $$$x_i$$$, the number of problems solved before the blind hour, $$$y_i$$$, the number of pending submissions in the blind hour, and $$$p_i$$$, the time penalty of the problems solved before the blind hour. It is guaranteed that $$$(0 \leq x_i + y_i \leq 25)$$$ and $$$(0 \leq p_i \leq 10^4)$$$. It is guaranteed that if the number of solved problems before blind hour ($$$x_i$$$) is $$$0$$$, the time penalty before blind hour ($$$p_i$$$) will also be $$$0$$$.

The second line will contain $$$y_i$$$ integers, the $$$j_{th}$$$ one denoted as $$$a_{i,j}$$$ $$$(240 \leq a_{i,j} \leq 300)$$$ , which represents the time penalty the contestant will receive if the result of that pending submission is accepted.

It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$100$$$.

Output

For each test case, print $$$n$$$ lines. in the $$$i_{th}$$$ line, print $$$n$$$ characters where each character is either 0 or 1, where the $$$j_{th}$$$ character in the $$$i_{th}$$$ line is $$$1$$$ if it is possible for the $$$i_{th}$$$ team to have a rank equal to $$$j$$$.

Example
Input
1
4
3 0 1000

3 0 2000

3 0 3000

2 1 500
300
Output
1100
0110
0011
1001
Note

First example:

Final scoreboard before if the pending submission wasn't accepted:

Final scoreboard before if the pending submission was accepted: