[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 𝑎𝑖>0$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 𝑑>0$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 𝑦+1$y+1$, the energy level will be decreased by 1$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$1$. A dancer will stop moving to the right when his energy level reaches 0$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:-  👉CLICK HERE👈

👇👇👇👇👇

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,…,𝑥𝑘,𝑛$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≤𝑛≤105$1\le n\le {10}^5$; 1≤𝑑≤109$1\le d\le {10}^9$; 1≤𝑞≤105$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 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎1<𝑎2<⋯<𝑎𝑛≤109$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≤𝑘𝑖≤109$1\le k_i\le {10}^9$, 1≤𝑚𝑖≤𝑛$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.