선형화

두 음이 아닌 정수의 비트 단위 and는 다음과 같이 계산한다. 두 수를 이진법으로 쓰면, 결과의 $i$번째 이진 자릿수는 두 인수의 $i$번째 자릿수가 모두 $1$일 때 $1$이다. 예를 들어 $(14 \text{ and } 7) = (1110\_2 \text{ and } 0111\_2) = 110\_2 = 6$이다.

두 이진 자릿수의 배타적 논리합(xor)은 두 자릿수가 다르면 $1$, 같으면 $0$이다. 따라서 $0 \text{ xor } 0 = 0$, $0 \text{ xor } 1 = 1$, $1 \text{ xor } 0 = 1$, $1 \text{ xor } 1 = 0$이다.

음이 아닌 정수 $x$에 대한 패리티 함수 $P(x)$는 $x$의 이진 표현에서 $1$의 개수가 홀수이면 $1$, 짝수이면 $0$이다. 예를 들어 $P(5) = P(101\_2) = 0$, $P(7) = P(111\_2) = 1$이다.

길이가 2의 거듭제곱인 이진 문자열 $s = s\_0s\_1\ldots s\_{n-1}$을 생각하자. 여기서 $n = 2^k$이다. $0 \le x < n$인 정수 $x$와 이진 자릿수 $b$가 존재하여 모든 $i$($0$부터 $n-1$까지)에 대해 $s\_i = P(i \text{ and } x) \text{ xor } b$가 성립하면 이 문자열을 선형이라 한다.

예를 들어 문자열 "1100"은 선형이다. $x = 2 = 10\_2$, $b = 1$을 택하면 된다.

• $s\_0 = P(0 \text{ and } 2) \text{ xor } 1 = P(0) \text{ xor } 1 = 0 \text{ xor } 1 = 1$
• $s\_1 = P(1 \text{ and } 2) \text{ xor } 1 = P(0) \text{ xor } 1 = 0 \text{ xor } 1 = 1$
• $s\_2 = P(2 \text{ and } 2) \text{ xor } 1 = P(2) \text{ xor } 1 = 1 \text{ xor } 1 = 0$
• $s\_3 = P(3 \text{ and } 2) \text{ xor } 1 = P(2) \text{ xor } 1 = 1 \text{ xor } 1 = 0$

한편 "0001"은 선형이 아니다. 어떤 $x$를 택하더라도 $P(0 \text{ and } x) = P(0) = 0$이므로 $b = 0$이다. $0 = P(1 \text{ and } x)$이고 $0 = P(2 \text{ and } x)$이므로 $x = 0$이다. 그런데 $P(3 \text{ and } 0) = 0 \ne s\_3 = 1$이다.

이진 문자열을 생각하자. 한 번의 행동으로 연속한 자릿수 구간을 택해 뒤집을 수 있다. 즉 모든 0을 1로, 1을 0으로 바꾼다. 이 문자열의 선형화 난이도를 선형으로 만들기 위해 필요한 최소 행동 횟수라 하자.

예를 들어 문자열 "0001"의 선형화 난이도는 $1$이다. 왼쪽 세 자릿수를 뒤집어 문자열 "1111"을 얻으면 $x = 0$, $b = 1$로 선형이다. 한 번의 행동으로 선형화하는 다른 방법도 있다.

문자열 $t$와 $q$개의 질의 $(l\_i, r\_i)$가 주어진다. 각 질의에서 $t$의 $l\_i$번째 자릿수부터 $r\_i$번째 자릿수까지(양 끝 포함)의 부분 문자열을 생각한다. $t$의 자릿수는 왼쪽부터 $0$부터 시작하여 번호를 매긴다. 각 질의의 길이는 2의 거듭제곱임이 보장된다. 주어진 모든 부분 문자열의 선형화 난이도를 계산하라.

첫째 줄에 문자열 $t$의 길이 $m$이 주어진다($1 \le m \le 200\,000$). 둘째 줄에 길이 $m$의 이진 문자열 $t$가 주어진다.

다음 줄에 질의의 수 $q$가 주어진다($1 \le q \le 200\,000$). 다음 $q$개 줄에 두 정수 $l\_i$, $r\_i$가 주어진다($0 \le l\_i \le r\_i < m$, $r\_i - l\_i + 1 \ge 2$, 부분 문자열의 길이는 2의 거듭제곱).

각 질의마다 $t$의 해당 부분 문자열의 선형화 난이도를 한 줄에 하나씩 출력한다.

첫 번째 질의에서는 전체 문자열을 선형화해야 한다. 예를 들어 $4$번째부터 $6$번째 자릿수까지의 구간을 뒤집어 문자열 "00001011"을 얻고, 이어서 $5$번째 자릿수를 뒤집어 "00001111"을 얻으면 $x = 4$, $b = 0$으로 선형이다.

두 번째 질의에서 문자열 "0001"은 문제 설명에서처럼 한 번의 행동으로 선형화할 수 있다.

세 번째 질의에서 문자열 "0000"은 $x = 0$, $b = 0$으로 이미 선형이다.