화성

최근 화성에서 새로운 생명체를 발견했다. 화성 생명체의 DNA는 네 글자가 아니라 두 글자만 쓰는 문자열이므로, 이진 문자열로 나타낼 수 있다.

길이가 $n$인 생명체의 DNA를 $s$라고 하자. 이 DNA에는 유전자로 지정된 구간이 $q$개 있다. 구간 $[a, b]$에 있는 유전자는 DNA의 $a$번째 문자부터 $b$번째 문자까지를 포함하는 부분 문자열이다 ($1 \le a \le b \le n$). 두 유전자는 서로 겹칠 수도 있고, 한 유전자가 다른 유전자 안에 들어 있을 수도 있다.

화성 생명체가 살아가는 동안 각 유전자는 수십억 번 복제된다. 단백질이 유전자의 앞쪽에 붙어서 앞에서 뒤로 복제하는데, 이 과정이 완전하지는 않아서 돌연변이가 생기기도 한다. 돌연변이 한 번은 유전자의 0을 1로, 또는 1을 0으로 복제한다. 돌연변이가 일어난 복제본은 원래 유전자와 일치하지 않지만, DNA의 다른 위치에 있는 부분 문자열과 일치할 수는 있다. 이때 그 부분 문자열이 원래 유전자와 겹쳐도 된다.

예를 들어 $s$가 001011111이고 유전자가 $[3, 6]$에 있다고 하자. 유전자 문자열은 1011이다. 두 번째 글자에 돌연변이가 일어난 복제본 1111은 $[3, 6]$의 부분 문자열과 일치하지 않지만 $[5, 8]$의 부분 문자열과 일치한다. 복제본이 DNA 전체의 어느 위치에도 나타나지 않으면 그 복제본을 퇴화 복제본이라고 한다. 네 번째 글자에 돌연변이가 일어난 복제본 1010은 퇴화 복제본이지만, 1111은 퇴화 복제본이 아니다.

각 유전자마다 퇴화 복제본을 만드는 돌연변이의 최소 개수를 구하라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 $n$과 $q$가 주어진다 ($2 \le n \le 10000$, $1 \le q \le 1000$). 다음 줄에는 길이가 $n$인 이진 문자열 $s$가 주어진다. 이어지는 $q$개 줄에는 유전자의 위치 $[a, b]$가 공백으로 구분된 두 정수 $a$와 $b$로 주어진다 ($1 \le a \le b \le n$). 입력의 마지막 줄에는 0 0이 주어지며, 이 줄은 처리하지 않는다.

각 유전자마다 퇴화 복제본을 만드는 돌연변이의 최소 개수를 출력한다. 그 유전자에 어떤 돌연변이를 적용해도 퇴화 복제본을 만들 수 없으면 Impossible을 출력한다.