Problem B: [Easy II] Nearest Price

Problem B: [Easy II] Nearest Price

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 1533  Solved: 245
[Submit][Status][Web Board]


Neko likes to eat fish recently. There are various kinds of fish in the market and Neko has \(X\) dollars. If the market happens to have a fish with a price of \(X\), Neko will say "Meow". Otherwise, Neko will buy the most expensive fish which he can afford and say the change. (If Neko can't afford any fish, he will come back directly and say the money he has.)

Neko will go to the market with \(X\) dollars for \(T\) days. \(X\) may change everyday but the kinds of fish in the market will never change.


The first line contains a single integer \(T(1{\leq}T{\leq}10^6)\) —— the number of the days when Neko needs to buy fish.

The second line contains a single integer \(N(1{\leq}N{\leq}10^6)\) —— denoting there are/is \(N\) kind(s) of fish in the market.

The third line contains \(T\) integers \(x_1, x_2, x_3, ... , x_T(1{\leq}x_i{\leq}10^9,1{\leq}i{\leq}T)\) —— the money Neko has for each day.

The fourth line contains \(N\) integers \(p_1, p_2, p_3, ... , p_N(1{\leq}p_i{\leq}10^9,1{\leq}i{\leq}N)\) which are the prices of the fish in the market.

It is guaranteed that prices are in ascending order.


For each day, print only one line for what Neko said.

Sample Input

1 3
2 3

Sample Output