Problem Statement

You are given integers $N,M,C,K$ and an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$.

You are given $Q$ queries, which you should process in order. The $q$-th $(1\le q\le Q)$ query gives integers $i_q,X_q$, and you should solve the following problem after changing $A_{i_q}$ to $X_q$.

Find the value of $\displaystyle \sum_{k=0}^{K-1} \mathop{\mathrm{mex}}\limits_{1 \le i \le N} \lbrace (Ck+A_i)\bmod M\rbrace$. Here, $\displaystyle \mathop{\mathrm{mex}}\limits_{1 \le i \le N} B_i$ denotes the smallest non-negative integer not contained in $B$, for an integer sequence $B=(B_1,B_2,\ldots,B_N)$.

Constraints

• $1\le N\le 2\times 10^5$
• $0\le C < M \le 10^9$
• $1\le K\le 10^9$
• $0\le A_i < M$
• $1\le Q\le 2\times 10^5$
• $1\le i_q \le N$
• $0\le X_q < M$
• All input values are integers.

Input

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

N M C K
A_1 A_2 \ldots A_N
Q
i_1 X_1
i_2 X_2
\vdots
i_Q X_Q

Output

Output $Q$ lines.

The $q$-th line $(1\le q\le Q)$ should contain the answer to the problem after processing the $q$-th query.