Volcano is playing a game called "Legend of Iron-Beating," which involves two sides: the attacker and the defender. The attacker has two types of minions: Poisonous Fish and Small Fish. The defender has two types of minions: Divine Shield Fish and Big Fish. When two minions battle, the following rules apply:

1. After a Divine Shield Fish battles any fish, it becomes a Big Fish.
2. A Big Fish disappears after battling a Poisonous Fish, but does not disappear after battling a Small Fish (because the Big Fish is truly big!).

You are the attacker and you have $n$ minions. The game proceeds as follows: there are a total of $K$ attacks. In the $i$-th attack, you designate your $i$-th minion to battle any one of the opponent's remaining minions (if the opponent has no minions left, you may choose not to battle).

You are given your $n$ minions in order. For each query $(X, K)$, you need to answer: if the game consists of $K$ attacks and the opponent has $X$ Big Fish, what is the maximum number of Divine Shield Fish the opponent can have such that you can eliminate all of their fish? In other words, find the maximum $Y$ such that if the opponent has $X$ Big Fish and $Y$ Divine Shield Fish, you can eliminate all of them.

Input

The first line contains two positive integers $n$ and $Q$, representing the number of your minions and the number of queries.

The second line contains a binary string of length $n$. The $i$-th character is '1' if your $i$-th minion is a Poisonous Fish, and '0' if it is a Small Fish.

The next $Q$ lines each contain two integers $X$ and $K$, representing a query.

Output

For each query, output a single integer representing the maximum value of $Y$. If you cannot eliminate all of the opponent's fish even when they only have $X$ Big Fish, output $-1$.

Examples

Input 1

6 5
110110
0 6
0 3
1 6
2 6
3 6

Output 1

2
1
2
1
1