You and your band, the Amateurish Composers of Music (ACM), have just finished recording your first song, but once you get back from the studio, you realize that your singer is slightly off-key. You will have to wait too long to reserve more time at the recording studio, and you want to show your friends the result of all of your hard work.
Luckily, what many of your band mates lack in musical talent, they make up for with their programming prowess, and you decide to write an auto-tuning system to fix the off-key recording. Your drummer postulates that you can build a very basic auto-tuning system in three steps:
Convert the sound file into a series of frequencies for the computer to analyze.
Shift each of the frequencies to the closest frequency corresponding to a common note (for the case of this problem, call these “good” frequencies).
Convert the frequency list back into a sound file.
Your lead singer has volunteered to take on the audio conversion steps, but he has turned to you for help in figuring out how much he needs to shift the frequencies to get to the closest right note. Can you help him out?
Each input corresponds to one test case, although your program will be tested against many different sets of inputs. The first line of each input contains two space-separated integers: the number of good frequencies $n$ ($1 \leq n \leq 10^5$) and the number of sampled frequencies $m$ ($1 \leq m \leq 10^5$). The next $n$ lines contain a single integer $g_ i$ ($1 \leq g_ i \leq 10^9$), each representing a single good frequency. The list of good frequencies will be both ordered and will contain no repeated elements. The next $m$ lines each contain a single frequency sample for you to shift $s_ i$ ($1 \leq s_ i \leq 10^9$).
For each of the sample frequencies $s_ i$, print on its own line the value that must be added to $s_ i$ to shift $s_ i$ to the closest good note $g_ i$. For $s_ i$’s directly between two target frequencies, always print the positive shift.
Sample Input 1 | Sample Output 1 |
---|---|
1 3 2 1 2 3 |
1 0 -1 |
Sample Input 2 | Sample Output 2 |
---|---|
2 3 2 6 3 4 5 |
-1 2 1 |