Однажды, во время своего путешествия, Фрирен наткнулась на магазин гримуаров, и как можно догадаться, купила $$$n$$$ гримуаров, потратив на это почти все свои сбережения. Придя домой, Фрирен поверхностно изучила каждый из них, и охарактеризовала $$$i$$$-й гримуар двумя параметрами $$$a_i$$$ (сложность) и $$$b_i$$$ (потенциал).
Так как Фрирен никуда не торопится, при изучении для нее интересен не только потенциал полученных знаний, но и удовольствие от разбора сложных гримуаров. Поэтому она решила, что будет изучать гримуары в особом порядке. Если ей скучно, она будет изучать самый сложный гримуар (с максимальным $$$a_i$$$) из всех доступных; а если она почувствует, что ей хочется узнать что-то совершенно новое, она выберет гримуар с самым большим потенциалом $$$b_i$$$.
Если есть несколько гримуаров с максимальным интересующим Фрирен параметром, то она выберет тот из них, у которого максимален второй параметр, а если и вторые параметры равны, то Фрирен возьмет тот из них, который она купила раньше.
Фрирен будет выбирать книги по настроению и, очевидно, не будет заново изучать уже прочитанный гримуар. Поэтому Ферн планирует уже изученные гримуары продавать, чтобы хоть немного восстановить денежные ресурсы команды. Но, чтобы случайно не продать еще не изученный гримуар, она просит вас вывести, в каком порядке Фрирен будет их читать.
В первой строке ввода дано целое число $$$n$$$ — количество купленных гримуаров ($$$1 \le n \le 10^5$$$).
Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — значения сложности гримуаров в порядке их покупки ($$$1 \le a_i \le 10^9$$$). В третьей строке в том же формате даны целые числа $$$b_i$$$ — значения потенциалов гримуаров ($$$1 \le b_i \le 10^9$$$).
В последней строке через пробел перечислены $$$n$$$ целых чисел $$$p_i$$$ — индикаторы настроения Фрирен перед выбором $$$i$$$-го гримуара. Если $$$p_i = 1$$$, Фрирен будет выбирать гримуар с максимальным потенциалом, иначе $$$p_i = 0$$$ и Фрирен выберет самый сложный из доступных гримуаров.
Выведите $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$, разделенных пробелами; $$$i$$$-е число должно быть равно номеру гримуара, который выберет Фрирен в $$$i$$$-й раз.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 10 | $$$n, a_i, b_i \le 10$$$ | полная | |
| 2 | 5 | все $$$a_i$$$ одинаковы | первая ошибка | |
| 3 | 10 | $$$1 \le a_i, b_i \leq n$$$, $$$a_i \ne a_j$$$ и $$$b_i \ne b_j$$$ для всех $$$i \ne j$$$ | первая ошибка | |
| 4 | 30 | $$$n \le 1000$$$ | 1 | первая ошибка |
| 5 | 5 | для любых $$$i \ne j$$$ пары $$$(a_i, b_i)$$$ и $$$(a_j, b_j)$$$ различны | 3 | первая ошибка |
| 6 | 40 | без дополнительных ограничений | 1 – 5 | первая ошибка |
51 2 3 4 55 4 3 2 11 0 1 0 0
1 5 2 4 3
63 10 6 2 10 13 5 10 7 5 90 0 1 1 0 1
2 5 3 6 1 4
Фрирен анализирует барьер, возведенный Зерие над территорией проведения первого теста в экзамене на мага первого класса. Зерие — одна из древнейших и наиболее могущественных магов, поэтому разрушить этот барьер будет непросто. Но и Фрирен тоже имеет огромный тысячелетний опыт за плечами, поэтому сразу поняла, что барьер параметризован $$$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$$$. Помогите Фрирен найти ключевую последовательность барьера, чтобы она могла его разрушить и помочь своим сокомандникам.
В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$k$$$ — длина последовательности $$$a$$$ и длина искомой ключевой последовательности ($$$1 \le n, k \le 10^6$$$).
Во второй строке ввода через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — элементы последовательности параметров барьера ($$$0 \le a_i \le 10^6$$$).
В единственной строке ввода через пробел выведите $$$k$$$ целых чисел — элементы ключевой последовательности барьера.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 12 | $$$n, k \le 100$$$ | полная | |
| 2 | 13 | $$$a_i \le 10$$$ для всех $$$i$$$ | первая ошибка | |
| 3 | 13 | $$$n \le 10$$$ | первая ошибка | |
| 4 | 12 | $$$n, k \le 1000$$$ | 1 | первая ошибка |
| 5 | 21 | $$$n, k \le 10^5$$$ | 1, 4 | первая ошибка |
| 6 | 29 | без дополнительных ограничений | 1 – 5 | первая ошибка |
6 51 5 23 6 13 2
0 4 3 2 3
10 105 9 8 13 25 7 11 6 45 10
0 0 0 0 0 3 2 2 3 3
Несмотря на юную внешность, Фрирен прожила больше тысячи лет. Восприятие времени эльфийки отличается от человеческого, и год-другой для нее ничего не стоит. Тем не менее, она хорошо помнит, что в $$$i$$$-й год жизни с ней произошли $$$a_i$$$ хороших событий и $$$b_i$$$ плохих.
Однажды Ферн, ученица Фрирен, стала расспрашивать наставницу о ее прошлом. Она задала $$$q$$$ вопросов, в $$$i$$$-м из которых упомянула два года из жизни Фрирен: $$$x_i$$$-й и $$$y_i$$$-й. Фрирен, хоть и хорошо помнит свою жизнь, не хочет отвечать на скучные вопросы, поэтому некоторые из них останутся без ответа.
Скажем, что два года $$$x$$$ и $$$y$$$ являются
Иными словами, если есть последовательность лет $$$x_1, \ldots, x_k$$$, что любые $$$x_i$$$ и $$$x_{i+1}$$$ либо $$$a$$$-интересные, либо $$$ab$$$-интересные, Фрирен считает $$$x_1$$$ и $$$x_k$$$ взаимно интересными.
Подскажите Ферн, какие из ее вопросов будут интересными (то есть упоминаемые в них года $$$x_i$$$ и $$$y_i$$$ взаимно интересные для Фрирен), а какие — нет.
В первой строке ввода дано одно целое число $$$n$$$ — количество лет, прожитых Фрирен ($$$2 \le n \le 3 \cdot 10^5$$$).
Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — количество хороших событий, произошедших с Фрирен в каждый год ее жизни ($$$1 \le a_i \le 3 \cdot 10^5$$$). Во третьей строке в том же формате даны $$$n$$$ целых чисел $$$b_i$$$ — количество плохих событий, произошедших с Фрирен в каждый год ее жизни ($$$0 \le b_i \le 3 \cdot 10^5$$$).
В четвертой строке ввода дано одно целое число $$$q$$$ — количество вопросов, которые хочет задать Ферн ($$$1 \le q \leq 5 \cdot 10^5$$$).
В $$$i$$$-й из следующих $$$q$$$ строк дана пара целых чисел $$$x_i$$$ и $$$y_i$$$ — упомянутые Ферн в $$$i$$$-м вопросе года из жизни Фрирен ($$$1 \le x_i, y_i \le n$$$).
Выведите $$$q$$$ строк, в $$$i$$$-й из которых выведите ответ на соответствующий запрос. Выведите «YES» (без кавычек), если $$$i$$$-й вопрос Ферн будет интересным, а иначе выведите «NO».
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 13 | $$$n, q \le 100$$$ | полная | |
| 2 | 14 | $$$b_i = 0$$$ для всех $$$i$$$ | первая ошибка | |
| 3 | 14 | $$$a_i$$$ — простое для всех $$$i$$$ | первая ошибка | |
| 4 | 14 | $$$n, q \le 1000$$$ | 1 | первая ошибка |
| 5 | 18 | $$$n \le 5000$$$, $$$q \le 5 \cdot 10^5$$$ | 1, 4 | первая ошибка |
| 6 | 27 | без дополнительных ограничений | 1 – 5 | первая ошибка |
47 5 2 102 7 2 1161 21 31 42 32 43 4
YES YES YES YES YES YES
62 3 4 5 6 79 9 9 9 9 951 21 41 54 64 5
YES NO YES NO NO
Прошло уже множество десятилетий с того дня, как Химмель, Хайтер, Айзен и Фрирен вместе победили Повелителя Демонов. Людям не суждено жить так же долго, как эльфам, поэтому со сменой поколений даже такие героические подвиги из прошлого постепенно забываются.
Одной из целей нынешнего путешествия Фрирен — посетить места, в которых она побывала с командой героев во время своего прошлого путешествия. Карта материка представляет из себя дерево, то есть между любыми двумя из $$$n$$$ городов существует единственный путь. Путешествие по каждому ребру дерева занимает ровно один год.
Помимо этого, каждый город характеризуется величиной $$$s_i$$$ — уровнем памяти о событиях тех дней. Известно, что с каждым годом уровень памяти во всех городах уменьшается на $$$1$$$. Иногда случаются события следующего вида:
Уровень памяти не опускается ниже $$$0$$$ и никогда не может увеличиваться. Гарантируется, что события типа '+' могут происходить только если до этого в том же городе случилось событие типа '-', после которого не было других событий типа '+'. Аналогично, событие типа '-' не может следовать после другого события типа '-' в том же городе.
Периодически Фрирен интересуется вопросами вида «если в начале года $$$t'_i$$$ выдвинуться в путь из города $$$x'_i$$$, и никаких изменений типа '+' или '-' в городах больше не будет происходить, какой максимальный уровень памяти о героях, победивших Повелителя Демонов, можно будет встретить?». Помогите ей и ответьте на все интересующие ее вопросы.
В первой строке входных данных через пробел даны два целых числа $$$n$$$ и $$$q$$$ — количество городов на континте, а также количество запросов ($$$1 \le n, q \le 10^5$$$).
Во второй строке через пробел даны $$$n$$$ целых чисел $$$s_i$$$ — начальные уровни памяти в городах в начале года номер $$$0$$$ ($$$0 \le s_i \le 10^9$$$).
Следующие $$$n - 1$$$ строк содержат описание ребер дерева: в $$$i$$$-й из них дана пара целых чисел $$$u_i$$$ и $$$v_i$$$ — номера городов, соединенных $$$i$$$-м ребром ($$$1 \le u_i, v_i \le n$$$). Гарантируется, что от любой вершины до любой существует единственный путь.
В следующих $$$q$$$ строках дано описание запросов. Каждый запрос начинается с символа '-', '+' или '?'. В первых двух случаях за символом через пробел следуют два целых числа $$$t_i$$$ и $$$x_i$$$, которые означают «остановить ('-') или возобновить ('+') процесс уменьшения уровня памяти в городе $$$x_i$$$, начиная с года $$$t_i$$$ включительно». Иначе далее через пробел даны два целых числа $$$t'_i$$$ и $$$x'_i$$$, означающие запрос «какой максимальный уровень памяти можно встретить, выйдя из города $$$x'_i$$$ в начале года $$$t'_i$$$?» ($$$0 \le t_i, t'_i \le 10^9$$$; $$$1 \le x_i, x'_i \le n$$$).
Запросы перечислены в хронологическом порядке. Гарантируется, что запросы типов '-' и '+' с одним и тем же городом чередуются, и первым в этой последовательности обязательно будет '-'.
Для каждого запроса типа '?' выведите ответ на него в отдельной строке. Обратите внимание, что при ответе на такой запрос не надо учитывать последующие запросы типов '-' и '+'.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Последняя подзадача состоит из $$$16$$$ тестов, каждый из которых независимо оценивается в $$$1$$$ балл.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 11 | $$$n \le 10, q \le 20, t \le 20$$$ | полная | |
| 2 | 17 | $$$n \le 5000, q \le 2000$$$ | 1 | первая ошибка |
| 3 | 16 | $$$n \le 10000, q \le 30000$$$ | 1, 2 | первая ошибка |
| 4 | 9 | $$$t_i = 0$$$, типы запросов только '?' | – | первая ошибка |
| 5 | 15 | типы запросов только '?' | 4 | первая ошибка |
| 6 | 16 | типы запросов только '-', '?' | 4, 5 | первая ошибка |
| 7 | 16 | без дополнительных ограничений | 1 – 6 | полная, потестовая оценка |
3 95 7 41 21 3- 0 3? 0 1? 0 2? 0 3+ 3 3- 4 1? 5 1? 5 2? 5 3
6 7 5 1 2 2
5 95 7 4 0 01 21 33 43 5- 0 3? 0 1? 0 2? 0 3+ 4 3- 5 1? 5 1? 5 2? 5 3
6 7 5 2 2 3