Problem Statement

Takahashi will receive some presents from now on.

He has an integer parameter called mood, and the mood changes each time he receives a present. Each present has an integer parameter called value $P$, and Takahashi's mood changes according to this parameter as follows:

• If the value $P$ of the received present is greater than or equal to the mood value, he is delighted with the present, and the mood increases by $A$.
• If the value $P$ of the received present is less than the mood value, he is disappointed with the present, and the mood decreases by $B$.

Initially, there are $N$ presents that Takahashi is scheduled to receive, and the value of the $i$-th present he will receive $(1\le i\le N)$ is $P _ i$.

You are given $Q$ queries consisting of two types: addition queries and question queries. Process all of them in order, and answer all question queries.

The $i$-th query is represented by two integers $T _ i,X _ i$, and it is an addition query if $T _ i=1$, and a question query if $T _ i=2$.

In an addition query, add a new present with value $X _ i$ to the end of the presents to be received.

In a question query, answer the following question:

Find Takahashi's mood after receiving all the presents he is scheduled to receive when his mood is initially $X _ i$.

Constraints

• $1\le N\le2\times10 ^ 5$
• $1\le A\le10 ^ 9$
• $1\le B\le10 ^ 9$
• $-10 ^ 9\le P _ i\le10 ^ 9\ (1\le i\le N)$
• $1\le Q\le2\times10 ^ 5$
• $T _ i=1$ or $T _ i=2\ (1\le i\le Q)$
• There exists an integer $i\ (1\le i\le Q)$ such that $T _ i=2$.
• If $T _ i=1$, then $-10 ^ 9\le X _ i\le10 ^ 9$. $(1\le i\le Q)$
• If $T _ i=2$, then $-10 ^ {12}\le X _ i\le10 ^ {12}$. $(1\le i\le Q)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N A B
P _ 1 P _ 2 \ldots P _ N
Q
T _ 1 X _ 1
T _ 2 X _ 2
\vdots
T _ Q X _ Q

Output

Let $q$ be the number of question queries, and print $q$ lines. The $i$-th line $(1\le i\le q)$ should contain the answer to the $i$-th question query.