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

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

Constraints

• 1 ≤ h, w, n ≤ 200000
• w は偶数
• 1 ≤ a_i ≤ h
• 1 ≤ b_i ≤ w − 1
• a_i ≡ b_i (mod 2)
• (a_i, b_i) = (a_j, b_j) となるような相異なる 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

---