Mars

A new form of life was found on Mars. Every alien has a DNA that uses an alphabet of two letters instead of four, so the DNA of a Mars alien is written as a binary string.

Let $s$ be an alien DNA of length $n$. The DNA has $q$ marked regions called genes. The gene at $[a, b]$ is the substring of the DNA that runs from position $a$ to position $b$, both included ($1 \le a \le b \le n$). Genes may overlap, and one gene may sit inside another.

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 it from start to end. This process is not error free and may produce mutations. In one mutation a 0 in the gene is copied as 1, or a 1 in the gene is copied as 0. A mutated copy no longer matches the gene, but it may still match a substring at another position of the DNA, and that substring may overlap the gene.

For example, let $s$ be 001011111 with a gene at $[3, 6]$, so the gene string is 1011. One copy of this gene is 1111, mutated at the second letter. That copy does not match the substring at $[3, 6]$, but it matches the substring at $[5, 8]$. A mutated copy is called degenerate if it occurs at no position of the whole DNA. The copy 1010, which mutates the fourth letter, is degenerate, but 1111 is not.

For each gene, find the smallest number of mutations that can produce a degenerate copy of that gene.

The input has several test cases. The first line of a test case has two integers $n$ and $q$ ($2 \le n \le 10000$, $1 \le q \le 1000$). The next line has a binary string $s$ of length $n$. Each of the next $q$ lines has the location $[a, b]$ of one gene as two space separated integers $a$ and $b$ ($1 \le a \le b \le n$). The input ends with a line holding 0 0, which you do not process.

For each gene, print the smallest number of mutations that can produce a degenerate copy. If no set of mutations applied to that gene can produce a degenerate copy, print Impossible instead.