Problem
A storm of diamond dust has risen on Shelezyak's planet. As you know, diamond dust causes paralysis in robots. At the beginning of the storm, all the robots were busy working along one straight road. There are m repair shops along the same road. Therefore, it was decided to send each robot to the nearest repair shop to renew their lubricant.
It is necessary for each robot to determine the nearest repair shop to it.
Input
The first line contains the number
n - the number of robots(
\(1 <= n <= 100000\)). The second line contains
n different integers, the
i-th of these numbers specifies the distance from the beginning of the road to the place of work of the
i-th robot . The third line of the input contains the number
m - the number of repair shops (
1 <= m <= 100000). The fourth line contains
m various integers, the
ith of these numbers specifies the distance from the beginning of the road to the
ith repair shop. All distances are positive and do not exceed
109. The robot and the workshop can be located at the same point.
Imprint
Print
n numbers - for each robot, print the number of the nearest repair shop. Repair shops are numbered from
1 to
m in the order in which they are given in the input.
Examples
| # |
Input |
Output |
| 1 |
4
1 2 6 10
2
7 3
| 2 2 1 1 |