WK is hungry now and he needs to eat some food. His Hamster WCQ puts $n$ dishes of food in front of him, numbered from $1$ to $n$. Alice tells him that he can only eat continuous dishes of food, or he will be poisoned by food. For example, if there are $10$ dishes, he can eat the food in the $2$-nd, $3$-rd and $4$-th dishes but he can not eat the food in the $2$-nd, $3$-rd and $5$-th dishes because there is the $4$-th dish between them so it's not continuous. Furthermore, if he chooses to eat food in the $i$-th dish, he has to eat all food in that dish.

WK's stomach has a strange feature that if there is at least $t$ ($= 998857459$) kg food in it, the weight in it will reduce $t$ kg repeatedly until it is strictly lower than $t$ kg. Also, if the weight of food in his stomach is exactly $t$ kg, his stomach will be empty. Now WK wants to eat the smallest number of dishes and remains no less than $k$ kg food in his stomach. Can you tell him how many dishes he needs to choose?

Input

The first line contains two integers $n$ and $m$ ($1 \le n \le 100000, 1 \le m \le 10000$), indicates the number of dishes and the number of queries.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, which is a permutation of $1, 2, \cdots, n$, indicates that there is $(a_i!)$ kg food in the $i$-th dish, where $s! = 1 \times 2 \times 3 \times \cdots \times s$.

The third line contains $m$ integers, the $i$-th integer $k_i$ ($1 \le k_i < t$) indicates a query with the lower bound of weight.

Output

Each line of $m$ lines contains an integer indicates the number of dishes WK needs to choose in that query. If there is no way to reach WK's target, output "-1" instead.

Examples

Input 1

4 2
1 2 3 4
29 31

Output 1

2
3