F. Harvest Statistics
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the beautiful Sweet Apple Acres, Applejack is facing her busiest harvest season of the year. She has sorted the harvested apples into $$$n$$$ quality grades (numbered from $$$1$$$ to $$$n$$$). Specifically, she has harvested exactly $$$a_i$$$ apples of grade $$$i$$$.

However, the energetic Rainbow Dash decided to "help" out. She attempted to clear the fallen leaves quickly using her Sonic Rainboom. Unfortunately, she used a bit too much force, and a gust of wind blew away exactly $$$k$$$ apples, causing them to disappear.

As the Element of Honesty, Applejack didn't blame Rainbow Dash. However, she is now facing a mathematical puzzle. Among all possible ways to remove exactly $$$k$$$ apples, there are various outcomes for the "mode" (the most frequent grade) of the remaining pile. She wants to find the maximum possible grade that can serve as a mode in any such outcome.

The problem setter, Mofusigil, who is secretly snacking on apples nearby, wipes his mouth and throws this problem to you.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \times 10^5$$$), representing the number of apple grades (the value range) and the number of queries.

The second line contains $$$n$$$ non-negative integers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ ($$$0 \le a_i \le 10^6$$$) represents the initial count of apples of grade $$$i$$$.

The following $$$q$$$ lines each contain a single integer $$$k$$$ ($$$0 \le k \le \sum_{i=1}^{n} a_i$$$), representing the number of apples blown away by Rainbow Dash.The queries are independent.

It is guaranteed that the initial sequence contains at least one number.

Output

For each query, output a single line containing one integer representing the maximum possible mode of the remaining sequence after removing exactly $$$k$$$ elements.

Example
Input
7 2
1 9 1 9 8 1 0
5
23
Output
5
6
Note

A grade $$$i$$$ is considered a mode if its frequency in the remaining pile is greater than or equal to the frequency of any other grade.