DTL 工程师喜欢在周末参加聚会。埃拉也一样!不幸的是,她还不知道如何跳舞。因此,她决定参加舞蹈班。
舞蹈班有$$$n$$$个学生,其中包括Ela。在期末项目中,$$$n$$$ 学生将参与如下所述的编排。
$$$n$$$ 学生位于 $$$Ox$$$ 轴的正侧。第 $$$i$$$ 舞者位于 $$$a_i > 0$$$。有些舞者会在舞蹈过程中改变位置(我们将其称为可移动舞者),而另一些舞者将在编舞过程中保持在同一个位置(我们将其称为不可移动舞者)。我们使用长度为$$$n$$$的二进制字符串$$$s$$$来区分舞者:如果$$$s_i$$$等于'1',则第$$$i$$$个舞者是可移动的,否则第$$$i$$$个舞者是不可移动的。
我们称编舞的“正能量值”为$$$d > 0$$$。舞者将根据该值执行“动作”。
舞蹈开始后的每一分钟,$$$x$$$坐标最小的可移动舞者将开始向右移动并发起“运动”。在动作开始时,舞者的能量水平将与编舞的正能量值相等,即$$$d$$$。每次它们从 $$$y$$$ 移动到 $$$y+1$$$ 时,能量水平就会降低 $$$1$$$。在某些时候,舞者可能会在同一坐标中遇到其他舞者。如果发生这种情况,那么舞者的能量水平将增加$$$1$$$。当舞者的能量水平达到 $$$0$$$ 时,他将停止向右移动,并且他不与其他舞者共享位置。
舞者训练有素,每个“动作”都会在下一分钟开始前结束。
为了表明她对这种编排的理解,Ela 必须回答 $$$q$$$ 查询,每个查询由两个整数 $$$k$$$ 和 $$$m$$$ 组成。此查询的答案是编舞开始后第 $$$k$$$ 分钟从左起第 $$$m$$$ 两种类型的舞者的坐标。换句话说,将 $$$x_{k, 1}, x_{k, 2}, \dots, x_{k, n}$$$ 表示为从开始起第 $$$k$$$ 分钟的舞者的排序坐标,您需要打印 $$$x_{k, m}$$$。
输入
第一行包含三个整数 $$$n$$$、$$$d$$$ 和 $$$q$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le d \le 10^9$$$; $$$1 \le q \le 10^5$$$) — 舞者数量、编舞正能量值、舞者数量查询。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 < a_2 < \dots < a_n \le 10^9$$$) — 每个舞者的坐标。
第三行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ — 每个舞者的可移动性。每个字符要么是“0”,要么是“1”。保证 $$$s$$$ 至少包含一个字符“1”。
接下来是 $$$q$$$ 行,其中第 $$$i$$$ 包含两个整数 $$$k_i$$$ 和 $$$m_i$$$ ($$$1 \le k_i \le 10^9$$$, $$$1 \le m_i \le n$$$) — 每个查询的内容。
输出
输出 $$$q$$$ 行,每行包含一个整数 - 相应查询的答案。
示例
输入 #1
4 3 8 1 3 6 7 1011 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4
输出 #1
3 5 6 7 3 6 7 10
输入 #2
1 1 5 2 1 1 1 2 1 3 1 4 1 5 1
输出 #2
3 4 5 6 7
注意
让我们考虑第一个示例测试用例。
第一分钟,$$$1$$$是可移动舞者之间的最低坐标。能量级别从 $$$3$$$ 开始。然后会发生以下情况:
- 舞者从 $$$1$$$ 移动到 $$$2$$$。能量水平下降至$$$2$$$。
- 舞者从 $$$2$$$ 移动到 $$$3$$$。当她在 $$$3$$$ 遇到另一位舞者时,能量水平下降到 $$$1$$$,然后增加到 $$$2$$$。
- 舞者从 $$$3$$$ 移动到 $$$4$$$。能量水平下降至$$$1$$$。
- 舞者从 $$$4$$$ 移动到 $$$5$$$。能量水平降低至$$$0$$$。
第一分钟结束时,舞者的排序坐标变为$$$[3,5,6,7]$$$,各自的可移动性为'0111'。
第二分钟,$$$5$$$是可移动舞者之间的最低坐标。能量级别从 $$$3$$$ 开始。然后会发生以下情况:
- 舞者从 $$$5$$$ 移动到 $$$6$$$。当她在 $$$6$$$ 遇到另一位舞者时,能量水平下降到 $$$2$$$,然后增加到 $$$3$$$。
- 舞者从 $$$6$$$ 移动到 $$$7$$$。能量水平下降到$$$2$$$,然后当她在$$$7$$$遇到另一位舞者时增加到$$$3$$$。
- 舞者从 $$$7$$$ 移动到 $$$8$$$。能量水平下降至$$$2$$$。
- 舞者从 $$$8$$$ 移动到 $$$9$$$。能量水平下降至$$$1$$$。
- 舞者从 $$$9$$$ 移动到 $$$10$$$。能量水平降低至$$$0$$$。
第二分钟结束时,舞者的排序坐标变为$$$[3,6,7,10]$$$,他们各自的可移动性为'0111'。