暗号（cypher）

题目描述

$\text{Luca}$ 有一个密码锁，这个密码锁由 $n$ 个数字轮组成。每个数字轮上都有一个数字 $a_i$，数字范围是 $0$ 到 $9$。

$\text{Luca}$ 曾经对每个数字轮进行了一些操作。每次操作有两种类型：

• $\texttt{U}$：将当前数字增加 $1$。如果当前数字是 $9$，执行 $\texttt{U}$ 后会变成 $0$；
• $\texttt{D}$：将当前数字减少 $1$。如果当前数字是 $0$，执行 $\texttt{D}$ 后会变成 $9$。

现在 $\text{Luca}$ 只知道每个数字轮经过所有操作后的 最终数字 ，以及每个数字轮执行过的操作序列。

请你帮助 $\text{Luca}$ 推出每个数字轮 最开始的数字 。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

对于每个测试用例：

第一行包含一个整数 $n$，表示数字轮的数量。

第二行包含 $n$ 个整数 $a_i$，表示每个数字轮经过所有操作后的最终数字。

接下来有 $n$ 行，第 $i$ 行包含一个整数 $b_i$ 和一个长度为 $b_i$ 的字符串，表示第 $i$ 个数字轮执行了 $b_i$ 次操作。

字符串只包含字符 $\texttt{U}$ 和 $\texttt{D}$。

输出格式

对于每个测试用例，输出一行，包含 $n$ 个整数，表示每个数字轮最开始的数字。

相邻两个整数之间用一个空格隔开。

输入输出样例 #1

输入 #1

3
3
9 3 1
3 DDD
4 UDUU
2 DU
2
0 9
9 DDDDDDDDD
9 UUUUUUUUU
5
0 5 9 8 3
10 UUUUUUUUUU
3 UUD
8 UUDUUDDD
10 UUDUUDUDDU
4 UUUU

输出 #1

2 1 1
9 0
0 4 9 6 9

样例解释 #1

对于第 $1$ 组测试数据：

第 $1$ 个数字轮最终为 $9$，操作序列为 $\texttt{DDD}$。 因为 $\texttt{D}$ 表示原操作中数字减少 $1$，所以反推时要将数字增加 $1$。

$$9 \to 0 \to 1 \to 2$$

因此它最开始的数字是 $2$。

第 $2$ 个数字轮最终为 $3$，操作序列为 $\texttt{UDUU}$。 操作中一共有 $3$ 次 $\texttt{U}$ 和 $1$ 次 $\texttt{D}$，所以原来的数字经过操作后整体相当于增加了 $2$。反推时需要减少 $2$：

$$3 \to 1$$

因此它最开始的数字是 $1$。

第 $3$ 个数字轮最终为 $1$，操作序列为 $\texttt{DU}$。 一次 $\texttt{D}$ 和一次 $\texttt{U}$ 相互抵消，所以最开始的数字仍然是 $1$。

输入输出样例 #2

输入 #2

2
1
0
1 U
4
0 9 5 6
10 UUUUUUUUUU
10 DDDDDDDDDD
5 UUUUU
5 DDDDD

输出 #2

9
0 9 0 1

样例解释 #2

对于第 $1$ 组测试数据：

最终数字为 $0$，操作为 $\texttt{U}$。说明最开始的数字是 $9$，因为：

$$9 \xrightarrow{U} 0$$

对于第 $2$ 组测试数据：

• 第 $1$ 个数字轮执行了 $10$ 次 $\texttt{U}$，数字绕了一整圈，所以初始数字仍为 $0$；
• 第 $2$ 个数字轮执行了 $10$ 次 $\texttt{D}$，数字绕了一整圈，所以初始数字仍为 $9$；
• 第 $3$ 个数字轮最终为 $5$，执行了 $5$ 次 $\texttt{U}$，所以初始数字为 $0$；
• 第 $4$ 个数字轮最终为 $6$，执行了 $5$ 次 $\texttt{D}$，所以初始数字为 $1$。

数据范围与约定

对于所有测试数据，保证：

$$1 \le t \le 100,\quad 1 \le n \le 100,\quad 0 \le a_i \le 9,\quad 1 \le b_i \le 10 $$

测试点	分值	$t$	$n$	$b_i$	特殊性质
$1\sim 2$	$10$	$\le 5$		$\le 3$	无
$3\sim 5$	$15$	$\le 20$		$\le 10$	$\text{A}$
$6\sim 8$					$\text{B}$
$9\sim 12$	$20$	$\le 50$			无
$13\sim 16$		$\le 100$
$17\sim 20$

特殊性质 $\text{A}$：保证所有操作字符均为 $\texttt{U}$。

特殊性质 $\text{B}$：保证所有操作字符均为 $\texttt{D}$。