Hide

Problem F
Liftkarta

Languages en sv

Berget Bergurbulgur är uppbyggt av N olika punkter och M skidbackar där varje skidbacke har en viss svårighetsgrad Si. 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 Ai till en punkt Bi genom någon väg av backar och liftar. Varje familj har Fi 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 kij+li där ki och li ä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 (1N,Q105, 1M5105).

Därefter följer M rader med tre heltal ui, vi, Si (1ui,viN, 1Si109, uivi), vilket betyder att det finns en backe som går från punkt ui till punkt vi med svårighetsgrad Si, för alla 1iM.

De sista Q raderna beskriver vardera en familj. Varje beskrivning innehåller fem heltal Ai, Bi, Fi, ki och li (1Ai,BiN, 1Fi10000, 1ki,li100000) för alla 1iQ. li är den i:te familjens lägsta kompetensnivå och ki 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 Ai till punkt Bi.

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.

Grupp

Poäng

Gränser

1

15

N,M,Q,Si100,Fi10

2

20

N,M,Q,Si1000,Fi100

3

20

Fi100

4

20

M=N1, grafen är alltså ett träd.

5

25

Inga ytterligare begränsningar.

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.

Sample Input 1 Sample Output 1
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
Hide