ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2051. Физика

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Андроид Вася читает книгу «Занимательная физика для самых маленьких». Недавно он прочитал главу о равноускоренном движении и решил поставить несколько опытов. Для этого он собрал механическую черепашку, которой можно с помощью пульта управления задавать разное ускорение.
Вася отправил свою черепашку в путешествие по коридору, время от времени изменяя с пульта ее ускорение. Построив график кусочно-линейной зависимости скорости черепашки от времени v1(t), Вася повторил свой эксперимент. Во второй раз он получил кусочно-линейную функцию v2(t), для которой также построил график.
Перед третьим запуском черепашки Вася понял, что зря изобразил графики v1(t) и v2(t) на одном рисунке. Теперь стало непонятно, к какому графику какой отрезок относится. Помогите Васе восстановить графики функций, зная, что оба эксперимента продолжались одно и то же время T и оба раза черепашка преодолела одинаковое расстояние — длину коридора.

Исходные данные

В первой строке дано целое число T — длительность каждого из экспериментов (2 ≤ T ≤ 106). Далее описаны функции h(t) = max(v1(t), v2(t)) и g(t) = min(v1(t), v2(t)). Вторая строка содержит целое число n — количество узлов функции h(t). Следующие n строк содержат пары целых чисел ti и h(ti) — узлы функции h(t) (0 = t1 < t2 < … < tn−1 < tn = T; 0 ≤ h(ti) ≤ 106). Никакие три последовательных узла не лежат на одной прямой. Далее описана функция g(t) в аналогичном формате. Для любого t ∈ [0; T] g(t) ≤ h(t), причем g(t) = h(t) не более чем в 30 точках (в частности, графики не имеют общего подотрезка). Количество узлов каждой функции лежит в пределах от 2 до 100 000.

Результат

Выведите функции v1(t) и v2(t) в формате, аналогичном h(t) и g(t), в том числе никакие три последовательных узла не должны лежать на одной прямой. Все числа на выходе должны быть целыми. Если задача имеет несколько решений, выведите любое из них. Гарантируется, что хотя бы одно решение существует.

Пример

исходные данныерезультат
6
6
0 2
1 1
2 2
3 1
4 2
6 0
6
0 0
1 1
2 0
3 1
4 0
6 0
5
0 2
1 1
2 2
4 0
6 0
5
0 0
1 1
2 0
4 2
6 0

Замечания

В примере длина коридора равняется 5.
Автор задачи: Виктор Камашев (подготовил Булат Зайнуллин)
Источник задачи: XIX Открытый чемпионат Урала по спортивному программированию (апрель, 2015)