Minimum Bottleneck for Reconnecting Special Residences

Pear City originally had \(N\) (\(\le 50000\)) residences connected by \(M\) (\(\le 2\times10^5\)) bidirectional roads. It was guaranteed that every pair of residences is connected by some path. After a catastrophic earthquake destroyed all \(M\) roads, Pear decided to repair a subset of them.

Repairing the \(i\)-th road requires \(P_i\) units of time. However, Pear does not intend to reconnect all of the residences. Instead, for each query, Pear selects all residences with indices in the interval \([l, r]\) that also satisfy \(i \bmod K = C\) and wants to repair some roads so that these selected residences become connected. Since all repairs can be carried out concurrently, the total completion time is determined by the road that takes the longest to repair, i.e. the maximum \(P_i\) among those chosen.

Your task is to help Pear determine the minimum possible completion time for each query. In other words, for the selected set \(S\) in a query, find the minimum possible value \(X\) such that there exists a set of roads (from the original roads) whose repair (with each road having its inherent repair time) connects all vertices in \(S\) and the maximum repair time among them is \(X\). It can be shown that the answer for \(S\) is equal to the maximum edge weight in the unique Steiner tree of \(S\) in the Minimum Spanning Tree (MST) of the original graph under the \(\min\text{-}\max\) criteria.

Note: The queries are independent; the repair plan in one query does not affect another.

inputFormat

The first line contains two integers \(N\) and \(M\) denoting the number of residences and the number of roads, respectively.

Each of the next \(M\) lines contains three integers \(u\), \(v\) and \(P\) indicating a bidirectional road between residences \(u\) and \(v\) with repair time \(P\).

The next line contains an integer \(Q\), the number of queries.

Each of the following \(Q\) lines contains four integers \(l\), \(r\), \(K\) and \(C\). For each query, Pear selects all residences with indices in the interval \([l, r]\) for which \(i \bmod K = C\).

It is guaranteed that the original graph is connected.

outputFormat

For each query, output a single integer representing the minimum required time (i.e. the minimized maximum repair time among the chosen roads) needed to connect the selected residences. If the selected set contains at most one residence, output 0.

sample

4 4
1 2 3
2 3 5
2 4 2
3 4 4
3
1 4 1 0
2 3 2 0
1 3 1 0

4
0
4