#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 dishes of food in front of him, numbered from to . Alice tells him that he can only eat continuous dishes of food, or he will be poisoned by food. For example, if there are dishes, he can eat the food in the -nd, -rd and -th dishes but he can not eat the food in the -nd, -rd and -th dishes because there is the -th dish between them so it's not continuous. Furthermore, if he chooses to eat food in the -th dish, he has to eat all food in that dish.
Bob's stomach has a strange feature that if there is at least kg food in it, the weight in it will reduce kg repeatedly until it is strictly lower than kg. Also, if the weight of food in his stomach is exactly kg, his stomach will be empty. Now Bob wants to eat the smallest number of dishes and remains no less than kg food in his stomach. Can you tell him how many dishes he needs to choose?
Input Format
The first line contains two integers and , indicates the number of dishes and the number of queries.
The second line contains integers , which is a permutation of , indicates that there is kg food in the -th dish, where .
The third line contains integers, the -th integer indicates a query with the lower bound of weight.
Output Format
Each line of 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