Logistika

문제

Maailmakuulus tööstusfirma Universal Manufacturing otsustas hiljuti oma tegevust laiendada. Firma toodab palju erinevaid tooteid, lampidest traktoriteni, ja korraldab kogu tootmisprotsessi, toorainetest lõpliku tooteni, oma tehastes.

Firma $NN$ tehast on nummerdatud $1\dots N1\; \backslash ldots\; N$, kusjuures tehas nr. $11$ on peatehas. Tehased on oma\-vahel ühendatud $N-1N-1$ teega ja on teada, et peatehasest on võimalik mööda neid teid pääseda kõigisse teistesse tehastesse.

Igal tehasel $ii$ on oma tase $T_{i}T\_i$, mis tähendab et see tehas on võimeline koostama nii selle tasemega komponente teiste tehaste jaoks kui ka sama tasemega valmistooteid. Tehas võib sisendina kasutada suvalise madalama tasemega komponente, aga tulemusena saadud komponendi või toote tase on alati $T_{i}T\_i$.

Firma otsustas avada tehaste juures $MM$ poodi, kus pood $ii$ asub tehase $C_{i}C\_i$ juuures ja võib müüa tooteid tasemetega $L_i\dots R_{i}L\_i\; \backslash ldots\; R\_i$. Valmistamisel läbib iga toode mingi tehaste jada $(j_1,j_2,\dots ,j_c)(j\_1,\; j\_2,\; \backslash ldots,\; j\_c)$, kus esialgsed komponendid valmistatakse tehases $j_{1}j\_1$, siis viiakse need tehasesse $j_{2}j\_2$, kus neist valmistatakse kõrgema taseme komponendid, mida omakorda töödeldakse edasi kuni tehaseni $j_{c}j\_c$, kus valmistatakse lõplik toode, mis transporditakse poodi. Baaskomponendid valmistatakse alati peatehases, seega $j_1=1j\_1\; =\; 1$. Kuna iga tehas saab töödelda ainult madalama tasemega komponente, siis iga korral peab kehtima .

Kuna transport on kogu tootmisprotsessi kõige kallim osa, otsustati, et ühegi toote valmistamise käigus ei tohi toode ei komponentidena ega valmiskujul ühtki tehast korduvalt läbida (isegi kui toodet seal tehases ei töödelda). Kui mingi toote jaoks ei leidu poodi, kuhu ta nii müügile jõuda saaks, siis seda toodet poes ei müüda.

Universal Manufacturingi tööpakkumisi uurides panid Sa tähele, et neil on vaba väga hea palgaga tarkvarainseneri töökoht. Lisaks avastasid Sa, et nad kasutavad oma logistika planeerimiseks algoritmi, mis vaatab iga poe juures iga toote jaoks läbi kõik võimalikud tehaste jadad, millega seda toota saaks, ja siis valib neist selle, mis nende logistikavõrku kõige vähem koormab. Nutika programmeerijana taipasid kohe, et firma suure tehastevõrgu juures võib see algoritm joosta universumi lõpuni.

Sa soovid firmat veenda nende algoritmi ebaefektiivsuses (ja loodetavasti saada palgatud seda parandama). Selleks tuleb Sul kirjutada programm, mis arvutab iga poe jaoks, kui palju tehaste valikuid firma praegune algoritm läbi vaatab.

입력

Standardsisendi esimesel real on tehaste arv $NN$ ($1\le N\le {10}^{5}1\; \backslash le\; N\; \backslash le\; 10^5$). Teisel real on $NN$ täisarvu $P_1\dots P_{N}P\_1\; \backslash ldots\; P\_N$ (), kus $P_{i}P\_i$ tähendab, et tehaste $ii$ ja $P_{i}P\_i$ vahel on tee (erandina $P_1=0P\_1\; =\; 0$ ja ei esita teed). Kolmandal real on $NN$ täisarvu $T_1\dots T_{N}T\_1\; \backslash ldots\; T\_N$ (), mis näitavad tehaste tasemeid. On teada, et $T_1=0T\_1\; =\; 0$ ja et kõik $T_{i}T\_i$ väärtused on erinevad. Neljandal real on poodide arv $MM$ ($1\le M\le {10}^{5}1\; \backslash le\; M\; \backslash le\; 10^5$). Viimasel $MM$ real on igaühel kolm täisarvu $C_{i}C\_i$, $L_{i}L\_i$ ja $R_{i}R\_i$ ($1\le C_i\le N1\; \backslash le\; C\_i\; \backslash le\; N$ ja ), mis tähistavad et pood $ii$ asub tehase $C_{i}C\_i$ juures ja võib müüa tooteid tasemetega $L_i\dots R_{i}L\_i\; \backslash ldots\; R\_i$.

출력

Standardväljundi reale $ii$ väljastada poele $ii$ sobivate tootedete kõigile võimalikele tootmisprotsessidele vastavate tehasejadade koguarv. Kuna variante võib olla väga palju, väljastada tegeliku arvu asemel jääk, mis tekib selle jagamisel arvuga ${10}^9+710^9+7$.

8
0 1 2 2 4 2 1 7
0 7 5 1 3 6 4 2
4
5 1 4
8 2 4
6 1 4
2 1 7

3
2
0
1