Angry Birds
Birds are known for their fondness of sitting on wires. In the provincial town K, there is a particularly long wire that has become a favorite spot for them. One day, several birds were perched on this wire when a pig ran underneath, kicking up a cloud of dust that greatly disturbed them.
Irritated, the birds began running along the wire in different directions—some to the left, others to the right. Each bird runs at a constant speed of one meter per minute. When two birds moving towards each other meet, they immediately turn around and continue running at the same speed in the opposite direction. This process would go on indefinitely, but the wire is finite. As soon as a bird reaches the end of the wire, it flies away, causing all the other birds to turn around and run in the opposite direction. If two birds reach the edge at the same time, two turns occur, effectively resulting in no change.
Your task is to write a program that, given the length of the wire, the initial positions, and the running directions of the birds, determines the exact moment each bird will fly off the wire.
Input
The first line contains a single integer L (1 ≤ L ≤ 10^9) — the length of the wire in meters.
The second line contains the number n (0 ≤ n ≤ 100000) — the number of birds running to the right. The third line contains n different integers a_i (0 < a_i < L) — the distances in meters from the left end of the wire to the birds running to the right.
The fourth line contains the number m (0 ≤ m ≤ 100000) — the number of birds running to the left. The fifth line contains m different integers b_i (0 < b_i < L) — the distances in meters from the left end of the wire to the birds running to the left.
No two birds start at the same position. It is guaranteed that there is at least one bird on the wire.
Output
In the first line, output n integers t_i — the number of minutes after which the i-th bird running to the right, in the order given in the input, will fly off the wire. In the second line, output m integers u_i — the number of minutes after which the i-th bird running to the left, in the order given in the input, will fly off the wire.