razbunare

Gigel are un graf neorientat G cu N noduri și M muchii etichetate cu costuri pozitive. După încurcătura făcută de Gigel la Olimpiada Naţională de Informatică, Ninel, fratele mai mic al lui Gigel, i-a furat toate muchiile. Gigel dorește să recupereze muchiile, dar Ninel îl pune la grele încercări.

Fie S un șir de lungime L ce conține pe fiecare poziție o muchie neorientată cu un cost asociat și un cost r de refuz. Gigel are de îndeplinit următoarea misiune primită de la Ninel: trebuie să afle costul minim pentru a se deplasa din nodul u (din graful G) în nodul v (din graful G) folosindu-se de o secvență de muchii din șirul S. Acesta are la dispoziție un interval [a, b] (a ≤ b) care determină ce muchii din șirul S are voie să folosească. Astfel Gigel se află inițial în nodul u și parcurge muchiile cu pozițiile corespunzătoare din [a, b] de la stânga la dreapta. La fiecare pas Gigel:

• fie alege să folosească muchia curentă dacă se afla în nodul x ajungând astfel în nodul y (respectiv dacă se afla în nodul y ajungând în nodul x); costul crește cu costul asociat muchiei de la pasul curent
• fie refuză muchia curentă și rămâne în nodul în care se afla în momentul când a ajuns la pasul curent; costul crește cu costul de refuz asociat elementului din pasul curent

Cerință

Se știe numărul N de noduri, șirul S de muchii și Q numărul de misiuni primite de Gigel. Șirul S conține pe fiecare poziție un tuplu de forma:

• <x, y, c, r> : c - reprezintă costul muchiei cu capetele în x și y ; r - reprezintă costul de refuz al muchiei curente

Cele Q misiuni sunt de forma:

• <u, v, a, b> : Gigel se află inițial în nodul u și vrea să ajungă în nodul v. Acesta începe să parcurgă muchiile din intervalul [a, b] de la stânga la dreapta, la fiecare pas, alegând muchia sau refuzând-o.

Se cere să se afle costul minim pentru fiecare din cele Q misiuni. În cazul în care Gigel nu poate ajunge din nodul u în nodul v se afișează -1.

Date de intrare

Fișierul razbunare.in conține pe prima linie N, numărul de noduri din graful G, urmat de L, lungimea șirului S, urmat de Q care reprezintă numărul de misiuni pe care Gigel trebuie să le facă. Pe următoarele S linii se află un tuplu de forma <x, y, c, r> cu semnificațiile enunțate mai sus reprezentând muchiile din șirul S. Pe următoarele Q linii se află un tuplu de forma <u, v, a, b> reprezentând misiunile pe care trebuie să le facă Gigel.

Date de ieșire

Fișierul razbunare.out conține Q numere reprezentând răspunsurile misiunilor primite de Gigel în ordinea din fișierul de intrare.

Restricții și precizări

• 2 ≤ N ≤ 30
• $1 ≤ L ≤ 3 \cdot 10^4$
• $1 ≤ Q ≤ 3 \cdot 10^5$
• $0 ≤ c \text{ (costul unei muchii) }, r \text{ (costul de refuz) } ≤ 10^4$
• 1 ≤ x, y, u, v ≤ N
• Pentru 10 puncte N ≤ 7, L ≤ 200, Q ≤ 200
• Pentru alte 30 puncte N ≤ 7, L ≤ 20 000, Q ≤ 20 000
• Pentru alte 10 puncte N ≤ 10, L ≤ 20 000, Q ≤ 60 000
• Pentru alte 25 de puncte N ≤ 22, L ≤ 20 000, Q ≤ 60 000
• Pentru alte 15 puncte N ≤ 30, L ≤ 25 000, Q ≤ 150 000
• Pentru restul de 10 puncte: restricțiile originale
• Pentru fiecare muchie din șirul S avem x ≠ y
• Nodurile sunt indexate de la 1 la N
• Șirul este indexat de la 1
• În cazul în care Gigel nu poate ajunge din nodul u în nodul v se afișează -1
• După ce Gigel a parcurs toate muchiile din interval, trebuie să se afle în nodul v

Exemplu

razbunare.in

5 5 3
1 4 4 5
4 1 6 1
2 1 2 9
2 5 1 0
1 5 2 5
2 2 2 4
5 4 5 5
1 5 2 5

razbunare.out

10
-1
9

Explicatii

Pentru prima misiune: Gigel se află în nodul 2 și vrea să ajungă tot în nodul 2. Costul minim de a ajunge din 2 în 2 e să refuze toate muchiile din [2, 4]: 1 + 9 + 0 (astfel rămâne tot timpul în nodul 2).
Pentru a doua misiune: Gigel nu poate ajunge din 5 în 4
Pentru a treia misiune: Gigel se află inițial în 1 și folosește muchiile din [2, 5]. Refuză a doua muchie (4, 1); alege a treia muchie si ajunge în 2; alege a patra muchie si ajunge în 5 si refuză a cincea muchie: 1 + 2 + 1 + 5.

razbunare.in

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

razbunare.out

32
-1
41
14
36
27