Read problems statements [Hindi] ,[Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

Alice and Bob are playing a game with a $(N+1)\times (M+1)$ table. Let's denote the cell in the $i$-th row and $j$-th column ($0 ≤ i ≤ N$, $0 ≤ j ≤ M$) by $(i, j)$. The rules of the game are:
At the beginning, a stone is placed in some cell of the table.
The players alternate turns, Alice goes first. 
In each turn, the current player must move the stone from its current cell (let's denote it by $(x, y)$) to the cell $(x-1, y)$ or to the cell $(x, y-1)$.
As soon as the stone is placed in a cell $(x, y)$ with $x=0$ or $y=0$, the game ends.
The winner of the game is determined by the cell the stone ended up in and the player who moved it there; you are given this information for all possible terminal cells on the input. (Note that the stone never reaches the cell $(0, 0)$.)

You should answer $Q$ queries. In each query, you are given the initial position $(x, y)$ of the stone, and you should determine the winner of the game.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single string with length $M$. For each $i$ ($1 ≤ i ≤ M$), the $i$-th digit of this string is '1' if the player that moves the stone to the cell $(0, i)$ loses the game or '0' if this player wins.
The second line contains a single string with length $N$. For each $i$ ($1 ≤ i ≤ N$), the $i$-th digit of this string is '1' if the player that moves the stone to the cell $(i, 0)$ loses the game or '0' if this player wins.
The third line contains a single integer $Q$ denoting the number of queries.
Each of the following $Q$ lines contains two space-separated integers $x$ and $y$ describing one query.

------  Output ------
For each test case, print a single line containing a string with length $Q$. For each valid $i$, the $i$-th digit should be '1' if Alice wins the game for query $i$ or '0' if Bob wins that game.

------  Constraints  ------
$1 ≤ N, M, Q ≤ 10^{5}$
$1 ≤ x ≤ N$
$1 ≤ y ≤ M$
the sum of $N+M+Q$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (30 points): the sum of $N+M$ over all test cases does not exceed $10^{3}$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1

101

01

6

1 1

1 2

1 3

2 1

2 2

2 3
----- Sample Output 1 ------ 
110011

Difficulty: HARD
Tags: Preprocessing

Data structures

Game theory

String algorithms
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	r = input()
	c = input()
	m = len(r) + 1
	n = len(c) + 1
	a = {}
	if r[0] == '0' or c[0] == '0':
		a[1 * 1000000 + 1] = '1'
	else:
		a[1 * 1000000 + 1] = '0'
	for i in range(2, m):
		if r[i - 1] == '0' or a[1 * 1000000 + i - 1] == '0':
			a[1 * 1000000 + i] = '1'
		else:
			a[1 * 1000000 + i] = '0'
	for i in range(2, n):
		if c[i - 1] == '0' or a[(i - 1) * 1000000 + 1] == '0':
			a[i * 1000000 + 1] = '1'
		else:
			a[i * 1000000 + 1] = '0'
	for i in range(2, min(n, 5)):
		for j in range(2, m):
			if a[(i - 1) * 1000000 + j] == '0' or a[i * 1000000 + j - 1] == '0':
				a[i * 1000000 + j] = '1'
			else:
				a[i * 1000000 + j] = '0'
	for i in range(2, n):
		for j in range(2, min(m, 5)):
			if a[(i - 1) * 1000000 + j] == '0' or a[i * 1000000 + j - 1] == '0':
				a[i * 1000000 + j] = '1'
			else:
				a[i * 1000000 + j] = '0'
	q = int(input())
	s = ''
	for i in range(q):
		(x, y) = map(int, input().split())
		if x < 5 or y < 5:
			s = s + a[x * 1000000 + y]
		elif x == y:
			s = s + a[4 * 1000000 + 4]
		elif x > y:
			s = s + a[(x - (y - 4)) * 1000000 + 4]
		else:
			s = s + a[4 * 1000000 + y - (x - 4)]
	print(s)


t = int(input())
from sys import stdin, stdout
for _ in range(t):
	dd = []
	r = list(map(int, list(input().strip())))
	c = list(map(int, list(input().strip())))
	for i in range(len(c)):
		if i <= 1:
			t = c[i]
			r[0] = int(not (r[0] and t))
			for j in range(1, len(r)):
				r[j] = int(not (r[j - 1] and r[j]))
			dd.append(list(r))
		else:
			r = r[:2]
			t = c[i]
			r[0] = int(not (r[0] and t))
			for j in range(1, 2):
				r[j] = int(not (r[j - 1] and r[j]))
			dd.append(list(r))
	q = int(input())
	for _ in range(q):
		(u, v) = map(int, stdin.readline().strip().split(' '))
		if u <= 2 or v <= 2:
			stdout.write(str(dd[u - 1][v - 1]))
		elif u == v:
			stdout.write(str(dd[1][1]))
		else:
			stdout.write(str(dd[u - (min(u, v) - 2) - 1][v - (min(u, v) - 2) - 1]))
	print()


for t in range(int(input())):
	top = list(map(int, list(input().strip())))
	left = list(map(int, list(input().strip())))
	row0 = [not top[0] or not left[0]]
	for i in range(1, len(top)):
		row0.append(not top[i] or not row0[-1])
	if len(left) > 1:
		row1 = [not row0[0] or not left[1]]
		for i in range(1, len(top)):
			row1.append(not row0[i] or not row1[-1])
	col0 = [not left[0] or not top[0]]
	for i in range(1, len(left)):
		col0.append(not left[i] or not col0[-1])
	if len(top) > 1:
		col1 = [not col0[0] or not top[1]]
		for i in range(1, len(left)):
			col1.append(not col0[i] or not col1[-1])
	ans = []
	for q in range(int(input())):
		(x, y) = map(int, input().split())
		(x, y) = (x - 1, y - 1)
		if x == 0:
			res = row0[y]
		elif y == 0:
			res = col0[x]
		elif x <= y:
			res = row1[y - (x - 1)]
		else:
			res = col1[x - (y - 1)]
		ans.append(int(res))
	print(*ans, sep='')


import sys
for _ in range(int(input())):
	m = input()
	n = input()
	a = [[None] * min(len(n), 3) for _ in range(len(m))]
	b = [[None] * len(n) for _ in range(min(len(m), 3))]
	s = set()
	a[0][0] = b[0][0] = m[0] == '0' or n[0] == '0'
	if not a[0][0]:
		s.add(0)
	for i in range(1, len(m)):
		a[i][0] = m[i] == '0' or not a[i - 1][0]
		if not a[i][0]:
			s.add(i)
	for i in range(1, min(len(n), 3)):
		a[0][i] = n[i] == '0' or not a[0][i - 1]
		if not a[0][i]:
			s.add(-i)
	for i in range(1, len(m)):
		for j in range(1, min(len(n), 3)):
			a[i][j] = not a[i - 1][j] or not a[i][j - 1]
			if not a[i][j]:
				s.add(i - j)
	for i in range(1, len(n)):
		b[0][i] = n[i] == '0' or not b[0][i - 1]
		if not b[0][i]:
			s.add(-i)
	for i in range(1, min(len(m), 3)):
		b[i][0] = m[i] == '0' or not b[i - 1][0]
		if not b[i][0]:
			s.add(i)
	for i in range(1, min(len(m), 3)):
		for j in range(1, len(n)):
			b[i][j] = not b[i - 1][j] or not b[i][j - 1]
			if not b[i][j]:
				s.add(i - j)
	for _ in range(int(input())):
		(x, y) = map(int, input().split())
		if x <= min(len(n), 3):
			v = '1' if a[y - 1][x - 1] else '0'
		elif y <= min(len(m), 3):
			v = '1' if b[y - 1][x - 1] else '0'
		else:
			v = '0' if y - x in s else '1'
		sys.stdout.write(v)
	print('')


for _ in range(int(input())):
	c = input()
	r = input()
	a = []
	b = []
	x = []
	d = []
	op = ''
	if r[0] == '0' or c[0] == '0':
		a.append('1')
	elif r[0] == '1' and c[0] == '1':
		a.append('0')
	for i in range(1, len(c)):
		if c[i] == '0':
			a.append('1')
		elif c[i] == '1' and a[i - 1] == '1':
			a.append('0')
		elif c[i] == '1' and a[i - 1] == '0':
			a.append('1')
	x.append(a[0])
	for i in range(1, len(r)):
		if r[i] == '0':
			x.append('1')
		elif r[i] == '1' and x[i - 1] == '1':
			x.append('0')
		elif r[i] == '1' and x[i - 1] == '0':
			x.append('1')
	if len(r) > 1:
		for i in range(0, len(a)):
			if i == 0:
				b.append(x[1])
			elif a[i] == b[i - 1] == '1':
				b.append('0')
			else:
				b.append('1')
	if len(c) > 1:
		for i in range(0, len(r)):
			if i == 0:
				d.append(a[1])
			elif x[i] == d[i - 1] == '1':
				d.append('0')
			else:
				d.append('1')
	q = int(input())
	for _ in range(q):
		(p, t) = [int(i) for i in input().split()]
		if p == 1 and t != 1:
			op += a[t - 1]
		elif p == t == 1:
			op += a[0]
		elif t == 1 and p != 1:
			op += x[p - 1]
		elif p == 2:
			op += b[t - 1]
		elif t == 2 and p != 2:
			op += d[p - 1]
		elif t > 2 and p > 2:
			if p > t:
				diff = t - 2
				ans = p - diff
				op += d[ans - 1]
			elif p < t:
				diff = p - 2
				ans = t - diff
				op += b[ans - 1]
			else:
				op += b[1]
	print(op)


def special(m, n):
	if m == '0' or n == '0':
		return '1'
	return '0'
for j in range(int(input())):
	m = input()
	n = input()
	solm = special(m[0], n[0])
	soln = special(m[0], n[0])
	for i in range(1, len(m)):
		solm += special(solm[i - 1], m[i])
	for i in range(1, len(n)):
		soln += special(soln[i - 1], n[i])
	if len(m) > 1 and len(n) > 1:
		solm_next = special(solm[1], soln[1])
		soln_next = special(solm[1], soln[1])
		for i in range(1, len(m) - 1):
			solm_next += special(solm_next[i - 1], solm[i + 1])
		for i in range(1, len(n) - 1):
			soln_next += special(soln_next[i - 1], soln[i + 1])
	q = ''
	for qweqw in range(int(input())):
		(x, y) = map(int, input().split())
		if x == 1:
			q += solm[y - 1]
		elif y == 1:
			q += soln[x - 1]
		elif x == y:
			q += solm_next[0]
		elif x > y:
			q += soln_next[x - y]
		elif y > x:
			q += solm_next[y - x]
	print(q)


def solve():
	for _ in range(int(input())):
		top = input()
		left = input()
		table = [['W' for i in range(len(top) + 1)] for j in range(4)]
		table_left = [['W' for i in range(len(left) + 1)] for j in range(4)]
		for i in range(len(left)):
			if left[i] == '1':
				table_left[0][i + 1] = 'L'
		for i in range(len(top)):
			if top[i] == '1':
				table[0][i + 1] = 'L'
				if i < min(3, len(left)):
					table_left[i + 1][0] = 'L'
		for i in range(1, min(4, len(left) + 1)):
			for j in range(1, len(top) + 1):
				if j == 1:
					if table[i - 1][j] == 'L' and left[i - 1] == '1':
						table[i][j] = '0'
						continue
					if left[i - 1] == '0' or table[i - 1][j] == 'W':
						table[i][j] = '1'
						continue
					if table[i - 1][j] == 'L' and left[i - 1] == '1':
						table[i][j] = '0'
						continue
					if left[i - 1] == '1':
						table[i][j] = '0' if table[i - 1][j] == '1' else '1'
						continue
					if table[i - 1][j] == 'L':
						table[i][j] = '0' if left[i - 1] == '1' else '1'
						continue
				if table[i - 1][j] == 'L' and table[i][j - 1] == 'L':
					table[i][j] = '0'
					continue
				if table[i][j - 1] == '1' and table[i - 1][j] == '1':
					table[i][j] = '0'
					continue
				if table[i][j - 1] == 'W' or table[i - 1][j] == 'W':
					table[i][j] = '1'
					continue
				if table[i][j - 1] == '0' or table[i - 1][j] == '0':
					table[i][j] = '1'
					continue
				if table[i][j - 1] == 'L':
					table[i][j] = '0' if table[i - 1][j] == '1' else '1'
					continue
				if table[i - 1][j] == 'L':
					table[i][j] = '0' if table[i][j - 1] == '1' else '1'
					continue
				if left[i - 1] == '0' or table[i - 1][j] == 'W':
					table[i][j] = '1'
					continue
		for i in range(1, min(4, len(top) + 1)):
			for j in range(1, len(left) + 1):
				if j == 1:
					if table_left[i - 1][j] == 'L' and top[i - 1] == '1':
						table_left[i][j] = '0'
						continue
					if top[i - 1] == '0' or table_left[i - 1][j] == 'W':
						table_left[i][j] = '1'
						continue
					if table_left[i - 1][j] == 'L' and top[i - 1] == '1':
						table_left[i][j] = '0'
						continue
					if i == 1 and left[i - 1] == '1':
						table_left[i][j] = '0' if table_left[i - 1][j] == '1' else '1'
						continue
					if table_left[i - 1][j] == 'L':
						table_left[i][j] = '0' if left[i - 1] == '1' else '1'
						continue
				if table_left[i - 1][j] == 'L' and table_left[i][j - 1] == 'L':
					table_left[i][j] = '0'
					continue
				if table_left[i][j - 1] == '1' and table_left[i - 1][j] == '1':
					table_left[i][j] = '0'
					continue
				if table_left[i][j - 1] == 'W' or table_left[i - 1][j] == 'W':
					table_left[i][j] = '1'
					continue
				if table_left[i][j - 1] == '0' or table_left[i - 1][j] == '0':
					table_left[i][j] = '1'
					continue
				if table_left[i][j - 1] == 'L':
					table_left[i][j] = '0' if table_left[i - 1][j] == '1' else '1'
					continue
				if table_left[i - 1][j] == 'L':
					table_left[i][j] = '0' if table_left[i][j - 1] == '1' else '1'
					continue
		res = []
		for _ in range(int(input())):
			(x, y) = input().split()
			(x, y) = (int(x), int(y))
			if min(x, y) < 4:
				if x > y:
					r = table_left[y][x]
				else:
					r = table[x][y]
				res.append(r)
				continue
			k = 2 if min(x, y) > 2 else 1
			if x > y:
				r = table_left[k][x - y + k]
			else:
				r = table[k][y - x + k]
			res.append(r)
		print(''.join(res))
solve()


def nand(a, b):
	if a == '1' and b == '1':
		return '0'
	else:
		return '1'
t = int(input())
while t > 0:
	row = str(input())
	col = str(input())
	q = int(input())
	m = len(col)
	n = len(row)
	ans = ''
	row1 = ['0' for i in range(0, n)]
	row2 = ['0' for i in range(0, n)]
	col1 = ['0' for i in range(0, m)]
	col2 = ['0' for i in range(0, m)]
	if m == 1:
		col = col + '1'
	if n == 1:
		row = row + '1'
	row1[0] = nand(row[0], col[0])
	row2[0] = nand(row1[0], col[1])
	for i in range(1, n):
		row1[i] = nand(row[i], row1[i - 1])
		row2[i] = nand(row1[i], row2[i - 1])
	col1[0] = row1[0]
	col2[0] = row1[1]
	for i in range(1, m):
		col1[i] = nand(col1[i - 1], col[i])
		col2[i] = nand(col2[i - 1], col1[i])
	for k in range(0, q):
		(i, j) = map(int, input().split())
		if i == 1:
			ans = ans + row1[j - 1]
		elif i == 2:
			ans = ans + row2[j - 1]
		elif j == 1:
			ans = ans + col1[i - 1]
		elif j == 2:
			ans = ans + col2[i - 1]
		elif i == j:
			ans = ans + row2[1]
		elif i < j:
			ans = ans + row2[j - i + 1]
		elif j < i:
			ans = ans + col2[i - j + 1]
	print(ans)
	t = t - 1


MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
(t,) = I()
while t:
	t -= 1
	ms = input()
	ns = input()
	n = len(ns)
	m = len(ms)
	table = [[0 for i in range(m + 1)] for j in range(min(3, n + 1))]
	table[0][0] = 1 if ms[0] == '0' or ns[0] == '0' else 0
	col = [[0 for i in range(min(3, m + 1))] for j in range(n + 1)]
	col[0][0] = 1 if ms[0] == '0' or ns[0] == '0' else 0
	i = 1
	winner = 0
	while i < m:
		if ms[i] == '0':
			table[0][i] = 1
		else:
			winner = 1 if table[0][i - 1] == 0 else 0
			table[0][i] = winner
		i += 1
	i = 1
	while i < n:
		if ns[i] == '0':
			col[i][0] = 1
		else:
			winner = 1 if col[i - 1][0] == 0 else 0
			col[i][0] = winner
		i += 1
	if n >= 2 and m >= 2:
		table[1][1] = col[1][1] = 0 if table[0][1] and col[1][0] else 1
	for j in range(2, m + 1):
		if table[0][j] == 1 and table[1][j - 1] == 1:
			table[1][j] = 0
		else:
			table[1][j] = 1
	for j in range(2, n + 1):
		if col[j][0] == 1 and col[j - 1][1] == 1:
			col[j][1] = 0
		else:
			col[j][1] = 1
	(q,) = I()
	s = ''
	while q:
		q -= 1
		(x, y) = I()
		if x == y == 1:
			s += str(table[0][0])
			continue
		elif x == 1:
			s += str(table[0][y - 1])
			continue
		elif y == 1:
			s += str(col[x - 1][0])
			continue
		k = min(x, y) - 1
		x -= k
		y -= k
		if y < x:
			s += str(col[x][y])
		else:
			s += str(table[x][y])
	print(s)


def nand(a, b):
	if not (a and b) == True:
		return 1
	elif not (a and b) == False:
		return 0

def rec(val, lm, dic):
	if val in dic.keys():
		return dic[val]
	else:
		dic[val] = nand(rec(val - 1, lm, dic), rec(val - 1 - lm, lm, dic))
		return dic[val]

def findvalue(r, c, new, nm, lm):
	step = 0
	if r == 1:
		return new[c]
	elif c == 1:
		return new[lm + r - 1]
	if r > c:
		step = c - 2
		(r, c) = (r - step, 2)
	else:
		step = r - 2
		(r, c) = (2, c - step)
	if r == 2:
		pos = c - 1
	elif c == 2:
		pos = lm - 1 + r - 2
	return inner[pos]
for qwerty in range(int(input())):
	m = input()
	n = input()
	lm = len(m)
	ln = len(n)
	try:
		table = []
		nm = []
		nm.append(-1)
		for i in range(1, lm + 1):
			nm.append(int(m[i - 1]))
		for i in range(lm + 1, lm + ln + 1):
			nm.append(int(n[i - lm - 1]))
		for i in range(2 * (lm + ln)):
			table.append(-1)
		for i in range(1, 1 + lm):
			table[i] = int(m[i - 1])
		table[lm + 1] = int(n[0])
		table[2 * lm + 2] = int(n[1])
		k = 2
		for i in range(1, ln - 1):
			if table[2 * lm + 2 + k] == -1:
				table[2 * lm + 2 + k] = int(n[i + 1])
			k = k + 2
		count = 0
		new = [-1]
		for i in range(lm, len(table)):
			if table[i] == -1:
				if count > lm:
					table[i] = nand(table[i - 1], table[i - 2])
					new.append(table[i])
				else:
					table[i] = nand(table[i - 1], table[i - 1 - lm])
					new.append(table[i])
				count = count + 1
		inner = [-1]
		for i in range(ln + lm - 3):
			inner.append(-1)
		inner[1] = nand(new[2], new[lm + 1])
		if len(inner) > lm:
			inner[lm] = nand(inner[1], new[lm + 2])
		for i in range(2, lm):
			if inner[i] == -1:
				inner[i] = nand(new[i + 1], inner[i - 1])
		for i in range(lm, len(inner)):
			if inner[i] == -1:
				inner[i] = nand(new[i + 2], inner[i - 1])
		q = int(input())
		answer = []
		for j in range(q):
			(r, c) = list(map(int, input().split(' ')))
			value = findvalue(r, c, new, nm, lm)
			answer.append(value)
		answer = ''.join(list(map(str, answer)))
		print(str(answer))
	except:
		dic = {}
		table = []
		for i in range(1, lm + 1):
			dic[i] = int(m[i - 1])
		for i in range(1, ln + 1):
			dic[i * lm + i] = int(n[i - 1])
		q = int(input())
		answer = []
		for j in range(q):
			(r, c) = list(map(int, input().split(' ')))
			pos = r * lm + r + c
			value1 = rec(pos - 1, lm, dic)
			value2 = rec(pos - 1 - lm, lm, dic)
			if value1 == 0 or value2 == 0:
				answer.append(1)
			else:
				answer.append(0)
		answer = ''.join(list(map(str, answer)))
		print(str(answer))


I = lambda : list(map(int, list(input())))
from sys import stdin, stdout
for _ in range(int(input())):
	a = I()
	b = I()
	c = [int(not (b[0] and a[0]))]
	d = [int(not (b[0] and a[0]))]
	for i in range(1, len(a)):
		c.append(int(not (a[i] and c[i - 1])))
	for i in range(1, len(b)):
		d.append(int(not (b[i] and d[i - 1])))
	if len(a) > 1 and len(b) > 1:
		e = [d[1], int(not (c[1] and d[1]))]
		f = [c[1], int(not (c[1] and d[1]))]
		for i in range(2, len(a)):
			e.append(int(not (c[i] and e[-1])))
		for i in range(2, len(b)):
			f.append(int(not (d[i] and f[-1])))
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		if x != 1 and x == y:
			print(e[1], end='')
		elif x != 1 and y != 1 and (x > y):
			print(f[x - y + 1], end='')
		elif x != 1 and y != 1 and (y > x):
			print(e[y - x + 1], end='')
		elif x == 1 and y > x:
			print(c[y - 1], end='')
		elif y == 1 and x > y:
			print(d[x - 1], end='')
		else:
			print(c[0], end='')
	print('')


for t in range(int(input())):
	a = input()
	b = input()
	m = len(a)
	n = len(b)
	board = ['' for i in range(n + 1)]
	board[0] = '1' + a
	for i in range(1, n + 1):
		board[i] = b[i - 1]
	for j in range(1, m + 1):
		board[1] += str(1 - (int(board[0][j]) & int(board[1][j - 1])))
		if n > 1:
			board[2] += str(1 - (int(board[1][j]) & int(board[2][j - 1])))
	for i in range(3, n + 1):
		board[i] = b[i - 1] + str(1 - (int(board[i][0]) & int(board[i - 1][1])))
		if m > 1:
			board[i] += str(1 - (int(board[i][1]) & int(board[i - 1][2])))
	q = int(input())
	for Q in range(q):
		(x, y) = map(int, input().split())
		if x > 2 and y > 2:
			if x < y:
				print(board[2][y - (x - 2)], end='')
			else:
				print(board[x - (y - 2)][2], end='')
		else:
			print(board[x][y], end='')
	print()


t = int(input())
res = []
for _ in range(t):
	r = []
	N = list(map(int, list(input())))
	M = list(map(int, list(input())))
	n = len(N)
	m = len(M)
	Y = [1 for j in range(m + 1)]
	A = [Y.copy() for i in range(3)] + [[1 for j in range(3)] for i in range(n + 1 - 3)]
	A[0] = ['_'] + M
	for i in zip(A[1:], N):
		i[0][0] = i[1]
	for k in range(1, min(n, m, 2) + 1):
		for i in range(k, n + 1):
			if A[i - 1][k] and A[i][k - 1]:
				A[i][k] = 0
		for j in range(k + 1, m + 1):
			if A[k - 1][j] and A[k][j - 1]:
				A[k][j] = 0
	q = int(input())
	for i in range(q):
		(qj, qi) = map(int, input().split())
		if qi > 2 and qj > 2:
			if qi > qj:
				(x, y) = (qi - qj + 2, 2)
			else:
				(x, y) = (2, qj - qi + 2)
		else:
			(x, y) = (qi, qj)
		r.append(str(A[x][y]))
	res.append(''.join(r))
for i in res:
	print(i)


def NAND(a, b):
	if a == 1 and b == 1:
		return 0
	return 1
import numpy as np
for i in range(int(input())):
	m = list(input())
	n = list(input())
	l = np.full((min(2, len(n)), len(m)), -1)
	l_ = np.full((len(n), min(2, len(m))), -1)
	for j in range(min(2, len(n))):
		for k in range(len(m)):
			if j == 0 and k == 0:
				l[j][k] = NAND(int(m[k]), int(n[j]))
			elif j == 0:
				l[j][k] = NAND(int(m[k]), l[j][k - 1])
			elif k == 0:
				l[j][k] = NAND(int(n[j]), l[j - 1][k])
			else:
				l[j][k] = NAND(l[j - 1][k], l[j][k - 1])
	for j in range(len(n)):
		for k in range(min(2, len(m))):
			if j == 0 and k == 0:
				l_[j][k] = NAND(int(m[k]), int(n[j]))
			elif j == 0:
				l_[j][k] = NAND(int(m[k]), l_[j][k - 1])
			elif k == 0:
				l_[j][k] = NAND(int(n[j]), l_[j - 1][k])
			else:
				l_[j][k] = NAND(l_[j - 1][k], l_[j][k - 1])
	s = ''
	for j in range(int(input())):
		(x, y) = map(int, input().split())
		if x == 1:
			s += str(l[0][y - 1])
		elif y == 1:
			s += str(l_[x - 1][0])
		elif x > y:
			s += str(l_[x - y + 1][1])
		else:
			s += str(l[1][y - x + 1])
	print(s)


from sys import stdin, stdout
for _ in range(int(input())):
	a = list(map(int, list(input())))
	b = list(map(int, list(input())))
	a1 = [int(not (b[0] and a[0]))]
	b1 = [int(not (b[0] and a[0]))]
	for i in range(1, len(a)):
		a1.append(int(not (a[i] and a1[-1])))
	for i in range(1, len(b)):
		b1.append(int(not (b[i] and b1[-1])))
	if len(a) > 1 and len(b) > 1:
		a2 = [b1[1], int(not (a1[1] and b1[1]))]
		b2 = [a1[1], int(not (a1[1] and b1[1]))]
		for i in range(2, len(a)):
			a2.append(int(not (a1[i] and a2[-1])))
		for i in range(2, len(b)):
			b2.append(int(not (b1[i] and b2[-1])))
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		if x != 1 and x == y:
			print(a2[1], end='')
		elif x != 1 and y != 1 and (x > y):
			print(b2[x - y + 1], end='')
		elif x != 1 and y != 1 and (y > x):
			print(a2[y - x + 1], end='')
		elif x == 1 and y > x:
			print(a1[y - 1], end='')
		elif y == 1 and x > y:
			print(b1[x - 1], end='')
		else:
			print(a1[0], end='')
	print('')


T = int(input())
for t in range(T):
	Y = input()
	M = len(Y)
	X = input()
	N = len(X)
	Q = int(input())
	board = [['-']]
	for y in Y:
		board.append(list(y))
	for y in X:
		board[0].append(y)
	t = min(3, M + 1)
	for j in range(1, t):
		for i in range(1, N + 1):
			if board[j - 1][i] == '0' or board[j][i - 1] == '0':
				board[j].append('1')
			else:
				board[j].append('0')
	t = min(3, N + 1)
	for j in range(t, M + 1):
		for i in range(1, t):
			if board[j - 1][i] == '0' or board[j][i - 1] == '0':
				board[j].append('1')
			else:
				board[j].append('0')
	ans = ''
	for i in range(Q):
		(x, y) = [int(x) for x in input().split()]
		if x > 2 and y > 2:
			temp = min(x, y)
			x = x - temp + 2
			y = y - temp + 2
		ans = ans + board[y][x]
	print(ans)


def transform(string, start):
	temp = int(start)
	result = str(int(not temp & int(string[0])))
	i = 1
	while i < len(string):
		result += str(int(not int(string[i]) & int(result[-1])))
		i += 1
	return result
T = int(input())
for _ in range(T):
	row = []
	col = []
	row.append(input())
	col.append(input())
	if len(row[0]) != 1 and len(col[0]) != 1:
		row.append(transform(row[0], col[0][0]))
		col.append(transform(col[0], row[0][0]))
		row.append(transform(row[1], col[0][1]))
		col.append(transform(col[1], row[0][1]))
		Q = int(input())
		for i in range(Q):
			(r, c) = map(int, input().split())
			if r == 1 or c == 1:
				if r == 1:
					print(row[1][c - 1], end='')
				else:
					print(col[1][r - 1], end='')
			elif r < c:
				print(row[2][abs(r - c) + 1], end='')
			else:
				print(col[2][abs(r - c) + 1], end='')
		print()
	else:
		f = row[0]
		s = col[0]
		matrix = []
		for i in range(len(s) + 1):
			matrix.append([])
			for j in range(len(f) + 1):
				matrix[-1].append(0)
		for i in range(len(f)):
			matrix[0][i + 1] = int(f[i])
		for i in range(len(s)):
			matrix[i + 1][0] = int(s[i])
		for i in range(1, len(s) + 1):
			for j in range(1, len(f) + 1):
				matrix[i][j] = int(not (matrix[i - 1][j] and matrix[i][j - 1]))
		Q = int(input())
		for _ in range(Q):
			(i, j) = map(int, input().split())
			print(matrix[i][j], end='')
		print()


for _ in range(int(input())):
	m = [int(i) for i in input()]
	n = [int(i) for i in input()]
	res = []
	row = []
	col = []
	row2 = []
	col2 = []
	lm = len(m)
	ln = len(n)
	if m[0] == 0 or n[0] == 0:
		row.append(1)
		col.append(1)
	else:
		row.append(0)
		col.append(0)
	for i in range(1, lm):
		if m[i] == 0 or row[i - 1] == 0:
			row.append(1)
		else:
			row.append(0)
	for i in range(1, ln):
		if n[i] == 0 or col[i - 1] == 0:
			col.append(1)
		else:
			col.append(0)
	if ln > 1 and lm > 1:
		if row[1] == 0 or col[1] == 0:
			row2.append(1)
			col2.append(1)
		else:
			row2.append(0)
			col2.append(0)
		for i in range(1, lm - 1):
			if row[i + 1] == 0 or row2[i - 1] == 0:
				row2.append(1)
			else:
				row2.append(0)
		for i in range(1, ln - 1):
			if col[i + 1] == 0 or col2[i - 1] == 0:
				col2.append(1)
			else:
				col2.append(0)
	q = int(input())
	for x in range(q):
		(i, j) = map(int, input().split())
		if i < 3 or j < 3:
			if i == j:
				if i == 1:
					res.append(row[0])
				elif i == 2:
					res.append(row2[0])
			elif i < j:
				if i == 1:
					res.append(row[j - 1])
				elif i == 2:
					res.append(row2[j - 2])
			elif i > j:
				if j == 1:
					res.append(col[i - 1])
				elif j == 2:
					res.append(col2[i - 2])
		elif i == j:
			res.append(row2[0])
		elif i < j:
			res.append(row2[j - i])
		elif i > j:
			res.append(col2[i - j])
	for k in range(len(res)):
		print(res[k], end='')
	print()


for _ in range(int(input())):
	m = input().strip()
	n = input().strip()
	q = int(input())
	nl = len(n)
	ml = len(m)
	arh1 = [None for i in range(ml + 1)]
	arh1[0] = n[0]
	if nl > 1:
		arh2 = [None for i in range(ml + 1)]
		arh2[0] = n[1]
	for i in range(1, ml + 1):
		if arh1[i - 1] == '0' or m[i - 1] == '0':
			arh1[i] = '1'
		else:
			arh1[i] = '0'
		if nl > 1:
			if arh2[i - 1] == '0' or arh1[i] == '0':
				arh2[i] = '1'
			else:
				arh2[i] = '0'
	arv1 = [None for i in range(nl + 1)]
	arv1[0] = m[0]
	if ml > 1:
		arv2 = [None for i in range(nl + 1)]
		arv2[0] = m[1]
	for i in range(1, nl + 1):
		if arv1[i - 1] == '0' or n[i - 1] == '0':
			arv1[i] = '1'
		else:
			arv1[i] = '0'
		if ml > 1:
			if arv2[i - 1] == '0' or arv1[i] == '0':
				arv2[i] = '1'
			else:
				arv2[i] = '0'
	ans = ''
	for k in range(q):
		(x, y) = map(int, input().split())
		if x == 1 or y == 1:
			if x == 1:
				ans += arh1[y]
			else:
				ans += arv1[x]
		elif x < y:
			k = x - 2
			ans += arh2[y - k]
		else:
			k = y - 2
			ans += arv2[x - k]
	print(ans)


def mat1():
	global horiz
	horiz = ''
	ar1 = []
	ar1.append(['0'] + [r for r in s1])
	for i in range(0, 2):
		lw = []
		el = s2[i]
		sm = ''
		lw.append(el)
		for j in range(0, l1):
			if i == 0:
				if j == 0:
					if s1[j] == '1' and el == '1':
						lw.append('1')
						last = '1'
						sm += last
					else:
						lw.append('0')
						last = '0'
						sm += last
				elif s1[j] == '1' and last == '0':
					lw.append('1')
					last = '1'
					sm += last
				else:
					lw.append('0')
					last = '0'
					sm += last
			elif j == 0:
				if chk[j] == '0' and el == '1':
					lw.append('1')
					last = '1'
					sm += last
				else:
					lw.append('0')
					last = '0'
					sm += last
			elif chk[j] == '0' and last == '0':
				lw.append('1')
				last = '1'
				sm += last
			else:
				lw.append('0')
				last = '0'
				sm += last
		chk = sm
		ar1.append(lw)
	horiz = chk[1:]
	return ar1

def mat2():
	global vert
	vert = ''
	ar2 = []
	temp_var = ''
	for i in range(0, l2):
		lw = []
		el = s2[i]
		sm = ''
		lw.append(el)
		for j in range(0, 2):
			if i == 0:
				if j == 0:
					if s1[j] == '1' and el == '1':
						lw.append('1')
						last = '1'
						sm += last
					else:
						lw.append('0')
						last = '0'
						sm += last
				elif s1[j] == '1' and last == '0':
					lw.append('1')
					last = '1'
					sm += last
				else:
					lw.append('0')
					last = '0'
					sm += last
			elif j == 0:
				if chk[j] == '0' and el == '1':
					lw.append('1')
					last = '1'
					sm += last
				else:
					lw.append('0')
					last = '0'
					sm += last
			elif chk[j] == '0' and last == '0':
				lw.append('1')
				last = '1'
				sm += last
			else:
				lw.append('0')
				last = '0'
				sm += last
			if j == 1:
				temp_var += last
		chk = sm
		ar2.append(lw)
	vert = temp_var[1:]
	return ar2
for _ in range(0, int(input())):
	s1 = input()
	s2 = input()
	(l1, l2) = (len(s1), len(s2))
	horiz = ''
	vert = ''
	out = ''
	if l1 >= 2 and l2 >= 2:
		hor_ar = mat1()
		ver_ar = mat2()
		for q in range(0, int(input())):
			(x, y) = input().split()
			(x, y) = (int(x), int(y))
			if x > 2 and y > 2:
				if x > y:
					el_chk = vert[x - y]
				elif x < y:
					el_chk = horiz[y - x]
				else:
					el_chk = horiz[0]
			elif x > 2 and y <= 2:
				el_chk = ver_ar[x - 1][y]
			elif y > 2 and x <= 2:
				el_chk = hor_ar[x][y]
			else:
				el_chk = hor_ar[x][y]
			if el_chk == '0':
				out += '1'
			else:
				out += '0'
		print(out)
	else:
		ar = [[]]
		ar[0] = ['0'] + [r for r in s1]
		for i in range(0, l2):
			lw = []
			el = s2[i]
			sm = ''
			lw.append(el)
			for j in range(0, l1):
				if i == 0:
					if j == 0:
						if s1[j] == '1' and el == '1':
							lw.append('1')
							last = '1'
							sm += last
						else:
							lw.append('0')
							last = '0'
							sm += last
					elif s1[j] == '1' and last == '0':
						lw.append('1')
						last = '1'
						sm += last
					else:
						lw.append('0')
						last = '0'
						sm += last
				elif j == 0:
					if chk[j] == '0' and el == '1':
						lw.append('1')
						last = '1'
						sm += last
					else:
						lw.append('0')
						last = '0'
						sm += last
				elif chk[j] == '0' and last == '0':
					lw.append('1')
					last = '1'
					sm += last
				else:
					lw.append('0')
					last = '0'
					sm += last
			chk = sm
			ar.append(lw)
		for q in range(0, int(input())):
			(x, y) = input().split()
			(x, y) = (int(x), int(y))
			if ar[x][y] == '0':
				out += '1'
			else:
				out += '0'
		print(out)


tc = int(input())
while tc != 0:
	a = input()
	b = input()
	n = int(input())
	a = list(map(int, a))
	b = list(map(int, b))
	cu = b[0]
	cr = a[0]
	nuL = []
	nrL = []
	lst = []
	for i in range(0, len(a)):
		if a[i] == 1 and cu == 1:
			cu = 0
			nuL.append(cu)
		else:
			cu = 1
			nuL.append(cu)
	for i in range(0, len(b)):
		if b[i] == 1 and cr == 1:
			cr = 0
			nrL.append(cr)
		else:
			cr = 1
			nrL.append(cr)
	if len(nrL) > 1:
		nuL1 = []
		cu1 = nrL[1]
		for i in range(1, len(a)):
			if nuL[i] == 1 and cu1 == 1:
				cu1 = 0
				nuL1.append(cu1)
			else:
				cu1 = 1
				nuL1.append(cu1)
	if len(nuL) > 1:
		nrL1 = []
		cr1 = nuL[1]
		for i in range(1, len(b)):
			if nrL[i] == 1 and cr1 == 1:
				cr1 = 0
				nrL1.append(cr1)
			else:
				cr1 = 1
				nrL1.append(cr1)
	for i in range(0, n):
		case = input().split()
		case = list(map(int, case))
		p = case[0]
		t = case[1]
		if p == 1 or t == 1:
			if p == t:
				lst.append(nuL[0])
				continue
			if p < t:
				lst.append(nuL[t - p])
			if p > t:
				lst.append(nrL[p - t])
		else:
			if p <= t:
				lst.append(nuL1[t - p])
			if p > t:
				lst.append(nrL1[p - t])
	lst = list(map(str, lst))
	print(''.join(lst))
	tc -= 1


t = int(input())
for _ in range(t):
	s1 = input()
	s2 = input()
	query = int(input())
	arr = []
	s = ''
	arr.append([])
	arr[0].append(1)
	for i in s1:
		arr[0].append(int(i))
	for i in range(len(s2)):
		arr.append([])
		arr[i + 1].append(int(s2[i]))
	if arr[0][1] == 0 or arr[1][0] == 0:
		arr[1].append(0)
	else:
		arr[1].append(1)
	for i in range(2, len(s1) + 1):
		if arr[0][i] == 0 or arr[1][i - 1] == 1:
			arr[1].append(0)
		else:
			arr[1].append(1)
	for i in range(2, len(s2) + 1):
		if arr[i][0] == 0 or arr[i - 1][1] == 1:
			arr[i].append(0)
		else:
			arr[i].append(1)
	if len(s1) >= 2 and len(s2) >= 2:
		if arr[1][2] == 1 or arr[2][1] == 1:
			arr[2].append(0)
		else:
			arr[2].append(1)
	try:
		for i in range(3, len(s1) + 1):
			if arr[1][i] == 1 or arr[2][i - 1] == 1:
				arr[2].append(0)
			else:
				arr[2].append(1)
		for i in range(3, len(s2) + 1):
			if arr[i][1] == 1 or arr[i - 1][2] == 1:
				arr[i].append(0)
			else:
				arr[i].append(1)
	except Exception:
		pass
	try:
		for i in range(query):
			(a, b) = list(map(int, input().split()))
			if min(a, b) > 2:
				if a > b:
					(a, b) = (a - (b - 2), 2)
				else:
					(a, b) = (2, b - (a - 2))
			if arr[a][b] == 0:
				s += '1'
			else:
				s += '0'
	except Exception:
		pass
	print(s)


for _ in range(int(input())):
	xm = input()
	yn = input()
	m = len(xm)
	n = len(yn)
	q = int(input())
	mat = []
	if m <= 2 or n <= 2:
		for i in range(n + 2):
			x = []
			for j in range(m + 2):
				x.append(0)
			mat.append(x)
		try:
			for i in range(1, m + 1):
				mat[0][i] = int(xm[i - 1])
			for i in range(1, n + 1):
				mat[i][0] = int(yn[i - 1])
		except IndexError:
			print('pass 1')
			pass
		try:
			for i in range(1, m + 1):
				if i == 1:
					if mat[0][1] == 0 or mat[1][0] == 0:
						mat[1][1] = 'a'
					else:
						mat[1][1] = 'b'
				elif mat[0][i] == 0:
					mat[1][i] = 'a'
				elif mat[1][i - 1] == 'a':
					mat[1][i] = 'b'
				else:
					mat[1][i] = 'a'
		except IndexError:
			print('pass 2')
			pass
		try:
			for i in range(2, n + 1):
				if mat[i][0] == 0:
					mat[i][1] = 'a'
				elif mat[i - 1][1] == 'a':
					mat[i][1] = 'b'
				else:
					mat[i][1] = 'a'
		except IndexError:
			print('pass 3')
			pass
		try:
			for i in range(2, n + 1):
				for j in range(2, m + 1):
					if mat[i][j - 1] == 'a' and mat[i - 1][j] == 'a':
						mat[i][j] = 'b'
					elif mat[i][j - 1] == 'b' and mat[i - 1][j] == 'b':
						mat[i][j] = 'a'
					else:
						mat[i][j] = 'a'
		except IndexError:
			print('pass 4')
			pass
		ans = []
		try:
			for i in range(q):
				(p, q) = map(int, input().split())
				if mat[p][q] == 'a':
					ans.append(1)
				else:
					ans.append(0)
		except IndexError:
			print('pass 5')
			pass
		for i in range(len(ans)):
			print(ans[i], end='')
		print()
	else:
		marray = []
		narray = []
		for i in range(4):
			x = []
			for j in range(m + 1):
				x.append(0)
			marray.append(x)
		marray[0][0] = 0
		marray[1][0] = int(yn[0])
		marray[2][0] = int(yn[1])
		marray[3][0] = int(yn[2])
		for i in range(n + 1):
			x = []
			for j in range(4):
				x.append(0)
			narray.append(x)
		narray[0][0] = 0
		narray[0][1] = int(xm[0])
		narray[0][2] = int(xm[1])
		narray[0][3] = int(xm[2])
		for i in range(1, m + 1):
			marray[0][i] = int(xm[i - 1])
		for i in range(1, n + 1):
			narray[i][0] = int(yn[i - 1])
		for i in range(1, m + 1):
			if i == 1:
				if marray[0][1] == 0 or marray[1][0] == 0:
					marray[1][1] = 'a'
				else:
					marray[1][1] = 'b'
			elif marray[0][i] == 0:
				marray[1][i] = 'a'
			elif marray[1][i - 1] == 'a':
				marray[1][i] = 'b'
			else:
				marray[1][i] = 'a'
		for i in range(1, n + 1):
			if i == 1:
				if narray[1][0] == 0 or marray[0][1] == 0:
					narray[1][1] = 'a'
				else:
					narray[1][1] = 'b'
			elif narray[i][0] == 0:
				narray[i][1] = 'a'
			elif narray[i - 1][1] == 'a':
				narray[i][1] = 'b'
			else:
				narray[i][1] = 'a'
		for i in range(2, 4):
			for j in range(1, m + 1):
				if j == 1:
					if marray[i][0] == 0:
						marray[i][j] = 'a'
					elif marray[i - 1][1] == 'a' and marray[i][0] == 1:
						marray[i][j] = 'b'
					else:
						marray[i][j] = 'a'
				elif marray[i][j - 1] == 'a' and marray[i - 1][j] == 'a':
					marray[i][j] = 'b'
				elif marray[i][j - 1] == 'b' and marray[i - 1][j] == 'b':
					marray[i][j] = 'a'
				else:
					marray[i][j] = 'a'
		for i in range(1, n + 1):
			for j in range(2, 4):
				if i == 1:
					if narray[0][j] == 0:
						narray[i][j] = 'a'
					elif narray[1][j - 1] == 'a' and narray[0][j] == 1:
						narray[i][j] = 'b'
					else:
						narray[i][j] = 'a'
				elif narray[i][j - 1] == 'a' and narray[i - 1][j] == 'a':
					narray[i][j] = 'b'
				elif narray[i][j - 1] == 'b' and narray[i - 1][j] == 'b':
					narray[i][j] = 'a'
				else:
					narray[i][j] = 'a'
		ans = []
		query = q
		for _ in range(query):
			(p, q) = map(int, input().split())
			if p == 1 or q == 1:
				if p == 1:
					if marray[p][q] == 'a':
						ans.append(1)
					else:
						ans.append(0)
				elif narray[p][q] == 'a':
					ans.append(1)
				else:
					ans.append(0)
			elif p <= q:
				q = q - p + 2
				p = 2
				if marray[p][q] == 'a':
					ans.append(1)
				else:
					ans.append(0)
			else:
				p = p - q + 2
				q = 2
				if narray[p][q] == 'a':
					ans.append(1)
				else:
					ans.append(0)
		for i in range(query):
			print(ans[i], end='')
		print()


import sys
for _ in range(int(input())):
	m = sys.stdin.readline()
	n = sys.stdin.readline()
	(m1, n1) = (len(m), len(n))
	a = [['-1' for i in range(m1)] for j in range(2)]
	b = [['-1' for i in range(2)] for j in range(n1)]
	for i in range(n1):
		for j in range(min(2, m1)):
			if i == 0 and j == 0:
				if n[0] == '0' or m[0] == '0':
					b[0][0] = '1'
				else:
					b[0][0] = '0'
			elif i == 0 and j != 0:
				if m[j] == '0' or b[i][j - 1] == '0':
					b[i][j] = '1'
				else:
					b[i][j] = '0'
			elif j == 0 and i != 0:
				if n[i] == '0' or b[i - 1][j] == '0':
					b[i][j] = '1'
				else:
					b[i][j] = '0'
			elif b[i][j - 1] == '0' or b[i - 1][j] == '0':
				b[i][j] = '1'
			else:
				b[i][j] = '0'
	for i in range(min(2, n1)):
		for j in range(m1):
			if i == 0 and j == 0:
				if n[0] == '0' or m[0] == '0':
					a[0][0] = '1'
				else:
					a[0][0] = '0'
			elif i == 0 and j != 0:
				if m[j] == '0' or a[i][j - 1] == '0':
					a[i][j] = '1'
				else:
					a[i][j] = '0'
			elif j == 0 and i != 0:
				if n[i] == '0' or a[i - 1][j] == '0':
					a[i][j] = '1'
				else:
					a[i][j] = '0'
			elif a[i][j - 1] == '0' or a[i - 1][j] == '0':
				a[i][j] = '1'
			else:
				a[i][j] = '0'
	s = ''
	for i in range(int(input())):
		(l, r) = map(int, sys.stdin.readline().split())
		l -= 1
		r -= 1
		if l > r:
			if l == 0 or r == 0:
				s += b[l - r][0]
			else:
				s += b[l - r + 1][1]
		elif l == 0 or r == 0:
			s += a[0][r - l]
		else:
			s += a[1][r - l + 1]
	print(s)


for _ in range(int(input())):
	mi = input()
	ni = input()
	m = len(mi)
	n = len(ni)
	a = [[None]]
	out = []
	for i in range(1, n + 1):
		a.append([])
		a[i].append(ni[i - 1])
	for j in range(1, m + 1):
		a[0].append(mi[j - 1])
	for i in range(1, min(n + 1, 3)):
		for j in range(1, m + 1):
			if a[i - 1][j] == '0' or a[i][j - 1] == '0':
				a[i].append('1')
			else:
				a[i].append('0')
	for i in range(1, min(m + 1, 3)):
		for k in range(3, n + 1):
			if a[k - 1][i] == '0' or a[k][i - 1] == '0':
				a[k].append('1')
			else:
				a[k].append('0')
	q = int(input())
	for i in range(q):
		(x, y) = map(int, input().split())
		if x < 3 or y < 3:
			out.append(a[x][y])
		elif x > y:
			out.append(a[x - (y - 2)][2])
		elif x < y:
			out.append(a[2][y - (x - 2)])
		else:
			out.append(a[2][2])
	output = ''.join(out)
	print(output)


def cal(x, y):
	if x == 0 or x == 1:
		if x == 0:
			return str(col1[y])
		elif nl >= 2 and ml >= 2:
			return str(col2[y])
	if y == 0 or y == 1:
		if y == 0:
			return str(row1[x])
		elif nl >= 2 and ml >= 2:
			return str(row2[x])
for o in range(int(input())):
	m = list(map(int, list(input())))
	n = list(map(int, list(input())))
	nl = len(n)
	ml = len(m)
	q = int(input())
	p = []
	for _ in range(q):
		(x, y) = list(map(int, input().split()))
		(x, y) = (x - 1, y - 1)
		p.append([x, y])
	row1 = []
	row2 = []
	col1 = []
	col2 = []
	i = 0
	for i in range(nl):
		if i == 0:
			if m[0] == 1 and n[0] == 1:
				row1.append(0)
				continue
			row1.append(1)
			continue
		if row1[-1] == 1 and n[i] == 1:
			row1.append(0)
			continue
		row1.append(1)
	i = 0
	for i in range(ml):
		if i == 0:
			if m[0] == 1 and n[0] == 1:
				col1.append(0)
				continue
			col1.append(1)
			continue
		if col1[-1] == 1 and m[i] == 1:
			col1.append(0)
			continue
		col1.append(1)
	if nl >= 2 and ml >= 2:
		for i in range(nl):
			if i == 0:
				row2.append(col1[1])
				continue
			if row2[-1] == 1 and row1[i] == 1:
				row2.append(0)
				continue
			row2.append(1)
		for i in range(ml):
			if i == 0:
				col2.append(row1[1])
				continue
			if i == 1:
				col2.append(row2[1])
				continue
			if col2[-1] == 1 and col1[i] == 1:
				col2.append(0)
				continue
			col2.append(1)
	s = ''
	for (x, y) in p:
		if y > x and x > 1:
			z = x - 1
			y = y - z
			x = 1
			s += cal(x, y)
			continue
		if x > y and y > 1:
			z = y - 1
			y = 1
			x = x - z
			s += cal(x, y)
			continue
		if x == y and x >= 1:
			s += str(row2[1])
			continue
		else:
			s += cal(x, y)
	print(s)


T = int(input())
for test_case in range(T):
	M = input()
	N = input()
	Q = int(input())
	query = [list(map(int, input().split())) for i in range(Q)]
	result = ''
	for (y, x) in query:
		rLen = len(result)
		if x > y > 1:
			tempX = x - (y - 1)
			while tempX > 1:
				if M[tempX - 1:tempX + 1] == '01':
					result += '1'
					break
				elif M[tempX - 2:tempX] == '01':
					result += '0'
					break
				else:
					tempX -= 2
			if len(result) == rLen:
				if tempX == 1:
					result += '1' if (N[1] == '1' or M[1] == '1') and (N[0] == '0' or M[0] == '0') else '0'
				elif tempX == 0:
					result += '0' if (N[1] == '1' or M[1] == '1') and (N[0] == '0' or M[0] == '0') else '1'
		elif y > x > 1:
			tempY = y - (x - 1)
			while tempY > 1:
				if N[tempY - 1:tempY + 1] == '01':
					result += '1'
					break
				elif N[tempY - 2:tempY] == '01':
					result += '0'
					break
				else:
					tempY -= 2
			if len(result) == rLen:
				if tempY == 1:
					result += '1' if (N[1] == '1' or M[1] == '1') and (N[0] == '0' or M[0] == '0') else '0'
				elif tempY == 0:
					result += '0' if (N[1] == '1' or M[1] == '1') and (N[0] == '0' or M[0] == '0') else '1'
		elif x == y > 1:
			result += '1' if (N[1] == '1' or M[1] == '1') and (N[0] == '0' or M[0] == '0') else '0'
		elif x == 1:
			tempY = y
			while tempY > 1:
				if N[tempY - 1] == '0':
					result += '1'
					break
				elif N[tempY - 2] == '0':
					result += '0'
					break
				else:
					tempY -= 2
			if len(result) == rLen:
				if tempY == 1:
					result += '1' if N[0] == '0' or M[0] == '0' else '0'
				elif tempY == 0:
					result += '0' if N[0] == '0' or M[0] == '0' else '1'
		elif y == 1:
			tempX = x
			while tempX > 1:
				if M[tempX - 1] == '0':
					result += '1'
					break
				elif M[tempX - 2] == '0':
					result += '0'
					break
				else:
					tempX -= 2
			if len(result) == rLen:
				if tempX == 1:
					result += '1' if M[0] == '0' or N[0] == '0' else '0'
				elif tempX == 0:
					result += '0' if M[0] == '0' or N[0] == '0' else '1'
	print(result)


T = int(input())
for _ in range(T):
	top = 'X' + input().strip()
	left = 'X' + input().strip()
	M = len(top) - 1
	N = len(left) - 1
	table = {}
	for j in range(1, M + 1):
		table[0, j] = int(top[j])
	for i in range(1, N + 1):
		table[i, 0] = int(left[i])
	for j in range(1, min(M, 2) + 1):
		for i in range(1, N + 1):
			if table[i - 1, j] == 1 and table[i, j - 1] == 1:
				table[i, j] = 0
			else:
				table[i, j] = 1
	for i in range(1, min(N, 2) + 1):
		for j in range(1, M + 1):
			if table[i - 1, j] == 1 and table[i, j - 1] == 1:
				table[i, j] = 0
			else:
				table[i, j] = 1

	def value(x, y):
		if x <= 2 or y <= 2:
			return table[x, y]
		delta = min(x, y) - 2
		return value(x - delta, y - delta)
	Q = int(input())
	result = []
	for q in range(Q):
		(x, y) = map(int, input().strip().split())
		result.append(value(x, y))
	print(''.join(map(str, result)))


for _ in range(int(input())):
	a_m = '0' + str(input())
	a_n = '0' + str(input())
	(n, m) = (len(a_n), len(a_m))
	(a, ans) = ([], '')
	for i in range(n):
		if i <= 2:
			a.append(['-1'] * m)
		else:
			a.append(['-1'] * 3)
		a[i][0] = a_n[i]
	for i in range(m):
		a[0][i] = a_m[i]
	for i in range(1, n):
		for j in range(1, m):
			if i > 2 and j > 2:
				break
			if a[i - 1][j] in ['0', '3'] or a[i][j - 1] in ['0', '3']:
				a[i][j] = '2'
			else:
				a[i][j] = '3'
	for _ in range(int(input())):
		(l, r) = map(int, input().split())
		t = int()
		if l > 2 and r > 2:
			if l < r:
				ans += '1' if a[2][r - l + 2] == '2' else '0'
			else:
				ans += '1' if a[l - r + 2][2] == '2' else '0'
		else:
			ans += '1' if a[l][r] == '2' else '0'
	print(ans)


t = int(input())
for i in range(t):
	s1 = input()
	s2 = input()
	m = len(s1)
	n = len(s2)
	tabler = [[1 for _ in range(m + 1)] for _ in range(min(n + 1, 4))]
	tablec = [[1 for _ in range(min(4, m + 1))] for _ in range(n + 1)]
	for k in range(1, m + 1):
		tabler[0][k] = int(s1[k - 1])
	for y in range(1, n + 1):
		tablec[y][0] = int(s2[y - 1])
	q = int(input())
	s = ''
	for r in range(1, min(4, m + 1)):
		tablec[0][r] = tabler[0][r]
		for c in range(1, n + 1):
			tablec[c][r] = tabler[0][r]
			if tablec[c][r - 1] == 1 and tablec[c - 1][r] == 1:
				tablec[c][r] = 0
			else:
				tablec[c][r] = 1
	for i1 in range(1, min(4, n + 1)):
		tabler[i1][0] = tablec[i1][0]
		for j1 in range(1, m + 1):
			if tabler[i1][j1 - 1] == 1 and tabler[i1 - 1][j1] == 1:
				tabler[i1][j1] = 0
			else:
				tabler[i1][j1] = 1
	s = ''
	for a1 in range(q):
		(x, y) = map(int, input().split())
		if x > 3 and y > 3:
			x1 = min(x, y)
			id = x1 - 3
			x = x - id
			y = y - id
			if x < y:
				s = s + str(tabler[3][y])
			else:
				s = s + str(tablec[x][3])
		elif x <= 3 and y > 3:
			s = s + str(tabler[x][y])
		elif x > 3 and y <= 3:
			s = s + str(tablec[x][y])
		else:
			s = s + str(tabler[x][y])
	print(s)


T = int(input())
for i in range(T):
	M = str(input())
	N = str(input())
	Q = int(input())
	mapping = {}
	ans = ''
	for p in range(1, 3):
		for q in range(1, len(M) + 1):
			if p < len(N) + 1:
				if p - 1 == 0 and q - 1 == 0:
					if M[0] == '0' or N[0] == '0':
						mapping[p, q] = 'W'
					else:
						mapping[p, q] = 'L'
				elif p == 1:
					if M[q - 1] == '0':
						mapping[p, q] = 'W'
					elif mapping[p, q - 1] == 'W':
						mapping[p, q] = 'L'
					else:
						mapping[p, q] = 'W'
				elif q == 1:
					if N[p - 1] == '0':
						mapping[p, q] = 'W'
					elif mapping[p - 1, q] == 'W':
						mapping[p, q] = 'L'
					else:
						mapping[p, q] = 'W'
				elif mapping[p - 1, q] == 'L' or mapping[p, q - 1] == 'L':
					mapping[p, q] = 'W'
				else:
					mapping[p, q] = 'L'
	for p in range(2, len(N) + 1):
		for q in range(1, 3):
			if q < len(M) + 1:
				if q == 1:
					if N[p - 1] == '0':
						mapping[p, q] = 'W'
					elif mapping[p - 1, q] == 'W':
						mapping[p, q] = 'L'
					else:
						mapping[p, q] = 'W'
				elif mapping[p - 1, q] == 'L' or mapping[p, q - 1] == 'L':
					mapping[p, q] = 'W'
				else:
					mapping[p, q] = 'L'
	for j in range(Q):
		(x, y) = map(int, input().split())
		if x > y and y > 1:
			factor = y - 2
			x -= factor
			y = 2
		elif y >= x and x > 1:
			factor = x - 2
			y -= factor
			x = 2
		if x == 1 and y == 1:
			if mapping[x, y] == 'W':
				ans += '1'
			else:
				ans += '0'
		elif x == 1:
			if mapping[x, y] == 'W':
				ans += '1'
			else:
				ans += '0'
		elif y == 1:
			if mapping[x, y] == 'W':
				ans += '1'
			else:
				ans += '0'
		elif mapping[x, y] == 'W':
			ans += '1'
		else:
			ans += '0'
	print(ans)


t = int(input())
for x in range(t):
	m = input()
	n = input()
	t1 = m[0]
	t2 = n[0]
	l = ''
	for y in n:
		if y == '0' or t1 == '0':
			l += '1'
			t1 = '1'
		else:
			l += '0'
			t1 = '0'
	n = l
	l = ''
	for y in m:
		if t2 == '0' or y == '0':
			l += '1'
			t2 = '1'
		else:
			l += '0'
			t2 = '0'
	m = l
	s = ''
	q = int(input())
	for y in range(q):
		p = [int(z) for z in input().split()]
		x = p[0]
		y = p[1]
		if y == 1:
			s += n[x - y]
		elif x == 1:
			s += m[y - x]
		elif x == y:
			p = x - y
			if n[p] == '0':
				s += '0'
			elif n[p + 1] == '0':
				s += '1'
			elif m[1] == '0':
				s += str(1 - p % 2)
			else:
				s += str(p % 2)
		elif x > y:
			p = x - y
			if n[p] == '0':
				s += '0'
			elif n[p - 1] == '0' or n[p + 1] == '0':
				s += '1'
			else:
				for k in range(p - 1, -1, -1):
					if n[k] == '0':
						if k % 2 == 0:
							s += str(p % 2)
						else:
							s += str(1 - p % 2)
						break
				else:
					if m[1] == '0':
						s += str(1 - p % 2)
					else:
						s += str(p % 2)
		else:
			p = y - x
			if m[p] == '0':
				s += '0'
			elif m[p - 1] == '0' or m[p + 1] == '0':
				s += '1'
			else:
				for k in range(p - 1, -1, -1):
					if m[k] == '0':
						if k % 2 == 0:
							s += str(p % 2)
						else:
							s += str(1 - p % 2)
						break
				else:
					if n[1] == '0':
						s += str(1 - p % 2)
					else:
						s += str(p % 2)
	print(s)


def old(ns, ms, n, m, xx, yy, max_x, max_y):
	board = [['0'] * (m + 1) for x in range(n + 1)]
	for (index, y) in enumerate(ms):
		board[0][index + 1] = y
	for (index, x) in enumerate(ns):
		board[index + 1][0] = x
	for x in range(1, max_x + 1):
		for y in range(1, max_y + 1):
			res = '0'
			if x == 1 and y == 1:
				if board[x - 1][y] == '0' or board[x][y - 1] == '0':
					res = 'a'
				else:
					res = 'b'
			elif board[x - 1][y] == '0' or board[x][y - 1] == '0' or board[x - 1][y] == 'b' or (board[x][y - 1] == 'b'):
				res = 'a'
			else:
				res = 'b'
			board[x][y] = res
	result = []
	for index in range(len(xx)):
		(x, y) = (xx[index], yy[index])
		result.append('1' if board[x][y] == 'a' else '0')
	return ''.join(result)

def fix(board, x, y):
	res = '0'
	if x == 1 and y == 1:
		if board[x - 1][y] == '0' or board[x][y - 1] == '0':
			res = 'a'
		else:
			res = 'b'
	elif x <= 2 or y <= 2:
		if board[x - 1][y] == '0' or board[x][y - 1] == '0' or board[x - 1][y] == 'b' or (board[x][y - 1] == 'b'):
			res = 'a'
		else:
			res = 'b'
	else:
		return
	board[x][y] = res

def solve(ns, ms, n, m, xx, yy, max_x, max_y):
	board = {0: ['0'] + list(ms), 1: [ns[0]] + ['b'] * m, 2: [ns[1]] + ['b'] * m}
	for x in range(3, n + 1):
		board[x] = [ns[x - 1], 'b', 'b']
	for y in range(1, max_y + 1):
		fix(board, 1, y)
	for y in range(1, max_y + 1):
		fix(board, 2, y)
	for x in range(1, max_x + 1):
		fix(board, x, 1)
	for x in range(1, max_x + 1):
		fix(board, x, 2)
	result = []
	for index in range(len(xx)):
		(x, y) = (xx[index], yy[index])
		if x > 2 and y > 2:
			d = min([x, y]) - 2
			x -= d
			y -= d
		result.append('1' if board[x][y] == 'a' else '0')
	return ''.join(result)
for _ in range(int(input())):
	ms = list(input().strip())
	ns = list(input().strip())
	m = len(ms)
	n = len(ns)
	(xx, yy) = ([], [])
	for __ in range(int(input())):
		(x, y) = map(int, input().strip().split())
		xx.append(x)
		yy.append(y)
	max_x = max(xx)
	max_y = max(yy)
	if n == 1 or m == 1:
		print(old(ns, ms, n, m, xx, yy, max_x, max_y))
	else:
		print(solve(ns, ms, n, m, xx, yy, max_x, max_y))


def bob(x, y):
	if x == 0 or y == 0:
		return True
	if (x, y) in dct:
		return dct[x, y]
	flag1 = False
	flag2 = False
	if x == 1:
		if M[y] == '0':
			dct[x, y] = True
			return True
		flag1 = True
	if y == 1:
		if N[x] == '0':
			dct[x, y] = True
			return True
		flag2 = True
	if flag1 and flag2:
		dct[x, y] = False
		return False
	if x < y:
		a = not alice(x - 1, y)
		if a:
			dct[x, y] = True
			return True
		else:
			b = not alice(x, y - 1)
			if b:
				dct[x, y] = True
				return True
		return False
	else:
		a = not alice(x, y - 1)
		if a:
			dct[x, y] = True
			return True
		else:
			b = not alice(x - 1, y)
			if b:
				dct[x, y] = True
				return True
		return False

def alice(x, y):
	if x == 0 or y == 0:
		return True
	if (x, y) in dct:
		return dct[x, y]
	flag1 = False
	flag2 = False
	if x == 1:
		if M[y] == '0':
			dct[x, y] = True
			return True
		flag1 = True
	if y == 1:
		if N[x] == '0':
			dct[x, y] = True
			return True
		flag2 = True
	if flag1 and flag2:
		dct[x, y] = False
		return False
	if x < y:
		a = not bob(x - 1, y)
		if a:
			dct[x, y] = True
			return True
		else:
			b = not bob(x, y - 1)
			if b:
				dct[x, y] = True
				return True
		return False
	else:
		a = not bob(x, y - 1)
		if a:
			dct[x, y] = True
			return True
		else:
			b = not bob(x - 1, y)
			if b:
				dct[x, y] = True
				return True
		return False
T = int(input())
for z in range(T):
	M = list(input())
	M = ['0'] + M
	N = list(input())
	N = ['0'] + N
	dct = {}
	s = ''
	Q = int(input())
	for q in range(Q):
		(x, y) = map(int, input().split())
		if x <= 2 or y <= 2:
			pass
		elif x == 3 or y == 3:
			x -= 1
			y -= 1
		else:
			mn = min(x, y)
			x -= mn - 2
			y -= mn - 2
		if alice(x, y):
			s += '1'
		else:
			s += '0'
	print(s)


t = int(input())
for w in range(0, t):
	m = input()
	n = input()
	ml = len(m)
	nl = len(n)
	a = []
	a.append([])
	a[0].append(0)
	for i in range(1, ml + 1):
		if m[i - 1] == '1':
			a[0].append(1)
		else:
			a[0].append(0)
	for i in range(1, nl + 1):
		a.append([])
		if n[i - 1] == '1':
			a[i].append(1)
		else:
			a[i].append(0)
	for j in range(1, ml + 1):
		a[1].append(a[0][j] & a[1][j - 1] ^ 1)
		if nl >= 2:
			a[2].append(a[1][j] & a[2][j - 1] ^ 1)
	for j in range(3, nl + 1):
		a[j].append(a[j][0] & a[j - 1][1] ^ 1)
		if ml >= 2:
			a[j].append(a[j][1] & a[j - 1][2] ^ 1)
	q = int(input())
	ans = ''
	for i in range(1, q + 1):
		arr = [int(x) for x in input().split()]
		x = arr[0]
		y = arr[1]
		if x <= 2 or y <= 2:
			ans = ans + str(a[x][y])
		else:
			tx = x - 2 if x <= y else y - 2
			x = x - tx
			y = y - tx
			ans = ans + str(a[x][y])
	print(ans)


from random import randint
t = int(input())
for i in range(t):
	m = list(str(input()))
	n = list(str(input()))
	q = int(input())
	if len(m) == 1 or len(n) == 1:
		list1 = [[0 for j in range(len(m))] for k in range(len(n))]
		if m[0] == '0' or n[0] == '0':
			list1[0][0] = 1
		for j in range(1, len(m)):
			if m[j] == '0':
				list1[0][j] = 1
			elif list1[0][j - 1] == 0:
				list1[0][j] = 1
			else:
				continue
		for j in range(1, len(n)):
			if n[j] == '0':
				list1[j][0] = 1
			elif list1[j - 1][0] == 0:
				list1[j][0] = 1
			else:
				continue
		for j in range(1, len(n)):
			for k in range(1, len(m)):
				if list1[j - 1][k] == 0:
					list1[j][k] = 1
				if list1[j][k - 1] == 0:
					list1[j][k] = 1
		list2 = []
		for j in range(q):
			(a, b) = map(int, input().strip().split())
			list2.append(list1[a - 1][b - 1])
		print(''.join((str(e) for e in list2)))
	else:
		list1 = [[0, 0] for j in range(len(m))]
		list2 = [[0, 0] for j in range(len(n))]
		if m[0] == '0' or n[0] == '0':
			list1[0][0] = 1
			list2[0][0] = 1
		for j in range(1, len(m)):
			if m[j] == '0':
				list1[j][0] = 1
			elif list1[j - 1][0] == 0:
				list1[j][0] = 1
			else:
				continue
		for j in range(1, len(n)):
			if n[j] == '0':
				list2[j][0] = 1
			elif list2[j - 1][0] == 0:
				list2[j][0] = 1
			else:
				continue
		list1[0][1] = list2[1][0]
		for j in range(1, len(m)):
			if list1[j - 1][1] == 0:
				list1[j][1] = 1
			if list1[j][0] == 0:
				list1[j][1] = 1
		list2[0][1] = list1[1][0]
		for j in range(1, len(n)):
			if list2[j - 1][1] == 0:
				list2[j][1] = 1
			if list2[j][0] == 0:
				list2[j][1] = 1
		list3 = []
		for j in range(q):
			(a, b) = map(int, input().strip().split())
			if a <= 2:
				list3.append(list1[b - 1][a - 1])
			elif b <= 2:
				list3.append(list2[a - 1][b - 1])
			elif a >= b:
				if list2[a - b][0] == 1 and list2[a - b][1] == 1 and (list2[a - b + 1][0] == 1):
					list3.append(0)
				elif list2[a - b][0] == 0 and list2[a - b][1] == 0 and (list2[a - b + 1][0] == 0):
					list3.append(1)
				else:
					list3.append(list2[a - b][0])
			elif list1[b - a][0] == 1 and list1[b - a][1] == 1 and (list1[b - a + 1][0] == 1):
				list3.append(0)
			elif list1[b - a][0] == 0 and list1[b - a][1] == 0 and (list1[b - a + 1][0] == 0):
				list3.append(1)
			else:
				list3.append(list1[b - a][0])
		print(''.join((str(e) for e in list3)))


t = int(input())
for _ in range(t):
	M = input().strip()
	N = input().strip()
	dp1 = [[False] * (len(N) + 1) for _ in range(10)]
	dp2 = [[False] * 10 for _ in range(len(M) + 1 - 10)]
	dp = dp1 + dp2
	for (i, v) in enumerate(M):
		dp[i + 1][0] = v == '1'
	for (i, v) in enumerate(N):
		dp[0][i + 1] = v == '1'
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			dp[i][j] = not (dp[i][j - 1] and dp[i - 1][j])
			if i > 5 and j > 5:
				break
	ans = []
	for _ in range(int(input())):
		(x, y) = map(int, input().split())
		m = min(x, y)
		if m >= 3:
			x = x - m + 3
			y = y - m + 3
		ans.append('1' if dp[y][x] else '0')
	print(''.join(ans))


t = int(input())
for cas in range(t):
	row1 = list(input().strip())
	col1 = list(input().strip())
	(m, n) = (len(col1) + 1, len(row1) + 1)
	mat = []
	for i in range(3):
		row = [-1] * n
		mat.append(row)
	for i in range(m - 3):
		mat.append([-1, -1, -1, -1])
	for j in range(1, n):
		mat[0][j] = 'l' if int(row1[j - 1]) == 1 else 'w'
	for i in range(1, m):
		mat[i][0] = 'l' if int(col1[i - 1]) == 1 else 'w'
	mat[1][1] = 1 if mat[0][1] == 'w' or mat[1][0] == 'w' else 0
	for i in range(2, n):
		if mat[1][i - 1] == 0 or mat[0][i] == 'w':
			mat[1][i] = 1
		else:
			mat[1][i] = 0
	for i in range(2, m):
		if mat[i - 1][1] == 0 or mat[i][0] == 'w':
			mat[i][1] = 1
		else:
			mat[i][1] = 0
	if n > 2 and m > 2:
		mat[2][2] = 1 if mat[1][2] == 0 or mat[2][1] == 0 else 0
		diff = {}
		diff[0] = [2, 2]
		for i in range(3, n):
			if mat[2][i - 1] == 0 or mat[1][i] == 0:
				mat[2][i] = 1
			else:
				mat[2][i] = 0
			diff[2 - i] = [2, i]
		for i in range(3, m):
			if mat[i - 1][2] == 0 or mat[i][1] == 0:
				mat[i][2] = 1
			else:
				mat[i][2] = 0
			diff[i - 2] = [i, 2]
	ans = []
	q = int(input())
	for quer in range(q):
		cor = input().strip().split(' ')
		cor = [int(x) for x in cor]
		if cor[0] >= 2 and cor[1] >= 2:
			cor = diff[cor[0] - cor[1]]
		if mat[cor[0]][cor[1]] == 1:
			ans.append('1')
		else:
			ans.append('0')
	print(''.join(ans))


t = int(input())
for ty in range(t):
	s1 = input()
	s2 = input()
	arr = []
	n = len(s1)
	m = len(s2)
	arr.append([])
	for i in range(-1, n):
		if i == -1:
			arr[0].append(0)
		else:
			arr[0].append(int(s1[i]))
	for i in range(m):
		arr.append([])
		arr[i + 1].append(int(s2[i]))
	for j in range(2):
		if m > j:
			for k in range(n):
				arr[j + 1].append((arr[j][k + 1] * arr[j + 1][k] + 1) % 2)
	for j in range(2):
		if n > j:
			for k in range(2, m):
				arr[k + 1].append((arr[k][j + 1] * arr[k + 1][j] + 1) % 2)
	q = int(input())
	s = ''
	for i in range(q):
		(x, y) = map(int, input().split())
		try:
			s += str(arr[x][y])
		except:
			if x == y:
				s += str(arr[2][2])
			elif x > y:
				s += str(arr[x - y + 2][2])
			else:
				s += str(arr[2][y - x + 2])
	print(s)


t = int(input())
for z in range(t):
	s1 = input()
	s2 = input()
	m = len(s1)
	n = len(s2)
	if n < 2 or m < 2:
		a = [[-1] * (m + 1) for i in range(n + 1)]
		for i in range(m):
			a[0][i + 1] = int(s1[i])
		for j in range(n):
			a[j + 1][0] = int(s2[j])
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if a[i - 1][j] == 0 or a[i][j - 1] == 0:
					a[i][j] = 1
				elif a[i - 1][j] == 1 and a[i][j - 1] == 1:
					a[i][j] = 0
		c = []
		q = int(input())
		for i in range(q):
			(x, y) = map(int, input().split())
			c.append(a[x][y])
		for i in range(q):
			print(c[i], end='')
		print()
	else:
		a1 = [[-1] * (m + 1) for i in range(3)]
		for i in range(m):
			a1[0][i + 1] = int(s1[i])
		a1[1][0] = int(s2[0])
		a1[2][0] = int(s2[1])
		a2 = [[-1] * 3 for i in range(n + 1)]
		for j in range(n):
			a2[j + 1][0] = int(s2[j])
		a2[0][1] = int(s1[0])
		a2[0][2] = int(s1[1])
		for i in range(1, 3):
			for j in range(1, m + 1):
				if a1[i - 1][j] == 0 or a1[i][j - 1] == 0:
					a1[i][j] = 1
				elif a1[i - 1][j] == 1 and a1[i][j - 1] == 1:
					a1[i][j] = 0
		for i in range(1, n + 1):
			for j in range(1, 3):
				if a2[i - 1][j] == 0 or a2[i][j - 1] == 0:
					a2[i][j] = 1
				elif a2[i - 1][j] == 1 and a2[i][j - 1] == 1:
					a2[i][j] = 0
		c = []
		q = int(input())
		for i in range(q):
			(x, y) = map(int, input().split())
			if x <= 2:
				c.append(a1[x][y])
			elif y <= 2:
				c.append(a2[x][y])
			elif x < y:
				c.append(a1[2][y - (x - 2)])
			else:
				c.append(a2[x - (y - 2)][2])
		for i in range(q):
			print(c[i], end='')
		print()


for _ in range(int(input())):
	c = '0' + input()
	r = '0' + input()
	m = len(c)
	n = len(r)
	rd = [0] * n
	cd = [0] * m
	for i in range(1, n):
		if r[i] == '1' and r[i - 1] == '0':
			rd[i] = i
		else:
			rd[i] = rd[i - 1]
	for i in range(1, m):
		if c[i] == '1' and c[i - 1] == '0':
			cd[i] = i
		else:
			cd[i] = cd[i - 1]
	ans = ''
	for i in range(int(input())):
		f = 0
		(x, y) = map(int, input().split())
		if x == 1 and c[y] == '0' or (y == 1 and r[x] == '0'):
			f = 1
		if x == 1:
			k = cd[y]
			if k > 1:
				if (y - k) % 2 == 1:
					f = 1
			elif k == 1:
				if (y - k) % 2 == 0:
					if r[1] == '0':
						f = 1
				elif r[1] == '1':
					f = 1
		elif y == 1:
			k = rd[x]
			if k > 1:
				if (x - k) % 2 == 1:
					f = 1
			elif k == 1:
				if (x - k) % 2 == 0:
					if c[1] == '0':
						f = 1
				elif c[1] == '1':
					f = 1
		elif x == y:
			if x >= 2:
				if (r[2] == '1' or c[2] == '1') and (r[1] == '0' or c[1] == '0'):
					f = 1
			elif r[1] == '0' or c[1] == '0':
				f = 1
		elif x < y:
			k = cd[y - (x - 2)]
			if k > 1:
				if (x - 1 + y - k) % 2 != 0:
					f = 1
			elif k == 1:
				if c[2] == '0':
					if (x + y - 3) % 2 == 1:
						if r[2] == '1' and r[1] == '0':
							f = 1
					elif r[2] == '0' or r[1] == '1':
						f = 1
				elif (x - 1 + y - 1) % 2 == 0:
					if r[1] == '0':
						f = 1
				elif r[1] == '1':
					f = 1
			elif (x + y - 3) % 2 == 0:
				if r[2] == '0':
					f = 1
			elif r[2] == '1':
				f = 1
		else:
			k = rd[x - (y - 2)]
			if k > 1:
				if (x - k + y - 1) % 2 != 0:
					f = 1
			elif k == 1:
				if r[2] == '0':
					if (x + y - 3) % 2 == 1:
						if c[2] == '1' and c[1] == '0':
							f = 1
					elif c[2] == '0' or c[1] == '1':
						f = 1
				elif (x - 1 + y - 1) % 2 == 0:
					if c[1] == '0':
						f = 1
				elif c[1] == '1':
					f = 1
			elif (x + y - 3) % 2 == 0:
				if c[2] == '0':
					f = 1
			elif c[2] == '1':
				f = 1
		if f == 1:
			ans += '1'
		else:
			ans += '0'
	print(ans)


t = int(input())
for i in range(t):
	sm = input()
	sn = input()
	am = []
	an = []
	am1 = []
	an1 = []
	if sn == '':
		sn = '1'
		sn = sn + '1'
	if sm == '':
		sm = '1'
		sm = sm + '1'
	if sm[0] == '0' or sn[0] == '0':
		am.append('1')
		an.append('1')
	else:
		am.append('0')
		an.append('0')
	for j in range(1, len(sm)):
		if sm[j] == '0' or am[j - 1] == '0':
			am.append('1')
		else:
			am.append('0')
	for j in range(1, len(sn)):
		if sn[j] == '0' or an[j - 1] == '0':
			an.append('1')
		else:
			an.append('0')
	if len(am) > 1 and len(an) > 1:
		if am[1] == '0' or an[1] == '0':
			am1.append('1')
			an1.append('1')
		else:
			am1.append('0')
			an1.append('0')
		for j in range(1, len(am) - 1):
			if am[j + 1] == '0' or am1[j - 1] == '0':
				am1.append('1')
			else:
				am1.append('0')
		for j in range(1, len(an) - 1):
			if an[j + 1] == '0' or an1[j - 1] == '0':
				an1.append('1')
			else:
				an1.append('0')
	q = int(input())
	output = ''
	for j in range(q):
		(x, y) = [int(j) for j in input().split(' ')]
		if x == 1 or y == 1:
			if x > y:
				output = output + an[x - y]
			else:
				output = output + am[y - x]
		elif x > y:
			output = output + an1[x - y]
		else:
			output = output + am1[y - x]
	print(output)


def oh(c, r, d):
	for i in range(1, c + 1):
		if d[0, i] == 'll' or d[1, i - 1] == 'll' or d[0, i] == 0 or (d[1, i - 1] == 0):
			d[1, i] = 'w'
		else:
			d[1, i] = 'll'
	for i in range(1, r + 1):
		if d[i, 0] == 'll' or d[i - 1, 1] == 'll' or d[i, 0] == 0 or (d[i - 1, 1] == 0):
			d[i, 1] = 'w'
		else:
			d[i, 1] = 'll'
	if r >= 2:
		for i in range(2, c + 1):
			if d[1, i] == 'll' or d[2, i - 1] == 'll':
				d[2, i] = 'w'
			else:
				d[2, i] = 'll'
	if c >= 2:
		for i in range(2, r + 1):
			if d[i, 1] == 'll' or d[i - 1, 2] == 'll':
				d[i, 2] = 'w'
			else:
				d[i, 2] = 'll'
t = int(input())
for i in range(t):
	cx = input()
	rx = input()
	cl = len(cx)
	rl = len(rx)
	d = {}
	d[0, 0] = 'X'
	for i in range(cl):
		d[0, i + 1] = int(cx[i])
	for i in range(rl):
		d[i + 1, 0] = int(rx[i])
	oh(cl, rl, d)
	x = int(input())
	for i in range(x):
		(l, r) = input().split(' ')
		l = int(l)
		r = int(r)
		if (l, r) in d:
			sz = d[l, r]
		else:
			xz1 = r - 2
			xz2 = l - 2
			if xz1 < xz2:
				l = l - xz1
				sz = d[l, 2]
			else:
				r = r - xz2
				sz = d[2, r]
		if sz == 'w':
			print(1, end='')
		else:
			print(0, end='')
	print()


T = int(input())
for _ in range(T):
	Mstr = [int(x) for x in input().strip()]
	Nstr = [int(x) for x in input().strip()]
	(M, N) = (len(Mstr) + 1, len(Nstr) + 1)
	nrr = [[0]]
	nrr[0].extend(Nstr)
	nrr.extend([[0] * N for i in range(2)])
	mrr = [[0] * 3 for i in range(M)]
	(p, q) = (Mstr[0], Nstr[0])
	mrr[1][0] = p
	p = p & q
	mrr[1][1] = p
	nrr[1][1] = p
	for i in range(2, M):
		k = Mstr[i - 1]
		mrr[i][0] = k
		if k:
			mrr[i][1] = k ^ mrr[i - 1][1]
		else:
			mrr[i][1] = 0
	for i in range(2, N):
		k = nrr[0][i]
		if k == 0:
			nrr[1][i] = 0
		else:
			nrr[1][i] = k ^ nrr[1][i - 1]
	for i in range(1, 3):
		try:
			mrr[0][i] = nrr[0][i]
			nrr[i][0] = mrr[i][0]
			if i > 1:
				nrr[i][1] = mrr[i][1]
				mrr[1][i] = nrr[1][i]
				tmp = ((mrr[i][i - 1] | mrr[i - 1][i]) + 1) % 2
				(nrr[i][i], mrr[i][i]) = (tmp, tmp)
		except IndexError:
			pass
	for i in range(3, N):
		nrr[2][i] = not nrr[2][i - 1] | nrr[1][i]
	for i in range(3, M):
		mrr[i][2] = not mrr[i - 1][2] | mrr[i][1]
	Q = int(input())
	ans = ''
	for k in range(Q):
		(x, y) = [int(x) for x in input().strip().split(' ')]
		if x > 2 and y > 2:
			if x > y:
				if nrr[2][x - y + 2]:
					ans += '0'
				else:
					ans += '1'
			elif mrr[y - x + 2][2]:
				ans += '0'
			else:
				ans += '1'
		elif x < y:
			if mrr[y][x]:
				ans += '0'
			else:
				ans += '1'
		elif nrr[y][x]:
			ans += '0'
		else:
			ans += '1'
	print(ans)


for _ in range(int(input())):
	sm = input()
	sn = input()
	(n, m) = (len(sn), len(sm))
	a = {0: {}}
	for j in range(m):
		a[0][j + 1] = int(sm[j])
	for i in range(n):
		a[i + 1] = {0: int(sn[i])}
	for i in range(1, n + 1):
		for j in range(1, min(3, m + 1)):
			a[i][j] = int(not a[i - 1][j] & a[i][j - 1])
	for i in range(1, min(3, n + 1)):
		for j in range(1, m + 1):
			a[i][j] = int(not a[i - 1][j] & a[i][j - 1])
	r = ''
	for _ in range(int(input())):
		(x, y) = map(int, input().split())
		t = min(x, y) - 2
		if t > 0:
			x -= t
			y -= t
		r += str(a[x][y])
	print(r)


t = int(input())
for i in range(t):
	m = input().rstrip()
	n = input().rstrip()
	a = len(m)
	b = len(n)
	h = [2 for x in range(a)]
	v = [2 for y in range(b)]
	oh = [2 for x in range(a - 1)]
	ov = [2 for y in range(b - 1)]
	if m[0] == '0' or n[0] == '0':
		h[0] = 1
		v[0] = 1
	else:
		h[0] = 0
		v[0] = 0
	for ii in range(1, a):
		if m[ii] == '0':
			h[ii] = 1
		elif h[ii - 1] == 1:
			h[ii] = 0
		else:
			h[ii] = 1
	for ii in range(1, b):
		if n[ii] == '0':
			v[ii] = 1
		elif v[ii - 1] == 1:
			v[ii] = 0
		else:
			v[ii] = 1
	if a > 1 and b > 1:
		if h[1] == 1 and v[1] == 1:
			oh[0] = 0
			ov[0] = 0
		else:
			oh[0] = 1
			ov[0] = 1
		for g in range(1, a - 1):
			if h[g + 1] == 1 and oh[g - 1] == 1:
				oh[g] = 0
			else:
				oh[g] = 1
		for g in range(1, b - 1):
			if v[g + 1] == 1 and ov[g - 1] == 1:
				ov[g] = 0
			else:
				ov[g] = 1
	q = int(input())
	ans = ''
	for j in range(q):
		(x, y) = [int(xx) for xx in input().split()]
		mini = min(x - 1, y - 1)
		if mini > 1:
			x = x - 1
			y = y - 1
			if x > y:
				ans += str(ov[x - y])
			else:
				ans += str(oh[y - x])
		else:
			x = x - 1
			y = y - 1
			if x == 0:
				ans += str(h[y])
			elif y == 0:
				ans += str(v[x])
			elif x == 1:
				ans += str(oh[y - 1])
			elif y == 1:
				ans += str(ov[x - 1])
	print(ans)


num_cases = int(input())
for _ in range(num_cases):
	zero_row = ['0']
	zero_row.extend(list(input()))
	zero_column = ['0']
	zero_column.extend(list(input()))
	col_limit = min(6, len(zero_row))
	row_limit = min(6, len(zero_column))
	board = list()
	board.append(zero_row)
	for row_pos in range(1, row_limit):
		board.append(list())
		board[row_pos].append(zero_column[row_pos])
		for pos in range(1, len(zero_row)):
			if board[row_pos][pos - 1] == '0' or board[row_pos - 1][pos] == '0':
				board[row_pos].append('1')
			else:
				board[row_pos].append('0')
	for row_pos in range(row_limit, len(zero_column)):
		board.append(list())
		board[row_pos].append(zero_column[row_pos])
		for pos in range(1, col_limit):
			if board[row_pos][pos - 1] == '0' or board[row_pos - 1][pos] == '0':
				board[row_pos].append('1')
			else:
				board[row_pos].append('0')
	num_queries = int(input())
	solutions = list()
	for pos in range(num_queries):
		(row, column) = map(int, input().split())
		if row < row_limit or column < col_limit:
			solutions.append(board[row][column])
		else:
			minimum = min(row, column)
			solutions.append(board[row - minimum + 5][column - minimum + 5])
	print(''.join(solutions))


from collections import Counter
t = int(input())
for _ in range(t):
	m = input().strip()
	n = input().strip()
	m = list(m)
	n = list(n)
	m = [int(i) for i in m]
	n = [int(i) for i in n]
	cols = len(m)
	rows = len(n)
	matrix = []
	diag = []
	pnt = dict()
	for i in range(3):
		if i < rows:
			rowi = []
			if i == 0:
				x = not (n[i] and m[0])
				rowi.append(x)
				if x == False:
					diag.append(0)
					pnt[0] = [0, 0]
			else:
				x = not (n[i] and matrix[i - 1][0])
				rowi.append(x)
				if x == False:
					diag.append(i)
					if i not in pnt:
						pnt[i] = [i, 0]
			for j in range(1, cols):
				if i == 0:
					x = not (rowi[-1] and m[j])
					rowi.append(x)
					if x == False:
						diff = -1 * j
						diag.append(diff)
						if diff not in pnt:
							pnt[diff] = [i, j]
				else:
					x = not (rowi[-1] and matrix[i - 1][j])
					rowi.append(x)
					if x == False:
						diff = i - j
						diag.append(diff)
						if diff not in pnt:
							pnt[diff] = [i, j]
			matrix.append(rowi)
		else:
			break
	for i in range(3, rows):
		rowi = []
		x = not (n[i] and matrix[i - 1][0])
		rowi.append(x)
		if x == False:
			diag.append(i)
			if i not in pnt:
				pnt[i] = [i, 0]
		for j in range(1, 3):
			if j < cols:
				x = not (rowi[-1] and matrix[i - 1][j])
				rowi.append(x)
				if x == False:
					diff = i - j
					diag.append(diff)
					if diff not in pnt:
						pnt[diff] = [i, j]
			else:
				break
		matrix.append(rowi)
	c = Counter(diag)
	q = int(input())
	ans = ''
	for _ in range(q):
		(x, y) = map(int, input().split())
		diff = x - y
		if c[diff] > 0:
			if x > pnt[diff][0]:
				ans += '0'
			else:
				ans += '1'
		else:
			ans += '1'
	print(ans)


from collections import defaultdict
for i in range(int(input())):

	def setbdp(bdp, fdp, s1, s2):
		bdp[1] = min(int(s1[0]), int(s2[0]))
		fdp[1] = min(int(s1[0]), int(s2[0]))
	s = ''

	def nm(s1, s2):
		(n, m) = (len(s2), len(s1))
		return (n, m)
	d = defaultdict(int)
	s1 = input()
	s2 = input()
	(n, m) = nm(s1, s2)
	fdp = [0] * (m + 1)
	bdp = [0] * (n + 1)
	f1dp = [0] * (m + 1)
	b1dp = [0] * (n + 1)
	setbdp(bdp, fdp, s1, s2)
	for i in range(2, n + 1):
		bdp[i] = min(1 - bdp[i - 1], int(s2[i - 1]))
	for i in range(2, m + 1):
		fdp[i] = min(1 - fdp[i - 1], int(s1[i - 1]))
	try:
		d[0] = f1dp[2] = b1dp[2] = min(1 - fdp[2], 1 - bdp[2])
	except:
		pass
	for i in range(3, n + 1):
		b1dp[i] = min(1 - bdp[i], 1 - b1dp[i - 1])
		d[i - 2] = b1dp[i]
	for i in range(3, m + 1):
		f1dp[i] = min(1 - fdp[i], 1 - f1dp[i - 1])
		d[2 - i] = f1dp[i]
	for i in range(int(input())):
		(l, r) = map(int, input().split())
		if l == 1:
			s += str(1 - fdp[r])
		elif r == 1:
			s += str(1 - bdp[l])
		else:
			s += str(1 - d[l - r])
	print(s)


def get_next(row, col, flag):
	next_col = []
	next_row = []
	for elem in row[flag:]:
		if len(next_row) <= 0:
			next_row.append(not (int(elem) and int(col[0])))
		else:
			next_row.append(not (int(elem) and next_row[-1]))
	for elem in col[1:]:
		if len(next_col) <= 0:
			next_col.append(not (int(elem) and next_row[0]))
		else:
			next_col.append(not (int(elem) and next_col[-1]))
	return (next_row, next_col)
for i in range(int(input())):
	row = list(input())
	col = list(input())
	(flag, s, next_row2, next_col2) = (0, '', [], [])
	(next_row, next_col) = get_next(row, col, flag)
	if len(row) >= 2 and len(col) >= 2:
		flag = 1
		(next_row2, next_col2) = get_next(next_row, next_col, flag)
	for j in range(int(input())):
		(y, x) = map(int, input().split())
		if x > 1 and y > 1:
			if x >= y:
				s += str(int(next_row2[x - y]))
			else:
				s += str(int(next_col2[max(0, y - x - 1)]))
		elif x >= y:
			s += str(int(next_row[x - y]))
		elif y > x:
			s += str(int(next_col[max(0, y - x - 1)]))
	print(s)


t = int(input())
for _ in range(t):
	X = [int(c == '1') for c in input().strip()]
	m = len(X)
	Y = [int(c == '1') for c in input().strip()]
	n = len(Y)
	B = [[0] * (m + 1 if i < 2 or i == n else 3) for i in range(n + 1)]
	for i in range(n):
		B[i][-1] = Y[i]
	for j in range(m):
		B[-1][j] = X[j]
	for i in range(min(n, 2)):
		for j in range(m):
			B[i][j] = int(0 in (B[i - 1][j], B[i][j - 1]))
	for j in range(min(m, 2)):
		for i in range(2, n):
			B[i][j] = int(0 in (B[i - 1][j], B[i][j - 1]))
	destiny = [0] * (n + m + 1)
	j = 1
	for i in range(1, n):
		destiny[i - j] = B[i][j]
	i = 1
	for j in range(2, m):
		destiny[i - j] = B[i][j]
	q = int(input())
	R = []
	for _ in range(q):
		(i, j) = [int(x) - 1 for x in input().split()]
		if min(i, j) < 2:
			R.append(B[i][j])
		else:
			R.append(destiny[i - j])
	print(*R, sep='')


def fun(str1, str2):
	list1 = [int(i) for i in str1]
	list2 = [int(i) for i in str2]
	v = int(not (list1[0] and list2[0]))
	a1 = [v]
	b1 = [v]
	for i in range(1, len(str1)):
		v = int(not (a1[-1] and list1[i]))
		a1.append(v)
	for i in range(1, len(str2)):
		v = int(not (b1[-1] and list2[i]))
		b1.append(v)
	if len(str1) >= 2 and len(str2) >= 2:
		v = int(not (a1[1] and b1[1]))
		a2 = [v]
		b2 = [v]
		for i in range(2, len(str1)):
			v = int(not (a2[-1] and a1[i]))
			a2.append(v)
		for i in range(2, len(str2)):
			v = int(not (b2[-1] and b1[i]))
			b2.append(v)
	q = int(input())
	for x in range(q):
		(i, j) = map(int, input().split())
		if i == 1 or j == 1:
			diff = i - j
			if diff >= 0:
				print(b1[diff], end='')
			else:
				print(a1[-diff], end='')
		else:
			diff = i - j
			if diff >= 0:
				print(b2[diff], end='')
			else:
				print(a2[-diff], end='')
	print()
test = int(input())
for snju in range(test):
	str1 = input().strip()
	str2 = input().strip()
	fun(str1, str2)


import sys

def pmat(a):
	(r, c) = (len(a), len(a[0]))
	for i in range(r - 1, -1, -1):
		for j in range(c):
			if i == 0 and j == 0:
				print(a[i][j], '', end='')
			elif i == 0 or j == 0:
				print(a[i][j] ^ 1, '', end='')
			else:
				print(a[i][j], '', end='')
		print('')
	print('')

def force(m, n):
	(r, c) = (len(n), len(m))
	res = [[0] * (c + 1) for i in range(r + 1)]
	res[0] = ['x'] + m
	for i in range(r):
		res[i + 1][0] = n[i]
	for i in range(1, r + 1):
		for j in range(1, c + 1):
			(l, d) = (res[i - 1][j], res[i][j - 1])
			res[i][j] = max(l ^ 1, d ^ 1)
	pmat(res)
	ans = ''
	for q in range(int(input())):
		(x, y) = map(int, input().split())
		ans += str(res[x][y])
	return ans

def solve(m, n):
	(r, c) = ([0] * (len(m) + 1), [0] * (len(n) + 1))
	r[0] = n[0]
	for i in range(1, len(m) + 1):
		r[i] = max(r[i - 1] ^ 1, m[i - 1] ^ 1)
	c[0] = m[0]
	for i in range(1, len(n) + 1):
		c[i] = max(c[i - 1] ^ 1, n[i - 1] ^ 1)
	if len(m) > 1 and len(n) > 1:
		(r2, c2) = ([0] * len(m), [0] * len(n))
		r2[0] = c[2]
		for i in range(2, len(r)):
			r2[i - 1] = max(r2[i - 2] ^ 1, r[i] ^ 1)
		c2[0] = r[2]
		for i in range(2, len(c)):
			c2[i - 1] = max(c2[i - 2] ^ 1, c[i] ^ 1)
	ans = ''
	for q in range(int(input())):
		(x, y) = map(int, input().split())
		if x > 1 and y > 1:
			sub = min(x, y) - 1
			(x, y) = (x - sub, y - sub)
			if x < y:
				ans += str(r2[y])
			else:
				ans += str(c2[x])
		else:
			sub = min(x, y) - 1
			(x, y) = (x - sub, y - sub)
			if x < y:
				ans += str(r[y])
			else:
				ans += str(c[x])
	return ans
for _ in range(int(input())):
	m = [int(x) for x in input()]
	n = [int(x) for x in input()]
	print(solve(m, n))


def toggle(number):
	if number == 1:
		return 0
	else:
		return 1

def make_dict():
	mid1 = int(N[0][0]) and int(M[0][0])
	k = '1_1'
	dictionary[k] = mid1
	mid = mid1
	for i in range(2, len(N[0]) + 1):
		k = str(i) + '_' + str(1)
		dictionary[k] = int(N[0][i - 1]) and toggle(mid)
		mid = dictionary[k]
	mid = mid1
	for i in range(2, len(M[0]) + 1):
		k = str(1) + '_' + str(i)
		dictionary[k] = int(M[0][i - 1]) and toggle(mid)
		mid = dictionary[k]
	if len(N[0]) > 1 and len(M[0]) > 1:
		mid2 = toggle(dictionary['2_1']) and toggle(dictionary['1_2'])
		k = '2_2'
		dictionary[k] = mid2
		mid = mid2
		for i in range(3, len(N[0]) + 1):
			k = str(i) + '_' + '2'
			dictionary[k] = toggle(dictionary[str(i) + '_' + '1']) and toggle(mid)
			mid = dictionary[k]
		mid = mid2
		for i in range(3, len(M[0]) + 1):
			k = '2' + '_' + str(i)
			dictionary[k] = toggle(dictionary['1' + '_' + str(i)]) and toggle(mid)
			mid = dictionary[k]

def win(x, y):
	k = str(x) + '_' + str(y)
	return dictionary[k]
T = int(input())
for t in range(T):
	M = input().strip().split(' ')
	N = input().strip().split(' ')
	Q = int(input())
	dictionary = {}
	result = ''
	make_dict()
	for q in range(Q):
		(x, y) = input().strip().split(' ')[0:2]
		if int(x) > 1 and int(y) > 1:
			c = int(y) - int(x)
			if c == 0:
				(x, y) = (2, 2)
			elif c < 0:
				x = abs(c) + 2
				y = 2
			elif c > 0:
				y = c + 2
				x = 2
		result += str(toggle(win(int(x), int(y))))
	print(result)


t = int(input())
for _ in range(t):
	m = input().strip()
	n = input().strip()
	(sm, sn) = (len(m), len(n))
	arr = []
	for i in range(3):
		arr.append([0 for x in range(sm + 1)])
	i = 3
	while i <= sn:
		arr.append([0 for x in range(3)])
		i += 1
	for i in range(1, sm + 1):
		arr[0][i] = int(m[i - 1])
	for i in range(1, sn + 1):
		arr[i][0] = int(n[i - 1])
	for j in range(1, 3):
		for i in range(j, sm + 1):
			arr[j][i] = int(arr[j][i - 1] == 0 or arr[j - 1][i] == 0)
		for i in range(j, sn + 1):
			arr[i][j] = int(arr[i - 1][j] == 0 or arr[i][j - 1] == 0)
	q = int(input())
	s = ''
	for i in range(q):
		(x, y) = map(int, input().strip().split())
		if x > 2 and y > 2:
			if x < y:
				diff = x - 2
				x = 2
				y -= diff
			else:
				diff = y - 2
				y = 2
				x -= diff
		s += str(arr[x][y])
	print(s)


def solve(X, Y, qq):
	X = [0] + list(map(int, X))
	Y = [0] + list(map(int, Y))
	X1 = [Y[1]]
	Y1 = [X[1]]
	X2 = [Y[2] if len(Y) > 2 else 0]
	Y2 = [X[2] if len(X) > 2 else 0]
	for i in range(1, len(X)):
		X1 += [0 if X[i] + X1[i - 1] > 1 else 1]
		X2 += [0 if X1[i] + X2[i - 1] > 1 else 1]
	for i in range(1, len(Y)):
		Y1 += [0 if Y[i] + Y1[i - 1] > 1 else 1]
		Y2 += [0 if Y1[i] + Y2[i - 1] > 1 else 1]
	ret = []
	for (x, y) in qq:
		z = 0
		if x == 1:
			z = X1[y]
		elif y == 1:
			z = Y1[x]
		else:
			m = min(x, y)
			x -= m - 2
			y -= m - 2
			if x == 2:
				z = X2[y]
			else:
				z = Y2[x]
		ret += [z]
	return ''.join(map(str, ret))
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	X = f.readline()[:-1]
	Y = f.readline()[:-1]
	q = int(f.readline())
	qq = []
	for j in range(q):
		(x, y) = map(int, f.readline().split())
		qq += [(x, y)]
	z = solve(X, Y, qq)
	print(z)


import math
from collections import defaultdict as dd
import heapq
from bisect import bisect_left as bl

def make(x1, x2, l, t):
	for i in range(t, l):
		if x1[i] == 1 and x2[-1] == 1:
			x2.append(0)
		else:
			x2.append(1)
	return x2
for _ in range(int(input())):
	c1 = [int(i) for i in input()]
	m = len(c1)
	r1 = [int(i) for i in input()]
	n = len(r1)
	if r1[0] == 0 or c1[0] == 0:
		(c2, r2) = ([1], [1])
	else:
		(c2, r2) = ([0], [0])
	c2 = make(c1, c2, m, 1)
	r2 = make(r1, r2, n, 1)
	if n > 1 and m > 1:
		if c2[1] == 0 or r2[1] == 0:
			(c3, r3) = ([1], [1])
		else:
			(c3, r3) = ([0], [0])
		c3 = make(c2, c3, m, 2)
		r3 = make(r2, r3, n, 2)
	ans = ''
	for q in range(int(input())):
		(x, y) = [int(i) for i in input().split(' ')]
		if x == 1:
			ans += str(c2[y - 1])
		elif y == 1:
			ans += str(r2[x - 1])
		elif x < y:
			ans += str(c3[y - x])
		else:
			ans += str(r3[x - y])
	print(ans)


from collections import defaultdict

def winner(x, y, win, lose, wp):
	if not win:
		return (x + y) % 2
	if not lose:
		if x == 1 or y == 1:
			return 1
		return (x + y) % 2
	if x == 1 or x == 2 or y == 1 or (y == 2):
		return wp[x, y]
	mn = min(x, y)
	dif = mn - 2
	(x1, y1) = (x - dif, y - dif)
	z = wp[x1, y1]
	return z
for _ in range(int(input())):
	m = input()
	n = input()
	ans = ''
	(lm, ln) = (len(m), len(n))
	win = defaultdict(int)
	lose = defaultdict(int)
	wp = defaultdict(int)
	for i in range(lm):
		if m[i] == '1':
			lose[0, i + 1] = 1
		else:
			win[0, i + 1] = 1
	for i in range(ln):
		if n[i] == '1':
			lose[i + 1, 0] = 1
		else:
			win[i + 1, 0] = 1
	wp[1, 1] = win[1, 0] or win[0, 1]
	for i in range(2, ln + 1):
		if win[i, 0]:
			wp[i, 1] = 1
		else:
			wp[i, 1] = int(not wp[i - 1, 1])
	for i in range(2, lm + 1):
		if win[0, i]:
			wp[1, i] = 1
		else:
			wp[1, i] = int(not wp[1, i - 1])
	for i in range(2, ln + 1):
		wp[i, 2] = int(not wp[i - 1, 2] & wp[i, 1])
	for i in range(2, lm + 1):
		wp[2, i] = int(not wp[2, i - 1] & wp[1, i])
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		ans += str(winner(x, y, win, lose, wp))
	print(ans)


def tog(n):
	if n == 1:
		return 0
	if n == 0:
		return 1
	return 'WTF'

def print_grid(grid, N, M):
	for a in range(N):
		for b in range(M):
			if a <= 2 or b <= 2:
				print(grid[a][b], end=' ')
			elif a <= b:
				print(grid[2][b - (a - 2)], end=' ')
			else:
				print(grid[a - (b - 2)][2], end=' ')
		print()

def fn():
	row0 = '-' + input()
	column0 = '-' + input()
	C = len(row0)
	R = len(column0)
	C2 = min(3, C)
	R2 = min(3, R)
	grid_top = [[-1] * C for i in range(R2)]
	grid_left = [[-1] * C2 for i in range(R)]
	for i in range(0, R2):
		try:
			temp = int(column0[i])
			grid_top[i][0] = temp
		except:
			grid_top[i][0] = column0[i]
	for j in range(1, C):
		grid_top[0][j] = int(row0[j])
		if j == 1:
			grid_top[1][j] = grid_top[0][j] * grid_top[1][j - 1]
			try:
				grid_top[2][j] = grid_top[2][j - 1] * tog(grid_top[1][j])
			except:
				pass
		else:
			grid_top[1][j] = grid_top[0][j] * tog(grid_top[1][j - 1])
			try:
				grid_top[2][j] = tog(grid_top[1][j]) * tog(grid_top[2][j - 1])
			except:
				pass
	for j in range(0, C2):
		try:
			temp = int(row0[j])
			grid_left[0][j] = temp
		except:
			grid_left[0][j] = row0[j]
	for i in range(1, R):
		grid_left[i][0] = int(column0[i])
		if i == 1:
			grid_left[i][1] = grid_left[i - 1][1] * grid_left[i][0]
			try:
				grid_left[i][2] = grid_left[i - 1][2] * tog(grid_left[i][1])
			except:
				pass
		else:
			grid_left[i][1] = grid_left[i][0] * tog(grid_left[i - 1][1])
			try:
				grid_left[i][2] = tog(grid_left[i - 1][2]) * tog(grid_left[i][1])
			except:
				pass
	Q = int(input())
	for i in range(Q):
		a = input().split()
		p = int(a[0])
		q = int(a[1])
		if p <= 2:
			print(tog(grid_top[p][q]), end='')
		elif q <= 2:
			print(tog(grid_left[p][q]), end='')
		elif p == q:
			print(tog(grid_top[2][2]), end='')
		elif p > q:
			print(tog(grid_left[p - (q - 2)][2]), end='')
		elif p < q:
			print(tog(grid_top[2][q - (p - 2)]), end='')
T = int(input())
for i in range(T):
	fn()
	print()


taste_cash = int(input())
for f_k in range(taste_cash):
	s1 = input()
	s2 = input()
	m = len(s1)
	n = len(s2)
	a1 = []
	if s1[0] == s2[0] == '1':
		a1.append('0')
	else:
		a1.append('1')
	for j in range(1, m):
		if a1[-1] == '1' and s1[j] == '1':
			a1.append('0')
		else:
			a1.append('1')
	a2 = []
	a2.append(a1[0])
	for j in range(1, n):
		if a2[-1] == '1' and s2[j] == '1':
			a2.append('0')
		else:
			a2.append('1')
	if n == 1:
		s = ''
		nq = int(input())
		for kk in range(nq):
			(x, y) = [int(i) - 1 for i in input().split(' ')]
			s += a1[y]
		print(s)
	elif m == 1:
		s = ''
		nq = int(input())
		for kk in range(nq):
			(x, y) = [int(i) - 1 for i in input().split(' ')]
			s += a2[y]
		print(s)
	else:
		b1 = [a2[1]]
		for j in range(1, m):
			if b1[-1] == '1' and a1[j] == '1':
				b1.append('0')
			else:
				b1.append('1')
		b2 = [a1[1]]
		for j in range(1, n):
			if b2[-1] == '1' and a2[j] == '1':
				b2.append('0')
			else:
				b2.append('1')
		nq = int(input())
		s = ''
		for kk in range(nq):
			(x, y) = [int(i) - 1 for i in input().split(' ')]
			if x == 0:
				s += a1[y]
			elif y == 0:
				s += a2[x]
			elif x == y:
				s += b2[1]
			elif x < y:
				s += b1[y - x + 1]
			else:
				s += b2[x - y + 1]
		print(s)


t = int(input())
for test in range(t):
	a = input()
	b = input()
	n = len(a)
	m = len(b)
	while n < 4:
		a += '0'
		n += 1
	while m < 4:
		b += '0'
		m += 1
	a1 = ''
	b1 = ''
	for i in a:
		a1 += str(1 - int(i))
	for i in b:
		b1 += str(1 - int(i))
	an = []
	for i in range(3):
		an.append([])
	for i in range(3):
		for j in range(n + 1):
			an[i].append(0)
	bn = []
	for i in range(m + 1):
		bn.append([])
	for i in range(m + 1):
		for j in range(3):
			bn[i].append(0)
	for i in range(1, 3):
		bn[0][i] = int(a1[i - 1])
	for i in range(1, m + 1):
		bn[i][0] = int(b1[i - 1])
	for i in range(1, n + 1):
		an[0][i] = int(a1[i - 1])
	for i in range(1, 3):
		an[i][0] = int(b1[i - 1])
	for i in range(1, 3):
		for j in range(1, n + 1):
			an[i][j] = 1 - max(an[i - 1][j], an[i][j - 1])
	for i in range(1, m + 1):
		for j in range(1, 3):
			bn[i][j] = 1 - max(bn[i - 1][j], bn[i][j - 1])
	ans = ''
	q = int(input())
	for i in range(q):
		(x, y) = map(int, input().split())
		x1 = min(x - 2, y - 2)
		if x < 3 and y < 3:
			ans += str(an[x][y])
		elif x < 3 and y >= 3:
			ans += str(an[x][y])
		elif x >= 3 and y < 3:
			ans += str(bn[x][y])
		elif x > y:
			ans += str(bn[x - x1][y - x1])
		else:
			ans += str(an[x - x1][y - x1])
	anw = ''
	for i in range(len(ans)):
		if ans[i] == '1':
			anw += '0'
		else:
			anw += '1'
	print(anw)


T = int(input())
for _ in range(T):
	(*C,) = map(int, input())
	N = len(C)
	(*D,) = map(int, input())
	M = len(D)
	dp_x = [[0] * (N + 1) for i in range(4)]
	for i in range(N):
		dp_x[0][i + 1] = C[i]
	for i in range(min(3, M)):
		dp_x[i + 1][0] = D[i]
	dp_y = [[0] * (M + 1) for i in range(4)]
	for i in range(M):
		dp_y[0][i + 1] = D[i]
	for i in range(min(3, N)):
		dp_y[i + 1][0] = C[i]
	for i in range(3):
		for j in range(N):
			if dp_x[i][j + 1] == dp_x[i + 1][j] == 1:
				dp_x[i + 1][j + 1] = 0
			else:
				dp_x[i + 1][j + 1] = 1
		for j in range(M):
			if dp_y[i][j + 1] == dp_y[i + 1][j] == 1:
				dp_y[i + 1][j + 1] = 0
			else:
				dp_y[i + 1][j + 1] = 1
	ans = []
	Q = int(input())
	for q in range(Q):
		(x, y) = map(int, input().split())
		if x < 4 and y < 4:
			assert dp_x[x][y] == dp_y[y][x]
			ans.append(str(dp_x[x][y]))
		elif x < 4:
			ans.append(str(dp_x[x][y]))
		elif y < 4:
			ans.append(str(dp_y[y][x]))
		else:
			z = min(x, y) - 3
			if x > y:
				ans.append(str(dp_y[y - z][x - z]))
			else:
				ans.append(str(dp_x[x - z][y - z]))
	print(*ans, sep='')


import sys
from collections import defaultdict as dd
from itertools import permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
import heapq
mod = 10 ** 9 + 7

def ri(flag=0):
	if flag == 0:
		return [int(i) for i in input().split()]
	else:
		return int(input())
for _ in range(ri(1)):
	a = input()
	b = input()
	m = len(a)
	n = len(b)
	mat = [dd(int) for i in range(n + 1)]
	for i in range(m):
		mat[0][i + 1] = int(a[i])
	for i in range(n):
		mat[i + 1][0] = int(b[i])
	for i in range(1, min(3, n + 1)):
		for j in range(1, m + 1):
			mat[i][j] = max(mat[i - 1][j] ^ 1, mat[i][j - 1] ^ 1)
	for i in range(1, n + 1):
		for j in range(1, min(3, m + 1)):
			mat[i][j] = max(mat[i - 1][j] ^ 1, mat[i][j - 1] ^ 1)
	q = ri(1)
	ans = []
	for i in range(q):
		(l, r) = ri()
		if l <= 2 or r <= 2:
			pass
		else:
			k1 = l - 2
			k2 = r - 2
			if l > r:
				l = l - k2
				r = r - k2
			elif l < r:
				l = l - k1
				r = r - k1
			else:
				l = 2
				r = 2
		ans.append(str(mat[l][r]))
	print(''.join(ans))


t = int(input())
for _ in range(t):
	m = input()
	n = input()
	ml = len(m)
	nl = len(n)
	ar1 = [0] * ml
	ar2 = [0] * nl
	arr1 = [0] * (ml - 1)
	arr2 = [0] * (nl - 1)
	if m[0] == '0' or n[0] == '0':
		ar1[0] = 'w'
		ar2[0] = 'w'
	else:
		ar1[0] = 'l'
		ar2[0] = 'l'
	for i in range(1, ml):
		if m[i] == '0' or ar1[i - 1] == 'l':
			ar1[i] = 'w'
		else:
			ar1[i] = 'l'
	for i in range(1, nl):
		if n[i] == '0' or ar2[i - 1] == 'l':
			ar2[i] = 'w'
		else:
			ar2[i] = 'l'
	if ml > 1 and nl > 1:
		if ar1[1] == 'l' or ar2[1] == 'l':
			arr1[0] = 'w'
			arr2[0] = 'w'
		else:
			arr1[0] = 'l'
			arr2[0] = 'l'
		for i in range(2, ml):
			if ar1[i] == 'l' or arr1[i - 2] == 'l':
				arr1[i - 1] = 'w'
			else:
				arr1[i - 1] = 'l'
		for i in range(2, nl):
			if ar2[i] == 'l' or arr2[i - 2] == 'l':
				arr2[i - 1] = 'w'
			else:
				arr2[i - 1] = 'l'
	ans = ''
	for i in range(int(input())):
		(u, v) = tuple(map(int, input().split()))
		if u == 1:
			if ar1[v - 1] == 'l':
				ans += '0'
			else:
				ans += '1'
		elif v == 1:
			if ar2[u - 1] == 'l':
				ans += '0'
			else:
				ans += '1'
		else:
			mn = min(u, v) - 1
			u -= mn
			v -= mn
			if u == 1:
				if arr1[v - 1] == 'l':
					ans += '0'
				else:
					ans += '1'
			elif v == 1:
				if arr2[u - 1] == 'l':
					ans += '0'
				else:
					ans += '1'
	print(ans)