Студент первого курса ИТМО Миша изучает новый примитивный язык программирования. В этом языке все операции производятся над массивами целых неотрицательных чисел длины \(n\).
Миша успел создать массив \(a\) и равный ему массив \(b\). Также он успел реализовать четыре функции:
-
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{;}\]
-
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{;}\]
-
and — присваивает в массив \(b\) его поэлементный and (побитовое <<и>>) с массивом \(a\);
-
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\) после выполнения описанной программы.