时间限制：$1s$，空间限制：$512mb$

题目描述

小明喜欢去钓鱼。

有一天，小明发现了一个宝地：钓鱼一条街。

这条街上有编号为$1,...,n$的$n$个鱼塘。

其中，第$i$个鱼塘位于坐标$i$。小明一开始在坐标$0$，他从坐标$i$移动到坐标$i+1$需要花费$1$个小时，从坐标$i+1$移动到坐标$i$也需要$1$个小时。

通过小明的观察，小明发现，第$i$个鱼塘，第一次花费$1$小时钓鱼，可以钓到$a_i$条鱼，第二次花费$1$小时钓鱼，可以钓到$max(0,a_i-b_i)$条鱼。第$k$次花费$1$小时钓鱼，可以钓到$max(0,a_i-(k-1)\times b_i)$条鱼。

显然，小明在第$i$个鱼塘，最多会花费$\lceil \frac{a_i}{b_i}\rceil$小时来钓鱼，后续就不会钓鱼了，因为已经钓不到了。

小明一共有$T$个小时的时间，他需要在$T$小时内，从坐标$0$出发，最多走到鱼塘$k$，然后在这个过程中完成钓鱼的事情，最后带着鱼从坐标$0$回家。请帮小明算一算，对于$k=1,2,3,...,n$，小明最多可以钓到多少条鱼呢？

输入格式

第一行输入$n,T$，表示鱼塘的个数，以及小明的时间。

第二行输入$n$个正整数，表示$a_i$。

第三行输入$n$个正整数，表示$b_i$。

输出格式

输出$n$个整数表示答案。

样例输入 #1

3 10
10 10 1
5 5 1

样例输出 #1

15 30 30

样例解释 #1

如果最多只能走到鱼塘$1$再返回，小明将有$8$个小时来钓鱼，但只能在鱼塘$1$钓鱼，第一次钓到$10$条，第二次钓到$5$条，第三次以后都只能钓到$0$条，一共带着$15$条鱼回家。

如果最多只能走到鱼塘$2$再返回，小明可以先走到鱼塘$1$，花费$2$小时，钓到$15$条鱼，再走到鱼塘$2$，花费$2$小时，钓到$15$条鱼，然后再花费$2$小时回到坐标$0$，一共花费$8$个小时，带着$30$条鱼回家。

如果最多只能走到鱼塘$3$再返回，小明还是只会走到鱼塘$2$再带着$30$条鱼返回，因为鱼塘$1,2$的鱼实在是太多了，浪费时间去鱼塘$3$钓鱼是来不及的。

样例输入 #2

3 11
10 10 1
5 5 1

样例输出 #2

15 30 31

样例解释 #2

对于$11$小时来说，小明是可以去池塘$3$钓鱼的，往返加上钓完三个鱼塘的鱼，刚好花费$11$小时。

数据范围

一共$10$个测试点。

对于测试点1-2 ：$n\leq 20,a_i=b_i$。

对于测试点3-4 ：$n\leq 100,T\leq 500$。

对于测试点5-6 ：$n\leq 100,T\leq 10000$。

对于测试点7-8 ：$a_i=b_i$。

对于100%的数据：$1\leq n\leq 10^5,1\leq 2n\leq T\leq 10^6$，$1\leq a_i,b_i\leq 10^9$，保证$\sum_{i=1}^{n}\lceil \frac{a_i}{b_i}\rceil \leq 10^6$