卢卡有一个由 $$$n$$$ 轮子序列组成的密码,每个轮子上写有一个数字 $$$a_i$$$。在第 $$$i$$$ 轮上,他进行了 $$$b_i$$$ 动作。每个动作都是以下两种类型之一:
- 向上移动(用 $$$\texttt{U}$$$ 表示):它将 $$$i$$$ 位增加 $$$1$$$。在 $$$9$$$ 上应用上涨后,它变为 $$$0$$$。
- 向下移动(用 $$$\texttt{D}$$$ 表示):将 $$$i$$$ 位数字减少 $$$1$$$。在 $$$0$$$ 上应用向下移动后,它变为 $$$9$$$。
$$$n=4$$$ 的示例。当前序列是 0 0 0 0。
卢卡知道轮子的最终顺序以及每个轮子的动作。帮助他找到原始序列并破解密码。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 轮子的数量。
第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$0 \leq a_i \leq 9$$$) — 执行所有移动后第 $$$i$$$ 轮上显示的数字。
接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含整数 $$$b_i$$$ ($$$1 \leq b_i \leq 10$$$) 和 $$$b_i$$$ 字符,这些字符可以是 $$$\texttt{U}$$$ 或 $$$\texttt{D}$$$ — 在$$$i$$$ 个轮子,以及执行的移动。 $$$\texttt{U}$$$ 和 $$$\texttt{D}$$$ 分别表示向上移动和向下移动。
输出
对于每个测试用例,输出 $$$n$$$ 空格分隔的数字 - 密码的初始序列。
示例
输入 #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
注意
在第一个测试用例中,我们可以证明初始序列是$$$[2,1,1]$$$。在这种情况下,执行了以下操作:
- 在第一个轮子上:$$$2 \xrightarrow[\texttt{D}]{} 1 \xrightarrow[\texttt{D}]{} 0 \xrightarrow[\texttt{D}]{} 9$$$。
- 在第二个轮子上:$$$1 \xrightarrow[\texttt{U}]{} 2 \xrightarrow[\texttt{D}]{} 1 \xrightarrow[\texttt{U}]{} 2 \xrightarrow[\texttt{U}]{} 3$$$。
- 在第三个轮子上:$$$1 \xrightarrow[\texttt{D}]{} 0 \xrightarrow[\texttt{U}]{} 1$$$。