eolymp
bolt
Try our new interface for solving problems
Problems

Xoring Machine

Xoring Machine

Time limit 1 second
Memory limit 128 MiB

Consider a sequence consisting of n positive integers: x[1], x[2], ..., x[n]. You can perform the following operations with this sequence:

  1. For each i from 2 to n in increasing order, set x[i] = x[i]xorx[i-1]. Denote this operation as "L".

  2. For each i from n to 2 in decreasing order, set x[i] = x[i]xorx[i-1]. Denote this operation as "R".

You are given an initial sequence x[1], x[2], ..., x[n] and a string of operations which consists of "L", "R" and repeat commands. A repeat command looks like "T(...)", where T (1T10^6) is an integer and the brackets contain an arbitrary non-empty string of operations. It means that you must apply the string in brackets T times.

Apply all the operations to the initial sequence and print the result.

Input data

The first line contains the length n (1n30000) of the initial sequence.

The second line contains n integers x[i] (0x[i]10^9). The third line contains a string of operations formatted as described above. It is guaranteed that this string contains no more than 100000 characters. Also it is guaranteed that the number of operations after expanding all repeat commands will be no more than 10^18.

Output data

Print in one line the resulting sequence x[1], x[2], ..., x[n] after performing the given sequence of operations.

Examples

Input example #1
4
1 2 3 4
LLRL
Output example #1
1 2 2 6
Input example #2
5
8 2 1 4 16
3(L)2(R)LR4(L2(R))
Output example #2
8 10 11 15 23
Source 2013 Petrozavodsk, Moscow SU ST + NNSU Contest, Day 2, August 24, Problem B