Revenge

Gigel has an undirected graph $G$ with $N$ nodes and $M$ edges with positive costs. After the mess Gigel got into at the Romanian National Olympiad in Informatics, Ninel, Gigel's little brother, stole all his edges. Gigel wants to get the edges back, but Ninel makes him go through some challenges. You are given an array of undirected edges $S$ of length $L$. Every edge has a regular cost and a rejection cost $r$. Gigel must complete a mission from Ninel: find the minimum cost of going from node $u$ to node $v$ using a subarray of edges of $S$. The allowed edges are given by an interval $[a,b]$ with $a \le b$, which gives the indices of the edges in $S$ Gigel may use.

Gigel starts at node $x$ and iterates over the edges $S_a, S_{a+1}, \dots, S_b$. At each step he does one of two things. He can use the current edge $(x,y)$ when he is at node $x$ to move to node $y$ (or the other way around, from $y$ to $x$), and the travel cost increases by the cost of the edge. Or he can reject the current edge and stay at his current node, and the travel cost increases by the rejection cost of the edge.

You know $N$, the array $S$, and $Q$ missions. Each edge in $S$ is a tuple $\langle x,y,c,r \rangle$ for an edge $(x,y)$ with cost $c$ and rejection cost $r$. Each mission is a tuple $\langle u,v,a,b \rangle$: Gigel starts at $u$, must reach $v$, and may only use the edges with indices between $a$ and $b$. Find the minimum cost for each mission. If Gigel cannot reach $v$, output $-1$.

The first line contains three integers $N$, $L$, and $Q$. The next $L$ lines each contain four integers $x$, $y$, $c$, $r$ describing the edges in $S$. The next $Q$ lines each contain four integers $u$, $v$, $a$, $b$ describing Gigel's missions.

Print $Q$ lines. The $i$-th line contains the answer for the $i$-th mission.

$2 \le N \le 30$, $1 \le L \le 3 \times 10^4$, $1 \le Q \le 3 \times 10^5$, $0 \le c, r \le 10^4$, $1 \le x, y, u, v \le N$.