Злые птицы
시간 제한2초메모리 제한256 MB
새들이 전선 위를 달리며 서로 부딪히면 방향을 바꾸고, 한 마리가 끝에 닿아 날아가면 나머지가 모두 되돌아설 때 각 새가 날아가는 시각을 구한다.
문제
Как известно, птицы любят сидеть на проводах. В уездном городе K есть один длинный, особенно полюбившийся им провод. В один прекрасный момент на нем сидело несколько птиц. Все было бы хорошо, да вот только пробежавшая под проводом свинья подняла такую тучу пыли, что очень разозлила птиц.
Став злыми, птицы начали бежать по этому проводу в разные стороны — кто-то налево, кто-то направо. При этом все птицы стали бежать с одинаковой скоростью, равной одному метру в минуту. При встрече двух птиц, двигающихся навстречу друг другу, они немедленно разворачиваются и начинают бежать с той же скоростью в противоположном направлении. Этот процесс продолжался бы бесконечно долго, но только провод оказался все-таки конечным, и как только какая-та из птиц добегает до конца провода, она тут же взлетает, а все остальные птицы, ошеломленные этим, разворачиваются и начинают бежать в противоположном направлении. Если же до края добегают одновременно две птицы, то происходит два разворота, или, что то же самое, ничего не происходит.
Вам необходимо написать программу, которая по длине провода, начальным позициям и направлениям бега птиц выяснит для каждой птицы, в какой момент времени она улетит с провода.
입력
В первой строке задано единственное целое число L (1 ≤ L ≤ 109) — длина провода в метрах.
Во второй строке записано число n (0 ≤ n ≤ 100 000) — количество птиц, бегущих направо. В третьей строке записано n различных целых чисел ai (0 < ai < L) — расстояния в метрах от левого конца провода до птиц, бегущих направо.
В четвертой строке записано число m (0 ≤ m ≤ 100 000) — количество птиц, бегущих налево. В пятой строке записано m различных целых чисел bi (0 < bi < L) — расстояния в метрах от левого конца провода до птиц, бегущих налево.
Никакие две птицы не находятся исходно в одном и том же месте. Гарантируется, что на проводе сидит хотя бы одна птица.
출력
В первой строке выведите n целых чисел ti — через сколько минут улетит i-я по порядку описания во вводе птица, бегущая направо. Во второй строке выведите m целых чисел ui — через сколько минут улетит i-я по порядку описания во вводе птица, бегущая налево.