Xor Машина

Розглянемо послідовність із n натуральних чисел: x[1], x[2], ..., x[n]. З цією послідовністю можна виконувати такі операції:

1. Для кожного i від 2 до n у порядку зростання встановити x[i] = x[i] xor x[i-1]. Позначимо цю операцію як "L".

2. Для кожного i від n до 2 у порядку спадання встановити x[i] = x[i] xor x[i-1]. Позначимо цю операцію як "R".

Дана початкова послідовність x[1], x[2], ..., x[n] та рядок операцій, що складається з команд "L", "R" і повторень. Команда повторення має вигляд "T(...)", де T (1 ≤ T ≤ 10^6) - ціле число, а дужки містять довільний непорожній рядок операцій. Це означає, що рядок у дужках виконується T разів.

Виконайте всі операції над заданою початковою послідовністю і виведіть результат.

Вхідні дані

Перша строка містить довжину вихідної послідовності n (1 ≤ n ≤ 30000).

Друга строка містить n цілих чисел x[i] (0 ≤ x[i] ≤ 10^9). Третя строка містить рядок операцій у форматі, описаному вище. Відомо, що рядок містить не більше 100000 символів. Також відомо, що кількість операцій після розкриття всіх повторюваних команд не перевищує 10^18.

Вихідні дані

В одному рядку виведіть отриману послідовність x[1], x[2], ..., x[n] після виконання заданої послідовності операцій.

Приклади