Sim-4-1 | bleah

Atunci când Vlad a văzut problema asta a zis bleah... Miki are o colecție de paralelipipede pe care le ține minte după dimensiunea laturilor lor, date prin trei variabile întregi $x$, $y$ și $z$.

Ea a stat cam mult să se gândească la paralelipipede și a inventat o operație de înmulțire pentru ele pe care o definește în felul următor: pentru două paralelipipede $p = (p_x, p_y, p_z)$ și $c = (c_x, c_y, c_z)$ paralelipipedul obținut are dimensiunile:
$p \times c = (p_y \cdot c_z − p_z \cdot c_y, p_z \cdot c_x − p_x \cdot c_z, p_x \cdot c_y − p_y \cdot c_x)$

Ea ține să menționeze că aceasta nu este o înmulțire obișnuită și nu are proprietățile acesteia. Mai exact această operație nu este nici asociativă, deci $a \times (b \times c)$ nu este neapărat egal cu $(a \times b) \times c$ și nici comutativă, deci $a \times b$ nu este neapărat egal cu $b \times a$. Așadar ordinea și parantezarea unei expresii care conține înmulțirea mai multor paralelipipede este foarte importantă, dar, pentru că suntem foarte drăguți și nu vrem să vă punem să parsați o astfel de expresie, o vom da exprima cu ajutorul unui arbore binar! Astfel vi se dă un arbore cu $N$ noduri. Nodurile sunt indexate de la $1$ la $N$ și se știe că nodul $1$ este mereu rădăcină. Nodurile pot fi de două tipuri:

• Tipul $1$, nod de tip frunză (care nu are fii) în care regăsim un paralelipiped $(x, y, z)$.
• Tipul $2$, nod intern (care are exact doi copii): în stânga nodul indexat cu $s$ și în dreapta nodul indexat cu $d$.

Definim valoarea unui nod $\text{val}(nod)$ ca fiind:

• Pentru un nod de tip $1$ valoarea sa este $(x, y, z)$, unde $(x, y, z)$ sunt dimensiunile paralelipipedului aflat în frunza respectivă.
• Pentru un nod de tip $2$ valoarea sa este $\text{val}(s) \times \text{val}(d)$, unde $s$ este copilul stâng, iar $d$ este copilul drept al nodului respectiv.

Cerință

Se dau $Q$ întrebări de forma:

• Se dă o frunză $f$ și un paralelipiped $(x, y, z)$ și vrem să știm care ar fi valoarea rădăcinii, $\text{val}(1)$, dacă am înlocui paralelipipedul aflat în frunza $f$ cu paralelipipedul dat.

Pentru fiecare întrebare vă roagă să afișați resturile împărțirii la $1 \ 000 \ 000 \ 007$ pentru cele trei numere care compun valoarea rădăcinii.

Date de intrare

Pe prima linie se află două numere naturale, $N$ și $Q$, separate printr-un spațiu. Pe următoarele $N$ linii descriem nodurile arborelui. Pe a $i$-a linie dintre cele $N$ descriem nodul cu indicele $i$ astfel:

• $1 \ x \ y \ z$: nodul $i$ este frunză și dimensiunile paralelipipedului din el sunt $(x, y, z)$.
• $2 \ s \ d$: nodul $i$ este nod intern, $s$ este fiul lui stâng și $d$ este fiul lui drept.

Următoarele $Q$ linii descriu întrebările. Fiecare dintre aceste linii are formatul:

• $i \ x \ y \ z$ unde $i \leq N$ reprezintă indicele frunzei care își schimbă dimensiunile paralelipipedului în $(x, y, z)$.

Atenție! întrebările sunt doar ipotetice, deci o schimbare nu se păstrează pentru întrebările viitoare.

Date de ieșire

Se vor afișa $Q$ linii, răspunsurile la întrebări în ordine. Fiecare dintre aceste $Q$ linii trebuie să conțină trei valori naturale mai mici decât $1 \ 000 \ 000 \ 007$, separate prin câte un spațiu.

Restricții și precizări

• $1 \leq N, Q \leq 200 \ 000$
• $0 \leq x, y, z \leq 1 \ 000 \ 000 \ 000$
• Se garantează că datele de intrare descriu un arbore binar cu rădăcina în nodul $1$.
• Se garantează că toate nodurile date în întrebări sunt frunze (noduri de tip $1$) în arbore.

  #	Punctaj	Restricții
  1	22	$1 \leq N, Q \leq 1 \ 000$
  2	25	$1 \leq N, Q \leq 50 \ 000$ și se garantează că arborele are adâncimea $\leq 15$.
  3	18	$1 \leq N, Q \leq 200 \ 000$ și se garantează că doar $x$ este diferit la noul paralelipiped.
  4	11	$1 \leq N, Q \leq 50 \ 000$
  5	24	Fără restricții suplimentare

Exemplul 1

stdin

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

stdout

1000000005 0 2
0 1 0
1000000005 2 2

Explicație

Pentru prima întrebare, arborele se modifică astfel:

Exemplul 2

stdin

15 10
2 2 3
2 4 5
2 6 7
2 8 9
2 10 11
2 12 13
2 14 15
1 1 5 2
1 2 2 2
1 1 1 0
1 12 0 1
1 1 3 1
1 4 1 1
1 5 1 0
1 5 1 2
10 1 7 1
11 2 3 1
9 2 1 1
14 1 0 3
8 1 2 3
15 5 1 0
15 2 1 9
13 1 2 1
8 0 1 2
10 1 3 1

stdout

999989503 999992207 51040
188 724 999998599
999999173 999999497 3960
2488 999999959 999989671
632 999998927 999998247
0 0 0
999991679 144 34464
999999351 999999767 704
632 999998927 999998247
999996335 999993823 20768