题目描述

小珅有一个密码锁，密码是由 $n$ 个轮子组成，每个轮子上都写着数字。在第 $i$ 个轮子上他可以拨动轮子移动。每次移动有两种类型：

1. 向上移动（用字符 U 表示）：第 $i$ 个数字向上移动 1 步，数字 9 向上移动之后回到数字 0；
2. 向下移动（用字符 D 表示）：第 $i$ 个数字向下移动 1 步，数字 0 向下移动之后回到数字 9。

原图举例：当 $n=4$ 时，密码锁显示的数字序列是 0 0 0 0。

小珅把正确密码打乱之后忘记了开锁密码，但是他记得密码锁从左到右每个轮子上显示的数字，以及打乱密码时每个轮子的移动方式。请帮助他找到正确密码。

输入格式

第一行一个整数 $t$，表示测试数据组数。每组第一行一个整数 $n$，表示密码锁有 $n$ 个轮子；第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个轮子显示的数字；接下来 $n$ 行，每行一个只包含 U 和 D 的字符串，依次表示从左到右每个轮子的移动方式。

输出格式

每组数据输出一行 $n$ 个整数，表示正确密码。

样例 1

输入

2
2
2 8
DDDDDDD
DDU
3
6 8 2
DDDU
UUD
U

输出

9 9
8 7 1

数据范围

$1\le t\le100$，$1\le n\le100$，$0\le a_i\le9$；每个移动字符串长度为 $1$ 至 $100$，只包含 U、D。本站输入不单独给出移动次数。

以上为本站练习评测范围，不作为原比赛范围。