Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Trina Loves Mangoes

By ovis96 · Limits 1.5s, 512 MB

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 nn 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 RL+1R - L + 1) with mangoes size of SS for each people who sat on the range of (L,R)(L, R) (inclusive). More formally, if someone sat on the ithith chair (1in1 \leq i \leq n) and for that turn if LiRL \leq i \leq R satisfies, then that person will get the mango of size SS. 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.

Input

First line contains a single integer TT, (1T10)(1 \leq T \leq 10), denoting the number of test cases.
Each of the test cases starts with two space-separated integers, nn and mm, where nn is the number of participants and mm is the number of turns the mangoes will come (1n, m105)(1 \leq n,\ m \leq 10^5).

The next mm lines will contain three space-separated integers, L R SL\ R\ S which means the event is giving mangoes from LL to RR of size SS(1LRn;1S106)(1 \leq L \leq R \leq n; 1 \leq S \leq 10^6).

Output

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.

Sample

InputOutput
1
6 4
2 4 4
4 5 6
5 6 3
1 2 2
101101

Note

Dataset is huge. Usage of faster I/O is advised.

Discussion

Statistics


50% Solution Ratio

BrehamPieEarliest, 1M ago

arnab_1810043Fastest, 0.3s

BrehamPieLightest, 6.0 MB

likhon5Shortest, 2360B

Submit

Login to submit

Editorial

Let’s come up with a O(n * m) brute force solution. What is the solution? We will loop through L to ...

Toph uses cookies. By continuing you agree to our Cookie Policy.