Слалом
Незважаючи на те, що снігопади в Мадриді трапляються рідко, інтерес до зимових видів спорту в місті зростає, особливо до лижного спорту. Багато жителів проводять кілька вихідних або навіть цілі тижні, вдосконалюючи свої навички в горах.
У цій задачі ми зосередимося на одній з дисциплін гірськолижного спорту: слаломі. Траса будується шляхом встановлення ряду воріт, які формуються двома стійками. Лижник повинен пройти між двома стійками, що утворюють кожні ворота. Переможцем стає той, хто витратить найменший час на проходження траси, не пропустивши жодних воріт.
Ви нещодавно почали вчитися кататися на лижах, але вже поставили перед собою мету взяти участь у Зимових Олімпійських іграх 2018 року, для яких Мадрид, можливо, представить свою кандидатуру. У рамках теоретичної підготовки вам потрібно написати програму, яка обчислює мінімальну довжину шляху, починаючи з заданої точки і проходячи через усі ворота, поки ви не досягнете останніх, які є фінішною лінією. Ви можете припустити, що ворота розташовані горизонтально і впорядковані від найвищих до найнижчих, так що вам потрібно проходити через них по порядку. Ви вважаєте себе досвідченим лижником, тому можете виконувати будь-які серії поворотів, якими б складними вони не були, і ваше єдине завдання — мінімізувати загальну довжину шляху.
Вхідні дані
Перший рядок кожного випадку містить кількість воріт n (1 ≤ n ≤ 1 000). Наступний рядок містить два числа з плаваючою комою, декартові координати x і y початкової позиції, в цьому порядку. Далі слідують n рядків, кожен з яких містить три числа з плаваючою комою, y x_1 x_2, що означає, що наступні ворота — це горизонтальна лінія від (x_1, y) до (x_2, y). Ви можете бути впевнені, що x_1 < x_2. Значення y строго спадають і завжди менші, ніж у початкової позиції. Останні ворота представляють собою фінішну лінію. Усі координати знаходяться в межах від −500 000 до 500 000 включно. Значення 0 для n означає кінець вводу. Після кожного випадку слідує порожній рядок.
Вихідні дані
Для кожного тестового випадку виведіть рядок з мінімальною відстанню, необхідною для досягнення фінішної лінії. Ваша відповідь повинна бути точною в межах абсолютної або відносної похибки 10^{−7}.