C. Шифр
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лука имеет шифр, представляющий собой последовательность из $$$n$$$ колёсиков, каждое с написанной на нём цифрой $$$a_i$$$. Известно, что он прокрутил $$$i$$$-е колёсико $$$b_i$$$ раз. Каждое колёсико может крутиться:

  • вверх (обозначено символом $$$\texttt{U}$$$): прокрутка вверх увеличивает значение на $$$i$$$-м колёсике на $$$1$$$. После прокрутки $$$9$$$ вверх, значение становится равным $$$0$$$.
  • вниз (обозначено символом $$$\texttt{D}$$$): прокрутка вниз уменьшает значение на $$$i$$$-м колёсике на $$$1$$$. После прокрутки $$$0$$$ вниз, значение становится равным $$$9$$$.
Пример для $$$n=4$$$. Текущая последовательность цифр: 0 0 0 0.

Лука знает конечные значения колёсиков и последовательность совершённых прокруток для каждого из них. Помогите ему восстановить изначальную последовательность цифр, чтобы взломать шифр!

Входные данные

Первая строка содержит число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

Первая строка каждого набора содержит число $$$n$$$ ($$$1 \leq n \leq 100$$$) — количество колёсиков.

Вторая строка содержит $$$n$$$ чисел $$$a_i$$$ ($$$0 \leq a_i \leq 9$$$) — значение на $$$i$$$-м колёсике после всех прокруток.

Далее следуют $$$n$$$ строк, $$$i$$$-я из которых содержит число $$$b_i$$$ ($$$1 \leq b_i \leq 10$$$) и $$$b_i$$$ символов, каждый из которых является либо $$$\texttt{U}$$$, либо $$$\texttt{D}$$$ — количество совершённых прокруток $$$i$$$-го колёсика и описание прокруток соответственно. Символы $$$\texttt{U}$$$ и $$$\texttt{D}$$$ означают прокрутку вверх и вниз соответственно.

Выходные данные

Для каждого набора выведите $$$n$$$ разделённых пробелом цифр  — изначальные значения на колёсиках шифра.

Пример
Входные данные
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
Примечание

В первом наборе можно показать, что изначальным шифром являлось $$$[2,1,1]$$$. В таком случае колёсики были прокручены следующим образом:

  • Первое колёсико: $$$2 \xrightarrow[\texttt{D}]{} 1 \xrightarrow[\texttt{D}]{} 0 \xrightarrow[\texttt{D}]{} 9$$$.
  • Второе колёсико: $$$1 \xrightarrow[\texttt{U}]{} 2 \xrightarrow[\texttt{D}]{} 1 \xrightarrow[\texttt{U}]{} 2 \xrightarrow[\texttt{U}]{} 3$$$.
  • Третье колёсико: $$$1 \xrightarrow[\texttt{D}]{} 0 \xrightarrow[\texttt{U}]{} 1$$$.
Получившаяся последовательность $$$[9,3,1]$$$ совпадает с заданной во входных данных.