== include(page="template/taskheader" task_id="hardtask") ==

Poveste şi cerinţă...

Se da un arbore cu N noduri si radacina in nodul 1, iar fiecare muchie are o valoare si M operatii de forma:
1 nod s -> valoarea muchiei dintre nod si tatal nodului devine s
2 nr k x~1~ x~2~ ... x~nr~ -> sa se afiseze numarul de perechi neordonate (x,y), cu x si y apartinand multimii citite de nr elemente, care au suma valorilor de pe drumul de la x la y divizibila cu k

h2. Date de intrare

Fişierul de intrare $hardtask.in$ ...

Fişierul de intrare $hardtask.in$ contine pe prima linie numerele naturale N si M despartite printr-un spatiu. Pe liniile de la 2 la N se afla cate 2 numere naturale **tata** si **val** reprezentand tatal nodului **i**, respectiv valoarea muchiei intre nodul **i** si tatal acestuia. Pe urmatoarele M linii se afla cate o operatie: prima valoare este tip, iar daca tip este 1 atunci urmeaza 2 numere naturale nod si s cu semnificatiile de mai sus, iar daca tip este 2 atunci urmeaza 2 numere naturale nr si k cu semnificatiile anterioare si un sir de nr numere distincte reprezentand multimea de noduri.

h2. Date de ieşire

În fişierul de ieşire $hardtask.out$ ...

În fişierul de ieşire $hardtask.out$ se va afisa raspunsul pentru operatiile de tipul 2, fiecare pe cate o linie.

h2. Restricţii