题目描述

光头强有一个由 $n$ 个轮子组成的密码，每个轮子上都写着一个数字 $a_i$。在第 $i$ 个轮子上，他做了 $b_i$ 个操作。每次操作都有两种类型：

• 向上转动（用 U 表示）：将第 $i$ 位数字增加 $1$。在 $9$ 上应用向上转动后，它变为 $0$。

• 向下转动（用 D 表示）：将第 $i$ 位数字减少 $1$。在 $0$ 上应用向下转动后，它变为 $9$。

  

  $n=4$ 的示例。当前序列为 $0\ 0\ 0\ 0$。

光头强知道轮子的最终序列和每个轮子的转动过程。帮他找到初始的密码序列。

输入格式

第一行包含单个整数 $t(1≤t≤100)$ 表示测试用例数。

每个测试用例的第一行包含单个整数 $n(1≤n≤100)$ 代表转轮数量。

第二行包含 $n$ 个整数 $a_i(0≤a_i≤9)$ 代表执行所有转动后第 $i$ 个转轮上显示的数字。

然后是 $n$ 行，其中第 $i$ 行包含整数 $b_i(1≤b_i≤10)$ 和 U 或 D 组成的字符串，表示第 $i$ 个转轮上执行的操作次数和执行的操作。U 和 D 分别表示向上转动和向下转动。

输出格式

对于每个测试用例，输出 $n$ 个空格分隔的数字，表示初始的密码序列。

测试样例

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

2 1 1 
9 0 
0 4 9 6 9 

样例说明

在第一个测试用例中，我们可以证明初始序列是 $[2,1,1]$。在这种情况下，执行了以下操作：

在第一个转轮上：$2→1→0→9$。

在第二个转轮上：$1→2→1→2→3$。

在第三个转轮上：$1→0→1$。

最终序列为 $[9,3,1]$，与输入匹配。