Рассмотрим последовательность из n натуральных чисел: x1, x2, ..., xn. С ней разрешено проводить следующие операции:

1. Для каждого i от 2 до n по возрастанию установить xi = xixorxi-1. Определим эту операцию как "L".
2. Для каждого i от n до 2 по убыванию установить xi = xixorxi-1. Определим эту операцию как "R".

Задана начальная последовательность x1, x2, ..., xn, строка операций, состоящая из "L", "R" команд повторений. Команда повторения имеет вид "T(...)", где T (1 ≤ T ≤ 106) - целое число, а скобки содержат произвольную непустую строку операций. Она означает, что строка в скобках должна быть выполнена T раз.

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

Входные данные

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

Вторая строка содержит n целых чисел xi (0 ≤ xi ≤ 109). Третья строка содержит строку операций в формате, описанном выше. Известно, что строка содержит не более 100000 символов. Также известно, что количество операций после раскрытия всех повторяющихся команд не более 1018.

Выходные данные

В одной строке выведите полученную последовательность x1, x2, ..., xn после выполнения заданной последовательности операций.