Description

Pear City has a total of $N$ ($\le 50000$) settlements, and there are $M$ ($\le 2\times 10^5$) undirected roads connecting these settlements. Any two settlements can reach each other through these undirected roads. This situation lasted until recently, when a severe earthquake destroyed all $M$ roads.

After the earthquake, Pear plans to repair some of the roads. Repairing the $i$-th road takes $P_i$ time. However, Pear does not plan to make all nodes connected; instead, he chooses some specially indexed nodes and makes them connected.

Pear has $Q$ ($\le 50000$) queries. In each query, he selects all nodes whose indices are in $[l,r]$ and whose index satisfies $\bmod{K}=C$, and repairs some roads to make these nodes connected. Since all road repairs can start at the same time, the completion time depends on the road that takes the longest time, that is, the maximum $P_i$ among the roads involved.

Can you help Pear compute the minimum time needed for each query? The queries are independent, meaning the repair plan in one query is not actually carried out.

Input Format

The first line contains three positive integers $N$, $M$, and $Q$, as described above.

The next $M$ lines each contain three positive integers $X_i$, $Y_i$, and $P_i$, representing an undirected road between $X_i$ and $Y_i$ that takes $P_i$ time to repair. Self-loops and multiple edges may exist. $1 \le P_i \le 10^6$.

The next $Q$ lines each contain four positive integers $L_i$, $R_i$, $K_i$, and $C_i$, indicating that the nodes in this query are all nodes in the interval $[L_i,R_i]$ whose indices satisfy $\bmod{K_i}=C_i$. It is guaranteed that at least two nodes participate in each query.

Output Format

Output $Q$ lines. Each line contains one positive integer, the answer to the corresponding query.

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

9
6
8
8

Hint

For $20\%$ of the testdata, $N,M,Q \le 30$.

For $40\%$ of the testdata, $N,M,Q \le 2000$.

For $100\%$ of the testdata, $N \le 50000$, $M \le 2 \times 10^5$, $Q \le 50000$, $P_i \le 10^6$. $L_i$, $R_i$, and $K_i$ are all in the range $[1,N]$, and $C_i$ is in the range $[0,K_i)$.

Time limit: 5 seconds, 256 MB.

Lanqiao Cup 2015 Provincial Contest A Division, Problem J.

Translated by ChatGPT 5