题目描述

有一把 $n$ 个锁轮的锁，每个锁轮上写有数字 $a_i$ ，对于第 $i$ 个锁轮，做了 $b_i$ 次操作。这些操作有两种类型：

• U：锁轮上的数字 $+1$ ，超过 $9$ 则变为 $0$ 。
• D：锁轮上的数字 $-1$ ，小于 $0$ 则变为 $9$ 。

现在给定操作后的锁轮和操作，请你还原操作前的锁轮。

输入格式

第一行一个整数 $t$ ，表示测试点内数据组数。

每组数据中第一行是一个正整数 $n$ ，表示锁轮数。

下一行有 $n$ 个整数 $a_i$ ，表示每个锁轮操作后的数字。

输出格式

一行 $n$ 个用空格隔开的整数，表示操作前锁轮上的数字。

说明/提示

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

样例

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