题目描述

有一个「数码折叠」游戏，规则如下：

给定一个正整数 $x$，把它的各位数字相加，得到一个新数。这样的一次变换称为一次「折叠」操作。

例如，对 $375$：

• 折叠一次：$3 + 7 + 5 = 15$；
• 折叠两次：$1 + 5 = 6$；
• 折叠三次：$6 = 6$。

现在给定 $n$ 个数（第 $i$ 个数就是 $i$），以及每个数要执行的折叠次数 $a_i$。请输出每个数折叠 $a_i$ 次后的结果。

输入格式

输入共两行。

第一行一个整数 $n$，表示要处理 $1 \sim n$ 这 $n$ 个数；
第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$，第 $i$ 个表示数字 $i$ 要做多少次折叠操作。

输出格式

输出一行 $n$ 个整数，第 $i$ 个表示数字 $i$ 做 $a_i$ 次折叠后得到的结果。

样例

11
1 3 2 1 99 100 93 57 18 2 1

1 2 3 4 5 6 7 8 9 1 2

20
3 10 4 1 6 7 2 6 3 9 3 4 4 1 3 6 7 7 2 7

1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2

提示

样例 1 解释

• 对于 $1 \sim 9$，无论折叠多少次，结果始终是自身；
• 对于 $10$，第一次折叠得 $1 + 0 = 1$，第二次折叠得 $1 = 1$；
• 对于 $11$，第一次折叠得 $1 + 1 = 2$。

数据规模与约定

本题共 $10$ 个测试点。对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$；