M. Nightmare
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

"The story remains unfinished...""Wait a minute, haven't we already escaped from the Duskbreaker??"

It had been a long time since they escaped from that simulated world. One day, Tsuki awakened her consciousness within Saturday's inner world, only to see a familiar yet strange scene before her—a glitchy transition, followed by several locks appearing in front of her. Just like when she broke through LOCK C long ago, these locks described a puzzle, and she needed to find the answer to unlock them. And if she succeeded... perhaps she could escape this nightmare.

The puzzle was as follows:

There is a chain with $$$n$$$ nodes, labeled from $$$1$$$ to $$$n$$$. There are $$$n-1$$$ edges connecting these $$$n$$$ nodes, where the $$$i$$$-th edge connects node $$$i$$$ and node $$$i+1$$$. Each point has a weight $$$w_i$$$ and a color $$$c_i$$$, where $$$c_i$$$ can only be either black or white.

Starting from the $$$1$$$st moment, the chain undergoes color changes at each time step. Specifically, we examine every maximal monochromatic connected component on the chain. If a connected component has an adjacent heavier connected component of the opposite color, then all nodes in this connected component will flip their color (black becomes white, and white becomes black). Note that all connected components flip their colors simultaneously.

A connected component $$$S$$$ is considered heavier than another connected component $$$T$$$ if and only if the total weight of all nodes in $$$S$$$ is greater than that of $$$T$$$, or if their weights are equal and the smallest-numbered node in $$$S$$$ has a smaller index than the smallest-numbered node in $$$T$$$.

Beside the puzzle, there were $$$q$$$ markers indicating how to extract information from this process as the solution. The $$$i$$$-th marker was a pair of positive integers $$$(t_i,x_i)$$$, representing the color (black or white) of the $$$x_i$$$-th node at the $$$t_i$$$-th moment as the answer.

Tsuki, being not very skilled at solving puzzles, asked for your help to determine the answers corresponding to these $$$q$$$ markers so she could crack the puzzle and escape this nightmare.

Input

The first line contains a positive integer $$$n$$$, representing the number of nodes. It is guaranteed that $$$1\le n\le2\times10^5$$$.

The second line contains a binary string of length $$$n$$$, where the $$$i$$$-th character represents $$$c_i$$$ ($$$0$$$ for black, $$$1$$$ for white).

The third line contains $$$n$$$ positive integers, where the $$$i$$$-th integer represents $$$w_i$$$. It is guaranteed that $$$1\le w_i\le10^9$$$.

The fourth line contains a positive integer $$$q$$$, representing the number of markers. It is guaranteed that $$$1\le q\le2\times10^5$$$.

The following $$$q$$$ lines each contain two positive integers, representing $$$t_i,x_i$$$. It is guaranteed that $$$1\le t_i\le10^9$$$ and $$$1\le x_i\le n$$$.

Output

Output a string of length $$$q$$$ where the $$$i$$$-th character represents the answer to the $$$i$$$-th marker ($$$0$$$ for black, $$$1$$$ for white) in a single line.

Examples
Input
5
01010
5 4 1 6 1
5
1 1
1 2
1 4
2 2
2 3
Output
00100
Input
9
000110101
1 6 7 3 1 3 1 6 2
4
2 9
1 9
3 3
3 4
Output
0000
Input
2
11
1 2
4
1 1
1 2
2 1
755908319 2
Output
1111