English · Original
Chinese · Translation
Formal · Original
_Wherever the destination is, whoever we meet, let's render this song together._
On a Cartesian coordinate plane lies a rectangular stage of size _w_ × _h_, represented by a rectangle with corners (0, 0), (_w_, 0), (_w_, _h_) and (0, _h_). It can be seen that no collisions will happen before one enters the stage.
On the sides of the stage stand _n_ dancers. The _i_\-th of them falls into one of the following groups:
* **Vertical**: stands at (_x__i_, 0), moves in positive _y_ direction (upwards);
* **Horizontal**: stands at (0, _y__i_), moves in positive _x_ direction (rightwards).
<center></center>According to choreography, the _i_\-th dancer should stand still for the first _t__i_ milliseconds, and then start moving in the specified direction at 1 unit per millisecond, until another border is reached. It is guaranteed that no two dancers have the same group, position and waiting time at the same time.
When two dancers collide (i.e. are on the same point at some time when both of them are moving), they immediately exchange their moving directions and go on.
<center></center>Dancers stop when a border of the stage is reached. Find out every dancer's stopping position.
## Input
The first line of input contains three space-separated positive integers _n_, _w_ and _h_ (1 ≤ _n_ ≤ 100 000, 2 ≤ _w_, _h_ ≤ 100 000) — the number of dancers and the width and height of the stage, respectively.
The following _n_ lines each describes a dancer: the _i_\-th among them contains three space-separated integers _g__i_, _p__i_, and _t__i_ (1 ≤ _g__i_ ≤ 2, 1 ≤ _p__i_ ≤ 99 999, 0 ≤ _t__i_ ≤ 100 000), describing a dancer's group _g__i_ (_g__i_ = 1 — vertical, _g__i_ = 2 — horizontal), position, and waiting time. If _g__i_ = 1 then _p__i_ = _x__i_; otherwise _p__i_ = _y__i_. It's guaranteed that 1 ≤ _x__i_ ≤ _w_ - 1 and 1 ≤ _y__i_ ≤ _h_ - 1. It is guaranteed that no two dancers have the same group, position and waiting time at the same time.
## Output
Output _n_ lines, the _i_\-th of which contains two space-separated integers (_x__i_, _y__i_) — the stopping position of the _i_\-th dancer in the input.
[samples]
## Note
The first example corresponds to the initial setup in the legend, and the tracks of dancers are marked with different colours in the following figure.
<center></center>In the second example, no dancers collide.
_Wherever the destination is, whoever we meet, let's render this song together._
在笛卡尔坐标平面上有一个大小为 $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, stage width, and stage height, respectively.
Let $ D = \{d_1, \dots, d_n\} $ be the set of dancers. For each dancer $ d_i $:
- $ g_i \in \{1, 2\} $: group identifier ($ g_i = 1 $: vertical motion, $ g_i = 2 $: horizontal motion).
- $ p_i \in \mathbb{Z} $: position along the fixed axis ($ p_i = x_i $ if $ g_i = 1 $, $ p_i = y_i $ if $ g_i = 2 $).
- $ t_i \in \mathbb{Z}_{\geq 0} $: waiting time before movement begins.
The stage is the rectangle $ [0, w] \times [0, h] $.
Dancers start on the boundary:
- If $ g_i = 1 $: $ d_i $ starts at $ (p_i, 0) $ or $ (p_i, h) $ (bottom or top edge).
- If $ g_i = 2 $: $ d_i $ starts at $ (0, p_i) $ or $ (w, p_i) $ (left or right edge).
**Constraints**
1. $ 1 \leq n \leq 100{,}000 $
2. $ 2 \leq w, h \leq 100{,}000 $
3. $ 1 \leq p_i \leq 99{,}999 $
4. $ 0 \leq t_i \leq 100{,}000 $
5. For $ g_i = 1 $: $ 1 \leq x_i \leq w-1 $; for $ g_i = 2 $: $ 1 \leq y_i \leq h-1 $
6. No two dancers share the same $ (g_i, p_i, t_i) $.
7. All dancers move at speed 1 unit/ms after waiting time $ t_i $.
8. Dancers move perpendicularly from their starting edge:
- $ g_i = 1 $: move vertically (along $ x = p_i $), direction determined by starting edge (up from bottom, down from top).
- $ g_i = 2 $: move horizontally (along $ y = p_i $), direction determined by starting edge (right from left, left from right).
9. When two dancers collide (occupy same point at same time while both moving), they instantaneously exchange direction vectors.
10. Dancers stop upon reaching any stage border ($ x \in \{0, w\} $ or $ y \in \{0, h\} $).
**Objective**
For each dancer $ d_i $, determine the point $ (x_i^*, y_i^*) \in \{0, w\} \times \{0, h\} $ where they stop, accounting for collisions and direction exchanges.
**Note**: Collision behavior is equivalent to dancers passing through each other without changing direction, while preserving their identities' endpoint mappings — due to indistinguishability in exchange, the final positions correspond to the set of destinations as if no collisions occurred, but assigned to dancers based on relative ordering and time delays.
API Response (JSON)
{
"problem": {
"name": "B. Rooter's Song",
"description": {
"content": "_Wherever the destination is, whoever we meet, let's render this song together._ On a Cartesian coordinate plane lies a rectangular stage of size _w_ × _h_, represented by a rectangle with corners (0",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF848B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_Wherever the destination is, whoever we meet, let's render this song together._\n\nOn a Cartesian coordinate plane lies a rectangular stage of size _w_ × _h_, represented by a rectangle with corners (0...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "_Wherever the destination is, whoever we meet, let's render this song together._\n\n在笛卡尔坐标平面上有一个大小为 $w × h$ 的矩形舞台，由四个顶点 $(0, 0)$、$(w, 0)$、$(w, h)$ 和 $(0, h)$ 构成的矩形表示。可以观察到，在任何人进入舞台之前不会发生碰撞。\n\n在舞台的边上站立着 $...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, w, h \\in \\mathbb{Z}^+ $ denote the number of dancers, stage width, and stage height, respectively. \nLet $ D = \\{d_1, \\dots, d_n\\} $ be the set of dancers. For each dancer $...",
"is_translate": false,
"language": "Formal"
}
]
}