C. Cypher

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Luca has a cypher made up of a sequence of nn wheels, each with a digit aiai written on it. On the ii-th wheel, he made bibi moves. Each move is one of two types:

• up move (denoted by UU): it increases the ii-th digit by 11. After applying the up move on 99, it becomes 00.
• down move (denoted by DD): it decreases the ii-th digit by 11. After applying the down move on 00, it becomes 99.

Example for n=4n=4. The current sequence is 0 0 0 0.

Luca knows the final sequence of wheels and the moves for each wheel. Help him find the original sequence and crack the cypher.

Input

The first line contains a single integer tt (1≤t≤1001≤t≤100) — the number of test cases.

The first line of each test case contains a single integer nn (1≤n≤1001≤n≤100) — the number of wheels.

The second line contains nn integers aiai (0≤ai≤90≤ai≤9) — the digit shown on the ii-th wheel after all moves have been performed.

Then nn lines follow, the ii-th of which contains the integer bibi (1≤bi≤101≤bi≤10) and bibi characters that are either UU or DD — the number of moves performed on the ii-th wheel, and the moves performed. UU and DD represent an up move and a down move respectively.

Output

For each test case, output nn space-separated digits  — the initial sequence of the cypher.

Example

input

Copy

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

output

Copy

2 1 1 
9 0 
0 4 9 6 9 

Note

In the first test case, we can prove that initial sequence was [2,1,1][2,1,1]. In that case, the following moves were performed:

• On the first wheel: 2→D1→D0→D92→D1→D0→D9.
• On the second wheel: 1→U2→D1→U2→U31→U2→D1→U2→U3.
• On the third wheel: 1→D0→U11→D0→U1.

The final sequence was [9,3,1][9,3,1], which matches the input.

Problem solving instructions ： This problem is a simulation problem , Reverse the number according to the input direction , Judge more than 10 Return to 0, by -1 Return to 9 that will do .

#include<stdio.h>
int main()
{
	int t, n, i, j, n2;
	int a[102];
	char b[12];
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		for (i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
		}
		for (i = 0; i<n; i++)
		{
			scanf("%d", &n2);
			
			scanf("%s", &b);
			for (j = 0; j<n2; j++)
			{
				if (b[j] == 'U')
				{
					a[i]--;
				}
				else
				{
					a[i]++;
				}
				if (a[i] == 10)
				{
					a[i] = 0;
				}
				else if (a[i] == -1)
				{
					a[i] = 9;
				}
			}
			printf("%d ", a[i]);
		}
		printf("\n");
	}
	return 0;
}