Sim-4-1 | bleah

This was the problem page during the contest. Access the current page here.
Time limit: 0.5s Memory limit: 256MB Input: Output:

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 xx, yy și zz.

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=(px,py,pz)p = (p_x, p_y, p_z) și c=(cx,cy,cz)c = (c_x, c_y, c_z) paralelipipedul obținut are dimensiunile:
p×c=(pyczpzcy,pzcxpxcz,pxcypycx)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×(b×c)a \times (b \times c) nu este neapărat egal cu (a×b)×c(a \times b) \times c și nici comutativă, deci a×ba \times b nu este neapărat egal cu b×ab \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 NN noduri. Nodurile sunt indexate de la 11 la NN și se știe că nodul 11 este mereu rădăcină. Nodurile pot fi de două tipuri:

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

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

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

Cerință

Se dau QQ întrebări de forma:

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

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

Date de intrare

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

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

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

  • i x y zi \ x \ y \ z unde iNi \leq N reprezintă indicele frunzei care își schimbă dimensiunile paralelipipedului în (x,y,z)(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 QQ linii, răspunsurile la întrebări în ordine. Fiecare dintre aceste QQ linii trebuie să conțină trei valori naturale mai mici decât 1 000 000 0071 \ 000 \ 000 \ 007, separate prin câte un spațiu.

Restricții și precizări

  • 1N,Q200 0001 \leq N, Q \leq 200 \ 000
  • 0x,y,z1 000 000 0000 \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 11.
  • Se garantează că toate nodurile date în întrebări sunt frunze (noduri de tip 11) în arbore.
    # Punctaj Restricții
    1 22 1N,Q1 0001 \leq N, Q \leq 1 \ 000
    2 25 1N,Q50 0001 \leq N, Q \leq 50 \ 000 și se garantează că arborele are adâncimea 15\leq 15.
    3 18 1N,Q200 0001 \leq N, Q \leq 200 \ 000 și se garantează că doar xx este diferit la noul paralelipiped.
    4 11 1N,Q50 0001 \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

Log in or sign up to be able to send submissions!