在通过以 $O(n^{1.999})$ 的时间复杂度解决 $(\min, +)$-卷积问题，从而在第 5202 届 IEEE 计算机科学基础年会 (FOCS) 上获得最佳论文奖后，小蓝鱼（Little Cyan Fish）想让你解决以下问题。

小蓝鱼将两个长度为 $n$ 的序列 $a_0, a_1, \cdots, a_{n-1}$ 和 $b_0, b_1, \cdots, b_{n-1}$ 的 $(\min, +)$ 循环卷积定义为另一个序列 $a \times b$，满足：

$$(a \times b)_k = \min_{(i+j) \equiv k \pmod n} (a_i + b_j)$$

对于正整数 $t$，小蓝鱼将序列 $a_0, a_1, \cdots, a_{n-1}$ 的 $t$ 次幂定义如下：

$$a^t = \begin{cases} a & t = 1 \\ a^{t-1} \times a & t > 1 \end{cases}$$

现在，小蓝鱼给你一个随机生成的长度为 $n$ 的序列 $a_0, a_1, \cdots, a_{n-1}$。他想让你计算序列 $a^n$，即 $\underbrace{a \times a \times \cdots \times a}_{n \text{ times}}$。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)。

第二行包含 $n$ 个整数 $a_0, a_1, \cdots, a_{n-1}$ ($1 \le a_i \le 10^9$)，表示该序列。

保证 $\{a_n\}$ 的每个元素都是独立且均匀随机地从 $1$ 到 $10^9$ 中选择一个整数生成的。本题中测试用例（包括样例）的数量不超过 100 个。

输出格式

输出单行，包含 $n$ 个整数 $c_0, c_1, \cdots, c_{n-1}$，表示答案。

样例

输入样例 1

2
82688973 409689707

输出样例 1

165377946 492378680

输入样例 2

3
965805101 983238551 643391778

输出样例 2

1930175334 2252588657 2270022107