Problem Q
Liftkarta

Berget Bergurbulgur är uppbyggt av $N$ olika punkter och $M$ skidbackar där varje skidbacke har en viss svårighetsgrad $S_i$. För varje skidbacke finns en ankarlift som går upp för backen. Eftersom ankarliftar kan vara riktigt jobbiga kan vi anta att de har samma svårighetsgrad som den motsvarande backen. På Bergurbulgur finns det även $Q$ olika familjer som ska åka från någon punkt $A_i$ till en punkt $B_i$ genom någon väg av backar och liftar. Varje familj har $F_i$ olika familjemedlemmar, och varje familjemedlem har någon kompetensnivå som motsvarar den högsta svårighetsgrad av backe eller lift som den kan och är villig att åka. Kompetensnivån för en given familjemedlem följer alltid formen $k_i\cdot j + l_i$ där $k_i$ och $l_i$ är två familjespecifika heltal och $j$ innebär den $j$:te familjemedlemmen.

Kan du hjälpa familjerna att lista ut hur många av deras familjemedlemmar som kan ta sig från punkt $A$ till $B$? Bergurbulgur är garanterat en sammanhängande graf - man kan alltså från varje punkt ta sig till varje annan punkt på berget genom någon sekvens av liftar och backar. Alltså hade en person med oändligt hög kompetensnivå alltid kunnat nå varje punkt på Bergurbulgur.

Indata

Första raden innehåller tre heltal $N$, $M$ och $Q$ ($1 \leq N, Q \leq 10^5$, $1 \leq M \leq 5 \cdot 10^5$).

Därefter följer $M$ rader med tre heltal $u_i$, $v_i$, $S_i$ ($1 \leq u_i, v_i \leq N$, $1 \leq S_i \leq 10^9$, $u_i \neq v_i$), vilket betyder att det finns en backe som går från punkt $u_i$ till punkt $v_i$ med svårighetsgrad $S_i$, för alla $1 \leq i \leq M$.

De sista $Q$ raderna beskriver vardera en familj. Varje beskrivning innehåller fem heltal $A_i$, $B_i$, $F_i$, $k_i$ och $l_i$ ($1 \leq A_i, B_i \leq N$, $1 \leq F_i \leq 10000$, $1 \leq k_i, l_i \leq 100000$) för alla $1 \leq i \leq Q$. $l_i$ är den $i$:te familjens lägsta kompetensnivå och $k_i$ koefficienten som beskrivs ovan.

Utdata

För varje familj, skriv ut ett heltal på en ny rad: antalet familjemedlemmar som kan åka från punkt $A_i$ till punkt $B_i$.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp måste du klara alla testfall i gruppen.

Förklaring av exempelfall 1

Oavsett hur den första familjen åker från punkt 6 till punkt 2 måste de åka upp för liften mellan 5-6 som har en svårighetsgrad av 7. Alltså kan bara en familjemedlem ta sig från 6 till 2. För den andra familjen behöver man minst åka ner för backen 1-2 som har en svårighetsgrad av 3, alltså kan endast 2 familjemedlemmar ta sig från 1 till 4.

6 9 2
1 2 3
2 3 3
3 4 2
2 4 5
2 5 6
1 4 4
1 5 4
4 5 5
5 6 7
6 2 2 2 5 
1 4 3 1 2 

1
2