Быстрый исполнитель

Студент первого курса ИТМО Миша изучает новый примитивный язык программирования. В этом языке все операции производятся над массивами целых неотрицательных чисел длины $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$ после выполнения описанной программы.