King Richard is leading a troop of $N^2$ knights into battle! Being very organized, he labels his knights $K_0,K_1,\ldots,K_{N^2-1}$ and arranges them in an $N\times N$ square formation, demonstrated below:

Before the battle begins, he wants to test how well his knights follow instructions. He issues $\mbox{S}$ drill commands, where each command follows the format $a_{i}$ $b_{i}$ $d_{i}$ and is executed like so:

All knights in the square having the top-left corner at location $(a_i,b_i)$ and the bottom-right corner at location $(a_i+d_i,b_i+d_i)$ rotate $90^{\circ}$ in the clockwise direction. Recall that some location $(r,c)$ denotes the cell located at the intersection of row $\textbf{r}$ and column $\textbf{c}$. For example:

You must follow the commands sequentially. The square for each command is completely contained within the square for the previous command. Assume all knights follow the commands perfectly.

After performing all $\mbox{S}$ drill commands, it's time for battle! King Richard chooses knights $K_{w_1},K_{w_2},...,K_{w_L}$ for his first wave of attack; however, because the knights were reordered by the drill commands, he's not sure where his chosen knights are!

As his second-in-command, you must find the locations of the knights. For each knight $K_{w_1}$, $K_{w_{2}},\ldots,K_{w_{L}}$, print the knight's row and column locations as two space-separated values on a new line.  

Input Format

This is broken down into three parts:

The first line contains a single integer, $N$.       
The second line contains a single integer, $\mbox{S}$. 

Each line $\boldsymbol{i}$ of the $\mbox{S}$ subsequent lines describes a command in the form of three space-separated integers corresponding to $a_i$, $b_i$, and $d_i$, respectively.  
The next line contains a single integer, $\boldsymbol{\mbox{L}}$. 
Each line $j$ of the $\boldsymbol{\mbox{L}}$ subsequent lines describes a knight the King wants to find in the form of a single integer corresponding to $w_j$.  

Constraints

$1\leq S\leq2\cdot10^5$  
$7\leq N\leq3\cdot10^7$
$1\leq a_i,b_i\leq N$  
$0\leq d_i<N$  
$a_{i-1}\leq a_i$ and $a_{i}+d_{i}\leq a_{i-1}+d_{i-1}$  
$b_{i-1}\leq b_{i}$ and $b_i+d_i\leq b_{i-1}+d_{i-1}$  
$1\leq L\leq2\cdot10^5$  
$0\leq w_j<N^2$  

Subtask     

$7\leq N\leq3000$ for $25\%$ of the maximum score.  

Output Format

Print $\boldsymbol{\mbox{L}}$ lines of output, where each line $j$ contains two space-separated integers describing the respective row and column values where knight $K_{w_j}$ is located.  

Sample Input
7
4
1 2 4
2 3 3
3 4 1
3 4 0
7
0
6
9
11
24
25
48

Sample Output
1 1
1 7
4 6
3 4
2 5
2 4
7 7

Explanation

The following diagram demonstrates the sequence of commands:

Click here to download a larger image.

In the final configuration:

Knight $\mathbf{K_0}$ is at location $(1,1)$
Knight $\mathbf{K_6}$ is at location $(1,7)$
Knight $\mathbf{K}_{9}$ is at location $(4,6)$
Knight $K_{11}$ is at location $(3,4)$
Knight $K_{24}$ is at location $(2,5)$
Knight $K_{25}$ is at location $(2,4)$
Knight $K_{48}$ is at location $(7,7)$

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Complete search


Solutions:
def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


N = int(input().strip())
S = int(input().strip())
Q = []
for i in range(S):
	(a, b, c) = [int(m) for m in input().strip().split()]
	Q.append((a - 1, b - 1, c))
L = int(input().strip())
K = []
for i in range(L):
	w = int(input().strip())
	y = w % N
	x = int((w - y) / N)
	K.append([x, y])

def ThreeByThreePsudo(A, B):
	Out = [[], [], [0, 0, 1]]
	for r in range(2):
		for c in range(3):
			Out[r].append(0)
			for i in range(3):
				Out[r][c] += A[r][i] * B[i][c]
	return Out

def MatVecPsudo(A, x):
	Out = [A[0][0] * x[0] + A[0][1] * x[1] + A[0][2], A[1][0] * x[0] + A[1][1] * x[1] + A[1][2]]
	return Out
IsValidShift = lambda xy, q: xy[0] >= q[0] and xy[0] <= q[0] + q[2] and (xy[1] >= q[1]) and (xy[1] <= q[1] + q[2])
I = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
TransformMat = [I]
Trans = I
QCondensed = []
for (I, i1) in enumerate(Q):
	(a, b, c) = i1
	T = [[0, 1, a - b], [-1, 0, a + b + c], [0, 0, 1]]
	Trans = ThreeByThreePsudo(T, Trans)
	if I == S - 1 or i1 != Q[I + 1]:
		TransformMat.append(Trans)
		QCondensed.append(Q[I])
Q = QCondensed
nSplit = min([90, N])
Increment = N // nSplit
GridList = []
for i1 in range(nSplit + 1):
	for i2 in range(nSplit + 1):
		x = i1 * Increment
		y = i2 * Increment
		GridList.append((x, y))

def BisectDepth(kw, TransformMat, LR=None):
	if LR == None:
		Left = [0, True]
		RightValid = IsValidShift(MatVecPsudo(TransformMat[-1], kw), Q[-1])
		Right = [len(Q), RightValid]
		if RightValid:
			return Right[0]
	else:
		Left = LR[0]
		Right = LR[1]
	while True:
		Mid = [(Left[0] + Right[0]) // 2]
		Mid.append(IsValidShift(MatVecPsudo(TransformMat[Mid[0]], kw), Q[Mid[0] - 1]))
		if Mid[1]:
			Left = Mid
		else:
			Right = Mid
		if Right[0] - Left[0] <= 1:
			return Left[0]
GridDict = {m: BisectDepth(m, TransformMat) for m in GridList}
MidGuess = []
for (I, i1) in enumerate(K):
	x1 = i1[0] // Increment * Increment
	x2 = -(-i1[0] // Increment) * Increment
	y1 = i1[1] // Increment * Increment
	y2 = -(-i1[1] // Increment) * Increment
	if x2 > N:
		x2 = x1
	if y2 > N:
		y2 = y1
	if x1 == x2:
		z1 = GridDict[x1, y1]
		z2 = GridDict[x1, y2]
	else:
		z1 = (i1[0] - x1) / (x2 - x1) * (GridDict[x2, y1] - GridDict[x1, y1]) + GridDict[x1, y1]
		z2 = (i1[0] - x1) / (x2 - x1) * (GridDict[x2, y2] - GridDict[x1, y2]) + GridDict[x1, y2]
	if y1 == y2:
		Z = (z1 + z2) // 2
	else:
		Z = (i1[1] - y1) / (y2 - y1) * (z2 - z1) + z1
	MidGuess.append(int(Z))
for (I, kw) in enumerate(K):
	Left = None
	Right = None
	Valid = IsValidShift(MatVecPsudo(TransformMat[MidGuess[I]], kw), Q[MidGuess[I] - 1])
	if Valid:
		Left = [MidGuess[I], True]
		Delta = 80
	else:
		Right = [MidGuess[I], False]
		Delta = -80
	NewDepth = min([max([0, MidGuess[I] + Delta]), len(Q)])
	Valid2 = IsValidShift(MatVecPsudo(TransformMat[NewDepth], kw), Q[NewDepth - 1])
	if Valid2 or NewDepth == 0:
		Left = [NewDepth, True]
	else:
		Right = [NewDepth, False]
	if Valid == Valid2:
		if not Valid:
			Delta = -1000
		else:
			Delta = 2000
		NewDepth2 = min([max([0, MidGuess[I] + Delta]), len(Q)])
		Valid3 = IsValidShift(MatVecPsudo(TransformMat[NewDepth2], kw), Q[NewDepth2 - 1])
		if Valid3 or NewDepth2 == 0:
			Left = [NewDepth2, True]
		else:
			Right = [NewDepth2, False]
		if Left == None:
			Left = [0, True]
		if Right == None:
			Right = [len(Q) + 1, False]
	Depth = BisectDepth(kw, TransformMat, [Left, Right])
	(x, y) = MatVecPsudo(TransformMat[Depth], kw)
	print(x + 1, y + 1)


def Mx(M, x):
	return (M[0] * x[0] + M[1] * x[1] + M[2], M[3] * x[0] + M[4] * x[1] + M[5])

def MM(M, M2):
	return (M[0] * M2[0] + M[1] * M2[3], M[0] * M2[1] + M[1] * M2[4], M[0] * M2[2] + M[1] * M2[5] + M[2], M[3] * M2[0] + M[4] * M2[3], M[3] * M2[1] + M[4] * M2[4], M[3] * M2[2] + M[4] * M2[5] + M[5])
n = int(input())
squares = [(1, 1, n - 1)]
maps = [(1, 0, 0, 0, 1, 0)]
s = int(input())
for _ in range(s):
	(a, b, d) = map(int, input().split())
	squares.append((a, b, d))
	maps.append(MM((0, 1, a - b, -1, 0, a + b + d), maps[-1]))
assert len(squares) == len(maps) == s + 1
for _ in range(int(input())):
	w = int(input())
	y = x = (w // n + 1, w % n + 1)
	(lo, hi) = (0, s + 1)
	while lo + 1 < hi:
		mid = (lo + hi) // 2
		(a, b, d) = squares[mid]
		(r, c) = Mx(maps[mid], x)
		if a <= r <= a + d and b <= c <= b + d:
			lo = mid
			y = (r, c)
		else:
			hi = mid
	print(y[0], y[1])


def apply_rot(rot, pos):
	d = (pos[2] + 1) % 4
	a = pos[0] - (rot[0] + rot[2] // 2)
	b = pos[1] - (rot[1] + rot[2] // 2)
	(a, b) = (-b, a)
	a += rot[0] + rot[2] // 2
	b += rot[1] + rot[2] // 2
	return (a, b, d)

def get_pos(pos, orig_pos):
	a = pos[0]
	b = pos[1]
	for _ in range(orig_pos[2]):
		(a, b) = (-b, a)
	a += orig_pos[0]
	b += orig_pos[1]
	return (a, b)

def inside(pos, orig_pos, rot):
	pos = get_pos(pos, orig_pos)
	return rot[0] <= pos[0] <= rot[0] + rot[2] and rot[1] <= pos[1] <= rot[1] + rot[2]
N = int(input())
S = int(input())
rots = []
for _ in range(S):
	(b, a, c) = map(int, input().split())
	a -= 1
	b -= 1
	rots.append((a * 2, b * 2, c * 2))
rots.append((rots[-1][0], rots[-1][1], 0))
orig_pos = (0, 0, 0)
origs = [orig_pos]
for r in rots:
	orig_pos = apply_rot(r, orig_pos)
	origs.append(orig_pos)
L = int(input())
for _ in range(L):
	i = int(input())
	(a, b) = (i % N, i // N)
	a *= 2
	b *= 2
	l = -1
	r = S
	while r - l > 1:
		m = (l + r) // 2
		if inside((a, b), origs[m], rots[m]):
			l = m
		else:
			r = m
	pos = get_pos((a, b), origs[r])
	print(pos[1] // 2 + 1, pos[0] // 2 + 1)


import math
import os
import random
import sys

def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])


def mat_fac(f):
	(a, b, d) = drill[dn]
	if f == 1:
		return ((a - b, a + b + d), ((0, 1), (-1, 0)))
	elif f == 2:
		return ((2 * a + d, 2 * b + d), ((-1, 0), (0, -1)))
	elif f == 3:
		return ((a + b + d, b - a), ((0, -1), (1, 0)))

def mat_mult(fac, pf):
	(c2, d2) = fac[0]
	(c1, d1) = pf[0]
	(k1, k2) = fac[1]
	(m1, m2) = pf[1]
	(cnext, dnext) = (c2 + k1[0] * c1 + k1[1] * d1, d2 + k2[0] * c1 + k2[1] * d1)
	knext1 = (k1[0] * m1[0] + k1[1] * m2[0], k1[0] * m1[1] + k1[1] * m2[1])
	knext2 = (k2[0] * m1[0] + k2[1] * m2[0], k2[0] * m1[1] + k2[1] * m2[1])
	return ((cnext, dnext), (knext1, knext2))

def revnew(drn, row, col):
	(c, d) = drill[drn][3][0]
	(k1, k2) = drill[drn][3][1]
	nrow = c + k1[0] * row + k1[1] * col
	ncol = d + k2[0] * row + k2[1] * col
	return (nrow, ncol)

def contained(x, row, col):
	(a, b, d, f) = drill[x]
	if row < a or row > a + d:
		return 0
	elif col < b or col > b + d:
		return 0
	else:
		return 1

def bin_s(row, col):
	(lower, upper) = (0, len(drill) - 1)
	if not contained(lower, row, col):
		return (row, col)
	(nrow, ncol) = revnew(upper, row, col)
	if contained(upper, nrow, ncol):
		return (nrow, ncol)
	while lower < upper:
		x = lower + (upper - lower) // 2
		(nrow, ncol) = revnew(x, row, col)
		if contained(x, nrow, ncol):
			if not contained(x + 1, nrow, ncol):
				return (nrow, ncol)
			else:
				lower = x + 1
				continue
		else:
			upper = x
	(nrow, ncol) = revnew(lower, row, col)
	return (nrow, ncol)
N = int(input())
S = int(input())
drill = [[int(t) for t in input().split()] for i in range(S)]
L = int(input())
trusty_k = [int(input()) for i in range(L)]
dn = 0
while dn < len(drill):
	if drill[dn][2] == 0:
		del drill[dn]
		continue
	elif dn + 3 < len(drill) and drill[dn] == drill[dn + 3]:
		del drill[dn:dn + 4]
		continue
	elif dn + 2 < len(drill) and drill[dn] == drill[dn + 2]:
		factor = mat_fac(3)
		del drill[dn:dn + 2]
	elif dn + 1 < len(drill) and drill[dn] == drill[dn + 1]:
		factor = mat_fac(2)
		del drill[dn]
	else:
		factor = mat_fac(1)
	if dn == 0:
		drill[dn] += [factor]
	else:
		drill[dn] += [mat_mult(factor, drill[dn - 1][3])]
	dn += 1
for sn in range(L):
	kn = trusty_k[sn]
	(row, col) = (kn // N + 1, kn % N + 1)
	newpos = bin_s(row, col)
	print(newpos[0], newpos[1])