Description

There are N players in a trading card game(集換式卡牌遊戲), each player has a card binder that holds a certain number of cards. Player i 's binder has Mi card slots, and initially, the j-th slot of player i 's binder holds a unique card numbered A_{i, j}.

Since this is a trading card game, "card trading" is naturally an essential aspect. You are given T trades between the players. Each trade involves 4 numbers: x1_i , y1_i , x2_i , and y2_i . This means player x1_i trades the card in slot y1_i of their binder with the card in slot y2_i of player x2_i ’s binder.

The trades occur in the order they are given. That is, the i-th trade happens before the (i +1)-th trade.

After all the trades are completed, you need to answer Q queries. Each query consists of a number, num_i. For each query, you need to report two numbers, p_i and c_i, representing that the card numbered num_i is in slot c_i of player p_i's binder after all the trades have taken place.

Input

The first line of input contains an integer N, representing the number of players.

The second line contains N integers M₁, M₂, ..., M_N, where M_i represents the capacity (number of cards) of the i-th player's card binder.

The next N lines, where the i-th line contains M_i integers, represent the initial card numbers in the binder of the i-th player: A_{i, 1}, A_{i, 2}, ..., A_{i, Mi}.

After that, there is an integer T representing the number of card trades.

The next T lines each contain 4 integers x1_i, y1_i, x2_i, y2_i, indicating that the card in the y1_i -th slot of the x1_i -th player’s binder is traded with the card in the y2_i -th slot of the x2_i -th player’s binder.

The final line contains an integer Q, representing the number of queries.

The next line contains Q integers num₁, num₂, ..., num_Q , separated by spaces, representing queries asking for the locations of the cards numbered num_i.

 

Constraints

• 1 ≤ N ≤ 1000
• 1 ≤ Q ≤ 10⁵
• 0 ≤ T ≤ 10⁶
• 1 ≤ M_i ≤ 10⁵ , Σ M_i ≤ 10⁶
• 1 ≤ A_{i, j} ≤ Σ M_i 
• for all ( i, j ) ≠ ( k, l ) ,  A_{i, j} ≠ A_{k, l} 
• 1 ≤ x1_i ,x2_i  ≤ N
• for all α = x1_i , 1 ≤ y1_i ≤ M_α
• for all α = x2_i , 1 ≤ y2_i ≤ M_α
• 1 ≤ num_i ≤ Σ M_i 

 

Subtasks

• Testcases 1: N = 1 ; T = 0
• Testcases 2~4: N = 1 ; T,Q ≤ 100 
• Testcases 5~6: N = 1
• Testcases 7: N = 2 ; Q ≤ 100
• Testcases 8: N,Q ≤ 100
• Testcases 9~10: No additional restrictions.

Output

For each query, output two integers, p_i and c_i representing that the card numbered num_i is in the c_i-th slot of the p_i-th player's binder after all the trades have taken place.

Please remember to print "\n" at the end of each query.

When outputting p_i and c_i, ensure there is a space between them, and make sure there is no space after c_i. Otherwise, you may get a Presentation Error.

Sample Input  Download

Sample Output  Download

Tags

Discuss