28561번 - Быстрый исполнитель 다국어

Студент первого курса ИТМО Миша изучает новый примитивный язык программирования. В этом языке все операции производятся над массивами целых неотрицательных чисел длины $n$.

Миша успел создать массив $a$ и равный ему массив $b$. Также он успел реализовать четыре функции:

1. shift --- делает циклический сдвиг массива $a$ влево на $d$, то есть при $a = [a_0, a_1, \ldots, a_{n-1}]$ выполняет присваивание $$a \gets [a_d, \ldots, a_{n-1}, a_0, \ldots, a_{d-1}] \text{;}$$
2. xor --- присваивает в массив $b$ его поэлементный xor (побитовое исключающее <<или>>) с массивом $a$, то есть $$b \gets [a_0 \oplus b_0, a_1 \oplus b_1, \ldots, a_{n-1} \oplus b_{n-1}] \text{;}$$
3. and --- присваивает в массив $b$ его поэлементный and (побитовое <<и>>) с массивом $a$;
4. or --- присваивает в массив $b$ его поэлементный or (побитовое <<или>>) с массивом $a$.

Используя эти функции, Миша написал программу, задаваемую последовательностью операций xor, and и or длины $m$. Программа в цикле $p$ раз выполняет следующие действия: для каждой операции из последовательности сначала вызывается shift, а затем соответствующая этой операции функция. Так, для последовательности операций $[\mathtt{or}, \mathtt{xor}, \mathtt{and}]$ и $p = 5$ программа будет выглядеть как

b = a = [...]
repeat 5 times {
    shift
    or
    shift
    xor
    shift
    and
}

К сожалению, язык еще новый, и его интерпретатор не справляется с выполнением такой программы. Помогите Мише определить, чему будет равно конечное состояние массива $b$ после выполнения заданной программы.

В первой строке ввода перечислены четыре целых числа $n$, $m$, $d$ и $p$ --- длина массива, количество операций в последовательности, величина сдвига и количество повторений ($0 \le d < n \le 2 \cdot 10^5$; $1 \le m \le 10$; $1 \le p \le 10^9$).

Во второй строке перечислены $n$ целых чисел $a_i$ --- элементы массива $a$, они же --- изначальные значения элементов массива $b$ ($0 \le a_i \le 10^9$).

В третьей строке через пробел перечисены $m$ слов, каждое из которых равно <<xor>>, <<and>> или <<or>> --- последовательность применяемых на каждой итерации цикла операций.

Выведите $n$ целых чисел --- элементы массива $b$ после выполнения описанной программы.