Problem:


w 本の縦棒からなり，高さ(横棒を追加することのできる段数) が h のあみだくじがある．w は偶数である．このあみだくじの横棒を追加する場所の候補のうち上から a 番目，左から b 番目を (a, b) という．((a, b) に横棒を追加した場合，上から a 段目で左から b 番目と b+1 番目の縦棒が結ばれる．) このような場所は合計 h(w &minus;1) 箇所(1 ≤ a ≤ h, 1 ≤ b ≤ w − 1) 存在する．

すぬけ君は，a &equiv; b (mod 2) をみたす場所 (a, b) に全て横棒を追加した．次に，すぬけ君は，(a1, b1), . . . , (an, bn) の場所の横棒を消した．上端で左から i 番目を選んだとき下端で左から何番目になるか，というのを全て求めよ．

Constraints

 1 ≤ h, w,  n ≤ 200000 

 w は偶数

 1 ≤ ai ≤ h

 1 ≤ bi ≤ w − 1

 ai &equiv; bi (mod 2)

 (ai, bi) = (aj, bj) となるような相異なる i, j は存在しない

Input

h w n
a1 b1
. . .
an bn

Output

w 行出力せよ．i 行目には，上端で左から i 番目を選んだとき下端で左から何番目になるかを出力せよ．

Sample Input 1

4 4 1
3 3

Sample Output 1

2
3
4
1

図1: たとえば，上端で左端の縦棒を選ぶと，(1, 1), (2, 2), (4, 2) を通って下端で左から二番目の縦棒にたどり着く．

Sample Input 2

10 6 10
10 4
4 4
5 1
4 2
7 3
1 3
2 4
8 2
7 5
7 1

Sample Output 2

1
4
3
2
5
6



Sample input:
4 4 1
3 3


Sample output:
2
3
4
1

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write
    H, W, N = map(int, readline().split())
    A = [0]*W
    B = [0]*W
    C = [0]*W
    for i in range(W//2):
        A[i] = i * 2 + 1
        A[-i-1] = i * 2
        B[i*2] = C[i*2 - 1] = i
        B[-1-i*2] = C[-1-i*2 + 1] = i + W//2
    *X, = range(W)
    P = [list(map(int, readline().split())) for i in range(N)]
    P.sort()
    for a, b in P:
        if a % 2 == 1:
            k = a // 2
            m = b//2*2
            p = A[(B[m] + k) % W]
            q = A[(B[m+1] + k) % W]
        else:
            k = a // 2 - 1
            m = (b-1)//2*2
            p = A[(C[m+1] + k) % W]
            q = A[(C[m+2] + k) % W]
        X[p], X[q] = X[q], X[p]

    *E0, = range(W)
    for i in range(W//2):
        E0[2*i], E0[2*i+1] = E0[2*i+1], E0[2*i]
    E1 = E0[:]
    for i in range(W//2-1):
        E1[2*i+1], E1[2*i+2] = E1[2*i+2], E1[2*i+1]
    k = H//2
    *Y, = range(W)
    while k:
        if k & 1:
            Y = [Y[e] for e in E1]
        E1 = [E1[e] for e in E1]
        k >>= 1
    if H % 2:
        Y = [Y[e] for e in E0]
    ans = [0]*W
    for i, e in enumerate(Y):
        ans[X[e]] = i+1
    for e in ans:
        write("%d\n" % e)
solve()