D. Rooter's Song

_无论目的地在哪里，无论我们会遇见谁，让我们一起唱出这首歌。_ 在笛卡尔坐标平面上有一个大小为 $w × h$ 的矩形舞台，由四个角点为 $(0, 0)$、$(w, 0)$、$(w, h)$ 和 $(0, h)$ 的矩形表示。可以观察到，在任何人进入舞台之前不会发生碰撞。 在舞台的边上站立着 $n$ 位舞者。第 $i$ 位舞者属于以下两类之一： 根据编舞安排，第 $i$ 位舞者将在前 $t_i$ 毫秒内保持静止，然后以每毫秒 $1$ 单位的速度沿指定方向移动，直到到达另一条边界。保证没有任何两位舞者具有相同的组别、位置和等待时间。 当两位舞者发生碰撞（即在某一时刻处于同一点且两人均在移动）时，他们会立即交换移动方向并继续前进。 当舞者到达舞台边界时停止。请找出每位舞者的停止位置。 输入的第一行包含三个用空格分隔的正整数 $n$、$w$ 和 $h$（$1 ≤ n ≤ 100 000$，$2 ≤ w, h ≤ 100 000$）——分别表示舞者的数量和舞台的宽与高。 接下来的 $n$ 行每行描述一位舞者：第 $i$ 行包含三个用空格分隔的整数 $g_i$、$p_i$ 和 $t_i$（$1 ≤ g_i ≤ 2$，$1 ≤ p_i ≤ 99 999$，$0 ≤ t_i ≤ 100 000$），分别描述舞者的组别 $g_i$（$g_i = 1$ 表示垂直方向，$g_i = 2$ 表示水平方向）、位置和等待时间。若 $g_i = 1$，则 $p_i = x_i$；否则 $p_i = y_i$。保证 $1 ≤ x_i ≤ w - 1$ 且 $1 ≤ y_i ≤ h - 1$。保证没有任何两位舞者具有相同的组别、位置和等待时间。 输出 $n$ 行，第 $i$ 行包含两个用空格分隔的整数 $(x_i, y_i)$ —— 输入中第 $i$ 位舞者的停止位置。 第一个例子对应于题面中的初始设置，舞者的运动轨迹在下图中用不同颜色标出。 在第二个例子中，没有舞者发生碰撞。 ## Input 输入的第一行包含三个用空格分隔的正整数 $n$、$w$ 和 $h$（$1 ≤ n ≤ 100 000$，$2 ≤ w, h ≤ 100 000$）——分别表示舞者的数量和舞台的宽与高。接下来的 $n$ 行每行描述一位舞者：第 $i$ 行包含三个用空格分隔的整数 $g_i$、$p_i$ 和 $t_i$（$1 ≤ g_i ≤ 2$，$1 ≤ p_i ≤ 99 999$，$0 ≤ t_i ≤ 100 000$），分别描述舞者的组别 $g_i$（$g_i = 1$ 表示垂直方向，$g_i = 2$ 表示水平方向）、位置和等待时间。若 $g_i = 1$，则 $p_i = x_i$；否则 $p_i = y_i$。保证 $1 ≤ x_i ≤ w - 1$ 且 $1 ≤ y_i ≤ h - 1$。保证没有任何两位舞者具有相同的组别、位置和等待时间。 ## Output 请输出 $n$ 行，第 $i$ 行包含两个用空格分隔的整数 $(x_i, y_i)$ —— 输入中第 $i$ 位舞者的停止位置。 [samples] ## Note 第一个例子对应于题面中的初始设置，舞者的运动轨迹在下图中用不同颜色标出。在第二个例子中，没有舞者发生碰撞。

**Definitions** Let $ n, w, h \in \mathbb{Z}^+ $ denote the number of dancers, width, and height of the rectangular stage, respectively. Let $ D = \{d_1, \dots, d_n\} $ be the set of dancers, where each dancer $ d_i $ is characterized by: - $ g_i \in \{1, 2\} $: group (1 = vertical, 2 = horizontal), - $ p_i \in \mathbb{Z} $: position along the respective axis (if $ g_i = 1 $, then $ p_i = x_i \in [1, w-1] $; if $ g_i = 2 $, then $ p_i = y_i \in [1, h-1] $), - $ t_i \in \mathbb{Z}_{\geq 0} $: waiting time before movement begins. Initial positions: - If $ g_i = 1 $, dancer $ d_i $ starts at $ (x_i, 0) $ and moves vertically upward. - If $ g_i = 2 $, dancer $ d_i $ starts at $ (0, y_i) $ and moves horizontally rightward. **Constraints** 1. $ 1 \leq n \leq 100{,}000 $ 2. $ 2 \leq w, h \leq 100{,}000 $ 3. $ 1 \leq x_i \leq w-1 $ for $ g_i = 1 $, $ 1 \leq y_i \leq h-1 $ for $ g_i = 2 $ 4. $ 0 \leq t_i \leq 100{,}000 $ 5. No two dancers share the same $ (g_i, p_i, t_i) $ **Objective** For each dancer $ d_i $, determine their final stopping position $ (x_i^*, y_i^*) $ upon reaching a stage border, accounting for: - Delayed start: movement begins at time $ t_i $. - Direction: vertical dancers move along $ x = x_i $ from $ y = 0 $ to $ y = h $; horizontal dancers move along $ y = y_i $ from $ x = 0 $ to $ x = w $. - Collisions: when two moving dancers meet at a point, they instantaneously exchange directions. **Key Insight** Due to the symmetry of direction exchange upon collision, the *set* of final positions is invariant under collisions — each dancer effectively "passes through" the other, and the final positions correspond to those of dancers with swapped identities but unchanged trajectories. Thus, we can ignore collision dynamics and compute final positions as if dancers pass through each other, then reassign positions based on relative ordering and timing. **Formal Reduction** Define for each dancer $ d_i $: - If $ g_i = 1 $: trajectory is $ (x_i, y(t)) $, with $ y(t) = \max(0, t - t_i) $, stops at $ y = h $ → arrival time $ T_i = t_i + h $. - If $ g_i = 2 $: trajectory is $ (x(t), y_i) $, with $ x(t) = \max(0, t - t_i) $, stops at $ x = w $ → arrival time $ T_i = t_i + w $. Let $ V = \{ d_i \mid g_i = 1 \} $, $ H = \{ d_i \mid g_i = 2 \} $. For vertical dancers: final position is $ (x_i, h) $. For horizontal dancers: final position is $ (w, y_i) $. Due to collision symmetry, the mapping from initial dancers to final positions is a permutation determined by relative arrival times and initial ordering along the direction of motion. **Final Computation** 1. For each dancer $ d_i $: - Compute arrival time $ T_i = t_i + h $ if $ g_i = 1 $, else $ T_i = t_i + w $. 2. Sort vertical dancers by $ x_i $; sort horizontal dancers by $ y_i $. 3. Sort all dancers by $ T_i $, and assign final positions in order: - The $ k $-th earliest arriving dancer (by $ T_i $) gets the $ k $-th final position in the sorted list of all final positions (sorted by type and coordinate). 4. Final positions are: - All vertical dancers end at $ (x_i, h) $, sorted by $ x_i $, - All horizontal dancers end at $ (w, y_i) $, sorted by $ y_i $. Concatenate these two sorted lists. 5. Assign each dancer’s final position based on the sorted order of their arrival time $ T_i $. **Output** For each dancer $ d_i $ in input order, output $ (x_i^*, y_i^*) $, the final position assigned via the above permutation.