该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你面对一个 n 位的环形密码锁，每位数字在 0 到 9 之间（加 1 超过 9 变成 0，减 1 低于 0 变成 9）。

已知：

• 每一位经过若干次 "U"（+1）或 "D"（-1）操作后，最终变成了给定的数字；
• 现在给你最终状态和每一位的操作序列，请你反推初始密码。

输入格式

第一行是一个整数 $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$