410721: GYM104090 J Painting

Putata likes painting very much. He is now painting on a piece of white paper, which can be regarded as a 2D plane. Initially, Putata drew a straight line $$$x=W$$$ on the paper. In each of the next $$$n$$$ steps, Putata will draw a segment. He will start drawing the $$$i$$$-th segment from $$$(0,a_i)$$$ to $$$(W,b_i)$$$. If his pencil touches any other segment drawn before, he will stop drawing at the point he touches other segments. After drawing a segment, Putata may think the current figure is not so beautiful, and erase the segment he just drew.

In this problem, your task is to report where each segment will end at.

The first line contains two integers $$$n$$$ and $$$W$$$ ($$$1 \leq n \leq 3\times 10^5$$$, $$$1\leq W\leq 10^6$$$), denoting the number of segments and the parameter $$$W$$$.

Each of the following $$$n$$$ lines contains three integers $$$a_i,b_i$$$ and $$$c_i$$$ ($$$1\leq a_i,b_i\leq 10^6$$$, $$$0\leq c_i\leq 1$$$). Putata will erase the $$$i$$$-th segment if and only if $$$c_i=0$$$. It is guaranteed that $$$(0,a_i)$$$ will not coincide with other segments.

Output $$$n$$$ lines, the $$$k$$$-th ($$$1\leq k\leq n$$$) of which contains the coordinate $$$(u_1/v_1,u_2/v_2)$$$ where the $$$k$$$-th segment will end at. You should guarantee that $$$\gcd(u_1,v_1)=\gcd(u_2,v_2)=1$$$.

4 3
1 2 1
2 1 1
3 1 0
3 2 1

(3/1,2/1)
(3/2,3/2)
(2/1,5/3)
(3/1,2/1)