结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

市田径队使用一条环形跑道进行耐力训练。跑道周长为 $C$，沿逆时针方向在跑道上标出位置坐标 $0 \sim C-1$。训练开始时，$n$ 名运动员站在跑道上，运动员按 $1 \sim n$ 编号，第 $i$ 名运动员的初始位置为 $x_i$，初始位置两两不同；第 $i$ 名运动员的跑动方向为 $s_i$（$s_i = 1$ 表示逆时针，$s_i = -1$ 表示顺时针）。所有运动员的速度均为每秒 $1$ 个单位，且全程不变速、不回头。

按队里的登记办法，每名运动员手持一张写有自己编号的号码布，即训练开始时运动员 $i$ 持有号码布 $i$。由于跑道较窄，任意两名运动员相遇时，两人交换手中持有的号码布（交换瞬间完成，不占用时间），随后各自继续按原方向前进。训练记录员需要据此推算号码布的流转情况。

训练在第 $T$ 秒（$T$ 为整数）准点结束。请确定结束时刻每名运动员手中持有的是几号号码布，按运动员编号顺序输出。

输入格式

从文件 baton.in 中读入数据。

• 第一行三个整数 $n, C, T$，表示运动员人数、跑道周长与训练结束时刻；
• 接下来 $n$ 行，每行两个整数 $x_i, s_i$，依次表示第 $i$ 名运动员的初始位置与跑动方向。

输出格式

输出到文件 baton.out 中。

输出 $n$ 行，第 $i$ 行一个整数，表示结束时刻运动员 $i$ 手中持有的号码布编号。

样例

3 10 3
0 1
4 -1
7 1

2
1
3

样例 1 解释

按时间线推演：第 $2$ 秒，运动员 $1$ 与运动员 $2$ 在位置 $2$ 相遇，交换号码布——运动员 $1$ 改持号码布 $2$，运动员 $2$ 改持号码布 $1$；此后到第 $3$ 秒训练结束，没有再发生相遇。运动员 $3$ 全程未与人相遇，仍持号码布 $3$。

2 6 7
0 1
3 -1

1
2

样例 2 解释

第 $1.5$ 秒，两名运动员在位置 $1.5$ 相遇并交换号码布；第 $4.5$ 秒，两人在位置 $4.5$ 再次相遇并交换，号码布各自回到原运动员手中。到第 $7$ 秒训练结束时没有再发生相遇，两名运动员仍各持自己的号码布。

3 10 4
0 1
8 -1
5 1

3
1
2

样例 3 解释

按时间线推演：第 $1.5$ 秒，运动员 $2$ 与运动员 $3$ 在位置 $6.5$ 相遇并交换号码布，运动员 $2$ 改持号码布 $3$，运动员 $3$ 改持号码布 $2$；第 $4$ 秒，运动员 $1$ 与运动员 $2$ 在位置 $4$ 相遇，此时训练恰好结束，两人仍按规则交换号码布——运动员 $1$ 改持号码布 $3$，运动员 $2$ 改持号码布 $1$。

数据范围

对于所有测试数据，保证：

• $2 \le n \le 10^5$，$2 \le C \le 10^9$，$0 \le T \le 10^{18}$；
• $0 \le x_i < C$，$s_i \in \{1, -1\}$；
• $x_1, x_2, \dots, x_n$ 两两不同；
• 任意时刻至多有两名运动员位于同一位置。

各测试点的约束如下：

• 特殊性质 A：$C$ 为偶数，且所有 $x_i$ 均为偶数。