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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 1000, 0 ≤ a_i < b_i ≤ 10000, 0 ≤ c_i < d_i ≤ 10000

b_i < a_i + 1, i = 1, …, N − 1

d_i < c_i + 1, i = 1, …, M − 1

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

3
0 3
5 9
12 14
3
1 4
5 11
13 15

3
1 3
5 9
13 14

2
0 4
7 10
2
5 7
10 13

0