Codeforces 848B. Rooter’s Song(乱搞)

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 (xi, 0), moves in positive y direction (upwards);
  • Horizontal: stands at (0, yi), moves in positive x direction (rightwards).

According to choreography, the i-th dancer should stand still for the first ti milliseconds, and then start moving in the specified direction at 1unit 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.

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 nw and h (1 ≤ n ≤ 100 0002 ≤ 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 gipi, and ti (1 ≤ gi ≤ 21 ≤ pi ≤ 99 9990 ≤ ti ≤ 100 000), describing a dancer’s group gi (gi = 1 — vertical, gi = 2 — horizontal), position, and waiting time. If gi = 1 then pi = xi; otherwise pi = yi. It’s guaranteed that 1 ≤ xi ≤ w - 1 and 1 ≤ yi ≤ 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 (xi, yi) — the stopping position of the i-th dancer in the input.

Examples
input

output

input

output

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.

In the second example, no dancers collide.

题意:给出n个点要么沿着y轴正方向或者x轴正方向,这个过程会发生碰撞,求每个点最后的位置。

非常有趣的题目,vp的时候想了半天,后来被旁边的chf提醒了才会做。。。

假设两个点在T这个时刻在(x,y)这个点发生了碰撞,这两个点自然是(x,0)和(0,y)。假设两个点的出发时刻为t1和t2。那么自然t1+y=T=t2+x。两边减去x+y得到t1-x=t2-y。那么也就是说只有满足t-p均为一个值的点集才可以发生碰撞,而别的点根本没有关系。。。

然后我们可以发现这么个规律:

图随便画的。。。

所以我们按照这个规律把点集内的点排序然后依次对应即可。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注