logo Algo Beat Contest
登录 注册

#998. 『ZOI Round #1』等地铁

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AlgoBeat 官方账号

题目描述

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

小 Z 常常选择乘坐地铁出行。

小 Z 所在的城市有一条共有 站的单向地铁线,每座站台按 编号。其中,对于 ,地铁从第 站到第 站需要 分钟。始发车会在 分钟时从第 站出发,之后每隔 分钟会发一班车。

小 Z 有 个形如 x t 的出行计划,表示他将在 分钟时来到第 站乘车。由于他不喜欢等车,他希望你能帮他算一算每次乘车他需要等待多长时间。

输入格式

第一行包含三个正整数 ,表示站台的数量,发车间隔时间和出行计划的数量。

第二行包含 个正整数 ,表示地铁从第 站到第 站需要的时间。

接下来 行,每行包含两个正整数 ,表示出行计划,即将在 分钟时来到第 站乘车。

输出格式

输出包含 行,每行一个整数,表示每次乘车需要的等待时间。

样例

输入 #1

3 2 5
1 2
3 0
3 1
3 2
3 3
3 4

输出 #1

3
2
1
0
1

输入 #2

10 7 10
2 8 5 1 10 5 9 9 3
6 64
2 45
2 27
6 91
8 42
2 36
3 4
3 53
2 82
9 16

输出 #2

4
6
3
5
5
1
6
6
4
33

数据范围与提示

样例解释 #1

地铁的发车时间为

地铁到达第二站的时间为

地铁到达第三站的时间为

第一次询问中,小 Z 在 分钟时来到第 站,等待 分钟时到达的地铁,需要等待 分钟。

第二次询问中,小 Z 在 分钟时来到第 站,等待 分钟时到达的地铁,需要等待 分钟。

第三次询问中,小 Z 在 分钟时来到第 站,等待 分钟时到达的地铁,需要等待 分钟。

第四次询问中,小 Z 在 分钟时来到第 站,地铁正好到达,需要等待 分钟。

第五次询问中,小 Z 在 分钟时来到第 站,等待 分钟时到达的地铁,需要等待 分钟。

数据范围

本题采用捆绑测试

  • Subtask 1(40 points):
  • Subtask 2(60 points):无特殊限制。

对于所有测试数据,