== include(page="template/taskheader" task_id="alimentara") ==
**The Joker: _Why so serious?_**
[_Joker flicks his wrist and Gambol goes down_]
[_Joker flicks his wrist and Gambol goes down._]
!>problema/alimentara?rsz_user21462_pic28746_1368451004.jpg!
După confruntarea finală dintre Suicide Squad și Batman, pierdută de cel din urmă, Joker și Harley Quinn s-au căsătorit și trăiesc fericiți în ceea ce a mai rămas din Gotham.
În orice familie cineva face piața, iar Joker-ul a primit această "onoare" (cine s-ar certa cu Harley Quinn oricum?). Astfel, săptămânal timp de $Q$ săptămâni, Joker-ul primește câte o listă de cumpărături, sub forma unui număr natural nenul. Deoarece Joker-ul a făcut burtică, Harley îl trimite de fiecare dată până la cea mai depărtată alimentară.
În orice familie cineva face piața, iar Joker-ul a primit această onoare (cine s-ar certa cu Harley Quinn oricum?). Astfel, ocazional, Joker-ul primește câte o listă de cumpărături, sub forma unui număr natural nenul. Deoarece Joker-ul a făcut burtică, Harley îl trimite mereu până la cea mai depărtată alimentară.
Gotham este un oraș modern, organizat sub forma unui arbore (graf conex, neorientat, aciclic) cu rădăcină (rădăcina este reprezentată de nodul cu numărul [$1$]). Nodurile reprezintă intersecțiile și sunt conectate între ele prin străzi bidirecționale, astfel încât din orice intersecție se poate ajunge în oricare alta. Casa celor doi se află în rădăcina arborelui (centrul monden al Gotham-ului). În Gotham există câte o alimentară în fiecare nod, cu un stoc inițial cunoscut (un număr natural nenul).
Gotham este un oraș modern, organizat sub forma unui arbore (graf conex aciclic) cu rădăcină (rădăcina este nodul 1). Nodurile reprezintă intersecțiile și sunt conectate între ele prin străzi bidirecționale, astfel încât din orice intersecție se poate ajunge în oricare alta. Toate străzile au lungime 1. Casa celor doi se află în nodul 1 (centrul monden al Gotham-ului). În Gotham există câte o alimentară în fiecare nod [$k$], cu un stoc inițial $S[~k~]$ (un număr natural nenul).
În Gotham se pot întâmpla două tipuri de evenimente:
* Se modifică stocul unei alimentare
* Harley îl trimite la cumpărături pe Joker iar aceasta se întreabă care este cea mai depărtată alimentară de casă care să conține vreun aliment de pe lista sa (reprezentată de numărul **l**). O alimentară cu stocul **s** conține vreun produs de pe lista fetei dacă **gcd(s, l) > [$1$]** (cel mai mare divizor comun dintre **s** și **l** este mai mare decât [$1$]).
* Se modifică stocul unei alimentare.
* Harley îl trimite la cumpărături pe Joker cu o listă de cumpărături [$L$]. Ea se întreabă care este cea mai depărtată alimentară de casă care să corespundă listei. O alimentară cu stocul $S$ corespunde listei dacă $cmmdc(S, L) > 1$.
h2. Date de intrare
Fișierul de intrare $alimentara.in$ va conține $N+Q+1$ linii.
Pe prima linie se vor afla $2$ numere, $N$ (numărul de intersecții ale orașului) și $Q$ (numărul de evenimente).
Pe următoare $N$ linii se vor afla câte $2$ numere, p (părintele nodului [$i$], $0$ pentru rădăcină) și value (stocul inițial al alimentarei din nodul [$i$]).
Pe următoare $Q$ linii se vor afla evenimentele sub forma:
Fișierul de intrare $alimentara.in$ va conține $N + Q + 1$ linii.
Pe prima linie se vor afla numerele $N$ (numărul de intersecții ale orașului) și $Q$ (numărul de evenimente).
Pe următoarele $N$ linii se vor afla perechi de numere $P[~k~] S[~k~]$. Ele reprezintă părintele nodului $k$ și respectiv stocul alimentarei [$k$]. Prin convenție, $P[~1~]$ este 0.
Pe următoarele $Q$ linii se vor afla evenimentele sub forma:
* 1 X key : alimentara din nodul X capătă stocul key
* 2 key : Harley se întreabă care este distanța maximă (de la casa ei) până la o alimentară ce conține vreun aliment din lista reprezentată de key.
* $1 X S$ : alimentara din nodul $X$ capătă stocul $S$
* $2 L$ : Harley se întreabă care este distanța maximă (de la casa ei) până la o alimentară ce corespunde listei de cumpărături [$L$].
h2. Date de ieșire
În fișierul de ieșire $alimentara.out$ va conține $p$ (p ≤ [$Q$]) linii reprezentând răspunsul la întrebările lui Harley (în ordinea în care apar în fișier).
În cazul în care nu există nicio alimentară care să respecte condițiile impuse de Harley Quinn se va afișa $-1$.
Fișierul de ieșire $alimentara.out$ va conține maxim $Q$ linii reprezentând răspunsurile la întrebările lui Harley (în ordinea în care apar în fișier).
În cazul în care pentru o listă $L$ nu există nicio alimentară care să corespundă se va afișa $-1$.
h2. Restricții
* $1 ≤ $N$ ≤ 150.000$
* $1 ≤ $Q$ ≤ 300.000$
* $1 ≤ value[~i~], key ≤ 1.000.000$, $1$ ≤ $i$ ≤ $N$
* $1 ≤ S[~k~], S, L ≤ 1.000.000, 1 ≤ k ≤ N$
* $Pentru 20% din punctaj se garantează că [$N$], $Q$ ≤ 1.000$
* $Pentru 40% din punctaj se garantează că [$N$], $Q$ ≤ 50.000$
* $Pentru 60% din punctaj se garantează că [$N$], $Q$ ≤ 100.000$
* $Distanța dintre două noduri se definește ca fiind numărul de muchii dintre cele două$
* +**Se recomandă parsarea intrării**+
h2. Exemplu
table(example).
|_. alimentara.in |_. alimentara.out |
|_. alimentara.in |_. alimentara.out |_. imagine |
| 7 3
0 1
1 4
1 7
5 3
3 8
3 3
3 5
2 2
1 3 10
2 7
0 1
1 4
1 7
5 3
3 8
3 3
3 5
2 2
1 3 10
2 7
| 2
-1
|
-1
| !problema/alimentara?tree1.png!
|
table(example).
|_. alimentara.in |_. alimentara.out |
|_. alimentara.in |_. alimentara.out |_. imagine |
| 5 5
0 3
3 1
1 2
3 10
1 6
2 20
1 4 7
2 40
2 991
2 35
0 3
3 1
1 2
3 10
1 6
2 20
1 4 7
2 40
2 991
2 35
| 2
1
-1
2
1
-1
2
| !problema/alimentara?tree2.png!
|
h3. Explicații pentru primul exemplu
Pentru prima întrebare există 2 alimentare posibile: 2, 5. Cea din nodul 5 este cea mai depărtată.
