Strange Calculator

JYY has a strange calculator. One day, the calculator broke, and JYY hopes you can help him write a program to simulate its operations.

JYY's calculator can execute $N$ preset instructions. Each time JYY inputs a positive integer $X$ into the calculator, the calculator uses $X$ as the initial value, then sequentially executes the $N$ preset instructions, and finally returns the resulting value to JYY.

Each instruction is one of the following four types (where $a$ represents a positive integer):

1. + a: Adds $a$ to the current result.
2. - a: Subtracts $a$ from the current result.
3. * a: Multiplies the current result by $a$.
4. @ a: Adds $a \times X$ to the current result (where $X$ is the number JYY initially input).

The calculator has a limited storage range for the variable recording the result, so overflow or underflow issues occur after each operation.

In JYY's calculator, the variable storing the result can only hold positive integers between $L$ and $R$. If, after an instruction is executed, the result exceeds $R$, the calculator automatically changes the result to $R$ and continues subsequent calculations using $R$ as the current result. Similarly, if the result is less than $L$, the calculator changes the result to $L$ and continues the calculation.

For example, suppose the calculator can store values between $1$ and $6$. If the current result is $2$, after executing the + 5 operation, the value in the variable will be $6$. Although the actual result of $2+5$ is $7$, since $7$ exceeds the upper bound of the storage range, the result is automatically corrected to the upper bound, which is $6$.

JYY wants to input $Q$ values into the calculator. He wants to know what the result will be for each of these $Q$ values.

Input

The first line of the input contains three positive integers: $N$, $L$, and $R$.

The next $N$ lines each contain an instruction. Each instruction consists of a character and a positive integer, separated by a space.

The $(N+2)$-th line contains an integer $Q$, representing the number of values JYY wishes to input.

The next $Q$ lines each contain a positive integer, where the $k$-th integer $X_k$ represents the integer JYY inputs for the $k$-th time.

Output

Output $Q$ lines, each containing a positive integer. The integer on the $k$-th line represents the result obtained after inputting $X_k$ and processing it through the $N$ instructions.

Examples

Input 1

5 1 6
+ 5
- 3
* 2
- 7
@ 2
3
2
1
5

Output 1

5
3
6

Note

When JYY inputs $2$, the calculator performs $5$ operations. The results after each operation are $6$ (the actual result is $7$ but it exceeds the upper bound), $3$, $6$, $1$ (the actual result is $-1$ but it is below the lower bound), and $5$ (since the initial input was $2$, this operation is $1 + 2 \times 2$).

Constraints

• For 10% of the data: $N, Q \leq 100$ and instructions only contain + and -.
• For 30% of the data: $N \leq 3000$ and instructions only contain + and -.
• For 50% of the data: $N \leq 3000$, $R, a \leq 10^6$, and instructions only contain +, -, and *.
• For an additional 30% of the data: instructions only contain +, -, and @.
• For 100% of the data: $1 \leq N, Q \leq 10^5$, $1 \leq L \leq X_k \leq R \leq 10^9$, $1 \leq a \leq 10^9$.