# Codeforces849d rooter's song

Posted by yjjr's blog on February 6, 2018

Wherever the destination is, whoever wemeet, let's render this song together.

On a Cartesian coordinate plane lies arectangular stage of sizew × h, represented by a rectangle withcorners (0, 0), (w, 0), (w, h) and (0, h).

On the sides of the stage standndancers. The i-th of them falls into one of the following groups:

• Vertical: stands at (xi, 0), moves in positivey direction (upwards);
• Horizontal: stands at (0, yi), moves in positivex direction (rightwards).

According to choreography, thei-thdancer should stand still for the first ti milliseconds, andthen start moving in the specified direction at 1 unit per millisecond, untilanother border is reached. It is guaranteed that no two dancers have the samegroup, position and waiting time at the same time.

When two dancers collide (i.e. are on thesame point at some time when both of them are moving), they immediatelyexchange their moving directions and go on.

Dancers stop when a border of the stage isreached. Find out every dancer's stopping position.

Input

The first line of input contains threespace-separated positive integersn, 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 describesa dancer: thei-th among them contains three space-separated integers gi,pi, andti (1 ≤ gi ≤ 2, 1 ≤ pi ≤ 99 999, 0 ≤ ti ≤ 100 000), describing a dancer's groupgi(gi = 1 — vertical, gi = 2 — horizontal), position, and waitingtime. Ifgi = 1 then pi = xi; otherwisepi = yi. It's guaranteed that 1 ≤ xi ≤ w - 1 and 1 ≤ yi ≤ h - 1. It is guaranteed that no two dancershave the same group, position and waiting time at the same time.

Output

Output n lines, thei-th ofwhich contains two space-separated integers (xi, yi) — the stopping positionof thei-th dancer in the input.

Example

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 theinitial setup in the legend, and the tracks of dancers are marked withdifferent colours in the following figure.

In the second example, no dancers collide.

#include<bits/stdc++.h>
using namespace std;
{
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,w,h;
const int maxt=100005,maxn=250000,maxw=200005;
int g[maxn],p[maxn],t[maxn],x[maxn];
pair<int,int>ans[maxn];
vector<int>vx[maxn],vy[maxn];

bool cmp(int x,int y)
{
return p[x]<p[y];
}

int main()
{
for(int i=1;i<=n;i++)
{
x[i]=p[i]-t[i]+1e5;
if(g[i]==1)vx[x[i]].push_back(i);
else vy[x[i]].push_back(i);
}
for(int i=1;i<=2e5;i++)
{
int lx=vx[i].size();
int ly=vy[i].size();
sort(vx[i].begin(),vx[i].end(),cmp);
sort(vy[i].begin(),vy[i].end(),cmp);
for(int j=0;j<lx;j++)
{
int id=vx[i][j];
int right=lx-j;
if(right>ly)ans[id]=make_pair(p[vx[i][j+ly]],h);
else ans[id]=make_pair(w,p[vy[i][right-1]]);
}
for(int j=0;j<ly;j++)
{
int id=vy[i][j];
int up=ly-j;
if(up>lx)ans[id]=make_pair(w,p[vy[i][j+lx]]);
else ans[id]=make_pair(p[vx[i][up-1]],h);
}
}
for(int i=1;i<=n;i++)printf("%d %d\n",ans[i].first,ans[i].second);
return 0;
}