README.md

K. Пересечение отрезков

Вам даны две последовательности отрезков. Каждый отрезок задаётся координатой начала и конца — [start_i, end_i].

Отрезки каждой последовательности отсортированы слева направо и не имеют общих точек. Найдите пересечение двух последовательностей отрезков. То есть третью последовательность отрезков, такую, что:

1. Каждый отрезок содержится в некотором отрезке и первой, и второй последовательности;
2. Никакой отрезок нельзя увеличить;
3. Отрезки этой последовательности не имеют общих точек;
4. Отрезки в последовательности также отсортированы в порядке возрастания.

Формат ввода

В первой строке дано число отрезков в первой последовательности n (0 ≤ n ≤ 100000) В следующих n строках даны отрезки первой последовательности по одному на строке.

Каждый отрезок записан в формате start_i end_i, координаты начала и конца целые неотрицательные числа, не превосходящие по модулю 10⁹.

Формат вывода

Выведите по одному в строке отсортированные отрезки из пересечения последовательностей в том же формате, что и во входных данных. Заметьте, что длина отрезков в пересечении может быть нулевой, в этом случае start_i = end_i.

Пример 1

3 1 4 5 10 15 16 2 0 2 4 5

1 2 4 4 5 5

Пример 2

1 1 4 1 1 4

1 4