题目描述

大师级模数变换（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$。