Стёпа и Катя работают в Яндексе и создают новый искусственный интеллект для научно-исследовательских целей. ИИ работает с целыми числами, особенно с числами от $$$1$$$ до $$$N$$$. Раскрыть предназначение ИИ они пока не готовы, но известно, что для него важно свойство обратимости чисел: так они называют тот факт, что $$$N - (N - X) = X$$$ для всех $$$X$$$ от $$$1$$$ до $$$N$$$.

Вы решили на шаг опередить разработки Яндекса и создать аналогичный ИИ, который тоже будет работать с числами от $$$1$$$ до $$$N$$$, но будет сосредоточен на операциях умножения и деления чисел. Для этого вы определили своё свойство суперобратимости. Будем говорить, что целое число $$$X$$$ ($$$1 \le X \le N$$$) суперобратимо для $$$N$$$, если $$$N\ div\ (N\ div\ X) = X$$$, где $$$div$$$ — операция целочисленного деления с округлением вниз.

К сожалению, не все числа оказались суперобратимы. Но нельзя терять время! Нужно скорее продолжить работу, а для этого нужно определить, сколько целых чисел от $$$1$$$ до $$$N$$$ являются суперобратимыми. Возможно, придётся даже перебрать несколько значений $$$N_i$$$, пока вы не найдёте подходящее.

$$$$$$ \begin{array} {|c|c|c|c|}

\hline \textbf{Подзадача} & \textbf{Баллы} & \textbf{Ограничения} & \textbf{Необходимые подзадачи} \\ \hline 1 & 34 & N_i \le 10^5 & \\ \hline 2 & 34 & N_i \le 10^9 & 1 \\ \hline 3 & 32 & N_i \le 10^{18} & 1, 2 \\ \hline \end{array} $$$$$$

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

Петя поступил на ФИИТ УрФУ и всё ещё не запомнил, как ориентироваться в учебном корпусе — матмехе. После второй пары Петя бесцельно слоняется по коридорам, которые представляют из себя сплошной лабиринт. Корпус имеет форму прямоугольника ширины $$$W$$$ и высоты $$$H$$$, разделённого на клетки $$$1 \times 1$$$. Клетки бывают четырёх типов:

• Пустая клетка;
• Клетка со стеной;
• Клетка с ключом;
• Клетка с запертой дверью.

Как назло уборщицы регулярно начинают мыть пол, поэтому если Петя начнёт двигаться в одном направлении, то он не остановится, пока не упрётся в препятствие. Препятствиями являются граница корпуса, стена, а также запертая дверь, если у Пети нет ключа.

По пути Петя может собирать ключи. Проходя мимо ключа, Петя моментально подбирает его, не останавливаясь. Он может носить с собой неограниченное количество ключей. Любой ключ подходит к любой двери. Если Петя упирается в запертую дверь, он моментально открывает её ключом и продолжает движение без остановки. Ключ остается в замочной скважине двери. Если же у Пети нет с собой ни одного ключа, то запертые двери для него не отличаются от стен.

Также известно, что во время пар декан открывает все двери. Поэтому во время пар на матмехе нет ни одной запертой двери и ни одного ключа. Во время перемены можно найти ключи и/или запертые двери.

Помогите Пете не заблудиться и выбраться в столовую. Он знает, в какой клетке он начал свой путь, а также всю историю своих передвижений. Он сделал $$$L$$$ шагов, каждый из шагов — перемещение в одном из четырех направлений: вверх, вправо, вниз или влево. Для каждого из шагов выведите, сколько клеток лабиринта он проскользил в этом направлении.

$$$$$$ \begin{array} {|c|c|c|c|}

\hline \textbf{Подзадача} & \textbf{Баллы} & \textbf{Ограничения} & \textbf{Необх. подзадачи} \\ \hline 1 & 25 & H \cdot W \le 100, L \le 100, D = 0 & \\ \hline 2 & 25 & H \cdot W \le 100, L \le 100, D \le 1 & 1 \\ \hline 3 & 25 & H \cdot W \le 10^5, L \le 10^5, D = 0 & 1 \\ \hline 4 & 25 & H \cdot W \le 10^5, L \le 10^5, D \le 1 & 1, 2, 3 \\ \hline \end{array} $$$$$$

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

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

В ходе наблюдений вы заметили, что объекты со временем меняются. Это вы решили записать в журнал с помощью правил. Всего получилось $$$N$$$ правил. Правило номер $$$i$$$ гласит, что объект $$$A_i$$$ со временем превратится в объект $$$B_i$$$. Такое правило записывается как «$$$A_i$$$ IS $$$B_i$$$». Заметим, что объекты $$$A_i$$$ и $$$B_i$$$ могут совпадать, в этом случае превращение всё равно происходит.

Сегодня вы вернулись в исследовательский центр и решили заняться теоретическими экспериментами. Вам дали план, состоящий из $$$Q$$$ запросов. У вас нет при себе экземпляров изученных объектов, поэтому при выполнении запросов приходится опираться на записи в журнале. Каждый запрос задаётся одним из двух способов:

1. «? $$$C_j$$$». Чтобы выполнить этот запрос, нужно провести эксперимент и определить, во что в конечном итоге превратится объект $$$C_j$$$ согласно записанным в журнале правилам.
2. «+ $$$C_j$$$ IS $$$D_j$$$». Чтобы выполнить этот запрос, нужно добавить новое правило в журнал, согласно которому объект $$$C_j$$$ превращается в объект $$$D_j$$$. Новое правило не отличается от старых, и оно начинает работать для всех последующих запросов.

Важная часть любой исследовательской деятельности — ведение отчёта об ошибках. В ходе проведения эксперимента может произойти ошибка одного из двух типов:

• «INFINITE LOOP»: эта ошибка происходит в том случае, если цепочка превращений объекта бесконечна, то есть объект будет превращаться в другой объект сколько угодно раз. Ошибка не возникает, если объект превращается сам в себя.
• «TOO COMPLEX»: эта ошибка происходит в том случае, если согласно записанным правилам объект одновременно должен превратиться в два разных объекта. При возникновении этой ошибки эксперимент нужно тут же прекратить. Ошибка не возникает, если объект превращается в один и тот же объект по двум различным правилам. Но ошибка возникает, если объект должен превратиться в себя и в другой объект.

Попробуйте для каждого запроса первого вида определить, во что превратится данный объект или какая ошибка возникнет в результате выполнения запроса. Обратите внимание, что в одном запросе не могут произойти две ошибки сразу.

$$$$$$ \begin{array} {|c|c|c|c|}

\hline \textbf{Подзадача} & \textbf{Баллы} & \textbf{Ограничения} & \textbf{Необх. подзадачи} \\ \hline 1 & 20 & N, Q \le 50, \text{нет запросов на добавление, нет ошибок} & \\ \hline 2 & 18 & N, Q \le 50 & 1 \\ \hline 3 & 20 & N, Q \le 1000 & 1, 2 \\ \hline 4 & 22 & N, Q \le 50000, \text{нет ошибок} & 1 \\ \hline 5 & 20 & N, Q \le 50000 & 1, 2, 3, 4 \\ \hline \end{array} $$$$$$

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

Обратите внимание на необычные ограничения в подзадачах $$$1$$$ и $$$4$$$. В них гарантируется, что при выполнении превращений не возникает ошибок. В подзадаче $$$1$$$ также гарантируется, что нет запросов второго вида.

В коридорах матмеха, где учатся студенты ФИИТ, есть много всего интересного: рояль на потолке, Хогвартс, оптические иллюзии на полу, качели, даже портал на платформу $$$9\frac{3}{4}$$$. А ещё есть шахматы на стене, в которые любят играть студенты Артемий и Михей. Во время каникул на матмехе начался ремонт, поэтому доску сняли.

Ребята не растерялись и решили нарисовать шахматы мелом на стене. За каникулы правила игры они подзабыли. Начертив мелом доску $$$M \times M$$$, они начали вспоминать, как должны быть расположены фигуры. Михей недолго думал и нарисовал на поле $$$N$$$ белых королей — король ведь лучшая фигура! Артемий разбирался в шахматах побольше, и он знал, что лучшая фигура — это ферзь. Поэтому Артемий решил нарисовать на свободной клетке одного чёрного ферзя, который поставил бы под бой всех белых королей и при этом сам не был бы под боем.

По авторитетному мнению Михея, король может бить 8 смежных клеток, имеющих общую сторону или общий угол с той клеткой, на которой стоит сам король. Ферзь же полностью бьёт горизонталь, вертикали и обе диагонали, на которых стоит. При этом наши герои забыли, что ферзь не может прыгать через фигуры: по их мнению, если два короля стоят на одной линии и по одну сторону от ферзя, ферзь может бить их обоих.

Всего они провели $$$T$$$ игр, каждый раз заново рисуя доску и фигуры. Зная, как Михей располагал своих королей, посчитайте количество позиций, куда Артемий мог поставить ферзя так, чтобы он не стоял под боем ни одного из королей и при этом все короли стояли под его боем.

$$$$$$ \begin{array} {|c|c|c|c|}

\hline \textbf{Подзадача} & \textbf{Баллы} & \textbf{Ограничения} & \textbf{Необх. подзадачи} \\ \hline 1 & 14 & M \le 100, N = 1 & \\ \hline 2 & 19 & M, N \le 100 & 1 \\ \hline 3 & 20 & M, N \le 1000 & 1, 2 \\ \hline 4 & 28 & M, N \le 10^5 & 1, 2, 3 \\ \hline 5 & 19 & M \le 10^9, N \le 10^5 & 1, 2, 3, 4 \\ \hline \end{array}$$$$$$

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

В компании NAUMEN очень ценятся личные качества сотрудников. Основными личными качествами являются сила и ум. Недавно компания провела тестирование всех своих сотрудников, в результате которого были определены показатели силы и ума. По мнению исследователей, эти параметры позволят объективно оценить работоспособность каждого сотрудника.

Всего в компании $$$N$$$ сотрудников, пронумерованных от $$$1$$$ до $$$N$$$. Компания имеет иерархическую структуру. Чем меньше номер сотрудника, тем он главнее. Сотрудник номер $$$1$$$ является директором, у него нет начальника. У всех остальных сотрудников есть начальник: у сотрудника номер $$$i$$$ начальником является сотрудник номер $$$P_i$$$ ($$$P_i \lt i$$$). Также принято считать, что $$$P_1 = 0$$$.

В результате исследования было определено, что $$$i$$$-й сотрудник имеет силу $$$A_i$$$ и ум $$$B_i$$$. Эти показатели важны при решении проблем. Исследователи компании NAUMEN предложили следующую математическую модель проблемы: по их мнению, проблема — это пара натуральных чисел $$$(x, y)$$$. Первое число описывает физическую сложность проблемы, второе число — умственную. Считается, что сотрудник номер $$$i$$$ может самостоятельно решить проблему $$$(x, y)$$$, если $$$A_i \ge x$$$ и $$$B_i \ge y$$$. Таким образом, учитываются как сила, так и ум.

Конечно, сотрудники не всегда решают проблемы поодиночке. Если у сотрудника в подчинении есть люди, он может делегировать любому своему непосредственному подчинённому эту проблему. Тот сотрудник, кому проблема была делегирована, может в свою очередь делегировать её одному из своих подчинённых, и так далее. Таким образом, если хотя бы один из подчинённых $$$i$$$-го сотрудника может решить проблему, то считается, что и $$$i$$$-й сотрудник может её решить.

Вам было поручено подведение итогов исследования. Для этого нужно для каждого сотрудника посчитать, сколько различных проблем он умеет решать. Обратите внимание, что раз параметры $$$x$$$ и $$$y$$$ в любой проблеме $$$(x, y)$$$ — натуральные числа, то множество различных проблем, которые умеет решать сотрудник, всегда конечно.

$$$$$$ \begin{array} {|c|c|c|c|}

\hline \textbf{Подзадача} & \textbf{Баллы} & \textbf{Ограничения} & \textbf{Необх. подзадачи} \\ \hline 1 & 21 & N \le 5, A_i \le 10, B_i \le 10 & \\ \hline 2 & 26 & N \le 50, A_i \le 100, B_i \le 10^6 & 1 \\ \hline 3 & 23 & N \le 5000, A_i \le 100, B_i \le 10^6 & 1, 2 \\ \hline 4 & 14 & N \le 500, A_i \le 10^6, B_i \le 10^6 & 1, 2 \\ \hline 5 & 16 & N \le 50000, A_i \le 10^6, B_i \le 10^6 & 1, 2, 3, 4 \\ \hline \end{array}$$$$$$

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

Ваня учится на ФИИТ в УрФУ, где каждый семестр студенты делают командные проекты. У Вани много друзей в группе, но у каждого свои требования. Например, если позвать в команду Петю, то должен прийти и Алёша, иначе Петя не придёт. Ваня по данным требованиям смог выяснить, что у него есть целых $$$N$$$ вариантов, кого пригласить. Каждый из способов он описал в виде величины $$$A_i$$$ — количество друзей в выборке под номером $$$i$$$.

Но это было полбеды! Ведь после того, как он с друзьями соберёт команду, нужно будет выбрать того, кто будет представлять проект на защите. Все ребята любят программировать, и никто не хочет заниматься презентацией, поэтому они договорились, что защищает проект тот, кого выберут по считалочке.

Ваня, будучи организатором этого выбора, должен проводить этот расчёт. Чтобы выбрать ответственного по считалочке, он выстраивает людей по кругу и начинает считать от себя, считая по одному слову на человека. На кого попадёт последнее слово, тот и защищает проект. Иван знает $$$Q$$$ считалочек. Считалочка номер $$$j$$$ состоит из $$$B_j$$$ слов. Он решил узнать, насколько удачной будет каждая из них. Для этого он ввёл понятие хорошей компании одногруппников — таковой она является, если в ней он не будет защищать проект при использовании данной считалочки.

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

$$$$$$ \begin{array} {|c|c|c|c|}

\hline \textbf{Подзадача} & \textbf{Баллы} & \textbf{Ограничения} & \textbf{Необх. подзадачи} \\ \hline 1 & 10 & N, Q \le 100; A_i, B_j \le 10^3 & \\ \hline 2 & 30 & N, Q \le 10^3; A_i, B_j \le 10^6 & 1 \\ \hline 3 & 16 & N \le 5000, Q \le 10^5; A_i, B_j \le 10^6 & 1, 2 \\ \hline 4 & 16 & N \le 10^5, Q \le 5000; A_i, B_j \le 10^6 & 1, 2 \\ \hline 5 & 15 & N, Q \le 10^5; A_i, B_j \le 10^6 & 1, 2, 3, 4 \\ \hline 6 & 13 & N \le 10^5, Q \le 10^6; A_i, B_j \le 10^7 & 1, 2, 3, 4, 5 \\ \hline \end{array}$$$$$$

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

Паша Вилкин, как и остальные студенты ФИИТ, проходит много разных курсов на платформе Ulearn.me. В последнее время у него скопилось много задачек на программирование, которые нужно успеть решить к дедлайну. Чтобы написать качественные решения и уложиться в срок, нужно пройти 4 этапа:

1. Написать код;
2. Отправить код на проверку автотестами;
3. Внести правки по результатам тестирования;
4. Отправить решение на код-ревью.

Первый и третий этапы требуют присутствия Паши и занимают время $$$A$$$. Для второго и четвёртого этапов присутствие Паши не требуется, каждый из них занимает время $$$B$$$. Чтобы решение получилось качественным, весь процесс должен идти без остановки. Помогите Паше рассчитать минимальное время, необходимое для решения $$$N$$$ задач.

$$$$$$ \begin{array} {|c|c|c|c|}

\hline \textbf{Подзадача} & \textbf{Баллы} & \textbf{Ограничения} & \textbf{Необх. подзадачи}\\ \hline 1 & 17 & B \lt A, N \le 10^5 & \\ \hline 2 & 15 & B \le A, N \le 10^5 & 1 \\ \hline 3 & 16 & B \le 2A, N \le 10^5 & 1, 2 \\ \hline 4 & 26 & N \le 10^5 & 1, 2, 3 \\ \hline 5 & 26 & N \le 10^9 & 1, 2, 3, 4 \\ \hline \end{array}$$$$$$

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