Ela Takes Dancing Class
Contest: Dytechlab Cup 2022
Difficulty rating: 3500
Tags: binary search, data structures

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 format:
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 format:
Output $$$q$$$ lines, each contains a single integer — the answer for the corresponding query.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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

Example 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

Example output:
3
5
6
7
3
6
7
10

Example input:
1 1 5
2
1
1 1
2 1
3 1
4 1
5 1

Example output:
3
4
5
6
7

Editorial:
Note that the immovable dancers don't change their positions during transformations.
Let's pretend that all immovable dancers disappeared. We denote an arrangement as "good" if the dancer in the first step jump over any other dancers (the new placement of the first dancer is greater than the position of any other dancers).
Denote $$$C$$$ as the number of dancers in the arrangement. A "good" dancer arrangement retains some properties:
• After $$$C$$$ operations, the relative coordinates of dancers are untouched, and the absolute coordinates of dancers are increased by $$$(C - 1 + d)$$$. Proof: by intuition. Dancer $$$1$$$'s position is increased by $$$C - 1 + d$$$ since it goes over $$$C - 1$$$ dancers and jumps to the following $$$d$$$-th space. Dancer $$$2$$$ must jump across dancer $$$1$$$ (there aren't enough empty spaces between them), and its position will be increased by the same amount. The description is the same for others.
• After $$$i$$$ operations ($$$i < C$$$), the absolute coordinates of the leftmost $$$i$$$ dancers increased by $$$C - 1 + d$$$.
• Repeatedly increase the current arrangement by several $$$C - 1 + d$$$ until dancer $$$1$$$ can go over dancer $$$i$$$.
• Increase the coordinate of all the arranged dancers that lie after dancer $$$i$$$ by $$$1$$$.
• Push the dancer into the maintained arrangement.
Let's binary search each query. We can safely remove all immovable dancers and the remaining dancers that haven't been observed, and appropriately adjust the query segment. In order to maintain the "good" arrangement, we may use any balanced binary search tree (treap for example).
The final complexity is $$$O((n + q) \log^2 n)$$$.