#P17747. 贪玩蓝月

贪玩蓝月

题目描述

在贪玩蓝月这款游戏中,一共有m 个副本,其中打每一个副本需要wiw_{i}的代价。

机房一共有n 个小伙伴,每一个小伙伴颓废的时间为tit_{i}。对于每一个小伙伴,他会顺次遍历所有副本,如果颓废的时间>=打当前副本的时间,他会选择打副本并消耗相应的时间;否则他会遍历下一个副本。

现在,小伙伴们想知道自己能打多少个副本。你能帮帮他吗?

输入格式

从标准输入读入。

输入第一行包含两个数,m、n。分别表示副本数和小伙伴的数量。

接下来输入m 个数wiw_{i},每一个数表示打第i 个副本需要的时间。

接下来输入n 个数tit_{i},每一个数表示第i 个小伙伴颓废的时间。

输出格式

输出到标准输出。

输出数据共n 行,第i 行输出的数为第i 个小伙伴能够打的副本数。

输入样例

5 5
3 2 4 1 5
7 4 3 100 9

输出样例

3
2
1
5
3

样例解释

对于第一个小伙伴,他打的副本为1、2、4;

对于第二个小伙伴,他打的副本为1、4;

对于第三个小伙伴,他打的副本为1;

对于第四个小伙伴,他打的副本为1、2、3、4、5;

对于第五个小伙伴,他打的副本为1、2、3。

数据约定

对于20%的数据,有n,m≤1000。

对于40%的数据,有n,m≤5000。

另有20%的数据,wiw_{i}满足单调不降。

对于100%的数据,满足1≤n,m≤1000000,1≤wiw_{i}、tit_{i}≤1000000