33OJ
登录 注册

#P17810. [ICPC 2019 Nanchang R] Eating Plan

[ICPC 2019 Nanchang R] Eating Plan

Problem Description

Bob is hungry now and he needs to eat some food. Alice puts nn dishes of food in front of him, numbered from 11 to nn. Alice tells him that he can only eat continuous dishes of food, or he will be poisoned by food. For example, if there are 1010 dishes, he can eat the food in the 22-nd, 33-rd and 44-th dishes but he can not eat the food in the 22-nd, 33-rd and 55-th dishes because there is the 44-th dish between them so it's not continuous. Furthermore, if he chooses to eat food in the ii-th dish, he has to eat all food in that dish.

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

Input Format

The first line contains two integers nn and m (1≤n≤100000,1≤m≤10000)m~(1\leq n\leq 100000,1\leq m\leq 10000), indicates the number of dishes and the number of queries.

The second line contains nn integers a1,a2,⋯ ,ana_1,a_2,\cdots,a_n, which is a permutation of 1,2,⋯ ,n1, 2, \cdots, n, indicates that there is (ai!)(a_i!) kg food in the ii-th dish, where s!=1×2×3×⋯×ss! = 1 \times 2 \times 3 \times \cdots \times s.

The third line contains mm integers, the ii-th integer ki(1≤ki<t)k_i(1\leq k_i<t) indicates a query with the lower bound of weight.

Output Format

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

4 2
1 2 3 4
29 31
2
3