球落下了

该装置包括一组水平放置的不同高度和长度的平板。这一层被认为是最低的一层。

时间为0时，球从给定位置自由下落。球以每秒1米的固定速度下落。当球到达平板时，可以根据玩家的选择以相同的速度(每秒1米)向左或向右滚动。当它到达平板边缘时，它继续垂直下落。球不允许一次下落超过最大米(在两个平板之间)。

工作

写一个程序，想办法让一个小球在平板上滚动，让它尽快不中断地到达地面。

投入

文件名:fall.in

第一行:n x y max

？四个整数——板数，球起始位置的X，Y坐标，最大允许下落距离。

第二行..n+1:

？三个整数——第I个平板放在高处，水平放置(包括和)，(

注意:

？忽略球的直径和板的厚度。如果球刚好落到板边，则认为是一次性落到板上。

？任何两个板块之间都没有共同点。

？测试数据总有解决方案。

？所有给出的尺寸都是米。

输出

文件名:fall.out

第一行:时间

？一个整数，当球落地的时候。

接下来，每个行为:

p t d

？三个整数，表示在时间t，球碰到板P，向D方向滚动(0表示向左，1表示向右)。

？不包括撞地的情况。

？必须按照球撞击和平板时间递增的顺序输出。

注意

？可能有多个解，只要找到一个解。

限制

？1 n 1000

？-xx0，xx0 (i=1..n)

？0 & lt& lty xx0

例子

秋天，秋天，秋天

3 8 17 20 23

0 10 8 2 4 1

0 10 13 1 11 1

4 14 3 3 16 1

& lt