P6638 "JYLOI Round 1" Routine.

LS has made $n$ routines, where the time when the $i$-th routine was created is $a_i$. For the $i$-th routine, every $k$ seconds after its creation time $a_i$, he has to do the $i$-th routine once. The time it takes to do a routine can be ignored. Now LS wants to ask you $m$ queries. Each query is given as an interval $[l_i, r_i]$, asking how many times in total he did all routines from second $l_i$ to second $r_i$.

The first line contains an integer $type$, which is either $0$ or $1$, and it will be used below. For $type = 0$, the next line contains three positive integers $n$, $m$, and $k$, with meanings as described above. The next line contains $n$ positive integers. The $i$-th positive integer in this line is $a_i$, with meaning as described above. Then there are $m$ lines. The $i$-th line indicates that the $i$-th query is an interval $[l_i, r_i]$, where $l_i$ and $r_i$ have meanings as described above. For all queries with $type = 0$, we do not apply any encryption. For $type = 1$, the next line contains four positive integers $n$, $m$, $k$, and $mod$. The meanings of $n$, $m$, and $k$ are as described above, and $mod$ is a parameter used below. The next line contains $n$ positive integers. The $i$-th positive integer in this line is $a_i$, with meaning as described above. Then there are $m$ lines. The $i$-th of these $m$ lines contains two positive integers $l_i$ and $r_i$, indicating that the $i$-th query is an interval $[l_i, r_i]$, where $l_i$ and $r_i$ have meanings as described above. In particular, we encrypt queries $2$ to $m$. For the $i$-th query $(2 \leq i \leq m)$, after decryption: $$l_i = \min((l_i + \text{lastans} - 1) \;\text{mod}\; mod + 1, (r_i + \text{lastans} - 1) \;\text{mod}\; mod + 1)$$ $$r_i=\max((l_i + \text{lastans} - 1) \;\text{mod}\; mod + 1, (r_i + \text{lastans} - 1) \;\text{mod}\; mod + 1)$$ Here $\text{lastans}$ is the answer to the $(i - 1)$-th query. For queries $2$ to $m$, your program needs to output the answer for the decrypted query. **In particular, the first query is not encrypted.**

Output $m$ lines in total. For each decrypted query, output one line. The $i$-th output line is the answer to the $i$-th query.

### Explanation of Sample 2 The decrypted queries are [1, 5], [4, 7], [8, 10], [9, 10], [8, 8], [12, 12], [21, 31], [28, 48], [36, 65], [55, 80], so the answers can be obtained. ____________ ### Constraints For $100\%$ of the data, $type \in \{0, 1\}; 1 \leq n, m \leq 10^5; 0 \leq l_i \leq r_i \leq 10^9; 0 \leq a_i \leq 10^9; 1 \leq k, mod \leq 10^9$. Subtask 1 (10 test points, 1 point each, 10 points total): $type = 0; n, m, k \leq 10^3; r_i \leq 10^3$. Subtask 2 (10 test points, 1 point each, 10 points total): $type = 0; n, m \leq 10^3$. Subtask 3 (2 test points, 5 points each, 10 points total): $type = 0, r_i \leq 10^5,k = 1$. Subtask 4 (20 points total): $type = 0, k \leq 10^5, r_i \leq 10^5$. Subtask 5 (30 points total): $type = 0$. Subtask 6 (20 points total): no special constraints. For Subtasks 4, 5, and 6, scoring is bundled (that is, you must pass all test points within a subtask to get the points for that subtask). This problem has 50 test points in total, worth 100 points. ## Problem Source "JYLOI Round 1" D. Idea / Solution / Data: abcdeffa. Translated by ChatGPT 5