avatarГость
← К соревнованиям

Sort Me Round

Дек с подвохом

Сложность: 89%

Задан изначально пустой массив vv. Структура данных "Дек с подвохом" умеет обрабатывать запросы шести типов:

  1. Вставить число xx в конец массива vv;
  2. Вставить число xx в начало массива vv;
  3. Удалить последний элемент из массива vv;
  4. Удалить первый элемент из массива vv;
  5. Применить XOR-перестановку с параметром xx к массиву vv;
  6. Вывести максимальный элемент, содержащийся в vv.

Пусть kk – текущая длина массива vv, тогда XOR-перестановка определяется, как массив pp длиной kk, у которого pi=i⊕xp_i = i \oplus x, где ⊕\oplus – операция побитового исключающего или. Гарантируется, что в pp каждое из чисел 0,1,…,k−10,1, \ldots , k-1 встречается ровно один раз. После применения перестановки pp к массиву vv получается новый массив v′v', такой что vi′=vpiv'_i = v_{p_i}. Элементы массивов pp и vv нумеруются с 00.

Реализуйте Дек с подвохом.

Входные данные

Первая строка входных данных содержит единственное число nn – количество запросов (1≤n≤5⋅1051 \leq n \leq 5 \cdot 10^5). Затем следует описание запросов. Описание каждого запроса начинается с числа от 11 до 66 – типа запроса. После запросов типа 11, 22 и 55 следует число xx (1≤x≤5⋅1051 \leq x \leq 5 \cdot 10^5).

Выходные данные

Для каждого запроса типа 33, 44 и 66 в отдельной строке выведите результат обработки запроса: значение удаленного элемента для запросов типа 33 и 44 или значение максимального элемента для запросов типа 66.

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

Если ваше решение пройдёт все три подзадачи, то будет оценено по количеству используемой памяти в худшем случае.

  • Решения, расходующие не более 256 Мб памяти, оцениваются в 60 баллов.
  • Решения, расходующие не более 80 Мб памяти, оцениваются в 80 баллов.
  • Решения, расходующие не более 40 Мб памяти, оцениваются в 100 баллов.

Подзадачи

№баллынеобх. подзадачиограничения
1

10

-

Размер массива vv никогда не превышает 50

2

10

-

Не более 10 запросов 5-го типа

3

80

1, 2

Нет дополнительных ограничений

STDINSTDOUT
12
1 3
2 3
6
1 7
2 1
6
5 1
3
4
6
3
6
3
7
3
3
7
7
1

Примечание

Рассмотрим, что происходит в примере:

  1. v=[3]v = [3];
  2. v=[3,3]v = [3, 3];
  3. v=[3,3]v = [3, 3], максимум - 33;
  4. v=[3,3,7]v = [3, 3, 7];
  5. v=[1,3,3,7]v = [1, 3, 3, 7];
  6. v=[1,3,3,7]v = [1, 3, 3, 7], максимум - 77;
  7. v=[3,1,7,3]v = [3, 1, 7, 3], XOR-перестановка имеет вид p=[1,0,3,2]p = [1, 0, 3, 2];
  8. v=[3,1,7]v = [3, 1, 7], удаленный элемент - 33;
  9. v=[1,7]v = [1, 7], удаленный элемент - 33;
  10. v=[1,7]v = [1, 7], максимум - 77;
  11. v=[1]v = [1], удаленный элемент - 77;
  12. v=[1]v = [1], максимум - 11.