G. Ela Takes Dancing Class
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Examples
Input
4 3 8
1 3 6 7
1011
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
Output
3
5
6
7
3
6
7
10
Input
1 1 5
2
1
1 1
2 1
3 1
4 1
5 1
Output
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'.