The Oracles

While on his crazy adventures, Rick and Morty stumbled upon an alien species called the Oracles, known for their great mathematical prowess. Among the Oracles was a game called the Oracle, which they taught their infants and toddlers. In this game, there is one dealer and one player (the infant). The dealer deals the player an initially empty array A. The dealer then has the ability to perform two kinds of operations on the list: Append any number x to the end of the array. Copy the array x times back-to-back to A. The dealer performs an operation but does not reveal the array's content to the player. The Oracle then rapidly asks the player what numbers are present at different indices of the array. Rick thinks the problem is in P, but is it? Help him solve this problem. Input Format The first line contains two integers n and q, where n denotes the number of operations the dealer performs, and q denotes the number of queries the dealer asks the player. The next n lines each contain two space-separated integers. The i-th line (1

• The following line contains q space-separated integers, q_j (1 Output Format Print q integers, each representing the value at the queried index of the array.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ q ≤ 10⁵
• b_i belongs to {1, 2}, for all i (1 ≤ i ≤ n)
• 1 ≤ x_i ≤ n for b_i = 1
• 1 ≤ x_i ≤ 10⁹ if b_i = 2
• 1 ≤ q_j ≤ min(10¹⁸, e) for all j (1 ≤ j ≤ q), where e is the final size of the array.

Example 1

Input:

n = 5
q = 10
operations = [[1, 5], [1, 2], [2, 1], [1, 3], [2, 1]]
queries = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Output:

[5, 2, 5, 2, 3, 5, 2, 5, 2, 3]

Explanation:

• Before the first operation: A = []
• After the first operation: A = [5]
• After the second operation: A = [5, 5]
• After the third operation: A = [5, 5, 2, 2]
• After the fourth operation: A = [5, 5, 2, 2, 5, 5, 2, 2]
• After the fifth operation: A = [5, 5, 2, 2, 5, 3, 5, 2, 5, 2, 3]