Graph Query with Edge Weight Constraints

You are given an undirected weighted graph with n vertices and m edges. The weight of vertex i is \(a_i\). Each edge has an associated weight.

There are q queries. In each query, you are given three integers \(u', x', k'\). First, these values are decrypted as follows:

• \(u = ((u' \oplus lastans) \bmod n) + 1\)
• \(x = x' \oplus lastans\)
• \(k = ((k' \oplus lastans) \bmod n) + 1\)

Here, \(lastans\) is initially 0 and is updated after each query to the answer of that query (if the answer is \(-1\) then consider \(lastans=0\) for the purpose of decryption).

For each query, starting from vertex \(u\), consider only those edges whose weight \(\le x\). Let the set of reachable vertices be \(S\). Sort the values \(\{a_i : i \in S\}\) in non-increasing order. Output the kth largest vertex weight among them. If there are fewer than \(k\) vertices reachable, output \(-1\).

Note: This is an online query problem. Make sure the decryption of queries is performed in order.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of vertices and edges respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) - the weights of the vertices.

Then, \(m\) lines follow, each containing three integers \(u\), \(v\), and \(w\), indicating an undirected edge between vertices \(u\) and \(v\) with weight \(w\).

The next line contains an integer \(q\) representing the number of queries.

Then \(q\) lines follow, each containing three integers \(u'\), \(x'\), and \(k'\). These are the encrypted query values.

outputFormat

For each query, output a single integer on a new line, which is the answer to that query—the kth largest vertex weight among those reachable using only edges with weight \(\le x\). If there are fewer than \(k\) reachable vertices, output \(-1\).

sample

5 5
1 5 2 4 3
1 2 3
2 3 2
3 4 4
4 5 1
1 5 5
3
0 3 1
0 6 0
7 1 3

2
3
4