Trina Loves Mangoes

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 $n$ 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 $R - L + 1$) with mangoes size of $S$ for each people who sat on the range of $(L, R)$ (inclusive). More formally, if someone sat on the $ith$ chair ($1 \leq i \leq n$) and for that turn if $L \leq i \leq R$ satisfies, then that person will get the mango of size $S$. 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 $T$, $(1 \leq T \leq 10)$, denoting the number of test cases.
Each of the test cases starts with two space-separated integers, $n$ and $m$, where $n$ is the number of participants and $m$ is the number of turns the mangoes will come $(1 \leq n,\ m \leq 10^5)$.

The next $m$ lines will contain three space-separated integers, $L\ R\ S$ which means the event is giving mangoes from $L$ to $R$ of size $S$$(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

Input	Output
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.