Двойная туристическая тропа, расположенная в одном из парков города Крайняя Туле, работает по следующему принципу:
- Вводится декартова система координат.
- В некоторые моменты времени из точек ( - 1, 0) и (1, 0) одновременно выходят два туриста. Первый — из точки ( - 1, 0), второй — из точки (1, 0).
- Оба туриста в паре движутся с одинаковой скоростью 1 (единица длины в секунду), первый — вдоль прямой x = - 1, второй — вдоль прямой x = 1, оба — в положительном направлении оси Oy.
- В некоторые моменты времени появляются перегородки. Перегородка (li, ri) — это отрезок между точками (0, li) и (0, ri). Каждая перегородка появляется мгновенно.
Правительство Крайней Туле хочет узнать для каждой пары туристов, выходящих одновременно, сколько времени (в секундах) они не будут видеть друг друга. Два туриста не видят друг друга, если отрезок, соединяющий их положения на плоскости, пересекает хотя бы одну перегородку. Два отрезка пересекаются, если они имеют хотя бы одну общую точку. Считается, что концы отрезков принадлежат отрезкам.
Помогите правительству, посчитайте требуемые времена. Обратите внимание, что перегородки могут пересекаться (любым способом), накладываться или совпадать.
Выходные данные
Для каждой пары выведите в отдельной строке единственное целое число — время в секундах, в течение которого туристы из соответствующей пары не будут видеть друг друга. Выводите эти числа в том же порядке, в каком пары заданы во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
1 4 3
3 6 5
0 1
|
2
4
|
|
2
|
3 3
0 3 4
0 1 2
2 4 0
1 3 4
|
2
4
4
|