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: Wrong Answer

Solution code:
def patam1(field, c):
    length = len(field[0]) // 2
    for row in field:
        for i, v in zip(range(c, min(c * 2, len(row))), row[:c]):
            row[i] += v
        for i in reversed(range(c * 2 - len(row))):
            row.append(row[i])
        del row[:c]

def patam2(field, c):
    length = len(field) // 2
    for i, row in zip(range(c, min(c * 2, len(field))), field[:c]):
        for target, cell in enumerate(row):
            field[i][target] += cell
    for i in reversed(range(c * 2 - len(field))):
        field.append(field[i])
    del field[:c]

def solve():
    n, m, t, p = map(int, input().split())
    if n == m == t == p == 0:
        return True
    field = [[1 for x in range(n)] for y in range(m)]
    for i in range(t):
        d, c = map(int, input().split())
        globals()["patam" + str(d)](field, c)
    for i in range(p):
        x, y = map(int, input().split())
        print(field[y][x])


while not solve(): pass

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# coding: utf-8

MAX_V = 70

# デバッグ用の関数
def show(origami):
    for i in range(MAX_V):
        for j in range(MAX_V):
            print(origami[i][j], end = " ")
        print()
    print("--------------------------------------")

# 右に c だけ折り返す処理
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]


# 上に c だけ折り返す処理
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# coding: utf-8

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("--------------------------------------")

# 右に c だけ折り返す処理
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]


# 上に c だけ折り返す処理
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
            # print(
            #     "i: {} j: {} length: {} i-j: {} i-j-length: {}".format(
            #         i, j, length, i - (length - 1 - j), i - j - length
            #     )
            # )
            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
    # print(*origami, sep="\n")
    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(d, c)
        # print(*origami, sep="\n")

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
                        # print(M,y,ori_x*2-x-1, ori_x,x)
                        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()

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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]


###############################################################################
# AUXILIARY FUNCTIONS

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys


from inspect import currentframe

def pri(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    # print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))


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)

Submission status: Accepted

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

Submission status: Accepted

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