• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت

A new form of life is recently discovered on Mars. Every alien has a DNA, that is a string with an alphabet of only two, rather than four, letters. Hence we can show the DNA of a Mars alien by a binary string. Let s be an alien DNA of length $n$. There are $q$ regions in the DNA specified as genes. A gene located at $[a, b]$ is a substring of the DNA, containing characters from position a to position $b$, inclusive ($1 \leq a \leq b \leq n$). A gene might overlap with or be inside the other genes.

During the life of a Mars alien, each gene is copied billions of times: a protein binds to the start of the gene, and copies the gene from start to the end. But this process is not error-free, and might produce mutations. In each mutation, a 0 in the gene is copied as 1, or vice-versa. A mutated copy does not match the gene, but might match a (possibly overlapping) substring in another position of the DNA. For instance, assume that $s = 001011111$ and a gene is located at $[3, 6]$. Hence, the gene string is $1011$. A copy of this gene can be $1111$, which is mutated at the second letter. Although $1111$ does not match the original $[3, 6]$ substring in the DNA, it matches $[5, 8]$. A mutated copy of a gene is called degenerate if it does not appear in any place of the whole DNA. Hence, $1010$, a copy of the same gene having one mutation at the fourth letter, is degenerate, but $1111$ is not.

Your task is to find, for each gene, the minimum number of mutations that can result in a degenerate copy of that gene

ورودی

There are multiple test cases in the input. The first line of each test case contains two integers $n$ and $q$ ($2 \leq n \leq 10, 000$ and $1 \leq q \leq 1000$). The next line contains a binary string $s$ of length $n$. Each of the next $q$ lines contains the location $[a, b]$ of a gene, in the form of two space-separated integers $a$ and $b$ ($1 \leq a \leq b \leq n$). The input terminates with a line containing 0 0 that should not be processed.

خروجی

For each gene, print the minimum number of mutations that can result in a degenerate copy. If no set of mutations applied on a gene can result in a degenerate copy, print Impossible instead.

مثال

ورودی نمونه ۱

4 3
0110
1 2
2 3
1 1
0 0

خروجی نمونه ۱

1
2
Impossible