584. Забавная очередь

У вас есть изначально пустой массив $v$ и $N$ возможных операций, которые можно совершить с этим массивом. Элементы массива нумеруются, начиная с 0. Операция может относиться к одному из типов:

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

XOR Перестановка с параметром $x$ — это перестановка вида $p_i = i \oplus x$, где $\oplus$ — это операция XOR. Гарантируется, что все перестановки корректны. Также, при выполнении операции удаления необходимо вывести значение элемента, который был удален из массива.

Первая строка входных данных содержит одно целое число $N$ — количество операций ($1 \leq N \leq 5 \cdot 10^5$). Затем следуют описания операций. Каждая операция начинается с одного целого числа, обозначающего ее тип, затем для операций 1, 2 и 5 следует целое число $x$ ($1 \leq x \leq 5 \cdot 10^5$).

Для каждой операции типа 3, 4 и 6 выводите ее результат (значение удаленного элемента или запрашиваемый максимум).