U392419 『ZOI Round #1』等地铁

“鸡鸣寺站到了，请准备下车。南京地铁祝福 2023 级广大新生，愿大家在人生的新起点追风逐梦，扬帆起航。”

小 Z 常常选择乘坐地铁出行。 小 Z 所在的城市有一条共有 $N$ 站的单向地铁线，每座站台按 $1 \sim N$ 编号。其中，对于 $1 \le i < N$，地铁从第 $i$ 站到第 $(i + 1)$ 站需要 $A_i$ 分钟。始发车会在 $0$ 分钟时从第 $1$ 站出发，之后每隔 $K$ 分钟会发一班车。 小 Z 有 $Q$ 个形如 `x t` 的出行计划，表示他将在 $t$ 分钟时来到第 $x$ 站乘车。由于他不喜欢等车，他希望你能帮他算一算每次乘车他需要等待多长时间。

无

无

#### 样例解释 #1 地铁的发车时间为 $0,2,4,6,8,\dots$。 地铁到达第二站的时间为 $1,3,5,7,9,\dots$。 地铁到达第三站的时间为 $3,5,7,9,11,\dots$。 第一次询问中，小 Z 在 $0$ 分钟时来到第 $3$ 站，等待 $3$ 分钟时到达的地铁，需要等待 $3$ 分钟。 第二次询问中，小 Z 在 $1$ 分钟时来到第 $3$ 站，等待 $3$ 分钟时到达的地铁，需要等待 $2$ 分钟。 第三次询问中，小 Z 在 $2$ 分钟时来到第 $3$ 站，等待 $3$ 分钟时到达的地铁，需要等待 $1$ 分钟。 第四次询问中，小 Z 在 $3$ 分钟时来到第 $3$ 站，地铁正好到达，需要等待 $0$ 分钟。 第五次询问中，小 Z 在 $4$ 分钟时来到第 $3$ 站，等待 $5$ 分钟时到达的地铁，需要等待 $1$ 分钟。 #### 数据范围 **本题采用捆绑测试**。 - Subtask 1（40 points）：$1 \le N,Q \le 10^3$。 - Subtask 2（60 points）：无特殊限制。 对于所有测试数据，$1 \le N,Q \le 10^5$，$1 \le K \le 10^9$，$1 \le A_i \le 10^9$，$1 \le x \le N$，$0 \le t \le 10^9$。