题目描述

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

① 向上移动（用字符U表示）：表示将第i数字向上移动1步，数字0向上移动之后会回到数字9；

② 向下移动（用字D表示）：表示将第i数字向下移动1步，数字9向下移动之后会回到数字0。

如上图所示，n=3 时，密码锁显示的数字序列是6,6,6。

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

输入格式

第一行一个整数t，表示有t组测试数据；

每组测试数据：

第一行，一个整n，表示密码锁有n个轮子；

第二行，n个整数a1, a2,...,an，表示每个轮子显示的数字；

接下n行，每行一个只包含字符U和D的字符串s，依次表示从左到右的每个轮子的移动方式。

输出格式

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

输入样例 #1

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

输出样例 #1

9 9
8 7 1

输入样例 #2

1
2
0 7
U
DDU

输出样例 #2

9 8

输入样例 #3

1
3
6 6 6
DD
DD
DD

输出样例 #3

8 8 8

数据范围

对于50% 的数据：1≤n≤100；

对于70% 的数据：1≤n≤5000；

对于100% 的数据：1≤n≤2×10^5