Задача C. Барабанная почта

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Когда-то давно члены одного африканского племени, жившие в разных деревнях, использовали для передачи информации звуковую почту. Чтобы передать сообщение, отправитель бил в барабан в промежутки времени ai ≤ t ≤ bi, а получатель слушал и рассказывал жителям своей деревни. Сила звука зависит от погоды — например, во время дождя и грозы звук барабана практически не слышен.

Однажды у племени поменялся вождь, и необходимо было оповестить об этом всех жителей племени. Но, как назло, погода в этот день была очень неустойчивая — то дождь, то туман, то ветер, то солнце. Поэтому звуки барабана можно было слышать только в промежутки времени ci ≤ t ≤ di.

Требуется определить, в какие промежутки времени получатели услышат звук барабана.

Формат входного файла

Входной файл содержит целое число N — количество промежутков [ai, bi]. Далее следуют N пар целых чисел ai bi. Далее во входном файле содержится целое число M — количество промежутков [ci, di], — за которым следуют M пар целых чисел ci di.

Формат выходного файла

Выходной файл должен содержать целое число K — количество промежутков [ei, fi] — и K пар целых чисел ei fi.

Должны выполняться неравенства: fi < ei + 1, i = 1, …, K − 1.

Промежутки нулевой длины выводить не нужно.

Ограничения

1 ≤ N, M ≤ 1000, 0 ≤ ai < bi ≤ 10000, 0 ≤ ci < di ≤ 10000

bi < ai + 1, i = 1, …, N − 1

di < ci + 1, i = 1, …, M − 1

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
0 3
5 9
12 14
3
1 4
5 11
13 15
3
1 3
5 9
13 14
2
2
0 4
7 10
2
5 7
10 13
0

0.072s 0.009s 13