Злые птицы
Как известно, птицы любят сидеть на проводах. В уездном городе K есть один длинный, особенно полюбившийся им провод. В один прекрасный момент на нем сидело несколько птиц. Все было бы хорошо, да вот только пробежавшая под проводом свинья подняла такую тучу пыли, что очень разозлила птиц.
Став злыми, птицы начали бежать по этому проводу в разные стороны — кто-то налево, кто-то направо. При этом все птицы стали бежать с одинаковой скоростью, равной одному метру в минуту. При встрече двух птиц, двигающихся навстречу друг другу, они немедленно разворачиваются и начинают бежать с той же скоростью в противоположном направлении. Этот процесс продолжался бы бесконечно долго, но только провод оказался все-таки конечным, и как только какая-та из птиц добегает до конца провода, она тут же взлетает, а все остальные птицы, ошеломленные этим, разворачиваются и начинают бежать в противоположном направлении. Если же до края добегают одновременно две птицы, то происходит два разворота, или, что то же самое, ничего не происходит.
Вам необходимо написать программу, которая по длине провода, начальным позициям и направлениям бега птиц выяснит для каждой птицы, в какой момент времени она улетит с провода.
Входные данные
В первой строке задано единственное целое число L (1 ≤ L ≤ 10^9) - длина провода в метрах.
Во второй строке записано число n (0 ≤ n ≤ 100000) - количество птиц, бегущих направо. В третьей строке записано n различных целых чисел a_i (0 < a_i < L) - расстояния в метрах от левого конца провода до птиц, бегущих направо.
В четвертой строке записано число m (0 ≤ m ≤ 100000) - количество птиц, бегущих налево. В пятой строке записано m различных целых чисел b_i (0 < b_i < L) - расстояния в метрах от левого конца провода до птиц, бегущих налево.
Никакие две птицы не находятся исходно в одном и том же месте. Гарантируется, что на проводе сидит хотя бы одна птица.
Выходные данные
В первой строке выведите n целых чисел t_i - через сколько минут улетит i-я по порядку описания во вводе птица, бегущая направо. Во второй строке выведите m целых чисел u_i - через сколько минут улетит i-я по порядку описания во вводе птица, бегущая налево.