В плоском королевстве заканчивается постройка новейшего космического корабля «Энтерпрайз» для полётов в плоском космосе на суб- и сверхсветовых скоростях (при этом корабль подвергается действию ворп-фактора и гравитационных полей плоских черных дыр, что иногда выражается в изменении привычных нам математических правил). Сейчас ведутся активные работы по завершению написания программных модулей для сверхразума корабля.
По проекту навигатор вводит описание траектории полёта в сверхразум корабля на специальном языке программирования 2NAV. Затем сверхразум должен расcчитать все параметры полёта и по специальной команде выполнить его.
В полёте корабль посылает через равные интервалы времени сигнал, содержащий координаты его текущего местоположения. Также сигнал всегда отправляется из точек отправления и прибытия. Выполнив кусочно-линейную интерполяцию по этим координатам, можно оценить траекторию корабля и пройденный им путь. Мы просим вас помочь в разработке навигационного модуля и написать модуль для вычисления длины пройденного пути.
Путь задаётся в параметрическом виде x = x(t) и y = y(t) на языке 2NAV. Этот язык программирования разработан на основе LISP специально для навигации в плоском космосе. Язык оперирует только вещественными числами двойной точности, записанными в формате с фиксированной точкой без знака, предопределёнными константами (число π) и (число e), предопределённой переменной . Выражением на этом языке может быть число, предопределённая переменная или константа, либо конструкция вида , где op — предопределённый в языке оператор или функция, а argi — аргумент, который может быть любым допустимым в языке выражением. Поддерживаемые операторы и функции приведены в списке ниже. В списке представлена операция (в программе записывается без кавычек), количество аргументов и результат ее применения.
Если у оператора с переменным числом аргументов задан только один аргумент, то остальные аргументы полагаются нейтральными относительно соответствующей операции.
Если абсолютная величина результата любого математического действия (включая промежуточные вычисления) оказывается больше 106, то результат округляется до - 106 или 106 в зависимости от того, был результат отрицательным или положительным. Если абсолютная величина результата любого математического действия оказывается меньше 10 - 6, то результат округляется до 0.
Первая строка содержит целые числа T и N (1 ≤ T ≤ 1000, 1 ≤ N ≤ T) — соответственно время, в течение которого корабль находился в пути, и интервал отправки сигналов с координатами.
Следующие строки содержат два корректных выражения на языке 2NAV для x(t) и y(t) соответственно. Числа, константы, переменные, операторы и функции в выражениях могут быть разделены произвольным количеством символов пробела, табуляции и перевода строки. Количество математических действий в каждом из выражений, включая неявные действия в операторах с переменным числом аргументов, не превосходит 104.
Выведите одно вещественное число — длину пути, пройденного кораблём за время T, определённое на основе кусочно-линейной интерполяции его траектории по переданным координатам. Точность ответа должна составлять не менее 2 знаков после десятичной точки.
## Входные Данные
Первая строка содержит целые числа T и N (1 ≤ T ≤ 1000, 1 ≤ N ≤ T) — соответственно время, в течение которого корабль находился в пути, и интервал отправки сигналов с координатами.Следующие строки содержат два корректных выражения на языке 2NAV для x(t) и y(t) соответственно. Числа, константы, переменные, операторы и функции в выражениях могут быть разделены произвольным количеством символов пробела, табуляции и перевода строки. Количество математических действий в каждом из выражений, включая неявные действия в операторах с переменным числом аргументов, не превосходит 104.
## Выходные Данные
Выведите одно вещественное число — длину пути, пройденного кораблём за время T, определённое на основе кусочно-линейной интерполяции его траектории по переданным координатам. Точность ответа должна составлять не менее 2 знаков после десятичной точки.
## Примеры
Входные данные1 1ttВыходные данные1.41Входные данные10 1(cos (/ (* t PI) 10.0))(sin (/ (* t PI) 10.0))Выходные данные3.13
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of generators.
Let $ X \in \mathbb{Z}^+ $ be the distance from Luke to the stormtrooper.
Let $ G = \{(x_i, t_i) \mid i \in \{1, \dots, N\}\} $ be the set of generators, where:
- $ x_i \in \mathbb{Z}^+ $ is the distance from Luke to generator $ i $,
- $ t_i \in \{0, 1\} $ is the type of generator: $ t_i = 1 $ if facing Luke, $ t_i = 0 $ if facing away.
Generators are ordered such that $ x_1 < x_2 < \dots < x_N $, and $ x_i \neq X $ for all $ i $.
**Constraints**
1. $ 1 \leq N \leq 100{,}000 $
2. $ 1 \leq X \leq 10^9 $
3. $ 1 \leq x_i \leq 10^9 $ for all $ i $
4. $ x_i < x_j $ for all $ i < j $
**Objective**
Simulate the trajectory of a plasma bolt fired from the stormtrooper at position $ X $ toward Luke at position $ 0 $. The bolt travels leftward (toward Luke).
- A generator at $ x_i $ with type $ t_i = 1 $ (facing Luke):
- If bolt arrives from the front (right), it is reflected rightward and the generator is destroyed.
- If bolt arrives from the back (left), it passes through unchanged.
- A generator at $ x_i $ with type $ t_i = 0 $ (facing away):
- If bolt arrives from the front (right), it passes through unchanged.
- If bolt arrives from the back (left), it is reflected rightward and the generator is destroyed.
The bolt is reflected by Luke’s lightsaber at position $ 0 $, reversing its direction.
Luke must reflect the bolt **each time** it returns to him after all generators are destroyed.
Determine:
- If it is possible to destroy all generators without the bolt hitting the stormtrooper (i.e., the bolt never reaches $ X $ before all generators are destroyed),
- If possible, compute the total number of times Luke reflects the bolt (including the final reflection after all generators are destroyed, if the bolt returns to him).
**Output**
- $ -1 $ if it is impossible to destroy all generators.
- Otherwise, output the number of times Luke reflects the bolt.