시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB0000.000%

문제

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 ⩽ a ⩽ b ⩽ 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 ≤ n ≤ 10, 000 and 1 ≤ q ≤ 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 ≤ a ≤ b ≤ 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.

예제 입력 1

4 3
0110
1 2
2 3
1 1
0 0

예제 출력 1

1
2
Impossible