eolymp
bolt
Try our new interface for solving problems
Məsələlər

Xor Машина

Xor Машина

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Рассмотрим последовательность из n натуральных чисел: x[1], x[2], ..., x[n]. С ней разрешено проводить следующие операции:

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

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

Задана начальная последовательность x[1], x[2], ..., x[n], строка операций, состоящая из "L", "R" команд повторений. Команда повторения имеет вид "T(...)", где T (1T10^6) - целое число, а скобки содержат произвольную непустую строку операций. Она означает, что строка в скобках должна быть выполнена T раз.

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

Giriş verilənləri

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

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
4
1 2 3 4
LLRL
Çıxış verilənləri #1
1 2 2 6
Giriş verilənləri #2
5
8 2 1 4 16
3(L)2(R)LR4(L2(R))
Çıxış verilənləri #2
8 10 11 15 23
Mənbə 2013 Петрозаводск, Moscow SU ST + NNSU Contest, День 2, Август 24, Задача B