Задачі
Злобні птахи
Злобні птахи
Як відомо, птахи полюбляють сидіти на проводах. В провінціальному місті \textbf{K} є один довгий провід, який особливо сподобався їм. В один прекрасний момент на ньому сиділо декілька птахів. Усе було б добре, да ось лише свиня, що пробігла під проводом, підняла таку хмару пилу, що дуже разсердила птахів.
Ставши злобними, птахи почали біжгти по цьому проводу у різні сторони --- хтось наліво, хтось направо. При цьому усі птхи стали бігти з однаковою швидкістю, рівною одному метру за хвилину. При зустрічі двох птахів, які рухаються назустріч один одному, вони відразу ж розвертаються і починають бігти з тією ж швидкісю у протилежному напрямку. цей процес продовжувався б нескінченно довго, але тільки провід виявився усе-таки скінченним, і як тільки якась з пташок добігає до кінця провода, вона тут же злітає, а усі інші птахи, ошарашені цим, розвертаються і починають бігти у протилежному напямку. Якщо ж до краю добігають одночасно дві пташки, то відувається два развороти, або, що те ж саме, нічого не відбувається.
Вам необхідно написати програму, яка по довжині провода, початковим позиціям і напрямкам бігу птахів вияснить для кожної пташки, у який момент часу вона злетить з провода.
\InputFile
У першому рядку задано єдине ціле число \textbf{L} (\textbf{1} ≤ \textbf{L} ≤ \textbf{10^9}) --- довжина провода в метрах.
У другому рядку записано число \textbf{n }(\textbf{0 }≤ \textbf{n }≤ \textbf{100000}) - кількість пташок, які біжать праворуч. У третьому рядку записано \textbf{n} різних цілих чисел \textbf{a_i} (\textbf{0 }< \textbf{a_i} < \textbf{L}) - відстані в метрах від лівого кінця провода до пташок, які біжжать праворуч.
У четвертому рядку записано число \textbf{m} (\textbf{0 }≤ \textbf{m }≤ \textbf{100000}) - кількість пташок, які біжать ліворуч. У п'ятому рядку записано \textbf{m }різних цілих чисел \textbf{b_i} (\textbf{0 }< \textbf{b_i} < \textbf{L}) - відстані в метрах від лівого кінця провода до птшок, які біжать ліворуч.
Ніякі дві пташки не знаходяться спочатку у одному і тому ж місці. Гарантується, що на проводі сидить хоча б одна пташка.
\OutputFile
У першому рядку виведіть \textbf{n }цілих чисел \textbf{t_i} - через скільки хвилин полетить \textbf{i}-та у порядку опису у вхідних даних пташка, яка біжить направо. У другому рядку виведіть \textbf{m }цілих чисел \textbf{u_i} - через скільки хвилин полетить \textbf{i}-та у порядку опису у вхідних даних пташка, яка біжить ліворуч.
Вхідні дані #1
10 2 8 9 3 2 5 7
Вихідні дані #1
5 1 10 13 10