19972번 - Москва 2042 스페셜 저지다국어

К 2042 году правительство Москвы завершило очередной масштабный проект, доведя количество кольцевых автодорог до $n$. Теперь у автомобилиста еще больше способов постоять в пробке в попытке добраться от одной точки города до другой.

Компания <<Giggle>> планирует в своем новом продукте <<Giggle Maps>> реализовать возможность проложить оптимальный маршрут от одного перекрестка до другого. Карта Москвы во внутреннем формате программы представляет собой набор из $m$ радиальных и $n$ кольцевых магистралей, при этом некоторые из кольцевых магистралей являются односторонними. 

В математической модели <<Giggle>> все кольцевые магистрали представляют собой концентрические окружности с центром на Красной площади и радиусами $r_1, r_2, \ldots, r_n$. Радиальные магистрали представляют собой отрезки, один из концов каждого отрезка лежит на Красной площади, а другой --- на кольцевой магистрали с максимальным радиусом. Если встать на Красной площади и смотреть на восток, то, чтобы посмотреть в направлении $j$-ой радиальной магистрали, нужно повернуться против часовой стрелки на $a_j$ градусов. По каждой из радиальных магистралей можно ехать в любом направлении. Кольцевые магистрали, в свою очередь, бывают как двусторонними, так и односторонними.

Помогите компании <<Giggle>> найти кратчайший путь от перекрестка где пересекаются $i_s$-я кольцевая и $j_s$-я радиальная магистраль до перекрестка, где пересекаются $i_t$-я кольцевая и $j_t$-я радиальная магистраль. При этом проезжать через Красную площадь не разрешается.

Первая строка входного файла содержит целые числа $n$ и $m$ ($1 \le n, m \le 100\,000$).

Следующие $n$ строк описывают кольцевые магистрали. Каждая магистраль описывается целым числом $r_i$ ($1 \le r_i \le 10^6$) и числом 0, если магистраль является двусторонней, 1, если по ней разрешено движение только против часовой стрелки (в сторону увеличения углов радиальных магистралей) или $-1$, если по ней разрешено движение только по часовой стрелке.

Следующие $m$ строк описывают радиальные магистрали. Каждая магистраль описывается одним целым числом $A_j$, причем $a_j = A_j / 10^6$ ($0 \le A_j < 360\cdot 10^6$).

Затем следует две строки: первая из них содержит числа $i_s$ и $j_s$, а вторая --- числа $i_t$ и $j_t$.

Выведите в выходной файл одно вещественное число: минимальное расстояние, которое придется проехать, чтобы попасть с перекрестка где пересекаются $i_s$-я кольцевая и $j_s$-я радиальная магистраль на перекресток, где пересекаются $i_t$-я кольцевая и $j_t$-я радиальная магистраль. Ваш ответ должен отличаться от правильного не больше чем на $10^{-4}$.