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

시간 제한3초메모리 제한1024 MB

요약

배열 a와 시프트 및 비트 연산의 반복 순서가 주어질 때, p번 반복한 뒤 배열 b의 최종 상태를 구한다.

난이도: 보통10점 중 6점
유형: 비트 연산, 시뮬레이션, 배열
정답자: 아직 제출이 없습니다

문제

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

예제4

예제 1
입력
```
5 3 2 2
1 0 1 0 1
or and or
```
예상 출력
```
1 0 1 1 1
```

예제 2

입력

6 3 2 3
1 2 3 4 5 6
xor and or

예상 출력

1 6 3 6 5 6

예제 3

입력

8 4 3 10
17 26 4 12 25 11 43 1
and or xor and

예상 출력

0 2 0 8 17 1 9 1

예제 4

입력

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