Лука имеет шифр, представляющий собой последовательность из \(n\) колёсиков, каждое с написанной на нём цифрой \(a_i\). Известно, что он прокрутил \(i\)-е колёсико \(b_i\) раз. Каждое колёсико может крутиться:
- вверх (обозначено символом \(\texttt{U}\)): прокрутка вверх увеличивает значение на \(i\)-м колёсике на \(1\). После прокрутки \(9\) вверх, значение становится равным \(0\).
- вниз (обозначено символом \(\texttt{D}\)): прокрутка вниз уменьшает значение на \(i\)-м колёсике на \(1\). После прокрутки \(0\) вниз, значение становится равным \(9\).
Пример для \(n=4\). Текущая последовательность цифр: 0 0 0 0. Лука знает конечные значения колёсиков и последовательность совершённых прокруток для каждого из них. Помогите ему восстановить изначальную последовательность цифр, чтобы взломать шифр!
Выходные данные
Для каждого набора выведите \(n\) разделённых пробелом цифр — изначальные значения на колёсиках шифра.
Примечание
В первом наборе можно показать, что изначальным шифром являлось \([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]\) совпадает с заданной во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
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
|