Petrică, pasionat de algoritmi și provocări logice, are un cod care reprezintă parola de acces la o bază de date foarte importantă de probleme de algoritmică.

Pentru că știe că ești un programator iscusit, acesta dorește să îți permită accesul la baza de date dacă poți afla codul secret, rezolvând o ghicitoare de la acesta.

Codul secret este reprezentat de un șir de numere întregi de lungime $N$, indexat de la $1$. Petrică îți comunică $M$ restricții pe care acest șir trebuie să le satisfacă simultan, fiecare dintre acestea având forma $(l, r, v)$, reprezentând faptul că elementele din șir cu indicii în intervalul $[l, r]$ au proprietatea că valoarea obținută aplicând operatorul binar | ("or") între valorile acestora este egală cu $v$.

Cerință

Petrică este totuși viclean și s-ar putea câteodată să îți comunice restricții care să nu permită toate simultan existența șirului. Tot ce vrea acesta de la tine este să îi comunici dacă poate exista un șir cu proprietățile date și acesta îți va spune în schimb care este codul bun.

Date de intrare

Prima linie a fișierului de intrare conține un număr întreg $T$, reprezentând numărul de scenarii de test care trebuie rezolvate.

Prima linie a fiecărui test conține $2$ numere $N$ și $M$, reprezentând lungimea șirului secret și numărul de restricții pe care acesta trebuie să le respecte.

Fiecare linie dintre următoarele $M$ linii din test conține câte 3 numere $l$, $r$, $v$, reprezentând capetele intervalului de indici pe care se aplică restricția, respectiv valoarea acesteia.

Date de ieșire

Programul trebuie să afișeze pe o singură linie, fără spații, un șir de lungime $T$ format din valorile 0 sau 1, unde elementul de pe poziția $i$ este 1 dacă scenariul de test cu numărul $i$ din input admite un cod posibil sau 0 în caz contrar.

Restricții și precizări

• $1 \leq T \leq 100$
• $1 \leq N \leq 200 \ 000$
• $1 \leq M \leq 200 \ 000$
• $1 \leq l \leq r \leq N$
• $0 \leq v \leq 10^9$
• Suma valorilor $N$ din toate testele dintr-un fișier de input va fi mereu mai mică sau egală decât $200 \ 000$.
• Suma valorilor $M$ din toate testele dintr-un fișier de input va fi mereu mai mică sau egală decât $200 \ 000$.

Exemplu

codulbun.in

2
5 2
1 3 3
2 5 0
4 2
1 3 1
2 3 4

codulbun.out

10

Explicație

Pentru primul test, un șir care respectă restricțiile date este $3 \ 0 \ 0 \ 0 \ 0$.

Pentru al doilea test, se poate demonstra că nu există o soluție care să satisfacă toate restricțiile simultan.