Xor Машина
Xor Машина
Рассмотрим последовательность из n натуральных чисел: x[1]
, x[2]
, ..., x[n]
. С ней разрешено проводить следующие операции:
Для каждого i от 2 до n по возрастанию установить
x[i]
=x[i]
xorx[i-1]
. Определим эту операцию как "L".Для каждого i от n до 2 по убыванию установить
x[i]
=x[i]
xorx[i-1]
. Определим эту операцию как "R".
Задана начальная последовательность x[1]
, x[2]
, ..., x[n]
, строка операций, состоящая из "L", "R" команд повторений. Команда повторения имеет вид "T(...)", где T (1 ≤ T ≤ 10^6
) - целое число, а скобки содержат произвольную непустую строку операций. Она означает, что строка в скобках должна быть выполнена T раз.
Выполните все операции над заданной начальной последовательностью и выведите результат.
Giriş verilənləri
Первая строка содержит длину исходной последовательности n (1 ≤ n ≤ 30000).
Вторая строка содержит n целых чисел x[i]
(0 ≤ x[i]
≤ 10^9
). Третья строка содержит строку операций в формате, описанном выше. Известно, что строка содержит не более 100000 символов. Также известно, что количество операций после раскрытия всех повторяющихся команд не более 10^18
.
Çıxış verilənləri
В одной строке выведите полученную последовательность x[1]
, x[2]
, ..., x[n]
после выполнения заданной последовательности операций.
Nümunə
4 1 2 3 4 LLRL
1 2 2 6
5 8 2 1 4 16 3(L)2(R)LR4(L2(R))
8 10 11 15 23