30005번 - 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 $N$ tehast on nummerdatud $1 \ldots N$, kusjuures tehas nr. $1$ on peatehas. Tehased on oma\-vahel ühendatud $N-1$ teega ja on teada, et peatehasest on võimalik mööda neid teid pääseda kõigisse teistesse tehastesse.

Igal tehasel $i$ on oma tase $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$.

Firma otsustas avada tehaste juures $M$ poodi, kus pood $i$ asub tehase $C_i$ juuures ja võib müüa tooteid tasemetega $L_i \ldots R_i$. Valmistamisel läbib iga toode mingi tehaste jada $(j_1, j_2, \ldots, j_c)$, kus esialgsed komponendid valmistatakse tehases $j_1$, siis viiakse need tehasesse $j_2$, kus neist valmistatakse kõrgema taseme komponendid, mida omakorda töödeldakse edasi kuni tehaseni $j_c$, kus valmistatakse lõplik toode, mis transporditakse poodi. Baaskomponendid valmistatakse alati peatehases, seega $j_1 = 1$. Kuna iga tehas saab töödelda ainult madalama tasemega komponente, siis iga $1 \le i < c$ korral peab kehtima $T_{j_i} < T_{j_{i+1}}$.

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 $N$ ($1 \le N \le 10^5$). Teisel real on $N$ täisarvu $P_1 \ldots P_N$ ($1 \le P_i < i$), kus $P_i$ tähendab, et tehaste $i$ ja $P_i$ vahel on tee (erandina $P_1 = 0$ ja ei esita teed). Kolmandal real on $N$ täisarvu $T_1 \ldots T_N$ ($0 \le T_i < N$), mis näitavad tehaste tasemeid. On teada, et $T_1 = 0$ ja et kõik $T_i$ väärtused on erinevad. Neljandal real on poodide arv $M$ ($1 \le M \le 10^5$). Viimasel $M$ real on igaühel kolm täisarvu $C_i$, $L_i$ ja $R_i$ ($1 \le C_i \le N$ ja $0 \le L_i \le R_i < N$), mis tähistavad et pood $i$ asub tehase $C_i$ juures ja võib müüa tooteid tasemetega $L_i \ldots R_i$.

Standardväljundi reale $i$ väljastada poele $i$ 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+7$.