Самая неприятная вещь в пробках в Москве заключается в том, что водители постоянно пытаются внезапно поменять полосу движения, чтобы двигаться быстрее. В этой задаче Вам следует выяснить, является ли такое поведение разумной стратегией или нет.

Мы изучим относительно простую математическую модель дорожного затора. Предположим, что имеющаяся дорога состоит из n полос, пронумерованных от 1 до n, на i-ой полосе движение происходит со скоростью bi + ai * sin(t + deltai) в момент времени t. Известно, что неравенство bi > ai всегда имеет место, то есть скорость движения всегда положительна. Вы можете сменить полосу движения в любой момент времени, причем c * |x - y| времени займет смена полосы x на полосу y. Мы предполагаем, что Вы не продвигаетесь вперед в течение этого периода.

Определите время, за которое Вы преодолеете расстояние d, а также способ достижения этого времени. Вы стартуете в момент времени 0 на полосе 1, финишировать Вы можете на любой полосе.

Входные данные

Первая строка содержит два целых числа n и d, а также действительное число c (1 ≤ n ≤ 5, 1 ≤ d ≤ 1000, 0.001 ≤ c ≤ 1000). Следующие n строк описывают полосы, каждая из которых содержит два целых числа ai и bi и действительное число deltai (0 ≤ ai < bi ≤ 100, 0 ≤ deltai < 2 * pi).

Выходные данные

В первой строке выведите минимальное время, необходимое для перемещения на расстояние d. Во второй строке выведите количество k изменений полосы движения, необходимых для этого. Значение k не должно быть больше 106. Гарантируется, что всегда существует оптимальная стратегия, требующая не более 106 изменений полос движения. В следующих k строках выведите сами изменения: каждая строка должна содержать новый номер полосы и время начала изменения. Изменения должны выводиться в хронологическом порядке. Если имеется несколько возможных решений, то выведите любой.

Числа с плавающей точкой следует выводить с максимальной точностью. Ваше решение будет считаться правильным, если проверка вашего расписания не приведет к несоответствиям более чем на 10-6 (при проверке пройденного расстояния, при проверке того, что изменения полосы движения не перекрываются и так далее). Поэтому Вам лучше вывести не менее 10 - 12 десятичных знаков в каждом действительном числе.