Xoring Machine

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] xor x[i-1]. Denote this operation as "L".

2. For each i from n to 2 in decreasing order, set x[i] = x[i] xor x[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 (1 ≤ T ≤ 10^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

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

The second line contains n integers x[i] (0 ≤ x[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

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

Examples