Задача №115262. Быстрый исполнитель

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

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1 11 \(n \le 1000\); \(p \le 100\) полная
2 14 \(m = 1\) первая ошибка
3 17 все \(m\) операций одинаковы 2 первая ошибка
4 15 нет операций xor первая ошибка
5 16 \(a_i \le 1\) для всех \(i\) первая ошибка
6 27 нет 1 – 5 первая ошибка

Примеры
Входные данные
5 3 2 2
1 0 1 0 1
or and or
Выходные данные
1 0 1 1 1
Входные данные
6 3 2 3
1 2 3 4 5 6
xor and or
Выходные данные
1 6 3 6 5 6
Входные данные
8 4 3 10
17 26 4 12 25 11 43 1
and or xor and
Выходные данные
0 2 0 8 17 1 9 1
Входные данные
10 4 8 10
9 4 4 5 13 2 2 11 0 12
or xor xor xor
Выходные данные
2 8 9 0 6 1 13 6 0 11
Сдать: для сдачи задач необходимо войти в систему