A71105.Zombie

题目背景

$\color{red}{\mathtt{FM}}$：“折磨人的有趣的比赛终于怎么就结束了啊。”

$\color{grey}{\mathtt{ST}}$：“是啊，我要回家睡觉，以回复我的脑力。”

$\color{red}{\mathtt{FM}}$：“我要告诉你一个坏消息：我们被僵尸困住了。”

$\color{grey}{\mathtt{ST}}$：“那很坏了。但是，谁都不能影响我睡觉！”

$\color{red}{\mathtt{FM}}$：“哔，周围有僵尸在游荡，你现在还不能睡觉。”

快来帮帮 ST，让他好好睡觉吧！

---

题目描述

现在有 $N$ 只僵尸围绕着 FM 和 ST，并且它们都在正整数位置游荡。

围绕着的僵尸会瞬移！第 $i$ 只僵尸从点 $a_i$ 出发，每秒都会从位置 $pos$ 瞬移到位置 $pos_{new}$，瞬移公式为：

$$pos_{new}=((pos+f(pos)) \bmod p)+1$$

其中，$f(pos)$ 表示数字 $pos$ 的最大数位。

僵尸并不是能无限瞬移的，第 $i$ 只僵尸瞬移 $n_i$ 次后就会停止。

容易发现，僵尸永远不可能到达原点，因此原点是绝对安全的。现在你的任务是计算出每只僵尸最终瞬移到的位置。

输入共 $N+1$ 行：

第一行 $1$ 个正整数 $N$，表示僵尸数量；

接下来 $N$ 行，每行 $3$ 个正整数 $a_i,p_i,n_i$，分别表示第 $i$ 只僵尸的起点、代入公式 $pos_{new}$ 计算的 $p$ 值和瞬移次数。

输出共 $N$ 行：

每行 $1$ 个正整数，表示第 $i$ 只僵尸最终瞬移到的位置。

【数据范围】

对于 $100\%$ 的数据，保证：

• $1 \le N \le 20$
• $1 \le a_i,p_i,n_i \le 10^{18}$

测试点编号	$a_i,p_i,n_i \le$
1~3	$10^6$
11~50	$10^{18}$