FastPrep

Description

Solutions

The Oracles

🤘 INTERN📚RELATED PROBLEMS

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 <= i <= n) contains two integers b_i and x_i:

👉 If b_i is 1, it denotes the operation of the first kind: the array becomes A <- A + [x_i].

👉 If b_i is 2, it denotes the operation of the second kind: the array becomes A <- [A | A | ... | A] (copied x_i times).

- The following line contains q space-separated integers, q_j (1 <= j <= q), where q_j is an index of the array.

Output Format

Print q integers, each representing the value at the queried index 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]

Constraints:

- 1 <= n <= 10^5

- 1 <= q <= 10^5

- b_i belongs to {1, 2}, for all i (1 <= i <= n)

- 1 <= x_i <= n for b_i = 1

- 1 <= x_i <= 10^9 if b_i = 2

- 1 <= q_j <= min(10^18, e) for all j (1 <= j <= q), where e is the final size of the array.