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 &times; 8 rectangular piece of paper shown at top left
three times results in the 6 &times; 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

d1 c1 

... 

dt ct 

x1 y1 

... 

xp yp 

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 di and ci gives the
i-th folding instruction as follows:

  
di is either 1 or 2.

  
ci is a positive integer.

  
If di is 1, the left-hand side of the vertical folding line that passes at ci right to the left boundary is folded onto the right-hand side. 

  
If di is 2, the lower side of the horizontal folding line that passes at ci above the lower boundary is folded onto the upper side. 

After performing the first i&#8722;1 folding instructions, if di is 1, the width of the shape is greater than ci.
Otherwise the height is greater than ci.

(xi + 1/2, yi + 1/2) gives the coordinates of
the point where the i-th punching instruction is performed.
The origin (0, 0) is at the bottom left of the finally obtained shape.
xi and yi are both non-negative integers and they are less than the width and the height, respectively, of the shape.
You can assume that no two punching instructions punch holes at the same location.

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



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


Sample output:
2
3
8
1
3
6

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    while True:
        n,m,t,p = map(int,input().split())
        if [n,m,t,p] == [0,0,0,0]:
            exit()
        dp = [[0]*(m*m+1) for i in range(n*n+1)]
        
        
        sx = 0
        sy = 0
        ex = n
        ey = m

        
        for i in range(n):
            for j in range(m):
                dp[sx+i][sy+j] = 1
        
        for i in range(t):
            d,c = map(int,input().split())
            if d == 1:
                for k in range(c):
                    for j in range(sy,ey):
                        dp[sx+c+k][j] += dp[sx+c-k-1][j]
                sx += c
                ex = max(ex,sx+c)
            else:
                for k in range(c):
                    for j in range(sx,ex):
                        dp[j][sy+c+k] += dp[j][sy+c-k-1]
                sy += c
                ey = max(ey,sy+c)
        res = 0
        for i in range(p):
            x,y = map(int,input().split())
            res = dp[sx+x][sy+y]
            print(res)
            
            
main()

Submission status: Accepted

Solution code:
# origami
import sys
input = sys.stdin.readline

def f(a, n):
    a = [list(e) for e in a]
    for j in range(len(a)):
        for i in range(n):
            if n + i >= len(a[j]):
                a[j].append(a[j][n-1-i])
            else:
                a[j][n+i] += a[j][n-1-i]
        a[j] = a[j][n:]
    return a


def g(a, n):
    return list(zip(*f(list(zip(*a)),n)))


while True:
    n, m, t, p = map(int, input().split())
    a = [[1]*n for _ in range(m)]
    if n == 0: break
    for _ in range(t):
        d, c = map(int, input().split())
        a = (f if d == 1 else g)(a, c)
    for _ in range(p):
        x, y= map(int, input().split())
        print(a[y][x])

Submission status: Accepted

Solution code:
while True:
  n, m, t, p = list(map(int, input().split()))
  if n==0:
    break
  gx, gy = 500, 500

  paper = [[0 for i in range(1000)] for i in range(1000)]
  for i in range(n):
    for j in range(m):
      paper[500+i][500+j] = 1
  for _ in range(t):
    d, c = list(map(int, input().split()))
    if d==1:
      gx = gx+c
      for i in range(c):
        for j in range(1000):
          paper[gx+i][j] += paper[gx-i-1][j]
          paper[gx-i-1][j] = 0
    if d==2:
      gy = gy+c
      for i in range(1000):
        for j in range(c):
          paper[i][gy+j] += paper[i][gy-j-1]
          paper[i][gy-j-1] = 0

  for i in range(p):
    x, y = list(map(int, input().split()))
    print(paper[gx+x][gy+y])

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    grid_wid, grid_hei, t, p = map(int, input().split())
    if grid_wid == 0:
        exit()
    grid = [[1]*grid_wid for _ in range(grid_hei)]

    fold = [list(map(int, input().split())) for _ in range(t)]
    pin = [list(map(int, input().split())) for _ in range(p)]

    # 区間の左端と右端[L,R)
    L = 0
    R = grid_wid
    # 区間の下端と上端[B,H)
    B = 0
    H = grid_hei

    for ope, axis in fold:
        if ope == 1:
            # 横におる
            current_width = R-L
            if axis > current_width/2:  # kaiten
                alter_axis = current_width-axis
                for i in range(alter_axis):
                    for j in range(grid_hei):
                        grid[j][axis-i-1+L] += grid[j][axis+i+L]
                        grid[j][axis+i+L] = 0

                # 回転させる
                for j in range(grid_hei):
                    grid[j] = list(reversed(grid[j]))
                # 区間の更新
                L, R = grid_wid-R+alter_axis, grid_wid-L

            else:
                for i in range(axis):
                    for j in range(grid_hei):
                        grid[j][axis+i+L] += grid[j][axis-i-1+L]
                        grid[j][axis-i-1+L] = 0
                L += axis

        if ope == 2:
            # 縦におる
            current_hei = H-B
            if axis > current_hei/2:  # kaiten
                alter_axis = current_hei-axis
                for i in range(alter_axis):
                    for j in range(grid_wid):
                        grid[axis-i-1+B][j] += grid[axis+B+i][j]
                        grid[axis+i+B][j] = 0

                # 回転させる
                grid = list(reversed(grid))
                # 区間の更新
                B, H = grid_hei-H+alter_axis, grid_hei-B
            else:
                for i in range(axis):
                    for j in range(grid_wid):
                        grid[axis+i+B][j] += grid[axis-i-1+B][j]
                        grid[axis-i-1+B][j] = 0
                B += axis
    for px, py in pin:
        ans = grid[B+py][L+px]
        print(ans)


while True:
    solve()

Submission status: Accepted

Solution code:
# coding: utf-8

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

    # show(origami)


# 横におる処理
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

    # show(origami)

while True:
    # n: 折り紙の幅, m: 折り紙の高さ
    # t: おる操作の回数 p: 穴を開ける操作の回数
    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

    # t回折り紙をおる
    for i in range(t):
        d, c = map(int, raw_input().split())
        # dが1なら横に折る
        if d == 1:
            fold_b(origami, c, satan)
            satan += c
        # dが2なら縦に折る
        if d == 2:
            fold_a(origami, c, katan)
            katan += c

    # p回穴を開ける
    for i in range(p):
        x, y = map(int, raw_input().split())

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

Submission status: Accepted

Solution code:
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])]
	#print('Matrix :', len(matrix), len(matrix[0]))
	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:
			#print('\tFlipping l-r\t:', b, ' Blocks')
			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:
			#print('\tFlipping d-u\t:', b, ' Blocks')
			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]
		#print('\t',matrix)
	for x, y in holing:
		print(matrix[len(matrix) - y - 1][x])

Submission status: Accepted

Solution code:
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')

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


def rev_w(MAP,H,W):
    nextMAP = [[] for y in range(H)]
    for y in range(H):
        nextMAP[y] = MAP[y][::-1]
    return nextMAP

def rev_h(MAP,H,W):
    nextMAP = [[] for y in range(H)]
    for y in range(H):
        for x in range(W):
            nextMAP[y][x] = MAP[H-y-1][x]
    return nextMAP

while True:
    W,H,t,p = inpl()
    if W == 0:
        break
    else:
        MAP = [[1]*W for y in range(H)]
        for _ in range(t):
            d,c = inpl()
            if d == 1:
                if W//2 >= c:
                    hanten = False
                else:
                    hanten = True

                if hanten:
                    MAP = rev_w(MAP,H,W)
                    c = W - c

                nextW = W - c
                nextH = H
                nextMAP = [[1]*nextW for y in range(H)]
                for y in range(H):
                    for x in range(c):
                        nextMAP[y][x] = MAP[y][x+c] + MAP[y][(c-1)-x]
                    for x in range(c,nextW):
                        nextMAP[y][x] = MAP[y][x+c]

                if hanten:
                    nextMAP = rev_w(nextMAP,H,nextW)
            elif d == 2:
                if H//2 >= c:
                    hanten = False
                else:
                    hanten = True

                if hanten:
                    MAP = rev_h(MAP,H,W)
                    c = H - c

                nextW = W
                nextH = H - c
                nextMAP = [[1]*W for y in range(nextH)]
                for x in range(W):
                    for y in range(c):
                        nextMAP[y][x] = MAP[y+c][x] + MAP[(c-1)-y][x]
                    for y in range(c,nextH):
                        nextMAP[y][x] = MAP[y+c][x]

                if hanten:
                    nextMAP = rev_h(nextMAP,H,nextW)

            MAP = nextMAP[:]
            H,W = nextH,nextW
            #for m in nextMAP:
            #    print(m)

        for _ in range(p):
            x,y = inpl()
            print(MAP[y][x])

Submission status: Runtime Error

Solution code:
from operator import add


def fold_right(v, length):
    for i in range(len(v[0])):
        if not any(list(zip(*v))[i]):
            continue
        for j in range(length):
            for yoko in range(len(v)):
                v[yoko][i + j + length] += v[yoko][i + j]
                v[yoko][i + j] = 0
        return v


def fold_up(v, length):
    for i in range(len(v) - 1, -1, -1):
        if not any(v[i]):
            continue
        for j in range(length):
            v[i - j - length] = list(map(add, v[i - j - length], v[i - j]))
            v[i - j] = [0] * len(v[i - j])
        return v


def cut_cut_cut(v, x, y):
    for i in range(len(v) - 1, -1, -1):
        if not any(v[i]):
            continue
        y = i - y
        break
    for i in range(len(v[0])):
        if not any(list(zip(*v))[i]):
            continue
        x = i + x
        break
    return v[y][x]


while True:
    n, m, t, p = map(int, input().split())
    if n == 0 and m == 0 and t == 0 and p == 0:
        break
    origami = [[0] * 63 for _ in range(63)]
    for i in range(m):
        for j in range(n):
            origami[len(origami) - 1 - i][j] = 1
    for i in range(t):
        d, c = map(int, input().split())
        if d == 1:
            origami = fold_right(origami, c)
        else:
            origami = fold_up(origami, c)

    # print(*origami, sep="\n")
    # print()
    for i in range(p):
        x, y = map(int, input().split())
        print(cut_cut_cut(origami, x, y))