B. Eren and Armored Titan
time limit per test
1 s.
memory limit per test
256 MB
input
standard input
output
standard output

As soon as Eren came to know the real identity of the Armored Titan, his wrath got no limits. He started attacking the Armoured Titan to bring peace to the paradis island. He seems to know (wonder why?) the total damage at different time stamps that he will deliver to the Armored Titan in the fight. Since he is busy fighting, he asked you to help him find the time stamp at which he will be able to win this fight.

Formally, you are given two sorted arrays of integers $$$a_1,a_2,\dots,a_n$$$ and $$$b_1,b_2,\dots,b_n$$$ where $$$a_i$$$ is the total damage(from $$$t=0$$$) done by Eren and $$$b_i$$$ is the time stamp at which this $$$a_i$$$ damage is received by the Armoured Titan. After that, you are given an array of integers $$$c_1,c_2,\dots,c_m$$$ where $$$c_j$$$ is the HP (health) of Armored Titan. For each $$$c_j$$$ you need to find the smallest timestamp $$$b_i$$$ at which Eren wins his fight.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1≤n,m≤10^5)$$$ — the size of arrays $$$a$$$,$$$b$$$ and size of array $$$c$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1≤a_i≤10^{9})$$$.

The third line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$ $$$(1≤b_i≤10^{9})$$$.

The fourth line contains $$$m$$$ integers $$$c_1,c_2,\dots,c_m$$$ $$$(1≤c_i≤10^{9})$$$.

Output

print $$$m$$$ integers $$$d_1,d_2,\dots,d_m$$$— where $$$d_j$$$ is equal to the smallest time stamp $$$b_i$$$ such that $$$a_i\ge c_j$$$. If it is impossible to defeat the Armoured Titan ($$$a_n \lt c_j$$$), print $$$-1$$$.

Examples
Input
5 3
3 7 8 8 9
1 2 4 7 8
4 8 10
Output
2 4 -1
Input
4 5
1 4 9 13
4 5 8 10
1 13 16 6 15
Output
4 10 -1 8 -1
Input
1 9
598654597
488228616
2 48 57 94 543358150 654502493 835120075 967529230 988262691
Output
488228616 488228616 488228616 488228616 488228616 -1 -1 -1 -1
Note

To avoid getting TLE, you need to solve this problem in $$$O(n+m\cdot log(n))$$$ or $$$O(n+m\cdot log(m))$$$ time.