Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Rooter's Song

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWherever 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).

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.

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.

Examples

Input

8 10 8

1 1 10

1 4 13

1 7 1

1 8 2

2 2 0

2 5 14

2 6 0

2 6 1

Output

4 8

10 5

8 8

10 6

10 2

1 8

7 8

10 6

Input

3 2 3

1 1 2

2 1 1

1 1 5

Output

1 3

2 1

1 3

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 03:47:48 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|