Background

颠簸了15天！他已从上海坐公交到达漠河！被网友笑称“中华铁腚” 光明网 2024-01-30 19:52 从上海出发 一路换乘各种公交 最远能到多远？ 一名“00后”大学生1月15日出发 1月29日上午 他到达了黑龙江漠河！ 3800多公里！ 公交上颠簸了15天！ 网友开玩笑叫他“中华铁腚” 哈哈哈，太牛了！

2022年，当时在上海读大二的医学生小江曾花9天时间从上海坐公交到北京。今年1月，参加完考研的他再次踏上了更为漫长的公交之旅。这一次，目的地是漠河北极村。 “我从小生活在南方，从来没有去过东北，很想去看看冰雪大世界，品尝东北早市的美食。” 小江表示 到达这次旅程最后一座城市漠河之后 他将前往北极村邮局 作为这次旅程的终点

“北极村邮局” 是中国最北的邮局 位于祖国最北、纬度最高的地方 最低气温曾达到零下53度！

从上海乘公交前往漠河 是一种怎样的体验？ 1月15日出发当日 小江给公交卡充了值 这是一张全国很多城市都能用的交通卡 出发当天余额有972元

1月29日到达漠河后 小江透露 公交卡里的钱居然没！用！完！

他规划的路线途经许多城市 3800多公里的旅途 公交要坐2000多站 上海-苏州-无锡-江阴-泰州…… 扬州-泰安-济南-保定-北京…… 盘锦-沈阳-铁岭-哈尔滨-漠河…… 光是看看这路线 我已经开始屁股疼 尾巴骨疼了

一路上 他晒出各地的风土人情 和各色风光

还看到了吉林雾凇 和美丽的夕阳

他晒出了一路上的车票 作为纪念

中途甚至还临时找了个网吧 因为被导师催着改开题报告 哈哈哈哈！

1月28日 他乘上从哈尔滨开往漠河的 “雪国列车” 一路上都是北国冰雪风光

有人关注有人质疑 曾被骂到差点中途放弃 小江这趟旅行并非一帆风顺 刚开始因这趟旅行爆火时 他曾多次遭到网友的质疑 各种不好听的话让他很难过 差一点打退堂鼓 但他最终坚持了下来 “我不是网红，也不是名人。” “我没有直播，没有卖货。” 他说到自己“公交旅行”的初衷 ↓↓↓ “我喜欢地理，想要慢慢欣赏沿途的山河风光，不想立刻到达终点。电影《阿甘正传》也给我很多力量，我羡慕主人公阿甘漫无目的地追寻与奔跑，在路上思考与治愈自己。” “我的旅途经费几乎全部来源我自己的奖学金。” “有人说我这么做浪费时间、没有意义。但我觉得只要把时间花在喜欢的事情上，因为开心，所以钱和时间都花得值。” 他经过河北一个叫“柏林”的小村庄 道路上很泥泞 但让人意外的是 公交车座椅上居然有专门的坐垫 让他这个“中华铁腚”感到很温暖

由于他在途中除了公交也搭乘了 地铁、火车等交通工具 遭到了一些“公交迷”诟病 认为他“违规” 有博取流量之嫌 换乘火车前往漠河时 他还特意发文解释 “这次是冬天 更想体验一下 哈尔滨开往漠河的‘雪国列车’ 这也是我一直以来的梦想”

他说 “把我当成旅行青蛙就好” “很多人也在问我，身体吃得消吗？我觉得还行，因为我体质蛮好，这一路上蛋白质、脂肪、热量等我都会摄入。路上还遇到很多来帮助我的人，他们会提前看我在哪一站下车，把饼干、面包等零食送到我手上。” “我是以一颗平常心去进行这趟旅程的。希望大家把我当成旅行青蛙，其他朋友如果想再走一遍我的路线，只要规划好，有毅力，有执行，其实也不难。” 不少一路关注他的网友 纷纷向他送上祝福 “终于见证你抵达！” “一路辛苦了！”

有的网友对这位“旅行青蛙”朋友 说出了不少人的心里话 “好感动， 世界这么大总有人带我们去看看！”

Description

现在你在家里，你需要坐公交车去漠河北极村邮局，有n个公交站。你只能从家步行到第一个公交站，然后在各个公交站之间乘公交车，最后在最后一个公交站步行到北极村邮局。每个公交站有一定的出发频率和到达时间。

具体操作如下:

1.第i个公交站的第一班车发车时间是PI，并且每隔P秒会出发一辆公交车。例如，第1个公交站的发车时间为P1,2× P1,3×P1,...。

2.从第i个公交站出发的公交车会在TI秒后到达第i＋1个公交站。

从家到第一个公交站步行时间为X秒，从最后一个公交站到邮局的步行时间为Y秒。如果到达某个公交站的同时，该公交站有公交车出发，你可以坐上该公交车。

现在有Q个询问，每个询问包含一个时间qi;，表示从家里出发的时间，请你求出到达邮局的时间为多少。

Format

Input

第一行一个整数 $n(2\le n \le 10^5) x, y (1\le X, Y \le 10^9)$ 。

接下来n-1行，每行两个整数 $Pi(\le 8)$ 和 $Ti(\le 10^9)$。

接下来一行一个整数 $Q(\le 2\times 10^5)$ 表示询问的次数。

接下来Q行，每行一个出发时间 $qi (0\le qi \le 10^9)$。

Output

输出Q行，第i行输出第i次询问的答案。

Samples

4 2 3
5 4
6 6
3 1
7
13
0
710511029
136397527
763027379
644706927
447672230

34
22
710511052
136397548
763027402
644706946
447672250

Limitation

1s, 1024KiB for each test case.