Cherry has a binary matrix $A$ consisting of $N$ rows and $M$ columns. The rows are numbered from $1$ to $N$, columns are numbered from $1$ to $M$. Element at row $i$ ($1$ ≤ $i$ ≤ $N$) and column $j$ ($1$ ≤ $j$ ≤ $M$) is denoted as $A_{ij}$. All elements of $A$ are either $0$ or $1$.
He performs $Q$ queries on matrix. Each query is provided by four integers $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ which define the rectangle, where ($x_{1}$, $y_{1}$) stands for the coordinates of the top left cell of the rectangle, while ($x_{2}$, $y_{2}$) stands for the coordinates of the bottom right cell. You need to flip all the bits i.e. ($0$ to $1$, $1$ to $0$) that are located fully inside the query rectangle.
Finally, print the matrix after performing all the queries.
Note: $x_{1}$ represents the row number while $y_{1}$ represents the column number.

-----Input:-----
- The first line of the input contains two integers $N$ and $M$ — the number of rows and the number of columns in the matrix.
- Each of the next $N$ lines contains a string of length $M$, where the $j^{th}$ character of $i^{th}$ line denotes the value of $A_{i,j}$. 
- Next line contains an integer $Q$ — the number of queries.
- Then follow $Q$ lines with queries descriptions. Each of them contains four space-seperated integers $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ — coordinates of the up left and bottom right cells of the query rectangle.

-----Output:-----
Print the matrix, in the form of $N$ strings, after performing all the queries.

-----Constraints-----
- $1 \leq N,M \leq 1000$
- $0 \leq  A_{ij}  \leq 1$
- $1 \leq Q \leq 10^6$
- $1 \leq x_{1} \leq x_{2} \leq N$
- $1 \leq y_{1} \leq y_{2} \leq M$

-----Sample Input:-----
2 2
00
00
3
1 1 1 1
2 2 2 2
1 1 2 2 

-----Sample Output:-----
01
10

-----Explanation:-----
Example case 1:
After processing the 1st query 1 1 1 1, matrix becomes:
[1000][1000]\begin{bmatrix} 10 \\ 00  \end{bmatrix}
After processing the 2nd query 2 2 2 2, the matrix becomes:
[1001][1001]\begin{bmatrix} 10 \\ 01  \end{bmatrix}
After processing the 3rd query 1 1 2 2, matrix becomes:
[0110][0110]\begin{bmatrix} 01 \\ 10  \end{bmatrix}
We need to output the matrix after processing all queries.

Source: codechef | Difficulty: HARD
Tags: Data structures

Range queries


Solutions:
import sys, os, io, time, copy, math, queue, bisect
from collections import deque
from functools import lru_cache
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
sys.setrecursionlimit(100000000)

def main():
	(n, m) = map(int, input().split())
	mat = []
	for _ in range(n):
		s = input()
		a = []
		for i in s:
			a.append(int(i))
		mat.append(a)
	Q = int(input())
	ans = [[0 for i in range(m + 1)] for j in range(n + 1)]
	for i in range(Q):
		(x1, y1, x2, y2) = map(int, input().split())
		x1 -= 1
		y1 -= 1
		x2 -= 1
		y2 -= 1
		ans[x1][y1] += 1
		ans[x2 + 1][y1] -= 1
		ans[x1][y2 + 1] -= 1
		ans[x2 + 1][y2 + 1] += 1
	for j in range(m + 1):
		for i in range(1, n + 1):
			ans[i][j] = ans[i - 1][j] + ans[i][j]
	for i in range(n + 1):
		for j in range(1, m + 1):
			ans[i][j] = ans[i][j - 1] + ans[i][j]
	for i in range(n):
		for j in range(m):
			mat[i][j] = (ans[i][j] + mat[i][j]) % 2
	for m in mat:
		for i in m:
			print(i, end='')
		print('')
main()


import math
import sys, collections
from sys import stdin, stdout

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def file():
	sys.stdin = open('input.py', 'r')
	sys.stdout = open('output.py', 'w')

def is_subsequence(x, y):
	x = list(x)
	for letter in y:
		if x and x[0] == letter:
			x.pop(0)
	return not x

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def getFloor(A, x):
	(left, right) = (0, len(A) - 1)
	(ind, floor) = (-1, -1)
	while left <= right:
		mid = (left + right) // 2
		if x < A[mid]:
			right = mid - 1
		else:
			floor = A[mid]
			ind = mid
			left = mid + 1
	return ind
mod = 10 ** 9 + 7

def main():
	(n, m) = get_ints()
	arr = []
	for i in range(n):
		s = input()
		arr.append(list(s))
	for i in range(n):
		for j in range(m):
			arr[i][j] = int(arr[i][j])
	temp = [[0 for i in range(m + 1)] for j in range(n + 1)]
	for que in range(int(input())):
		(x1, y1, x2, y2) = get_ints()
		temp[x1 - 1][y1 - 1] += 1
		temp[x2][y2] += 1
		temp[x1 - 1][y2] -= 1
		temp[x2][y1 - 1] -= 1
	for i in range(n + 1):
		for j in range(1, m + 1):
			temp[i][j] += temp[i][j - 1]
	for i in range(m + 1):
		for j in range(1, n + 1):
			temp[j][i] += temp[j - 1][i]
	for i in range(n):
		for j in range(m):
			if temp[i][j] % 2 == 0:
				print(arr[i][j], end='')
			elif arr[i][j] == 1:
				print(0, end='')
			else:
				print(1, end='')
		print()
main()


import sys
(n, m) = map(int, input().split())
dp = [[0 for j in range(m + 2)] for k in range(n + 2)]
a = []
for j in range(n):
	t = sys.stdin.readline().strip()
	a.append(list(t))
q = int(input())
for j in range(0, q):
	(x1, y1, x2, y2) = map(int, sys.stdin.readline().split())
	dp[x1][y1] += 1
	dp[x2 + 1][y2 + 1] += 1
	dp[x1][y2 + 1] -= 1
	dp[x2 + 1][y1] -= 1
for j in range(1, n + 1):
	for k in range(1, m + 1):
		dp[j][k] = dp[j][k] + dp[j - 1][k] + dp[j][k - 1] - dp[j - 1][k - 1]
		if dp[j][k] % 2 != 0:
			a[j - 1][k - 1] = int(a[j - 1][k - 1]) ^ 1
for j in range(n):
	print(''.join(map(str, a[j])))


(n, m) = map(int, input().split())
mat = []
for i in range(n):
	me = [int(i) for i in list(input())]
	mat.append(me)
dummy = [[0 for i in range(m + 1)] for j in range(n + 1)]
q = int(input())
for i in range(q):
	(x1, y1, x2, y2) = map(int, input().split())
	dummy[x1 - 1][y1 - 1] += 1
	dummy[x2][y1 - 1] -= 1
	dummy[x2][y2] += 1
	dummy[x1 - 1][y2] -= 1
for i in range(n + 1):
	for j in range(m + 1):
		if j == 0:
			continue
		else:
			dummy[i][j] += dummy[i][j - 1]
for j in range(m + 1):
	for i in range(n + 1):
		if i == 0:
			continue
		else:
			dummy[i][j] += dummy[i - 1][j]
for i in range(n):
	for j in range(m):
		print((mat[i][j] + dummy[i][j] + 2) % 2, end='')
	print()
print()


def issafe(a, b, n, m):
	if 0 <= a < n and 0 <= b < m:
		return True
	return False

def main():
	(n, m) = map(int, input().split())
	mat = [list(map(int, list(input()))) for i in range(n)]
	qmat = [[0 for i in range(m)] for j in range(n)]
	q = int(input())
	query = [list(map(int, input().split())) for i in range(q)]
	for k in query:
		(i1, j1, i2, j2) = map(lambda x: x - 1, k)
		qmat[i1][j1] += 1
		if issafe(i2 + 1, j2 + 1, n, m):
			qmat[i2 + 1][j2 + 1] += 1
		if issafe(i1, j2 + 1, n, m):
			qmat[i1][j2 + 1] += -1
		if issafe(i2 + 1, j1, n, m):
			qmat[i2 + 1][j1] += -1
	for i in range(n - 1):
		for j in range(m):
			qmat[i + 1][j] += qmat[i][j]
	for i in range(n):
		for j in range(m - 1):
			qmat[i][j + 1] += qmat[i][j]
	for i in range(n):
		for j in range(m):
			qmat[i][j] = (qmat[i][j] + mat[i][j]) % 2
	for i in qmat:
		print(*i, sep='')
main()


from sys import stdin
(n, m) = map(int, stdin.readline().split())
l = [list(map(int, stdin.readline().strip())) for _ in range(n)]
dp = [[0] * m for _ in range(n)]
for _ in range(int(stdin.readline())):
	(x1, y1, x2, y2) = map(int, stdin.readline().split())
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	dp[x1][y1] += 1
	if x2 + 1 < n:
		dp[x2 + 1][y1] -= 1
	if y2 + 1 < m:
		dp[x1][y2 + 1] -= 1
	if x2 + 1 < n and y2 + 1 < m:
		dp[x2 + 1][y2 + 1] += 1
for i in range(1, n):
	for j in range(m):
		dp[i][j] += dp[i - 1][j]
for i in range(n):
	for j in range(1, m):
		dp[i][j] += dp[i][j - 1]
for i in range(n):
	for j in range(m):
		print((dp[i][j] + l[i][j]) % 2, end='')
	print()


(n, m) = map(int, input().split())
mat = []
for _ in range(n):
	s = input()
	l = list(map(int, s))
	mat.append(l)
pref = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
p = [[0 for _ in range(m)] for _ in range(n)]
add = [[0 for _ in range(m)] for _ in range(n)]
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	pref[x1 - 1][y1 - 1] += 1
	pref[x2][y1 - 1] -= 1
	pref[x1 - 1][y2] -= 1
	pref[x2][y2] += 1
for i in range(n):
	for j in range(m):
		if i == 0:
			p[i][j] = pref[i][j]
		else:
			p[i][j] = p[i - 1][j] + pref[i][j]
for i in range(n):
	for j in range(m):
		if j == 0:
			add[i][j] = p[i][j]
		else:
			add[i][j] = add[i][j - 1] + p[i][j]
for i in range(n):
	for j in range(m):
		mat[i][j] += add[i][j]
		mat[i][j] %= 2
for i in range(n):
	for j in range(m):
		print(mat[i][j], end='')
	print()


(n, m) = map(int, input().split())
arr = []
for _ in range(n):
	s = input()
	a = [int(x) for x in s]
	arr.append(a)
Q = int(input())
ans = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(Q):
	(x1, y1, x2, y2) = map(int, input().split())
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	ans[x1][y1] += 1
	ans[x2 + 1][y2 + 1] += 1
	ans[x2 + 1][y1] -= 1
	ans[x1][y2 + 1] -= 1
for j in range(m + 1):
	for i in range(1, n + 1):
		ans[i][j] = ans[i - 1][j] + ans[i][j]
for i in range(n + 1):
	for j in range(1, m + 1):
		ans[i][j] = ans[i][j - 1] + ans[i][j]
for i in range(n):
	for j in range(m):
		arr[i][j] = (ans[i][j] + arr[i][j]) % 2
for i in range(n):
	for j in range(m):
		print(arr[i][j], end='')
	print()


R = lambda : map(int, input().split())
(n, m) = R()
a = [input() for _ in range(n)]
b = [[0] * (m + 2) for _ in range(n + 1)]
(q,) = R()
for _ in range(q):
	(x1, y1, x2, y2) = R()
	x1 -= 1
	y2 += 1
	for x in (x1, x2):
		for y in (y1, y2):
			b[x][y] ^= 1
dp = [0] * (m + 1)
for (r, d) in zip(a, b):
	for i in range(m):
		d[i + 1] ^= dp[i] ^ dp[i + 1] ^ d[i]
	dp = d
	print(*(int(x) ^ y for (x, y) in zip(r, d[1:])), sep='')


(n, m) = map(int, input().split())
MX = list()
for i in range(n):
	YYY = str(input())
	yy = list(YYY)
	a = []
	for j in range(m):
		a.append(yy[j])
	MX.append(a)
q = int(input())
dp = [[0 for i in range(m)] for i in range(n)]
for _ in range(q):
	(x, y, x2, y2) = map(int, input().split())
	dp[x - 1][y - 1] += 1
	if x2 < n:
		dp[x2][y - 1] -= 1
	if y2 < m:
		dp[x - 1][y2] -= 1
	if x2 < n and y2 < m:
		dp[x2][y2] -= 1
for i in range(n):
	for j in range(1, m):
		dp[i][j] += dp[i][j - 1]
for i in range(m):
	for j in range(1, n):
		dp[j][i] += dp[j - 1][i]
for i in range(n):
	for j in range(m):
		if dp[i][j] % 2 == 1:
			if MX[i][j] == '0':
				MX[i][j] = '1'
			else:
				MX[i][j] = '0'
for i in range(n):
	for j in range(m):
		print(MX[i][j], end='')
	print()


import sys
(n, m) = map(int, sys.stdin.readline().strip().split())
arr = []
for i in range(n):
	arr.append(list(input()))
temp = [[0 for i in range(m + 1)] for j in range(n + 1)]
q = int(sys.stdin.readline())
while q:
	q -= 1
	(x1, y1, x2, y2) = map(int, sys.stdin.readline().strip().split())
	x1 -= 1
	x2 -= 1
	y1 -= 1
	y2 -= 1
	temp[x1][y1] += 1
	temp[x1][y2 + 1] -= 1
	temp[x2 + 1][y1] -= 1
	temp[x2 + 1][y2 + 1] += 1
for i in range(n + 1):
	for j in range(m + 1):
		if j == 0:
			temp[i][j] = temp[i][j]
		else:
			temp[i][j] += temp[i][j - 1]
for j in range(m + 1):
	for i in range(n + 1):
		if i == 0:
			temp[i][j] = temp[i][j]
		else:
			temp[i][j] += temp[i - 1][j]
for i in range(n):
	for j in range(m):
		if temp[i][j] % 2 == 1:
			if arr[i][j] == '0':
				print('1', end='')
			else:
				print('0', end='')
		else:
			print(arr[i][j], end='')
	print()


from sys import stdin, stdout, setrecursionlimit
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007
(n, m) = iia()
arr = []
for i in range(n):
	arr.append(list(map(int, list(is1()))))
q = ii1()
temp = [[0 for i in range(m)] for j in range(n)]
for i in range(q):
	(x, y, x1, y1) = iia()
	temp[x - 1][y - 1] += 1
	if x1 < n:
		temp[x1][y - 1] -= 1
	if y1 < m:
		temp[x - 1][y1] -= 1
	if x1 < n and y1 < m:
		temp[x1][y1] -= 1
for i in range(n):
	for j in range(1, m):
		temp[i][j] += temp[i][j - 1]
for i in range(m):
	for j in range(1, n):
		temp[j][i] += temp[j - 1][i]
for i in range(n):
	for j in range(m):
		if temp[i][j] % 2 == 1:
			arr[i][j] = '0' if arr[i][j] == 1 else '1'
		else:
			arr[i][j] = str(arr[i][j])
for i in arr:
	print(''.join(i))


import sys

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
import math
from collections import defaultdict
(n, m) = get_ints()
a = []
arr = [[0 for _ in range(m + 2)] for _ in range(n + 2)]
for _ in range(n):
	t = list(input())
	a.append(t)
for i in range(n):
	for j in range(m):
		a[i][j] = int(a[i][j])
q = int(input())
for _ in range(q):
	(x1, y1, x2, y2) = get_ints()
	arr[x1][y1] += 1
	arr[x2 + 1][y2 + 1] += 1
	arr[x1][y2 + 1] -= 1
	arr[x2 + 1][y1] -= 1
for i in range(1, n + 1):
	for j in range(1, m + 1):
		arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1]
		if a[i - 1][j - 1] == 0 and arr[i][j] % 2 == 0:
			a[i - 1][j - 1] = 0
		elif a[i - 1][j - 1] == 1 and arr[i][j] % 2 == 0:
			a[i - 1][j - 1] = 1
		elif a[i - 1][j - 1] == 0 and arr[i][j] % 2 == 1:
			a[i - 1][j - 1] = 1
		elif a[i - 1][j - 1] == 1 and arr[i][j] % 2 == 1:
			a[i - 1][j - 1] = 0
for i in range(n):
	print(''.join(map(str, a[i])))


def method_1(dp, x1, y1, x2, y2):
	dp[x1][y1] += 1
	if y2 + 1 < m:
		dp[x1][y2 + 1] -= 1
	if x2 + 1 < n:
		dp[x2 + 1][y1] -= 1
	if x2 + 1 < n and y2 + 1 < m:
		dp[x2 + 1][y2 + 1] += 1
(n, m) = map(int, input().split())
arr = []
for i in range(n):
	arr.append(list(map(int, input())))
t = int(input())
dp = [[0 for j in range(m)] for i in range(n)]
for _ in range(t):
	(x1, y1, x2, y2) = map(int, input().split())
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	method_1(dp, x1, y1, x2, y2)
for i in range(n):
	for j in range(1, m):
		dp[i][j] += dp[i][j - 1]
for i in range(1, n):
	for j in range(m):
		dp[i][j] += dp[i - 1][j]
for i in range(n):
	for j in range(m):
		if dp[i][j] % 2 == 0:
			print(arr[i][j], end='')
		else:
			print(int(not arr[i][j]), end='')
	print()


import sys
try:

	def main():
		t = 1
		while t:
			(n, m) = [int(x) for x in sys.stdin.readline().split()]
			a = []
			update = []
			for i in range(n):
				tmp = sys.stdin.readline()
				a.append(tmp)
				update.append([0 for j in range(m + 1)])
			update.append([0 for j in range(m + 1)])
			q = int(sys.stdin.readline())
			while q:
				(x1, y1, x2, y2) = [int(z) for z in sys.stdin.readline().split()]
				update[x1][y1] += 1
				if x2 < n:
					update[x2 + 1][y1] += -1
				if y2 < m:
					update[x1][y2 + 1] += -1
				if x2 < n and y2 < m:
					update[x2 + 1][y2 + 1] += 1
				q -= 1
			for i in range(1, n + 1):
				for j in range(1, m + 1):
					update[i][j] += update[i][j - 1]
			for j in range(1, m + 1):
				for i in range(1, n + 1):
					update[i][j] += update[i - 1][j]
			for i in range(1, n + 1):
				for j in range(1, m + 1):
					if update[i][j] % 2 == 0:
						sys.stdout.write(a[i - 1][j - 1])
					else:
						sys.stdout.write(str(1 - (ord(a[i - 1][j - 1]) - 48)))
				sys.stdout.write('\n')
			t -= 1
	main()
except Exception as e:
	sys.stdout.write('ErrOR : ' + str(e))


(n, m) = map(int, input().split())
a = []
b = [0] * (m + 1)
for i in range(n + 1):
	a.append(b[:])
p = []
for i in range(n):
	r = input()
	q = []
	for j in range(len(r)):
		q.append(int(r[j]))
	p.append(q[:])
q = int(input())
while q:
	(i, j, k, l) = map(int, input().split())
	a[i - 1][j - 1] += 1
	a[i - 1][l] -= 1
	a[k][j - 1] -= 1
	a[k][l] += 1
	q -= 1
c = 0
for j in range(m + 1):
	for i in range(n + 1):
		c += a[i][j]
		a[i][j] = c
for i in range(n):
	for j in range(m):
		c += a[i][j]
		if c % 2 == 1:
			if p[i][j] == 1:
				p[i][j] = 0
			else:
				p[i][j] = 1
	c += a[i][m]
for i in range(n):
	for j in range(m):
		print(p[i][j], end='')
	print()


(n, m) = map(int, input().split())
arr = []
for i in range(n):
	s = input() + '0'
	temp = []
	for x in s:
		temp += [int(x)]
	arr += [temp]
arr += [[0] * (m + 1)]
add = [[0 for i in range(m + 1)] for j in range(n + 1)]
pref1 = [[0 for i in range(m + 1)] for j in range(n + 1)]
pref2 = [[0 for i in range(m + 1)] for j in range(n + 1)]
q = int(input())
for _ in range(q):
	(x1, y1, x2, y2) = map(int, input().split())
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	pref2[x1][y1] += 1
	pref2[x2 + 1][y1] -= 1
	pref2[x1][y2 + 1] += -1
	pref2[x2 + 1][y2 + 1] -= -1
for i in range(m):
	for j in range(n):
		if j == 0:
			pref1[j][i] = pref2[j][i]
		else:
			pref1[j][i] = pref1[j - 1][i] + pref2[j][i]
for i in range(n):
	for j in range(m):
		if j == 0:
			add[i][j] += pref1[i][j]
		else:
			add[i][j] = add[i][j - 1] + pref1[i][j]
for i in range(n):
	for j in range(m):
		arr[i][j] -= add[i][j]
		arr[i][j] %= 2
for i in range(n):
	for j in range(m):
		print(arr[i][j], end='')
	print('')


[n, m] = [int(x) for x in input().split()]
arr = []
for i in range(n):
	arr.append([int(x) for x in list(input())])
prefix = [[0] * (m + 1) for i in range(n + 1)]
q = int(input())
for i in range(q):
	[x1, y1, x2, y2] = [int(x) for x in input().split()]
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	prefix[x1][y1] += 1
	prefix[x2 + 1][y1] -= 1
	prefix[x1][y2 + 1] -= 1
	prefix[x2 + 1][y2 + 1] += 1
for i in range(m + 1):
	for j in range(1, n + 1):
		prefix[j][i] += prefix[j - 1][i]
for i in range(n + 1):
	for j in range(1, m + 1):
		prefix[i][j] += prefix[i][j - 1]
for i in range(n):
	ans = ''
	for j in range(m):
		ans += str((arr[i][j] + prefix[i][j]) % 2)
	print(ans)


import sys
import math
from math import *
from collections import Counter, defaultdict

def main():
	(n, m) = list(map(int, input().split()))
	arr = []
	temp = [[0 for i in range(m + 1)] for j in range(n + 1)]
	for _ in range(n):
		arr.append(list(map(int, list(input()))) + [0])
	arr.append([0 for j in range(m + 1)])
	for _ in range(int(input())):
		(a, b, c, d) = list(map(int, input().split()))
		temp[a - 1][b - 1] += 1
		temp[a - 1][d] += 1
		temp[c][b - 1] -= 1
		temp[c][d] -= 1
	prev = 0
	for i in range(m + 1):
		for j in range(1, n + 1):
			temp[j][i] += temp[j - 1][i]
	for i in range(n):
		for j in range(0, m + 1):
			prev += temp[i][j]
			arr[i][j] += prev
	for i in range(n):
		for j in range(m):
			arr[i][j] %= 2
	for i in range(n):
		print(''.join(map(str, arr[i][:-1])))
main()


(n, m) = map(int, input().split())
matrix = []
for _ in range(n):
	matrix.append(list(map(int, list(input()))))
extra = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	extra[x1 - 1][y1 - 1] += 1
	extra[x1 - 1][y2] -= 1
	extra[x2][y2] += 1
	extra[x2][y1 - 1] -= 1
for j in range(m):
	for i in range(1, n):
		extra[i][j] += extra[i - 1][j]
for i in range(n):
	for j in range(1, m):
		extra[i][j] += extra[i][j - 1]
for i in range(n):
	for j in range(m):
		matrix[i][j] += extra[i][j]
		matrix[i][j] %= 2
		print(matrix[i][j], end='')
	print()


(n, m) = map(int, input().split())
l = [list(map(int, input())) for _ in range(n)]
pre = [[0] * m for _ in range(n)]
for _ in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	pre[x1][y1] += 1
	if x2 + 1 < n:
		pre[x2 + 1][y1] -= 1
	if y2 + 1 < m:
		pre[x1][y2 + 1] -= 1
	if x2 + 1 < n and y2 + 1 < m:
		pre[x2 + 1][y2 + 1] += 1
for i in range(1, n):
	for j in range(m):
		pre[i][j] += pre[i - 1][j]
for i in range(n):
	for j in range(1, m):
		pre[i][j] += pre[i][j - 1]
for i in range(n):
	for j in range(m):
		print((pre[i][j] + l[i][j]) % 2, end='')
	print()


def flip(dp, x1, y1, x2, y2, n, m):
	dp[x1][y1] += 1
	if y2 + 1 < m:
		dp[x1][y2 + 1] -= 1
	if x2 + 1 < n:
		dp[x2 + 1][y1] -= 1
	if x2 + 1 < n and y2 + 1 < m:
		dp[x2 + 1][y2 + 1] += 1

def main():
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		matrix.append(list(map(int, input())))
	dp = [[0 for j in range(m)] for i in range(n)]
	q = int(input())
	for i in range(q):
		(x1, y1, x2, y2) = map(int, input().split())
		x1 -= 1
		y1 -= 1
		x2 -= 1
		y2 -= 1
		flip(dp, x1, y1, x2, y2, n, m)
	for i in range(n):
		for j in range(1, m):
			dp[i][j] += dp[i][j - 1]
	for i in range(1, n):
		for j in range(m):
			dp[i][j] += dp[i - 1][j]
	for i in range(n):
		for j in range(m):
			if dp[i][j] % 2 == 0:
				print(matrix[i][j], end='')
			else:
				print(int(not matrix[i][j]), end='')
		print()
main()


import sys
import bisect
t = 1
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	arr = [[0 for j in range(m + 2)] for i in range(n + 2)]
	for i in range(n):
		l.append(input())
	q = int(input())
	for __ in range(q):
		(x1, y1, x2, y2) = map(int, input().split())
		arr[x1][y1] += 1
		arr[x2 + 1][y1] -= 1
		arr[x1][y2 + 1] -= 1
		arr[x2 + 1][y2 + 1] += 1
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			x1 = arr[i - 1][j] + arr[i][j - 1]
			y1 = x1 - arr[i - 1][j - 1]
			arr[i][j] = arr[i][j] + y1
			print((arr[i][j] + int(l[i - 1][j - 1])) % 2, end='')
		print()
	print()


(r, c) = list(map(int, input().split()))
A = []
dp = [[0 for i in range(c + 1)] for j in range(r + 1)]
for i in range(r):
	A.append([int(j) for j in list(input())])
q = int(input())
for i in range(q):
	(x1, y1, x2, y2) = list(map(int, input().split()))
	(x1, y1, x2, y2) = (x1 - 1, y1 - 1, x2 - 1, y2 - 1)
	dp[x1][y1] += 1
	dp[x2 + 1][y2 + 1] += 1
	dp[x1][y2 + 1] -= 1
	dp[x2 + 1][y1] -= 1
for (i, v1) in enumerate(A):
	for (j, v2) in enumerate(v1):
		if i == 0 and j == 0:
			pass
		elif i == 0:
			dp[i][j] += dp[i][j - 1]
		elif j == 0:
			dp[i][j] += dp[i - 1][j]
		else:
			dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
		if dp[i][j] % 2 != 0:
			A[i][j] = 1 - A[i][j]
for i in A:
	for j in i:
		print(j, end='')
	print()


(n, m) = map(int, input().split())
a = [[int(i) for i in str(input())] for j in range(n)]
b = [[0 for i in range(m + 1)] for j in range(n + 1)]
for q in range(int(input())):
	(x1, y1, x2, y2) = map(int, input().split())
	b[x1 - 1][y1 - 1] += 1
	b[x1 - 1][y2] -= 1
	b[x2][y1 - 1] -= 1
	b[x2][y2] += 1
for i in range(n + 1):
	for j in range(1, m + 1):
		b[i][j] += b[i][j - 1]
for i in range(1, n + 1):
	for j in range(m + 1):
		b[i][j] += b[i - 1][j]
for i in range(n):
	for j in range(m):
		a[i][j] += b[i][j]
		a[i][j] %= 2
	print(''.join((str(k) for k in a[i])))


import sys
import math
from collections import defaultdict, Counter
(n, m) = map(int, input().split())
l = []
for i in range(n):
	s = input()
	l.append(s)
row = [[0] * m for i in range(n)]
q = int(input())
for j in range(q):
	(x1, y1, x2, y2) = map(int, input().split())
	row[x1 - 1][y1 - 1] += 1
	if y2 != m:
		row[x1 - 1][y2] -= 1
	if x2 != n:
		row[x2][y1 - 1] -= 1
		if y2 != m:
			row[x2][y2] -= 1
for i in range(n):
	for j in range(1, m):
		row[i][j] += row[i][j - 1]
for i in range(m):
	for j in range(1, n):
		row[j][i] += row[j - 1][i]
for i in range(n):
	s1 = ''
	for j in range(m):
		if row[i][j] & 1:
			s1 += str(int(l[i][j]) ^ 1)
		else:
			s1 += l[i][j]
	print(s1)


(n, m) = map(int, input().split())
mat = []
for x in range(n):
	row = input()
	mat.append(list(row))
q = int(input())
pref = [[0 for _ in range(m)] for _ in range(n)]
for _ in range(q):
	(x1, y1, x2, y2) = map(int, input().split())
	x1 -= 1
	x2 -= 1
	y1 -= 1
	y2 -= 1
	pref[x1][y1] += 1
	if x2 + 1 < n and y2 + 1 < m:
		pref[x2 + 1][y2 + 1] += 1
	if x2 + 1 < n:
		pref[x2 + 1][y1] -= 1
	if y2 + 1 < m:
		pref[x1][y2 + 1] -= 1
for i in range(m):
	for j in range(1, n):
		pref[j][i] += pref[j - 1][i]
for i in range(n):
	for j in range(1, m):
		pref[i][j] += pref[i][j - 1]
for x in range(n):
	for y in range(m):
		if pref[x][y] % 2:
			mat[x][y] = str(int(mat[x][y]) ^ 1)
for x in mat:
	print(''.join(x))


import sys
I = sys.stdin.readline
R = lambda : map(int, I().split())
(n, m) = R()
a = [I()[:-1] for _ in range(n)]
b = [[0] * (m + 2) for _ in range(n + 1)]
(q,) = R()
for _ in range(q):
	(x1, y1, x2, y2) = R()
	x1 -= 1
	y2 += 1
	for x in (x1, x2):
		for y in (y1, y2):
			b[x][y] ^= 1
dp = [0] * (m + 1)
for (r, d) in zip(a, b):
	for i in range(m):
		d[i + 1] ^= dp[i] ^ dp[i + 1] ^ d[i]
	dp = d
	print(''.join((str(int(x) ^ y) for (x, y) in zip(r, d[1:]))))


import os.path
import sys
from math import *
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def inp():
	return sys.stdin.readline().strip()
(n, m) = map(int, inp().split())
dp = [[0 for j in range(m + 2)] for k in range(n + 2)]
a = []
for j in range(n):
	t = inp()
	a.append(list(t))
q = int(inp())
for j in range(0, q):
	(x1, y1, x2, y2) = map(int, inp().split())
	dp[x1][y1] += 1
	dp[x2 + 1][y2 + 1] += 1
	dp[x1][y2 + 1] -= 1
	dp[x2 + 1][y1] -= 1
for j in range(1, n + 1):
	for k in range(1, m + 1):
		dp[j][k] = dp[j][k] + dp[j - 1][k] + dp[j][k - 1] - dp[j - 1][k - 1]
		if dp[j][k] % 2 != 0:
			a[j - 1][k - 1] = int(a[j - 1][k - 1]) ^ 1
for j in range(n):
	print(''.join(map(str, a[j])))


(n, m) = map(int, input().split())
arr = []
for _ in range(n):
	arr.append(list(map(int, list(input()))))
q = int(input())
flip = [[0] * m for _ in range(n)]
for _ in range(q):
	(x1, y1, x2, y2) = map(int, input().split())
	flip[x1 - 1][y1 - 1] += 1
	if x2 - 1 < n - 1:
		flip[x2 - 1 + 1][y1 - 1] -= 1
	if y2 - 1 < m - 1:
		flip[x1 - 1][y2 - 1 + 1] -= 1
	if x2 - 1 < n - 1 and y2 - 1 < m - 1:
		flip[x2 - 1 + 1][y2 - 1 + 1] -= 1
for i in range(1, n):
	for j in range(m):
		flip[i][j] += flip[i - 1][j]
for i in range(n):
	for j in range(1, m):
		flip[i][j] += flip[i][j - 1]
for i in range(n):
	for j in range(m):
		if flip[i][j] % 2:
			print(arr[i][j] ^ 1, end='')
		else:
			print(arr[i][j], end='')
	print()


(n, m) = map(int, input().split())
matrix = [list(input()) for _ in range(n)]
q = int(input())
prefix_sum = [[0] * (m + 2) for _ in range(n + 2)]
for _ in range(q):
	(x1, y1, x2, y2) = map(int, input().split())
	prefix_sum[x1][y1] += 1
	prefix_sum[x2 + 1][y2 + 1] += 1
	prefix_sum[x1][y2 + 1] -= 1
	prefix_sum[x2 + 1][y1] -= 1
flip = {'0': '1', '1': '0'}
for col in range(1, m + 1):
	for row in range(1, n + 1):
		prefix_sum[row][col] += prefix_sum[row - 1][col]
for row in range(1, n + 1):
	for col in range(1, m + 1):
		prefix_sum[row][col] += prefix_sum[row][col - 1]
		if prefix_sum[row][col] & 1:
			matrix[row - 1][col - 1] = flip[matrix[row - 1][col - 1]]
for row in range(n):
	print(''.join(matrix[row]))