Description

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 > 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 > 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}$.

Input

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 < a_2 < \dots < 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.

Output

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

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 1 5
2
1
1 1
2 1
3 1
4 1
5 1

3
5
6
7
3
6
7
10

3
4
5
6
7

Note

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'.