AT_abc465_g [ABC465G] Sum of Mex of Mod of Linear

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) $ .

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 $ Q $ lines. The $ q $ -th line $ (1\le q\le Q) $ should contain the answer to the problem after processing the $ q $ -th query.

### Sample Explanation 1 The first query sets $ A=(0,2) $ . The sought value is $ \displaystyle \text{mex}(\lbrace 0,2\rbrace)+\text{mex}(\lbrace 1,0\rbrace)=1+2=3 $ . The second query sets $ A=(1,2) $ . The sought value is $ \displaystyle \text{mex}(\lbrace 1,2\rbrace)+\text{mex}(\lbrace 2,0\rbrace)=0+1=1 $ . The third query sets $ A=(1,1) $ . The sought value is $ \displaystyle \text{mex}(\lbrace 1,1\rbrace)+\text{mex}(\lbrace 2,2\rbrace)=0+0=0 $ . ### 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.