Description

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

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

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

The variable that stores the computation result has a limited range, so overflow may occur after each computation.

In JYY’s calculator, the result variable can only store positive integers between $L$ and $R$. If after executing an instruction the result exceeds $R$, the calculator will automatically change it to $R$, then continue from $R$. Similarly, if the result is less than $L$, the calculator will change it to $L$, then continue computing.

For example, suppose the calculator can store values from $1$ to $6$. If the current result is $2$, then after executing $+5$, the stored value will be $6$. Although the actual result $2+5$ is $7$, since $7$ exceeds the upper bound, the result is clamped to the upper bound $6$.

JYY plans to input $Q$ values into the calculator and wants to know what result each input will produce.

Input Format

The first line contains three positive integers $N$, $L$, and $R$.

The next $N$ lines each contain one instruction. Each instruction, as described above, consists of one symbol and one positive integer, separated by a space.

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

The next $Q$ lines each contain a positive integer. The $k$-th positive integer $X_k$ is the integer JYY inputs on the $k$-th time.

Output Format

Output $Q$ lines, each with a positive integer. The integer on the $k$-th line is the result obtained after inputting $X_k$ and then executing the $N$ instructions in order.

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

5
3
6

Hint

Sample Explanation

When JYY inputs $2$, the calculator performs $5$ operations. After each operation, the results 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 step computes $1 + 2 \times 2$).

Constraints

For all testdata, $1 \le N, Q \le 10^5$, $1 \le L \le X_k \le R \le 10^9$, $1 \le a \le 10^9$.

Translated by ChatGPT 5