题目描述

在一个神秘的古老城堡中，有一扇被密码锁保护的门。这个密码锁有 $n$ 位，每位数字都是 $0$ 到 $9$ 之间的整数。城堡的主人留下了一张纸条，上面记录了密码锁的最终组合，以及对每位密码的操作过程。操作过程由一系列的 "U" 和 "D" 组成，其中 "U" 表示将该位数字加 $1$（如果该位数字为 $9$，则加 $1$ 后变为 $0$），"D" 表示将该位数字减 $1$（如果该位数字为 $0$，则减 $1$ 后变为 $9$）。

你的任务是根据最终的密码组合和操作过程，推断出最初的密码锁组合。

输入格式

第一行是一个整数 $n$ ，表示密码锁的位数。

第二行是一个长度为 $n$ 的数组，表示密码锁的最终组合，每位数字为 $0$ 到 $9$ 之间的整数。

接下来的 $n$ 行，每行包含一个整数 $x$ 和一个长度为 $x$ 的字符串，表示对第 $i$ 位密码的操作次数和操作序列（操作序列由 "U" 或 "D" 组成）。

输出格式

输出一个长度为 $n$ 的数组，表示最初的密码锁组合。

样例

3
9 3 1
3 DDD
4 UDUU
2 UD

2 1 1

提示

样例1解释

第 $1$ 位向下 $3$ 次得到 $9$，从 $9$ 逆向操作得到 $2$。

第 $2$ 位向上 $3$ 次，向下 $1$ 次得到 $3$，从 $3$ 逆向操作得到 $1$。

第 $3$ 位向上 $1$ 次，向下 $1$ 次得到 $3$，从 $1$ 逆向操作得到 $1$。

数据范围

$1≤n≤1000$

$1≤x≤100$