# [Solution] Ela Takes Dancing Class solution codeforces

Ela Takes Dancing Class solution codeforces – 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.

## [Solution] Ela Takes Dancing Class solution codeforces

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 𝑎𝑖>0ai>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 𝑠𝑖si 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 𝑑>0d>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 𝑦+1y+1, the energy level will be decreased by 11. 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 11. A dancer will stop moving to the right when his energy level reaches 00, 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.

## [Solution] Ela Takes Dancing Class solution codeforces

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 𝑥𝑘,1,𝑥𝑘,2,,𝑥𝑘,𝑛xk,1,xk,2,…,xk,n as the sorted coordinates of the dancers at 𝑘k-th minute from the beginning, you need to print 𝑥𝑘,𝑚xk,m.

Input

The first line contains three integers 𝑛n𝑑d and 𝑞q (1𝑛1051≤n≤1051𝑑1091≤d≤1091𝑞1051≤q≤105) — the number of dancers, the positive energy value of the choreography, and the number of queries.

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎1<𝑎2<<𝑎𝑛1091≤a1<a2<⋯<an≤109) — 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 𝑘𝑖ki and 𝑚𝑖mi (1𝑘𝑖1091≤ki≤1091𝑚𝑖𝑛1≤mi≤n) — the content of each query.

## [Solution] Ela Takes Dancing Class solution codeforces

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

Examples

input

Copy
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

Copy
3
5
6
7
3
6
7
10


input

Copy
1 1 5
2
1
1 1
2 1
3 1
4 1
5 1


output

Copy
3
4
5
6
7


## [Solution] Ela Takes Dancing Class solution codeforces

Let’s consider the first example test case.

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

• The dancer moves from 11 to 22. The energy level decreased to 22.
• The dancer moves from 22 to 33. The energy level decreased to 11, then increased to 22 when she met another dancer at 33.
• The dancer moves from 33 to 44. The energy level decreased to 11.
• The dancer moves from 44 to 55. The energy level decreased to 00.

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

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

• The dancer moves from 55 to 66. The energy level decreased to 22, then increased to 33 when she met another dancer at 66.
• The dancer moves from 66 to 77. The energy level decreased to 22, then increased to 33 when she met another dancer at 77.
• The dancer moves from 77 to 88. The energy level decreased to 22.
• The dancer moves from 88 to 99. The energy level decreased to 11.
• The dancer moves from 99 to 1010. The energy level decreased to 00.

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