Cypher
Description
Luca has a cypher made up of a sequence of $n$ wheels, each with a digit $a_i$ written on it. On the $i$-th wheel, he made $b_i$ moves. Each move is one of two types:
- up move (denoted by $\texttt{U}$): it increases the $i$-th digit by $1$. After applying the up move on $9$, it becomes $0$.
- down move (denoted by $\texttt{D}$): it decreases the $i$-th digit by $1$. After applying the down move on $0$, it becomes $9$.
Example for $n=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.
The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($1 \leq n \leq 100$) — the number of wheels.
The second line contains $n$ integers $a_i$ ($0 \leq a_i \leq 9$) — the digit shown on the $i$-th wheel after all moves have been performed.
Then $n$ lines follow, the $i$-th of which contains the integer $b_i$ ($1 \leq b_i \leq 10$) and $b_i$ characters that are either $\texttt{U}$ or $\texttt{D}$ — the number of moves performed on the $i$-th wheel, and the moves performed. $\texttt{U}$ and $\texttt{D}$ represent an up move and a down move respectively.
For each test case, output $n$ space-separated digits — the initial sequence of the cypher.
Input
The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($1 \leq n \leq 100$) — the number of wheels.
The second line contains $n$ integers $a_i$ ($0 \leq a_i \leq 9$) — the digit shown on the $i$-th wheel after all moves have been performed.
Then $n$ lines follow, the $i$-th of which contains the integer $b_i$ ($1 \leq b_i \leq 10$) and $b_i$ characters that are either $\texttt{U}$ or $\texttt{D}$ — the number of moves performed on the $i$-th wheel, and the moves performed. $\texttt{U}$ and $\texttt{D}$ represent an up move and a down move respectively.
Output
For each test case, output $n$ space-separated digits — the initial sequence of the cypher.
Samples
<div class="test-example-line test-example-line-even test-example-line-0">3</div><div class="test-example-line test-example-line-odd test-example-line-1">3</div><div class="test-example-line test-example-line-odd test-example-line-1">9 3 1</div><div class="test-example-line test-example-line-odd test-example-line-1">3 DDD</div><div class="test-example-line test-example-line-odd test-example-line-1">4 UDUU</div><div class="test-example-line test-example-line-odd test-example-line-1">2 DU</div><div class="test-example-line test-example-line-even test-example-line-2">2</div><div class="test-example-line test-example-line-even test-example-line-2">0 9</div><div class="test-example-line test-example-line-even test-example-line-2">9 DDDDDDDDD</div><div class="test-example-line test-example-line-even test-example-line-2">9 UUUUUUUUU</div><div class="test-example-line test-example-line-odd test-example-line-3">5</div><div class="test-example-line test-example-line-odd test-example-line-3">0 5 9 8 3</div><div class="test-example-line test-example-line-odd test-example-line-3">10 UUUUUUUUUU</div><div class="test-example-line test-example-line-odd test-example-line-3">3 UUD</div><div class="test-example-line test-example-line-odd test-example-line-3">8 UUDUUDDD</div><div class="test-example-line test-example-line-odd test-example-line-3">10 UUDUUDUDDU</div><div class="test-example-line test-example-line-odd test-example-line-3">4 UUUU</div><div class="test-example-line test-example-line-odd test-example-line-3"></div>
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]$. In that case, the following moves were performed:
- On the first wheel: $2 \xrightarrow[\texttt{D}]{} 1 \xrightarrow[\texttt{D}]{} 0 \xrightarrow[\texttt{D}]{} 9$.
- On the second wheel: $1 \xrightarrow[\texttt{U}]{} 2 \xrightarrow[\texttt{D}]{} 1 \xrightarrow[\texttt{U}]{} 2 \xrightarrow[\texttt{U}]{} 3$.
- On the third wheel: $1 \xrightarrow[\texttt{D}]{} 0 \xrightarrow[\texttt{U}]{} 1$.