Dense Amidakuji

Time Limit : 2 sec, Memory Limit : 262144 KB

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

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

Constraints

  • 1 ≤ h, w, n ≤ 200000
  • w は偶数
  • 1 ≤ aih
  • 1 ≤ biw − 1
  • aibi (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
Dense Amidakuji

図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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2014 , Day 2, Tokyo, Japan, 2014-09-13
http://acm-icpc.aitea.net/
http://jag2014summer-day2.contest.atcoder.jp/