Лука имеет шифр, представляющий собой последовательность из \(n\) колёсиков, каждое с написанной на нём цифрой \(a_i\). Известно, что он прокрутил \(i\)-е колёсико \(b_i\) раз. Каждое колёсико может крутиться:
Лука знает конечные значения колёсиков и последовательность совершённых прокруток для каждого из них. Помогите ему восстановить изначальную последовательность цифр, чтобы взломать шифр!
Первая строка содержит число \(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\) разделённых пробелом цифр — изначальные значения на колёсиках шифра.
В первом наборе можно показать, что изначальным шифром являлось \([2,1,1]\). В таком случае колёсики были прокручены следующим образом:
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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач