考虑一个由 $N$ 个正整数组成的序列：$x_1, x_2, \dots, x_N$。你可以对该序列进行以下操作：

1. 对于每个 $i$ 从 $2$ 到 $N$ 按递增顺序，令 $x_i = x_i \text{ xor } x_{i-1}$。将此操作记为 "L"。
2. 对于每个 $i$ 从 $N$ 到 $2$ 按递减顺序，令 $x_i = x_i \text{ xor } x_{i-1}$。将此操作记为 "R"。

给你一个初始序列 $x_1, x_2, \dots, x_N$ 以及一个由 "L"、"R" 和循环命令组成的字符串。一个循环命令的形式为 "$T(\dots)$"，其中 $T$ 是一个整数（$1 \le T \le 1\,000\,000$），括号内包含一个任意的非空操作字符串。它表示你必须将括号内的操作字符串重复执行 $T$ 次。

对初始序列应用所有操作并输出结果。

输入格式

输入的第一行包含一个整数 $N$（$1 \le N \le 30\,000$），表示初始序列的长度。

第二行包含 $N$ 个整数 $x_i$（$0 \le x_i \le 10^9$）。

第三行包含一个按上述格式给出的操作字符串。保证该字符串包含不超过 $100\,000$ 个字符。同时保证展开所有“循环”命令后的操作总数不超过 $10^{18}$。

输出格式

在第一行输出执行完给定的操作序列后得到的序列 $x_1, x_2, \dots, x_N$。

样例

输入样例 1

4
1 2 3 4
LLRL

输出样例 1

1 2 2 6

输入样例 2

5
8 2 1 4 16
3(L)2(R)LR4(L2(R))

输出样例 2

8 10 11 15 23