Nearest Shops

You are given two sets of points on a number line: one set representing the positions of houses and the other representing the positions of shops. For each house, your task is to determine the shop that is nearest to it. In other words, for each house at position \(h\), find the shop at position \(s\) such that \(|h - s|\) is minimized. If there is a tie, select the shop that appears first in the sorted order of shop positions.

Efficient solutions should consider using binary search to quickly determine the closest shop for each house.

inputFormat

The input is given from standard input (stdin) and consists of three lines:

• The first line contains two integers \(N\) and \(M\) representing the number of houses and shops respectively.
• The second line contains \(N\) space-separated integers, where each integer denotes the position of a house.
• The third line contains \(M\) space-separated integers, where each integer denotes the position of a shop.

outputFormat

Print a single line to standard output (stdout) containing \(N\) integers separated by spaces. Each integer denotes the position of the shop that is closest to the corresponding house (in the order the houses are given in the input).

3 4
1 5 9
2 4 6 8

2 4 8