UOJ Logo

NOI.AC

1S 512MB
统计

题目描述

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