Gcd Tree

RAU-Gigel și Vlad sunt prieteni buni și le place tot timpul să se provoace unul pe altul. De data aceasta, RAU-Gigel a inventat o problemă interesantă de matematică.

Acesta are un arbore secret cu $N$ noduri (numerotate de la $1$ la $N$), în care fiecare nod are asociată o valoare (pe lângă numărul său de ordine din arbore), care este un număr natural și ii spune lui Vlad informații despre unele drumuri din acest arbore. O informație are forma $x$, $y$, $val$ și reprezintă faptul că lanțul din arbore de la nodul $x$ la nodul $y$ are cel mai mare divizor comun al valorilor asociate nodurilor acestuia egal cu $val$, unde $val$ este un număr natural nenul.

Cerință

Vlad știe că RAU-Gigel minte câteodată și s-ar putea ca unele dintre restricțiile date să fie eronate, astfel că vrea să afle întâi folosind informațiile ce le are la îndemână dacă ar putea exista un arbore care să respecte toate restricțiile date de prietenul său.

Pentru că știe ce programator iscusit ești, Vlad ți-ar fi foarte recunoscător daca l-ai putea ajuta cu această problemă prin a scrie un program care să o rezolve cât mai eficient.

Date de intrare

Fișierul de intrare gcd_tree.in conține pe prima linie numărul $T$, care reprezintă numărul de scenarii de test care trebuie rezolvate.

Pentru fiecare test, prima linie 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.

A doua linie conține $N - 1$ numere naturale, al $i$-lea număr reprezentând părintele nodului $i + 1$ din arbore (se consideră că arbore are nodurile indexate de la $1$ și rădăcina în nodul $1$).

Fiecare dintre următoarele $M$ linii din test conține câte 3 numere $x$, $y$, $val$, capetele lanțului din arbore pe care se aplică restricția, respectiv valoarea acestei restricții.

Date de ieșire

Programul trebuie să afișeze în fișierul de ieșire gcd_tree.out, 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 arbore posibil care să satisfacă toate restricțiile sau $0$ în caz contrar.

Restricții și precizări

• $1 \leq T \leq 10$
• $1 \leq N,M \leq 100 \ 000$
• $1 \leq x,y \leq N$
• $1 \leq val \leq 20$
• Se notează cu $SN$ suma valorilor $N$ din toate scenariile de test dintr-un fișier de intrare și cu $SM$ suma valorilor $M$ din toate scenariile de test dintr-un fișier de intrare.
• $1 \leq SN \leq 300 \ 000$
• $1 \leq SM \leq 300 \ 000$
• Pentru teste în valoare de 13 puncte, arborele este un lanț simplu de forma $1 - 2 - \dots - N$; $1 \leq N, M \leq 1 \ 000$; $1 \leq SN, SM \leq 3 \ 000$ și $val \in \{2, 4, 8, 16\}$.
• Pentru alte teste în valoare de 19 puncte, arborele este un lanț simplu de forma $1 - 2 - \dots - N$; $1 \leq N, M \leq 1 \ 000$; $1 \leq SN, SM \leq 3 \ 000$ și $1 \leq val \leq 20$.
• Pentru alte teste în valoare de 17 puncte, arborele este un lanț simplu de forma $1 - 2 - \dots - N$ și $val \in \{2, 4, 8, 16\}$.
• Pentru alte teste în valoare de 24 puncte, arborele este un lanț simplu de forma $1 - 2 - \dots - N$.
• Pentru alte teste în valoare de 8 puncte, $1 \leq N, M \leq 1 \ 000$; $1 \leq SN, SM \leq 3 \ 000$ și $val \in \{2, 4, 8, 16\}$.
• Pentru alte teste în valoare de 6 puncte, $1 \leq N, M \leq 1 \ 000$; $1 \leq SN, SM \leq 3 \ 000$ și $1 \leq val \leq 20$.
• Pentru alte teste în valoare de 9 puncte, $val \in \{2, 4, 8, 16\}$.
• Pentru restul testelor nu există restricții suplimentare, adică se păstrează doar condițiile inițiale.

Exemplu

gcd_tree.in

2
4 2
3 1 3
1 4 11
2 4 12
3 2
1 2
1 3 4
3 2 3

gcd_tree.out

10

Explicație

Pentru primul scenariu de test din exemplu, arborele secret ar putea avea valorile $11$, $12$, $132$, $132$ asociate nodurilor sale (scrise în ordine, de la nodul cu numărul $1$ la nodul cu numărul $4$).

Pentru al doilea scenariu de test se poate demonstra ușor matematic că nu există soluție.