There is an integer register that can only hold numbers in ~[L,R]~. You need to simulate the following sequence of instructions over different inputs ~X~. Initially, the register holds the integer ~X~.

• 1 a: add ~a~ to the integer held in the register.
• 2 a: subtract ~a~ from the integer held in the register.
• 3 a: multiply the integer held in the register by ~a~.
• 4 a: add ~aX~ to the integer held in the register, where ~X~ denotes the initial input.

Since the register can only hold numbers in ~[L,R]~, if the result is less than ~L~, the register will be updated to ~L~ instead. If the result is larger than ~R~, the register will be updated to ~R~.

Output the final result over ~Q~ different queries ~X_i~ where ~X_i~ denotes a possible initial value.

Note: The parameter ~a~ in the queries does not have to be in ~[L,R]~. We just require ~a \in [1,10^9]~.

Input Specification

The first line of the input consists of three positive integers ~N,L,R \; (1 \leq N \leq 3 \times 10^5, 1 \leq L \leq R \leq 10^9)~.

In the following ~N~ lines, each line consists of an instruction using the format specified above. The argument ~a~ would satisfy ~1 \leq a \leq 10^9~.

In the ~(N+2)~-th line, there is an integer ~Q \; (1 \leq Q \leq 3 \times 10^5)~ denoting the number of queries.

In the following ~Q~ lines, each line has a positive integer ~X_i \; (L \leq X_i \leq R)~ denoting the initial value ~X_i~.

Output Specification

For each query, output a line with an integer denoting the result if we start from ~X_i~ and simulate the ~N~ instructions described in the input.

Sample Input

4 1 20
4 1
2 5
3 2
1 1
5
2
3
5
7
11

Sample Output

3
3
11
19
20

Constraints

For all test cases, ~1 \leq N,Q \leq 3 \times 10^5, 1 \leq L \leq X_i \leq R \leq 10^9, 1 \leq a \leq 10^9~.

Scoring

• Subtask 1 (20 points): ~N,Q \leq 2 \times 10^3~.
• Subtask 2 (12 points): ~N \leq 5 \times 10^3, R \leq 10^6~.
• Subtask 3 (8 points): ~R \leq 10^6~. Depends on Subtask 2.
• Subtask 4 (5 points): there are only operations of type 1 (1 a).
• Subtask 5 (12 points): there are only operations of type 1 and 2. Depends on Subtask 4.
• Subtask 6 (10 points): there are only operations of type 1,2,3. Depends on Subtask 4,5.
• Subtask 7 (8 points): there are only operations of type 1,2,4. Depends on Subtask 4,5.
• Subtask 8 (25 points): no further constraints. Depends on all previous subtasks.