T4--求求求求(1s/512M)

题目描述

给定矩阵 $C_{n\times n}$，求：

$$f_k=\sum_{i=1}^{n-k+1}\sum_{j=1}^{n-k+1}\left(\max_{i\leq x\leq i+k-1}\max_{j\leq y\leq j+k-1}C_{x,y}\right)$$

即 $f_k$ 是所有大小为 $k\times k$ 的子矩阵中元素最大值之和，但是数据忘记造 $k$ 了，所以请你对于 $1\leq k\leq n$ 求出每个整数 $k$ 的 $f_k$。而且矩阵太大了，输入在时限内完成不了，所以只给你两个正整数数列 $A_{1\cdots n},B_{1\cdots n}$，你需要自己生成矩阵 $C$，其中对于 $1\leq x,y\leq n$，$C_{x,y}=A_x\times B_y+x\times B_y+A_x\times y+x\times y$。

输入格式

第一行一个整数 $n$，第二行 $n$ 个整数 $A_{1\cdots n}$，第三行 $n$ 个整数 $B_{1\cdots n}$。

输出格式

一行 $n$ 个整数，第 $k$ 个整数表示 $f_k$ 对 $10^9+7$ 取模后的值。

样例

见 down/query 目录下的样例文件。

数据范围

对于 $30\%$ 的数据，$n\leq 50$；

对于 $50\%$ 的数据，$n\leq 3\times 10^3$；

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq A_i,B_i\leq 10^9$。