Trina loves mangoes. And she is a valuable member of the famous Mango Eaters Community. This community has some weird rules. But Trina likes them all! One of them is, if they are eating several mangoes (more than one), they can only eat the very next mango if it is strictly larger than the previous one! If someone can’t eat the mango they are given, they get very unhappy.
So one day Trina’s community arranged a Mango Eating Festival. At that festival, there were people participating (including Trina). The most attractive event of the festival was eating mangoes! At that event, all the participants of the community sat in one line next to each other. On each turn, the event gives away some mangoes (exactly ) with mangoes size of for each people who sat on the range of (inclusive). More formally, if someone sat on the chair () and for that turn if satisfies, then that person will get the mango of size . But remember, they have a weird rule for eating mangoes! So if anyone misses at least one mango, that person gets unhappy and leaves the festival! And others remain happy. You have to answer for each people whether or not he/she was happy at the festival.
Note that, if one or more people leaves the festival after being unhappy, their chairs remain empty and no other people will move to those chairs.
First line contains a single integer , , denoting the number of test cases.
Each of the test cases starts with two space-separated integers, and , where is the number of participants and is the number of turns the mangoes will come .
The next lines will contain three space-separated integers, which means the event is giving mangoes from to of size .
Print a binary string for every test case, if the ith person is happy the ith character should be ‘1’ otherwise ‘0’. See sample I/O for more clarification.
Input | Output |
---|---|
1 6 4 2 4 4 4 5 6 5 6 3 1 2 2 | 101101 |
Dataset is huge. Usage of faster I/O is advised.