CF1737G.Ela Takes Dancing Class

DTL engineers love partying in the weekend. Ela does, too! Unfortunately, she didn't know how to dance yet. Therefore, she decided to take a dancing class.

There are $n$ students in the dancing class, including Ela. In the final project, $n$ students will participate in a choreography described below.

$n$ students are positioned on the positive side of the $Ox$-axis. The $i$-th dancer is located at $a_i \gt 0$. Some dancers will change positions during the dance (we'll call them movable dancers), and others will stay in the same place during a choreography (we'll call them immovable dancers). We distinguish the dancers using a binary string $s$ of length $n$: if $s_i$ equals '1', then the $i$-th dancer is movable, otherwise the $i$-th dancer is immovable.

Let's call the "positive energy value" of the choreography $d \gt 0$. The dancers will perform "movements" based on this value.

Each minute after the dance begins, the movable dancer with the smallest $x$-coordinate will start moving to the right and initiate a "movement". At the beginning of the movement, the dancer's energy level will be initiated equally to the positive energy value of the choreography, which is $d$. Each time they move from some $y$ to $y+1$, the energy level will be decreased by $1$. At some point, the dancer might meet other fellow dancers in the same coordinates. If it happens, then the energy level of the dancer will be increased by $1$. A dancer will stop moving to the right when his energy level reaches $0$, and he doesn't share a position with another dancer.

The dancers are very well-trained, and each "movement" will end before the next minute begins.

To show her understanding of this choreography, Ela has to answer $q$ queries, each consisting of two integers $k$ and $m$. The answer to this query is the coordinate of the $m$-th dancer of both types from the left at $k$-th minute after the choreography begins. In other words, denote $x_{k, 1}, x_{k, 2}, \dots, x_{k, n}$ as the sorted coordinates of the dancers at $k$-th minute from the beginning, you need to print $x_{k, m}$.

DTL 工程师们热爱周末聚会，Ela 也不例外！但遗憾的是，她还不会跳舞。因此，她决定报名参加一个舞蹈班。

该舞蹈班共有 $n$ 名学生，其中包括 Ela。在期末项目中，这 $n$ 名学生将共同完成一段如下所述的编舞。

$n$ 名学生被安置在 $Ox$ 轴的正半轴上。第 $i$ 位舞者位于坐标 $a_i \gt 0$ 处。在舞蹈过程中，部分舞者会改变位置（我们称其为可移动舞者），其余舞者则在整个编舞过程中保持原位不动（我们称其为不可移动舞者）。我们使用一个长度为 $n$ 的二进制字符串 $s$ 来区分这些舞者：若 $s_i = \text{'1'}$，则第 $i$ 位舞者是可移动的；否则，第 $i$ 位舞者是不可移动的。

我们称该编舞的“正能量值”为 $d \gt 0$。所有舞者将依据该值执行“移动”。

自舞蹈开始后的每一分钟，当前 $x$ 坐标最小的可移动舞者将向右启动一次“移动”。在本次移动开始时，该舞者的能量值被初始化为编舞的正能量值 $d$。每当他从位置 $y$ 移动到 $y+1$ 时，其能量值减少 $1$。在移动过程中，他可能与其他舞者处于同一坐标位置；若发生这种情况，则其能量值增加 $1$。当某位舞者的能量值降至 $0$，且此时他未与任何其他舞者共处同一位置时，他即停止向右移动。

舞者们训练有素，每次“移动”均会在下一分钟开始前结束。

为了展示自己对这段编舞的理解，Ela 需要回答 $q$ 个查询，每个查询包含两个整数 $k$ 和 $m$。该查询的答案为：在编舞开始后第 $k$ 分钟时，所有 $n$ 位舞者（包括可移动与不可移动两类）按坐标从左到右排序后的第 $m$ 个坐标值。换言之，记第 $k$ 分钟时各舞者的坐标按升序排列为 $x_{k, 1}, x_{k, 2}, \dots, x_{k, n}$，你需要输出 $x_{k, m}$。

The first line contains three integers $n$, $d$ and $q$ ($1 \le n \le 10^5$; $1 \le d \le 10^9$; $1 \le q \le 10^5$) — the number of dancers, the positive energy value of the choreography, and the number of queries.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 \lt a_2 \lt \dots \lt a_n \le 10^9$) — the coordinates of each dancer.

The third line contains a binary string $s$ of length $n$ — the movability of each dancer. Each character is either '0' or '1'. It is guaranteed that $s$ contains at least one character '1'.

Then $q$ lines follow, the $i$-th of them contains two integers $k_i$ and $m_i$ ($1 \le k_i \le 10^9$, $1 \le m_i \le n$) — the content of each query.

第一行包含三个整数 $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 \lt a_2 \lt \dots \lt 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$）—— 表示每次查询的内容。

Output $q$ lines, each contains a single integer — the answer for the corresponding query.

输出 $q$ 行，每行包含一个整数——对应查询的答案。

Let's consider the first example test case.

In the first minute, $1$ is the lowest coordinate between movable dancers. The energy level is initiated with $3$. Then the following happens:

• The dancer moves from $1$ to $2$. The energy level decreased to $2$.
• The dancer moves from $2$ to $3$. The energy level decreased to $1$, then increased to $2$ when she met another dancer at $3$.
• The dancer moves from $3$ to $4$. The energy level decreased to $1$.
• The dancer moves from $4$ to $5$. The energy level decreased to $0$.

At the end of the first minute, the sorted coordinates of the dancers become $[3, 5, 6, 7]$, and their respective movability is '0111'.

In the second minute, $5$ is the lowest coordinate between movable dancers. The energy level is initiated with $3$. Then the following happens:

• The dancer moves from $5$ to $6$. The energy level decreased to $2$, then increased to $3$ when she met another dancer at $6$.
• The dancer moves from $6$ to $7$. The energy level decreased to $2$, then increased to $3$ when she met another dancer at $7$.
• The dancer moves from $7$ to $8$. The energy level decreased to $2$.
• The dancer moves from $8$ to $9$. The energy level decreased to $1$.
• The dancer moves from $9$ to $10$. The energy level decreased to $0$.

At the end of the second minute, the sorted coordinates of the dancers become $[3, 6, 7, 10]$, and their respective movability is '0111'.

我们来考虑第一个样例测试用例。

在第一分钟内，$1$ 是所有可移动舞者中坐标最小的一个。此时能量值初始化为 $3$。随后发生如下过程：

• 舞者从 $1$ 移动到 $2$，能量值减少至 $2$。
• 舞者从 $2$ 移动到 $3$，能量值减少至 $1$；当她在 $3$ 处遇到另一位舞者时，能量值增加至 $2$。
• 舞者从 $3$ 移动到 $4$，能量值减少至 $1$。
• 舞者从 $4$ 移动到 $5$，能量值减少至 $0$。

第一分钟结束时，舞者按坐标升序排列为 $[3, 5, 6, 7]$，其对应的可移动性字符串为 '0111'。

在第二分钟内，$5$ 是所有可移动舞者中坐标最小的一个。此时能量值初始化为 $3$。随后发生如下过程：

• 舞者从 $5$ 移动到 $6$，能量值减少至 $2$；当她在 $6$ 处遇到另一位舞者时，能量值增加至 $3$。
• 舞者从 $6$ 移动到 $7$，能量值减少至 $2$；当她在 $7$ 处遇到另一位舞者时，能量值增加至 $3$。
• 舞者从 $7$ 移动到 $8$，能量值减少至 $2$。
• 舞者从 $8$ 移动到 $9$，能量值减少至 $1$。
• 舞者从 $9$ 移动到 $10$，能量值减少至 $0$。

第二分钟结束时，舞者按坐标升序排列为 $[3, 6, 7, 10]$，其对应的可移动性字符串为 '0111'。