Predicting Chess Piece Destination on a Directed Graph

You are given a directed graph with \(n\) nodes and \(m\) edges. The nodes are numbered from \(1\) to \(n\) and the edges are labeled from \(1\) to \(m\). Each edge \(i\) has an associated positive integer \(w_i\) and is described by its starting node \(u\) and its ending node \(v\). Initially, no edge has been traversed.

The owner of the graph, Yazid, will perform \(Q\) operations sequentially. In each operation, two integers \(x\) and \(s\) are given. A chess piece is placed at node \(x\) and will move exactly \(s\) steps (or fewer if it cannot move). The movement of the chess piece is as follows:

• At the current node, if there is no outgoing edge, the piece stops immediately.
• If there are outgoing edges available, the piece will always pick the edge with the smallest label among the available ones.
• After the piece traverses an edge, the edge's traversal count increases by \(1\). When an edge \(i\) has been traversed exactly \(w_i\) times in total (over all operations), it is immediately removed from the graph and cannot be used in subsequent moves.

The piece moves until it has performed \(s\) moves or no outgoing edge is available. The node at which the piece finally stops is called the destination for that operation. After the operation, the chess piece is removed from the game. Note: The operations are persistent — any edge removals or traversal counts are maintained between operations.

Your task is to predict the destination node for each operation.

inputFormat

The first line contains three integers \(n\), \(m\), and \(Q\) where \(n\) is the number of nodes, \(m\) is the number of edges, and \(Q\) is the number of operations.

The next \(m\) lines each contain three integers \(u\), \(v\), and \(w_i\), representing a directed edge from node \(u\) to node \(v\) with a traversal limit of \(w_i\) times.

The following \(Q\) lines each contain two integers \(x\) and \(s\), indicating an operation where a chess piece is placed at node \(x\) and is allowed to move up to \(s\) steps.

outputFormat

Output \(Q\) lines. The \(i\)th line should contain a single integer denoting the destination node of the chess piece in the \(i\)th operation.

sample

3 3 3
1 2 2
2 3 1
2 1 1
1 2
2 3
3 1

3
2
3