Андроид Вася читает книгу «Занимательная физика для самых маленьких». Недавно он прочитал главу о равноускоренном движении и решил поставить несколько опытов. Для этого он собрал механическую черепашку, которой можно с помощью пульта управления задавать разное ускорение.

Вася отправил свою черепашку в путешествие по коридору, время от времени изменяя с пульта ее ускорение. Построив график кусочно-линейной зависимости скорости черепашки от времени v₁(t), Вася повторил свой эксперимент. Во второй раз он получил кусочно-линейную функцию v₂(t), для которой также построил график.

Перед третьим запуском черепашки Вася понял, что зря изобразил графики v₁(t) и v₂(t) на одном рисунке. Теперь стало непонятно, к какому графику какой отрезок относится. Помогите Васе восстановить графики функций, зная, что оба эксперимента продолжались одно и то же время T и оба раза черепашка преодолела одинаковое расстояние — длину коридора.

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

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

В примере длина коридора равняется 5.