В современном мире есть множество различных баз данных, основанных на разных структурах и принципах. В дополнение к реляционным (например, MySQL) и графовым (например, GraphQL), недавно стажер компании VK предложил идею новой базы данных DequeQL, основанной на деках. Разумеется, не все идеи стажеров действительно хорошие, но, будучи ответственным ментором, Лев решил реализовать его идею и проверить ее эффективность.

Дек — структура данных, хранящая последовательность элементов, и позволяющая добавлять новый элемент или вынимать элемент с любого из двух концов последовательности. Базовым блоком данных в DequeQL является юнит (unit) — пустой дек, соответствующий минимальной единице информации. Сама база данных представляет из себя множество пронумерованных деков, вложенных друг в друга. Дек, не вложенный ни в какой другой, называется корнем. Разумеется, если некоторый юнит не лежит в другом деке, он тоже считается корнем.

DequeQL поддерживает четыре операции на изменение:

1. push_back($$$d_1$$$, $$$d_2$$$) — положить корень $$$d_1$$$ в конец корня $$$d_2$$$ ($$$d_1$$$ перестает быть корнем);
2. push_front($$$d_1$$$, $$$d_2$$$) — положить корень $$$d_1$$$ в начало корня $$$d_2$$$ ($$$d_1$$$ перестает быть корнем);
3. pop_back($$$d$$$) — достать из корня $$$d$$$ последний элемент (при этом этот элемент становится корнем);
4. pop_front($$$d$$$) — достать из корня $$$d$$$ первый элемент (изъятый элемент тоже становится корнем);

Обратите внимание, что операции можно производить только над корневыми элементами базы данных. Лев уже реализовал эти операции, и решил, что DequeQL может быть полезна в одном из новых проектов VK, если расширить ее функционал и добавить поддержку ответов на запрос pop_complexity($$$d$$$) — какое минимальное количество операций pop_back или pop_front надо выполнить, чтобы $$$d$$$ стал корнем? Сама структура базы данных при этом не меняется, то есть выполнять соответствующие действия pop не надо.

Пока у Льва выходной, у вас есть возможность зарекомендовать себя в качестве квалифицированного разработчика. Вам дана база данных, состоящая из $$$n$$$ юнитов с номерами от $$$1$$$ до $$$n$$$. Реализуйте требуемый функционал и выведите ответ на каждый запрос.

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