问题描述

Amidakuji是一个著名的游戏。有$w$列（$w$是偶数），列之间有小短棍连接。每根小短棍都连接相邻两列，并放在$h$层的某一层中，即总共有$h(w-1)$个小短棍可能的位置，用$(a,b)$来表示从上到下第$a$层，从左往右$b$到$b+1$列之间的小短棍。

首先，小A在所有$a \equiv b \pmod 2$的位置上摆上了小短棍，然后他会移除$n$根小短棍。

游戏如下进行：每一列最顶端都放有一个球（标号$1 \sim w$），球各自往下落，落到一层如果有小短棍，球就会移动到相邻那一列去，然后继续下落……

给出移除的那$n$根小短棍的位置，小A想知道每一列的球最终会落到第几列。

输入格式

第一行3个整数$h,w,n$，$w$是偶数。

接下来$n$行，每行$a_i,b_i$表示移除了$(a_i,b_i)$这根小短棍（$1 \leq a_i \leq h,1 \leq b_i \leq w-1, a_i \equiv b_i \pmod 2$）。同一组$(a_i,b_i)$只会出现一次。

输出格式

输出$w$行，每行一个数表示第$i$列的小球会落到第几列。

样例一

input

4 4 1
3 3

output

2
3
4
1

样例二

input

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

output

1
4
3
2
5
6

数据规模

$30\%$的数据，$1 \leq h,w,n \leq 2000$。

$100\%$的数据，$1 \leq h,w,n \leq 2*10^5$。