Однажды, во время своего путешествия, Фрирен наткнулась на магазин гримуаров, и как можно догадаться, купила $$$n$$$ гримуаров, потратив на это почти все свои сбережения. Придя домой, Фрирен поверхностно изучила каждый из них, и охарактеризовала $$$i$$$-й гримуар двумя параметрами $$$a_i$$$ (сложность) и $$$b_i$$$ (потенциал).

Так как Фрирен никуда не торопится, при изучении для нее интересен не только потенциал полученных знаний, но и удовольствие от разбора сложных гримуаров. Поэтому она решила, что будет изучать гримуары в особом порядке. Если ей скучно, она будет изучать самый сложный гримуар (с максимальным $$$a_i$$$) из всех доступных; а если она почувствует, что ей хочется узнать что-то совершенно новое, она выберет гримуар с самым большим потенциалом $$$b_i$$$.

Если есть несколько гримуаров с максимальным интересующим Фрирен параметром, то она выберет тот из них, у которого максимален второй параметр, а если и вторые параметры равны, то Фрирен возьмет тот из них, который она купила раньше.

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

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

Фрирен анализирует барьер, возведенный Зерие над территорией проведения первого теста в экзамене на мага первого класса. Зерие — одна из древнейших и наиболее могущественных магов, поэтому разрушить этот барьер будет непросто. Но и Фрирен тоже имеет огромный тысячелетний опыт за плечами, поэтому сразу поняла, что барьер параметризован $$$n$$$ целыми числами $$$a_i$$$.

Для того, чтобы разрушить барьер, Фрирен необходимо по этим $$$a_i$$$ найти ключевую последовательность этого барьера. Ключевая последовательность состоит ровно из $$$k$$$ целых чисел $$$b_i$$$, где $$$$$$b_i = \mathtt{mex}\left( \left\lfloor\frac{a_1}{i}\right\rfloor, \left\lfloor\frac{a_2}{i}\right\rfloor, \ldots, \left\lfloor\frac{a_n}{i}\right\rfloor \right) \text{.}$$$$$$

Здесь $$$\mathtt{mex}$$$ означает минимальное целое неотрицательное число, которое отсутствует в последовательности, а $$$\left\lfloor\frac{a_j}{i}\right\rfloor$$$ — неполное частное при делении $$$a_j$$$ на $$$i$$$. Например, при $$$i = 3$$$ и $$$a = [1, 2, 5, 6, 13, 23]$$$, после деления на $$$i$$$ мы получим последовательность $$$[0, 0, 1, 2, 4, 7]$$$, и $$$\mathtt{mex}(0, 0, 1, 2, 4, 7) = 3$$$.

Иными словами, требуется для каждого $$$i$$$ от $$$1$$$ до $$$k$$$ найти $$$\mathtt{mex}$$$ последовательности, образованной из $$$a$$$ делением нацело на $$$i$$$. Помогите Фрирен найти ключевую последовательность барьера, чтобы она могла его разрушить и помочь своим сокомандникам.

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

Несмотря на юную внешность, Фрирен прожила больше тысячи лет. Восприятие времени эльфийки отличается от человеческого, и год-другой для нее ничего не стоит. Тем не менее, она хорошо помнит, что в $$$i$$$-й год жизни с ней произошли $$$a_i$$$ хороших событий и $$$b_i$$$ плохих.

Однажды Ферн, ученица Фрирен, стала расспрашивать наставницу о ее прошлом. Она задала $$$q$$$ вопросов, в $$$i$$$-м из которых упомянула два года из жизни Фрирен: $$$x_i$$$-й и $$$y_i$$$-й. Фрирен, хоть и хорошо помнит свою жизнь, не хочет отвечать на скучные вопросы, поэтому некоторые из них останутся без ответа.

Скажем, что два года $$$x$$$ и $$$y$$$ являются

• $$$a$$$-интересными, если $$$a_x$$$ делится на $$$a_y$$$ или, наоборот, является его делителем;
• $$$ab$$$-интересными, если $$$a_x = b_y$$$ или $$$a_y = b_x$$$;
• взаимно интересными, если либо они $$$a$$$-интересные, либо они $$$ab$$$-интересные, либо существует год $$$z$$$, что $$$x$$$ и $$$z$$$ взаимно интересные и $$$y$$$ и $$$z$$$ взаимно интересные.

Иными словами, если есть последовательность лет $$$x_1, \ldots, x_k$$$, что любые $$$x_i$$$ и $$$x_{i+1}$$$ либо $$$a$$$-интересные, либо $$$ab$$$-интересные, Фрирен считает $$$x_1$$$ и $$$x_k$$$ взаимно интересными.

Подскажите Ферн, какие из ее вопросов будут интересными (то есть упоминаемые в них года $$$x_i$$$ и $$$y_i$$$ взаимно интересные для Фрирен), а какие — нет.

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

Many decades have passed since the great war. Humans are not destined to live too long, so with the change of generations, even such events from the past are gradually forgotten.

You set out on a journey to visit the places where the team of heroes passed during their trip. The map of the continent is represented as a tree, meaning that there is a unique path between any two of the $$$n$$$ cities. Traveling along each edge of the tree takes exactly one year.

In addition, each city is characterized by the value $$$s_i$$$ — the level of memory of the events of those days. It is known that with each passing year, the level of memory in all cities decreases by $$$1$$$. Sometimes events of the following types occur:

• "- $$$t_i$$$ $$$x_i$$$" — at the beginning of year $$$t_i$$$, someone erects or restores a monument to the heroes and organizes an annual celebration in honor of the heroes' victory in city $$$x_i$$$. Then, starting from this year inclusive, the memory in this city stops decreasing.
• "+ $$$t_i$$$ $$$x_i$$$" — at the beginning of year $$$t_i$$$, a monument is destroyed or the celebration is canceled in city $$$x_i$$$. Then, starting from this year inclusive, the level of memory in this city begins to decrease annually by $$$1$$$ again.

The level of memory does not drop below $$$0$$$ and can never increase. It is guaranteed that events of type '+' can occur only if before that the last event that occurred in the same city was of type '-'. Similarly, an event of type '-' cannot follow another event of type '-' in the same city.

You are interested in questions of the form "if at the beginning of year $$$t'_i$$$ you set out on a journey from city $$$x'_i$$$, and no more changes of type '+' or '-' will occur in the cities, what is the maximum level of memory about the heroes can you encounter?". Find an answer for every such query.