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] после выполнения заданной последовательности операций.

Примеры