## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Ela Takes Dancing Class Codeforces Solution

G. Ela Takes Dancing Class
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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.

Solution Click Below:-  👉
👇👇👇👇👇

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}<\cdots <{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.