时间限制： 2.0 秒

空间限制： 512 MB

题目描述

光线追踪是计算机图形学领域的一个重要算法，其原理是追踪一束从光源发出的光，经过不同的反射面，最终到达摄像机处的过程。

在这道问题中，你需要实现一段程序来处理一个简易的光线追踪模型。

在平面中有一些反射面，为方便起见，我们设这些反射面都是线段，与坐标轴成 $45$ 度角摆放，且两个端点的坐标均为整数。为进一步简化问题，我们假设所有的反射表面都是镜面反射。任何一束光线照射到反射面上（为避免讨论，假设反射面不含端点）时，都会改变方向为相应的镜面反射方向。注意，反射面的两侧都可以反射光线。

平面中还有一些激光光源，每个光源位于一个坐标为整数的点上，会向某个水平或竖直的方向发射一定强度的激光。

所有的反射面都不是完美的，每个反射面有一个折损系数 $a$，当强度为 $I$ 的光线照射上去时，反射光线的强度会变成 $aI$。为了便于处理，你可以认为所有反射面的材质均不算太好也不算太糟，因此所有的 $a$ 均在 $0.2\sim 0.8$ 的范围内。

在一些超高速摄影问题中，有时甚至连光速都要考虑在内。在这个问题中，我们不妨假设激光在 $1$ 单位时间内恰好移动 $1$ 单位距离。然而，超高速摄影带来的往往是采样精度的损失，因此对于一束激光，最终采样到的光线强度都是向下取整后的数值。特别地，当一束激光的强度小于 $1$ 时，认为其已经完全耗散。

问题的最开始，平面上没有反射面也没有光源。接下来你需要处理若干个操作，每个操作形如：

1. $1~x_1~y_1~x_2~y_2~a$：在平面上插入一个分别以 $(x_1,y_1)$ 和 $(x_2,y_2)$ 为端点，反射系数为 $a$ 的反射面，保证反射面与坐标轴成 $45$ 度角摆放，且不与先前存在、且还没有被删除的反射面在非端点处相交；另外受到渲染效率的影响，问题中的所有反射面的总长度（可以理解为所有 $|x_1-x_2|$ 之和）不会太大；
2. $2~k$：删除第 $k$ 个操作插入的反射面，保证第 $k$ 个操作发生在当前操作之前，且为一个插入操作，且这个反射面还没有被删除；
3. $3~x~y~d~I~t$：在 $(x,y)$ 位置放置一个光源，发射光线方向为 $d$，强度为 $I$，求其所经 $t$ 时刻后光线到达的坐标以及采样得到的光线强度。其中 $d$ 的含义为：$d=0$ 表示沿 $x$ 坐标增加的方向，$d=1$ 表示沿 $y$ 坐标增加的方向，$d=2$ 表示沿 $x$ 坐标减小的方向，$d=3$ 表示沿 $y$ 坐标减小的方向。另外，保证光源不位于当前存在的某个反射面（不含端点）上。注意：如果 $t$ 时刻后光线刚好到达某个反射面，则其强度取反射后的强度。

输入格式

从标准输入读入数据。

第一行，一个正整数 $m$ 表示操作的总数量。

接下来 $m$ 行，每行描述一个操作，格式如题目描述。

其中，除了所有的 $a$ 和 $I$ 以外的输入均为绝对值不超过 $10^9$ 的整数，其中 $k$ 和 $t$ 为正整数；$a$ 和 $I$ 为小数点不超过 $6$ 位的正实数，其中 $a$ 在 $0.2\sim 0.8$ 之间，$I\le 10^9$。

输出格式

输出到标准输出。

对于每个查询操作输出一行 $3$ 个整数，形如 $x~y~I$，表示激光最终到达位置为 $(x,y)$，采样得到的光线强度为 $I$。特别地，如果采样得到的光线强度为 $0$（即光线已耗散），你也就无需关心最终到达的坐标，而只需要输出 0 0 0 即可。

题目数据保证，你可以在计算时直接使用 $64$ 位浮点数的运算和取整操作，而无需担心可能的精度误差问题。

7
1 0 4 2 2 0.4
1 2 2 0 0 0.45
3 -1 3 0 6 5
3 1 5 3 2.4 5
3 0 2 0 3 4
2 1
3 1 5 3 2.4 5

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

子任务

对于 $100\%$ 的数据，保证 $m\le 10^5$，所有反射面面 $|x_1-x_2|$ 之和不超过 $3\times 10^5$。