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:
Luca knows the final sequence of wheels and the moves for each wheel. Help him find the original sequence and crack the cypher.
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.
For each test case, output nn space-separated digits — the initial sequence of the cypher.
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
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: