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):
a = list(map(int,input().split()))

while sum(a) != 0:
	aa = [[1 for i in range(a[0])] for j in range(a[1])]
	for i in range(a[2]):
		k = list(map(int,input().split()))
		if k[0] == 1:
			if a[0] //2 >= k[1]:
				for m in range(a[1]):
					for n in range(k[1]):
						aa[m][2*k[1] - n - 1] += aa[m][n]
					aa[m] = aa[m][k[1]:]
				a[0] -= k[1]
			else:
				for m in range(a[1]):
					for n in range(a[0] - k[1]):
						aa[m][a[0]-(2*(a[0]-k[1])-n-1)-1] += aa[m][a[0]-n-1]
					aa[m].reverse()
					aa[m] = aa[m][a[0]-k[1]:]
				a[0]-=(a[0]-k[1])
		elif k[0] == 2:
			if a[1] // 2 >= k[1]:
				for n in range(a[0]):
					for m in range(k[1]):
						aa[2*k[1]-m-1][n] += aa[m][n]
				a[1] -= k[1]
				aa = aa[k[1]:]
			else:
				for n in range(a[0]):
					for m in range(a[1]-k[1]):
						aa[a[1]-(2*(a[1]-k[1])-m-1)-1][n] += aa[a[1]-m-1][n]
				aa.reverse()
				aa = aa[a[1]-k[1]:]
				a[1] -= (a[1] - k[1])

	for i in range(a[3]):
		p = list(map(int,input().split()))
		print(aa[p[1]][p[0]])
	a = list(map(int,input().split()))

Solution (Python):

import sys

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,sys.stdin.readline().split())
	a=[[1]*n for _ in range(m)]
	if n==0: break
	for _ in range(t):
		d,c=map(int,sys.stdin.readline().split())
		a=(f if d==1 else g)(a,c)
	for _ in range(p):
		x,y=map(int,sys.stdin.readline().split())
		print(a[y][x])

Solution (Python):

import sys

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,sys.stdin.readline().split())
	a=[[1]*n for _ in range(m)]
	if n==0: break
	for _ in range(t):
		d,c=map(int,sys.stdin.readline().split())
		a=(f if d==1 else g)(a,c)
	for _ in range(p):
		x,y=map(int,sys.stdin.readline().split())
		print(a[y][x])

Solution (Python):
def unite(l1, l2):
  len1 = len(l1)
  len2 = len(l2)
  if len1 < len2:
    ret = l2[:]
    for i in range(len1):
      ret[i] += l1[i]
    return ret
  else:
    ret = l1[:]
    for i in range(len2):
      ret[i] += l2[i]
    return ret

while True:
  n, m, t, p = map(int, input().split())
  if n == 0:
    break
  mp = [[1] * n for _ in range(m)]
  for _ in range(t):
    d, c = map(int, input().split())
    if d == 1:
      new_mp = []
      for h in range(m):
        left = mp[h][:c][::-1]
        right = mp[h][c:]
        new_mp.append(unite(left, right))
      n = len(new_mp[0])
    else:
      lenu = max(c, m - c)
      new_mp = [[] for _ in range(lenu)]
      for x in range(n):
        under = [mp[y][x] for y in range(c)][::-1]
        top = [mp[y][x] for y in range(c, m)]
        u = unite(top, under)
        for i in range(lenu):
          new_mp[i].append(u[i])
      m = len(new_mp)
    mp = new_mp
  
  for _ in range(p):
    x, y = map(int, input().split())
    print(mp[y][x])

Solution (Python):



MAX_V = 100


def show(origami):
    for i in range(MAX_V):
        for j in range(MAX_V):
            print(origami[i][j], end = " ")
        print()
    print("--------------------------------------")


def fold_a(origami, c):
    t = c
    for i in range(c):
        for j in range(MAX_V):
            origami[j][t+i] += origami[j][t-i-1]
            origami[j][t-i-1] = 0

    copy = [x[:] for x in origami]

    for i in range(MAX_V):
        for j in range(MAX_V):
            if j-c < 0 or MAX_V-1 < j-c:
                continue
            origami[i][j-c] = copy[i][j]



def fold_b(origami, c):
    t = MAX_V - c -1
    for i in range(MAX_V):
        for j in range(c):
            origami[t-j][i] += origami[t+j+1][i]
            origami[t+j+1][i] = 0

    copy = [x[:] for x in origami]

    for i in range(MAX_V):
        for j in range(MAX_V):
            if i+c < 0 or MAX_V-1 < i+c:
                continue
            origami[i+c][j] = copy[i][j]



def main():
    while True:
        n, m, t, p = map(int, input().split())

        origami = [[0 for i in range(MAX_V)] for _ in range(MAX_V)]

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

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

        for _ in range(t):
            d, c = map(int, input().split())

            if d == 1:
                fold_a(origami, c)
            if d == 2:
                fold_b(origami, c)

        for _ in range(p):
            x, y = map(int, input().split())
            print(origami[MAX_V-y-1][x])

    return 0

main()

Solution (Python):
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 = [[0]*W 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]

            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]

            MAP = nextMAP
            H,W = nextH,nextW

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

Solution (Python):
from operator import add


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


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


def cut_cut_cut(v):
    global white_right
    global white_up
    for i in range(len(v) - 1, -1, -1):
        if not any(v[i]):
            continue
        white_up = i
        break
    for i in range(len(v[0])):
        if not any(list(zip(*v))[i]):
            continue
        white_right = i
        break


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] * 500 for _ in range(500)]
    for i in range(m):
        for j in range(n):
            origami[len(origami) - 1 - i][j] = 1
    white_right = 0
    white_up = len(origami) - 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)
        
        

    cut_cut_cut(origami)
    for i in range(p):
        x, y = map(int, input().split())
        print(origami[white_up - y][white_right + x])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

class UnionFind:
    def __init__(self, size, m):
        self.m = m
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if s1 >= self.m:
                self.table[s1] = s2
            elif s2 >= self.m:
                self.table[s2] = s1
            elif self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    rr = []

    def f():
        n,m,t,p = LI()
        if n == 0:
            return

        dc = [LI() for _ in range(t)]
        xy = [LI() for _ in range(p)]

        ux = UnionFind(n*n, n)
        uy = UnionFind(m*m, m)
        xs = ys = 0
        for d,c in dc:
            if d == 1:
                for i in range(c):
                    ux.union(xs+i, xs+c*2-1-i)
                xs += c
            else:
                for i in range(c):
                    uy.union(ys+i, ys+c*2-1-i)
                ys += c

        for x,y in xy:
            xc = -ux.table[ux.find(xs+x)]
            yc = -uy.table[uy.find(ys+y)]
            rr.append(xc*yc)

        return True

    while f():
        pass

    return JA(rr, "\n")


print(main())

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N,M,T,P = (int(i) for i in input().split())
    answer = []
    while not(N == M == T == P == 0):
        DC = [[int(i) for i in input().split()] for _ in range(T)]
        XY = [[int(i) for i in input().split()] for _ in range(P)]
        rec = [[0]*(32**2+1) for _ in range(32**2+1)]
        for y in range(M):
            for x in range(N):
                rec[y][x] += 1
        ori_x,ori_y = 0,0
        for d,c in DC:
            if d == 1:
                ori_x += c
                for y in range(ori_y,32**2+1):
                    for x in range(ori_x,ori_x+c):
                        
                        rec[y][x] += rec[y][ori_x*2-x-1]
            else:
                ori_y += c
                for y in range(ori_y,ori_y+c):
                    for x in range(ori_x,32**2+1):
                        rec[y][x] += rec[ori_y*2-y-1][x]
        for px,py in XY:
            answer.append(rec[ori_y+py][ori_x+px])

        N,M,T,P = (int(i) for i in input().split())
    for a in answer:
        print(a)
if __name__ == "__main__":
    main()

Solution (Python):


import array
from fractions import Fraction
import functools
import itertools
import math
import os
import sys


def main():
    while True:
        N, M, T, P = read_ints()
        if (N, M, T, P) == (0, 0, 0, 0):
            break
        F = [read_ints() for _ in range(T)]
        H = [read_ints() for _ in range(P)]
        print(*solve(N, M, T, P, F, H), sep='\n')


def solve(N, M, T, P, F, H):
    w = N
    h = M
    paper = [[1] * w for _ in range(h)]

    for d, c in F:
        if d == 1:
            w1 = max(c, w - c)
            npaper = [[0] * w1 for _ in range(h)]
            for y in range(h):
                for dx in range(c):
                    npaper[y][c - 1 - dx] += paper[y][dx]
                for dx in range(c, w):
                    npaper[y][dx - c] += paper[y][dx]
            w = w1
            paper = npaper
            continue

        h1 = max(c, h - c)
        npaper = [[0] * w for _ in range(h1)]
        for x in range(w):
            for dy in range(c):
                npaper[c - 1 - dy][x] += paper[dy][x]
            for dy in range(c, h):
                npaper[dy - c][x] += paper[dy][x]
        h = h1
        paper = npaper

    return [paper[y][x] for x, y in H]





DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Solution (Python):
class Paper:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.table = [[1] * n for _ in range(m)]

    def __str__(self):
        return str(self.table)

    def thickness(self, x, y):
        return self.table[y][x]

    def fold(self, d, c):
        if d == 1:
            return self.foldl(c)
        else:
            return self.foldb(c)

    def foldl(self, c):
        nn = max(c, self.n - c)
        tbl = [[0] * nn for _ in range(self.m)]
        for y in range(self.m):
            for x in range(c):
                tbl[y][x] += self.table[y][c - x - 1]
            for x in range(self.n - c):
                tbl[y][x] += self.table[y][c + x]
        self.n = nn
        self.table = tbl

    def foldb(self, c):
        mm = max(c, self.m - c)
        tbl = [[0] * self.n for _ in range(mm)]
        for x in range(self.n):
            for y in range(c):
                tbl[y][x] += self.table[c - y - 1][x]
            for y in range(self.m - c):
                tbl[y][x] += self.table[c + y][x]
        self.m = mm
        self.table = tbl

while True:
    n, m, t, p = map(int, input().split())
    if n == m == t == p == 0:
        break

    paper = Paper(n, m)
    for i in range(t):
        d, c = map(int, input().split())
        paper.fold(d, c)
    for i in range(p):
        x, y = map(int, input().split())
        print(paper.thickness(x, y))

Solution (Python):
def main(n, m, t, p):
    dpn = [1] * n
    dpm = [1] * m
    ldpn = n
    ldpm = m
    for _ in range(t):
        d, c = map(int, input().split())
        if d == 1:
            if ldpn // 2 < c:
                for i in range(ldpn - c):
                    dpn[c - i - 1] += dpn[c + i]
                dpn = dpn[c - 1::-1]
                ldpn = c
            else:
                for i in range(c):
                    dpn[c + i] += dpn[c - 1 - i]
                dpn = dpn[c:]
                ldpn -= c
        else:
            if ldpm // 2 < c:
                for i in range(ldpm - c):
                    dpm[c - i - 1] += dpm[c + i]
                dpm = dpm[c - 1::-1]
                ldpm = c
            else:
                for i in range(c):
                    dpm[c + i] += dpm[c - 1 - i]
                dpm = dpm[c:]
                ldpm -= c
    ans = []
    for _ in range(p):
        x, y = map(int, input().split())
        ans.append(str(dpn[x] * dpm[y]))
    print("\n".join(ans))


while 1:
    n, m, t, p = map(int, input().split())
    if n == m == t == p == 0:
        break
    main(n, m, t, p)

Solution (Python):
while(True):
    n,m,t,p=map(int,input().split())
    if (n,m,t,p)==(0,0,0,0):
        break
    d=[0 for  i in range(t)]
    c=[0 for  i in range(t)]
    x=[0 for  i in range(p)]
    y=[0 for  i in range(p)]
    nnow,mnow=n,m
    for i in range(t):
        d[i],c[i]=map(int,input().split())
    for i in range(p):
        x[i],y[i]=map(int,input().split())
    paper=[[1 for j in range(n)] for i in range(m)]
    for k in range(t):
        if d[k]==1:
            nnext=max(c[k],nnow-c[k])
            nextpaper=[[0 for j in range(nnext)] for i in range(mnow)]
            if c[k]<=nnow-c[k]:
                for i in range(mnow):
                    for j in range(nnow-c[k]):
                        nextpaper[i][j]+=paper[i][j+c[k]]
                    for j in range(c[k]):
                        nextpaper[i][j]+=paper[i][c[k]-j-1]
            else:
                for i in range(mnow):
                    for j in range(c[k]):
                        nextpaper[i][-j-1]+=paper[i][j]
                    for j in range(nnow-c[k]):
                        nextpaper[i][j]+=paper[i][j+c[k]]
            nnow=nnext        
        else:
            mnext=max(c[k],mnow-c[k])
            nextpaper=[[0 for j in range(nnow)] for i in range(mnext)]
            if c[k]<=mnow-c[k]:
                for j in range(nnow):
                    for i in range(mnow-c[k]):
                        nextpaper[i][j]+=paper[i][j]
                    for i in range(c[k]):
                        nextpaper[-i-1][j]+=paper[i+mnow-c[k]][j]
            else:
                for j in range(nnow):
                    for i in range(mnow-c[k]):
                        nextpaper[-i-1][j]+=paper[mnow-c[k]-1-i][j]
                    for i in range(c[k]):
                        nextpaper[i][j]+=paper[-i-1][j]
            mnow=mnext
        paper=[[nextpaper[i][j] for j in range(nnow)] for i in range(mnow)]
    ans=0
    for i in range(p):
        print(paper[-y[i]-1][x[i]])

Solution (Python):
import sys


from inspect import currentframe

def pri(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    


def solve(n, m, t, p, d, c, x, y):

    a = [[1 for _ in range(m)] for _ in range(n)]
    pri(a)
    for i in range(t):
        if d[i] == 1:
            m = max(m - c[i], c[i])
            a_new = [[0 for _ in range(m)] for _ in range(n)]
            pri(a_new)
            for n_i in range(len(a)):
                for m_i in range(len(a[0])):

                    if m_i >= c[i]:
                        a_new[n_i][m_i - c[i]] += a[n_i][m_i]
                    else:
                        a_new[n_i][c[i] - m_i - 1] += a[n_i][m_i]

            pri(a_new)
            a = a_new
        else:
            n = max(n - c[i], c[i])
            a_new = [[0 for _ in range(m)] for _ in range(n)]
            pri(a_new)
            for n_i in range(len(a)):
                for m_i in range(len(a[0])):

                    if n_i >= c[i]:
                        a_new[n_i - c[i]][m_i] += a[n_i][m_i]
                    else:
                        a_new[c[i] - n_i - 1][m_i] += a[n_i][m_i]

            pri(a_new)
            a = a_new

    for j in range(p):
        print(a[y[j]][x[j]])


    return


if __name__ == '__main__':
    while True:
        n_imput, m_imput, t_imput, p_imput = map(int, input().split())
        if p_imput == m_imput == n_imput == t_imput == 0:
            break
        d_imput = [0 for _ in range(t_imput)]
        c_imput = [0 for _ in range(t_imput)]
        x_imput = [0 for _ in range(p_imput)]
        y_imput = [0 for _ in range(p_imput)]

        for i in range(t_imput):
            d_imput[i], c_imput[i] = map(int, input().split())
        for i in range(p_imput):
            x_imput[i], y_imput[i] = map(int, input().split())


        solve(m_imput, n_imput, t_imput, p_imput, d_imput, c_imput, x_imput, y_imput)

Solution (Python):
import copy

def main():
    while True:
        n,m,t,p = map(int,input().split())
        if not n and not m and not t and not p:
            return

        dlist,clist = [],[]
        
        for _ in range(t):
            d,c = map(int,input().split())
            dlist.append(d)
            clist.append(c)

        coorlist = [tuple(map(int,input().split())) for _ in range(p)]

        oldm = [[1 for _ in range(m)] for _ in range(n)]

        for d,c in zip(dlist,clist):
            if d == 1: 
                if 2*c <= n:
                    newm = [[0 for _ in range(m)] for _ in range(n-c)]
                    for i in range(c):
                        for j in range(m):
                            newm[i][j] = oldm[c+i][j] + oldm[c-1-i][j]
                    for i in range(c,n-c):
                        for j in range(m):
                            newm[i][j] = oldm[c+i][j]
                    n = n-c
                else:
                    newm = [[0 for _ in range(m)] for _ in range(c)]
                    for i in range(n-c):
                        for j in range(m):
                            newm[i][j] = oldm[c+i][j] + oldm[c-1-i][j]
                    for i in range(n-c,c):
                        for j in range(m):
                            newm[i][j] = oldm[c-1-i][j]
                    n = c
            else: 
                if 2*c <= m:
                    newm = [[0 for _ in range(m-c)] for _ in range(n)]
                    for i in range(n):
                        for j in range(c):
                            newm[i][j] = oldm[i][c+j] + oldm[i][c-1-j]
                    for i in range(n):
                        for j in range(c,m-c):
                            newm[i][j] = oldm[i][c+j]
                    m = m-c
                else:
                    newm = [[0 for _ in range(c)] for _ in range(n)]
                    for i in range(n):
                        for j in range(m-c):
                            newm[i][j] = oldm[i][c+j] + oldm[i][c-1-j]
                    for i in range(n):
                        for j in range(m-c,c):
                            newm[i][j] = oldm[i][c-1-j]
                    m = c
            oldm = newm

        ans = 0
        for c in coorlist:
            print(oldm[c[0]][c[1]])

def visualize(mmap):
    print("------------------")
    for j in range(len(mmap[0])):
        print('|', end="")
        for i in range(len(mmap)):
            print(mmap[i][len(mmap[0])-1-j], '|', end="")
        print()
    print("------------------")


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def MAP(): return map(int, input().split())

def remove_left(M, c):
	for i in range(len(M)):
		M[i] = M[i][c:]
	return M

def remove_bottom(M, c):
	M = M[:len(M)-c]
	return M

def reverse_tate(M):
	for i in range(len(M)//2):
		for j in range(len(M[0])):
			M[i][j], M[-1-i][j] = M[-1-i][j], M[i][j]

	return M
def reverse_yoko(M):
	for i in range(len(M)):
		M[i] = M[i][::-1]
	return M


def turn_left(M, c):
	if c > len(M[0])/2:
		M = reverse_yoko(M)
		c = len(M[0]) - c
	for i in range(len(M)):
		for j in range(c):
			M[i][c+j] += M[i][c-1-j]
	M = remove_left(M, c)
	return M

def turn_bottom(M, c):
	if c > len(M)/2:
		M = reverse_tate(M)
		c = len(M) - c
	for i in range(len(M[0])):
		for j in range(c):
			M[len(M)-c-1-j][i] += M[len(M)-c+j][i]
	M = remove_bottom(M, c)
	return M

ans = []
while 1:
	n, m, t, p = MAP()
	if (n, m, t, p) == (0, 0, 0, 0):
		break

	dc = [LIST() for _ in range(t)]
	xy = [LIST() for _ in range(p)]

	M = [[1]*n for _ in range(m)]
	for d, c in dc:
		if d == 1:  
			M = turn_left(M, c)
		else:  
			M = turn_bottom(M, c)

	for x, y in xy:
		ans.append(M[-1-y][0+x])

for i in ans:
	print(i)

Solution (Python):
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()

Solution (Python):

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])

Solution (Python):
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])

Solution (Python):

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 = 0
    R = grid_wid
    
    B = 0
    H = grid_hei

    for ope, axis in fold:
        if ope == 1:
            
            current_width = R-L
            if axis > current_width/2:  
                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:  
                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()