Amidakuji 是一种著名的日本游戏。该游戏包含 $w$（此处 $w$ 为偶数）条长垂直线段，Snuke 可以在它们之间添加一些短水平线段。每条水平线段连接两条相邻的垂直线段。游戏共有 $h$ 层，每条水平线段位于其中一层。因此，总共有 $h(w - 1)$ 个水平线段的候选位置。设 $(a, b)$ 为从上往下数第 $a$ 层、从左往右数第 $b$ 个（从 1 开始计数）候选位置。请查看下一页的图示以了解其外观。

首先，Snuke 在所有满足 $a \equiv b \pmod 2$ 的位置 $(a, b)$ 上添加水平线段。然后，他移除了 $n$ 条位于 $(a_1, b_1), \dots, (a_n, b_n)$ 的水平线段。

游戏规则如下：首先，Snuke 选择一条垂直线段。然后，他站在所选垂直线段的顶端并开始向下移动。当他到达某条水平线段的端点时，他会移动到该水平线段的另一端，并再次开始向下移动。当他到达底端时，游戏结束。对于每个 $i$（从 1 开始计数），请计算当 Snuke 选择第 $i$ 条垂直线段时，他最终到达的位置。

输入格式

第一行包含三个整数 $h, w$ 和 $n$ ($1 \le h, w, n \le 2 \cdot 10^5$，$w$ 为偶数)。接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \le h, 1 \le b_i \le w - 1, a_i \equiv b_i \pmod 2$，且 $(a_i, b_i)$ 两两不同)。

输出格式

输出 $w$ 行。第 $i$ 行输出 Snuke 选择第 $i$ 条线段时最终到达的位置。

样例

输入 1

4 4 1
3 3

输出 1

2
3
4
1

输入 2

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

输出 2

1
4
3
2
5
6

说明

例如，如果他在样例 1 中最初选择最左侧的线段，他会经过 $(1, 1), (2, 2), (4, 2)$ 并到达从左往右数第二条线段的底端。