题目描述

莫斯科堵车时最令人恼火的事情之一，就是司机总会突然变道，希望借此开得更快。现在考虑下面这个简化的数学模型，判断这种策略究竟能带来多大收益。

有一条包含 $N$ 条车道的道路，车道编号为 $1$ 到 $N$。

在时刻 $t$，第 $i$ 条车道向前移动的速度为：

$v_i(t)=b_i+a_i\sin(t+\delta_i)$。

始终满足 $b_i>a_i$，因此所有车道在任意时刻的速度都严格为正。

你可以在任意时刻从第 $x$ 条车道切换到第 $y$ 条车道。完成这次变道需要时间：

$c\cdot|x-y|$。

在变道所花费的这段时间中，你不会向前移动。

你在时刻 $0$ 从第 $1$ 条车道开始行驶，需要向前行驶总距离 $d$。终点时所在的车道可以任意。

请求出完成这段距离所需要的最短时间，并给出一种达到该最短时间的换道方案。

输入格式

第一行包含两个整数 $N,d$ 和一个实数 $c$：

• $1\le N\le5$；
• $1\le d\le1000$；
• $0.001\le c\le1000$。

接下来 $N$ 行描述各条车道。第 $i$ 行包含两个整数 $a_i,b_i$ 和一个实数 $\delta_i$：

• $0\le a_i<b_i\le100$；
• $0\le\delta_i<2\pi$。

第 $i$ 条车道在时刻 $t$ 的速度为 $b_i+a_i\sin(t+\delta_i)$。

输出格式

第一行输出完成距离 $d$ 所需的最短时间。

第二行输出变道次数 $K$。

要求：

$K\le10^6$。

题目保证总存在一种最优策略，使得变道次数不超过 $10^6$。

接下来 $K$ 行按照时间先后顺序输出每一次变道。每行包含：

new_lane time

其中：

• new_lane 表示变道结束后进入的车道编号；
• time 表示这次变道开始的时刻。

如果存在多种最优方案，输出任意一种即可。

所有实数应尽可能高精度输出。评测程序会根据你输出的换道计划重新模拟整个过程；总行驶距离、变道时间区间不重叠等条件的误差均不能超过约 $10^{-6}$。因此建议至少输出小数点后 $10$～$12$ 位。

样例 1

1 100 0.5
4 5 0

19.71726232777025
0

样例 2

3 100 0.5
4 5 0
2 5 0.5
0 5 0

19.052103083697858
4
2 3.6645304897691258
1 5.783185307179586
2 9.947715796948712
3 15.207963267948966

说明

在某一条车道 $i$ 上从时刻 $t_1$ 行驶到 $t_2$ 时，前进距离为该时间段内速度函数的积分：

$\displaystyle \int_{t_1}^{t_2}\left(b_i+a_i\sin(t+\delta_i)\right)dt$。

变道期间只消耗时间，不产生前进距离。