Migrated from Lutece 2662 奥日与风袭废墟

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

注：本题不计一血。

---

『光芒破碎，我们只剩下零星萤火』

『精灵不复存在，似乎一切皆已失落』

『预言说，希望会降临』

『希望会让我们睁开双眼，看清黑暗……』

---

---

随着精灵一族的消亡，黑暗在尼文的大地上蔓延。

在风袭废墟的深处，有一处铭刻着古老符号的岩壁，记录着精灵一族过去的辉煌。

一番探索后，奥日发现岩壁分为五层，每层由 $n$ 个整数构成。但是，在黑暗的侵蚀下，原本的字迹早已经变得难以辨析。只有每一层开头的神秘符号还清晰可见，奥日将这些符号记录了下来：

---

$\varphi\\\mu\\\sigma_0\\\sigma_1\\(\mu\cdot\varphi)*\sigma_1$

---

你能根据它们帮助奥日还原出岩壁的原貌吗？

Input

输入一行一个正整数 $n$.

Output

输出五行，分别为：

$\varphi(1),\varphi(2),\ldots ,\varphi(n)$ $\mu(1),\mu(2),\ldots ,\mu(n)$ $\sigma_0(1),\sigma_0(2),\ldots ,\sigma_0(n)$ $\sigma_1(1),\sigma_1(2),\ldots ,\sigma_1(n)$ $f(1),f(2),\ldots ,f(n)$

其中 $f=\sum_{i|n}\mu(i)\varphi(i)\sigma_1(\frac{n}{i})$。

每个数之间用空格隔开。

Samples

10

1 1 2 2 4 2 6 4 6 4
1 -1 -1 0 -1 1 -1 0 0 1
1 2 2 3 2 4 2 4 3 4
1 3 4 7 6 12 8 15 13 18
1 2 2 4 2 4 2 8 5 4

Constraints

$n=500000$

Note

$\varphi,\mu,\sigma_0,\sigma_1$ 分别为欧拉函数、莫比乌斯函数、因数个数函数、因数和函数。

Resources

2021, 2022 UESTC ICPC Training for Math and Geometry & 2023, 2024 UESTC ICPC Training for Math