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.
Input Format:
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 Format:
For each test case, output $$$n$$$ space-separated digits — the initial sequence of the cypher.
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$$$.