Problem Description

Given a directed graph with $n$ nodes and $m$ edges, where nodes are numbered from $1$ to $n$ and edges from $1$ to $m$.

The owner of the graph, Yazid, will perform $Q$ operations sequentially. Each operation involves placing a chess piece on node $x$ and setting an integer $s$. The chess piece will continuously move along the smallest numbered outgoing edge from its current node. Each edge $i$ will be removed from the graph after being traversed $w_i$ times. The piece will stop moving either when it has moved $s$ steps or when there are no outgoing edges left. The node where the piece stops is called the destination of that operation. After this, Yazid will remove the chess piece from the game.

You need to predict the destination node for each of Yazid's operations.

Note that all operations have cumulative effects. This means that edges removed and the counts of traversals in previous operations will not be reset for subsequent operations.

Input Format

The first line contains two integers $n$ and $m$ separated by a space.

The next $m$ lines describe the directed graph. Each line (for $1 \leq i \leq m$) contains three integers $u_i$, $v_i$, and $w_i$ separated by spaces, representing a directed edge from $u_i$ to $v_i$ that will be removed after being traversed $w_i$ times.

• It is guaranteed that $1 \leq u_i, v_i \leq n$ and $w_i \leq 10^{18}$.

The next line contains an integer $Q$.

The next $Q$ lines describe the operations sequentially. Each line contains two integers $x$ and $s$ separated by a space, representing an operation.

• It is guaranteed that $1 \leq x \leq n$ and $1 \leq s \leq 10^{9}$.

Output Format

Output $Q$ lines, each containing a single integer, representing the destination node for each operation in the order they were given.

Sample Input and Output

Sample Input #1

7 8
3 1 3
1 2 5
2 3 2
6 3 1
5 2 2
4 2 1
7 5 3
2 2 2
3
7 7
6 2
6 2

Sample Output #1

1
1
6

Sample Input #2

See attached file 2.in.

Sample Output #2

See attached file 2.ans.

Notes/Hints

[Sample Explanation #1]

For the first operation, the chess piece moves as follows:

1. Place the piece on node $7$.
2. Move along the smallest numbered edge from node $7$ to node $5$.
3. Move along the smallest numbered edge from node $5$ to node $2$.
4. Move along the smallest numbered edge from node $2$ to node $3$.
5. Move along the smallest numbered edge from node $3$ to node $1$.
6. Move along the smallest numbered edge from node $1$ to node $2$.
7. Move along the smallest numbered edge from node $2$ to node $3$. The edge from $2$ to $3$ is now removed.
8. Move along the smallest numbered edge from node $3$ to node $1$.
9. The piece stops at node $1$, which is the destination.

For the second operation, the chess piece moves as follows:

1. Place the piece on node $6$.
2. Move along the smallest numbered edge from node $6$ to node $3$. The edge from $6$ to $3$ is now removed.
3. Move along the smallest numbered edge from node $3$ to node $1$. The edge from $3$ to $1$ is now removed.
4. The piece stops at node $1$ after moving 2 steps, which is the destination.

For the third operation, the chess piece moves as follows:

1. Place the piece on node $6$.
2. Node $6$ has no outgoing edges, so the piece stops at node $6$, which is the destination.

[Subtasks]

This problem consists of multiple subtasks. Each subtask may contain multiple test cases, and you must pass all test cases in a subtask to earn points for that subtask.

Each subtask has specific constraints, as detailed in the table below:

For all test cases, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq m \leq 1.5 \times 10^5$, $1 \leq Q \leq 10^5$, $1 \leq s \leq 10^9$, and $1 \leq w_i \leq 10^{18}$.

• Property 0: No special properties.
• Property 1: The graph is randomly generated, with each edge $(u, v)$ appearing with a probability of $1 / n^2$.
• Property 2: Guaranteed $w_i = 10^{18}$.
• Property 3: The graph forms a rooted tree.
• Property 4: The graph forms a tree with a cycle.
• Property 5: The first $n$ edges form a tree with a cycle.

见题面 Input 部分

见题面 Output 部分