题目描述

LS 制定了 $n$ 项常规，其中第 $i$ 项常规制定的时间是 $a_i$。

对于第 $i$ 项常规，从第 $i$ 项常规的制定时间 $a_i$ 后的每 $k$ 秒，他都要做一次第 $i$ 项常规，他做一次常规的时间可以忽略不计。

现在 LS 想给你 $m$ 个询问，每个询问用一个区间 $[l_i, r_i]$ 来表示，问你在第 $l_i$ 到 $r_i$ 秒，他一共做了多少次常规。

输入格式

输入的第一行是一个为 0 或 1 的整数 $type$，在接下来会用到。

对于 $type = 0$ 的情况，接下来有一行三个正整数 $n$、$m$、$k$，含义如题所述。

接下来有一行 $n$ 个正整数，这一行中的第 $i$ 个正整数表示的是 $a_i$，$a_i$ 的含义如题所述。

接下来有 $m$ 行，第 $i$ 行表示的是第 $i$ 个询问是一个区间 $[l_i, r_i]$，$l_i$ 和 $r_i$ 的含义如题所述。对于 $type = 0$ 的所有询问，我们都没有进行加密。

对于 $type=1$ 的情况，接下来有一行四个正整数 $n$、$m$、$k$ 和 $mod$，$n$、$m$、$k$ 的含义如题所述，其中 $mod$ 是一个会在下面用到的参数。

接下来有一行 $n$ 个正整数，这一行中的第 $i$ 个正整数表示的是 $a_i$，$a_i$ 的含义如题所述。

接下来有 $m$ 行，这 $m$ 行中的第 $i$ 行有两个正整数 $l_i$ 和 $r_i$，表示第 $i$ 个询问是一个区间 $[l_i, r_i]$，$l_i$ 和 $r_i$ 的含义如题所述。特别地，我们加密了第 2 至第 $m$ 个询问，对于第 $i(2 \leq i \leq m)$ 个询问，解密后的：

其中 $\text{lastans}$ 是第 $(i - 1)$ 个询问的答案，对于第 2 到第 $m$ 个询问，你的程序需要回答解密后的询问所对应的答案。

特别地，第一个询问没有被加密。

输出格式

输出共有 $m$ 行，对于每个解密后的询问输出一行，输出中的第 $i$ 行表示的是第 $i$ 个询问的答案。

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

提示

样例 2 说明

解密后的询问分别为 [1, 5]、[4, 7]、[8, 10]、[9, 10]、[8, 8]、[12, 12]、[21, 31]、[28, 48]、[36, 65]、[55, 80]，因此可以得出答案。

数据范围

对于 $100\%$ 的数据，满足 $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$。

子任务 1（有 10 个测试点，每个测试点 1 分，共 10 分）：$type = 0; n, m, k \leq 10^3; r_i \leq 10^3$。

子任务 2（有 10 个测试点，每个测试点 1 分，共 10 分）：$type = 0; n, m \leq 10^3$。

子任务 3（有 2 个测试点，每个测试点 5 分，共 10 分）：$type = 0, r_i \leq 10^5,k = 1$。

子任务 4（共 20 分）：$type = 0, k \leq 10^5, r_i \leq 10^5$。

子任务 5（共 30 分）：$type = 0$。

子任务 6（共 20 分）：无特殊限制。

对于子任务 4、5、6，分别捆绑计分（即你需要通过一个子任务内的所有测试点才能够拿到这个子任务的分数），本题总共 50 个测试点、100 分。

题目来源

「JYLOI Round 1」 D

Idea / Solution / Data ：abcdeffa