题目描述
大师级模数变换（Master Modular Transform）是小Z近期想出的一个难题，它基于两个数组$a_i$和$b_i$，并生成一个新的数组$c_i$。
具体地说，MMT给出了如下的变换公式：
$$c_i=\sum_{j=1}^i a_{\lfloor \frac{i}{j} \rfloor} b_{i \text{ mod } j}$$
其中$\lfloor \frac{i}{j} \rfloor$表示$i$除以$j$下取整后的结果，$i \text{ mod } j$表示$i$除以$j$的余数。为了方便，每个$c_i$最后都对$123456789$取模。
在欣喜之余，小Z开始思考如何高效地求解MMT，你一定能帮他解决这个问题的。
格式
输入格式
第一行为一个正整数$n$。
第二行为$n$个非负整数，第$i$个数为$a_i$。
第三行为$n$个非负整数，第$i$个数为$b_{i-1}$。
输出格式
你需要输出$n$行，每行一个非负整数，第$i$行的数表示$c_i$对$123456789$取模的值。
样例
输入1
10
8 3 6 5 6 7 0 2 0 10
3 6 7 6 8 8 7 3 1 10输出1
24
33
90
96
164
176
230
227
306
354输入2
见附件。
输出2
见附件。
数据规模与约定
对于$30\%$的数据，$n\le 3000$；
另存在$20\%$的数据，$a_i=1\ (1\le i\le n),\ b_i=i\ (0\le i \lt n)$；
另存在$20\%$的数据，$a_i=i\ (1\le i\le n),\ b_i=i\ (0\le i \lt n)$；
对于所有的数据，$n\le 10^5,\ a_i, b_i \le 10^9$。
