Problem:
Origami, or the art of folding paper Master Grus is a famous origami (paper folding) artist, who is
enthusiastic about exploring the possibility of origami art.
For future creation, he is now planning fundamental
experiments to establish the general theory of origami. One rectangular piece of paper is used in each of his experiments.
He folds it horizontally and/or vertically several times and then
punches through holes in the folded paper. The following figure illustrates the folding process of a simple experiment,
which corresponds to the third dataset of the Sample Input below.
Folding the 10 × 8 rectangular piece of paper shown at top left
three times results in the 6 × 6 square shape shown at
bottom left.
In the figure, dashed lines indicate the locations to fold the paper
and round arrows indicate the directions of folding.
Grid lines are shown as solid lines to tell the sizes of rectangular
shapes and the exact locations of folding.
Color densities represent the numbers of overlapping layers.
Punching through holes at A and B in the folded paper makes
nine holes in the paper, eight at A and another at B.     Your mission in this problem is to write a computer program to count
the number of holes in the paper, given the information on a rectangular
piece of paper and folding and punching instructions. Input The input consists of at most 1000 datasets, each in the following format.   n  m  t  p  d 1  c 1  ...  d t  c t   x 1  y 1  ...  x p  y p     n and m are the width and the height, respectively, of
a rectangular piece of paper.
They are positive integers at most 32. t and p are the numbers of folding and punching
instructions, respectively.
They are positive integers at most 20.
The pair of d i and c i gives the i -th folding instruction as follows:  d i is either 1 or 2.  c i is a positive integer.  If d i is 1, the left-hand side of the vertical folding line that passes at c i right to the left boundary is folded onto the right-hand side.  If d i is 2, the lower side of the horizontal folding line that passes at c i above the lower boundary is folded onto the upper side.  i d i c i c i x i y i i x i y i The end of the input is indicated by a line containing four zeros. Output For each dataset, output p lines, the i -th of which contains
the number of holes punched in the paper by the i -th punching instruction. Sample Input 2 1 1 1
1 1
0 0
1 3 2 1
2 1
2 1
0 0
10 8 3 2
2 2
1 3
1 1
0 1
3 4
3 3 3 2
1 2
2 1
1 1
0 1
0 0
0 0 0 0 Output for the Sample Input 2
3
8
1
3
6

Solution (Python):


max_v = 450


def show(origami):
    print "-----------"
    for i in origami:
        for j in i:
            print j,
        print
    print "-----------"

5

def fold_a(origami, c, katan):
    t = max_v-1-katan-c

    for i in range(max_v):
        for j in range(c):
            origami[t-j][i] += origami[t+1+j][i]
            origami[t+1+j][i] = 0

    



def fold_b(origami, c, satan):
    t = satan+c

    for i in range(max_v):
        for j in range(c):
            origami[i][t+j] += origami[i][t-1-j]
            origami[i][t-1-j] = 0

    

while True:
    
    
    n, m, t, p = map(int, raw_input().split())

    
    if n == 0 and m == 0 and t == 0 and p == 0:
        break

    
    origami = [[0] * max_v for _ in range(max_v)]

    for i in range(n):
        for j in range(m):
            origami[-1-j][i] = 1

    
    katan, satan = 0, 0

    
    for i in range(t):
        d, c = map(int, raw_input().split())
        
        if d == 1:
            fold_b(origami, c, satan)
            satan += c
        
        if d == 2:
            fold_a(origami, c, katan)
            katan += c

    
    for i in range(p):
        x, y = map(int, raw_input().split())

        print origami[max_v-1-katan-y][satan+x]

Solution (Python):
while True:
	data = [int(x) for x in input().split()]
	if data == [0, 0, 0, 0]:
		break
	matrix = [[1 for x in range(data[0])] for y in range(data[1])]
	
	n = data[2] + data[3]
	command = list()
	while n > 0:
		command.append([int(x) for x in input().split()])
		n -= 1
	flipping = [command[x] for x in range(data[2])]
	holing = [command[x] for x in range(data[2], len(command))]
	for c, b in flipping:
		matrixtemp = list()
		if c == 1:
			
			matrixtemp = [[matrix[y][x] for x in range(b)] for y in range(len(matrix))]
			for n in range(len(matrixtemp)):
				matrixtemp[n] = matrixtemp[n][::-1]
			for n in range(len(matrix)):
				matrix[n] = matrix[n][b:]
			if len(matrixtemp[0]) > len(matrix[0]):
				for y in range(len(matrix)):
					for x in range(len(matrix[n])):
						matrixtemp[y][x] += matrix[y][x]
				matrix = matrixtemp
			else:
				for y in range(len(matrix)):
					for x in range(b):
						matrix[y][x] += matrixtemp[y][x]
		else:
			
			matrixtemp = matrix[-b:]
			matrixtemp = matrixtemp[::-1]
			matrix = matrix[:-b]
			if len(matrixtemp) > len(matrix):
				for y in range(-len(matrix), 0, 1):
					for x in range(len(matrixtemp[0])):
						matrixtemp[y][x] += matrix[y][x]
				matrix = matrixtemp
			else:
				for y in range(-b, 0, 1):
					for x in range(len(matrixtemp[0])):
						matrix[y][x] += matrixtemp[y][x]
		
	for x, y in holing:
		print(matrix[len(matrix) - y - 1][x])

Solution (Python):
ans = []
while 1:
    N, M, T, P = map(int, input().split())
    if N == 0:
        break
    A = [[1]*N for i in range(M)]
    for i in range(T):
        d, c = map(int, input().split())
        if d == 1:
            B = [[0]*max(c, N-c) for i in range(M)]
            for x in range(N-c):
                for y in range(M):
                    B[y][x] = A[y][c+x]
            for x in range(c):
                for y in range(M):
                    B[y][x] += A[y][c-1-x]
            N = max(c, N-c)
        else:
            B = [[0]*N for i in range(max(c, M-c))]
            for x in range(N):
                for y in range(M-c):
                    B[y][x] = A[c+y][x]
            for x in range(N):
                for y in range(c):
                    B[y][x] += A[c-1-y][x]
            M = max(c, M-c)
        A = B
    cnt = 0
    for i in range(P):
        x, y = map(int, input().split())
        ans.append(B[y][x])
print(*ans, sep='\n')