Description

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

Input Format

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 Format

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.

0
5 10 3
1 2 3 4 5
1 5
2 5
3 5
4 5
5 5
10 10
20 30
10 30
1 30
5 30

2
2
2
2
1
2
18
35
43
42

1
5 10 3 100
1 2 3 4 5
1 5
2 5
3 5
4 5
5 5
10 10
20 30
10 30
1 30
5 30

2
5
5
3
2
1
18
35
50
44

Hint

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