두 단어

마르친(Marcin)은 이제 막 단어를 배우기 시작한 나이입니다. 신기하게도 지금까지 배운 단어들은 모두 길이가 같습니다. 만약 길이가 서로 다른 단어들을 알았다면 형과 누나에게서 들은 여러 놀이를 즐길 수 있었겠지만, 지금 할 수 있는 것은 오직 글자를 바꿔 넣는 놀이뿐입니다.

놀이 방법은 이렇습니다. 마르친은 먼저 두 단어를 적어 둡니다. 그런 다음 두 단어에서 각각 글자를 하나씩 골라 서로 자리를 바꿉니다. 자리를 바꾼 뒤에는 두 단어 중 어느 쪽이 사전순으로 더 뒤에 오는지 엄마에게 물어봅니다. 엄마는 언제나 정확하게 답해 주고, 마르친은 이렇게 바뀐 단어로 놀이를 계속 이어 갑니다. 한 번 이루어진 교환은 그대로 유지되므로, 다음 질문은 언제나 지금 상태의 두 단어를 대상으로 합니다.

요즘 엄마가 무척 바쁘니, 대신 여러분이 마르친을 도와 질문에 답해 주세요.

첫째 줄에 단어의 길이를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어진다.

다음 두 줄에는 각각 길이가 $n$인 단어가 하나씩 주어지며, 두 단어 모두 영어 소문자로만 이루어져 있다. 단어 안의 글자 위치는 $0$부터 $n-1$까지 번호가 매겨진다.

그다음 줄에는 질문의 개수를 나타내는 정수 $t$ ($1 \le t \le 10^5$)가 주어진다.

이어지는 $t$개의 줄에는 각각 두 정수 $a_i$와 $b_i$ ($0 \le a_i, b_i \le n-1$)가 주어진다. 이는 $i$번째 질문 직전에 마르친이 첫 번째 단어의 $a_i$번 위치에 있는 글자와 두 번째 단어의 $b_i$번 위치에 있는 글자를 서로 바꾸었음을 뜻한다. 교환은 누적되어 이후의 질문에도 계속 반영된다.

표준 출력에 정확히 $t$개의 줄을 출력한다. 각 줄에는 해당 교환을 마친 뒤 마르친의 질문에 대한 답을 출력한다. 두 단어가 같으면 0을, 사전순으로 첫 번째 단어가 더 뒤에 오면 1을, 두 번째 단어가 더 뒤에 오면 2를 출력한다.

예시 설명: 첫 번째 교환 뒤 첫 번째 단어는 aabb, 두 번째 단어는 aaaa가 되므로 사전순으로 첫 번째 단어가 더 뒤에 온다. 두 번째 교환 뒤에는 두 단어가 모두 aaba가 되어 서로 같아진다.