Angry Birds#3817
Birds are known for their fondness for sitting on wires. In the provincial town , 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, raising such a cloud of dust that the birds became very angry.
Irritated, the birds began to run along the wire in different directions—some to the left, others to the right. All the birds move at the same 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 any bird reaches the end of the wire, it takes off immediately, and all the other birds, startled by this, turn around and start running in the opposite direction. If two birds reach the edge at the same time, two turns occur, which is effectively the same as nothing happening.
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 for each bird the exact moment it will fly off the wire.
The first line contains a single integer (1 \leq L \leq 10^9) — the length of the wire in meters.
The second line contains the integer (0 \leq n \leq 100000) — the number of birds running to the right.
The third line contains different integers a_i (0 < a_i < L) — the distances in meters from the left end of the wire to each bird running to the right.
The fourth line contains the integer (0 \leq m \leq 100000) — the number of birds running to the left.
The fifth line contains different integers b_i (0 < b_i < L) — the distances in meters from the left end of the wire to each bird running to the left.
No two birds start at the same position. It is guaranteed that at least one bird is on the wire.
In the first line, output integers t_i — for each bird running to the right (in the order given in the input), the number of minutes after which it will fly off the wire.
In the second line, output integers u_i — for each bird running to the left (in the order given in the input), the number of minutes after which it will fly off the wire.
Example 1