Прошло уже множество десятилетий с того дня, как Химмель, Хайтер, Айзен и Фрирен вместе победили Повелителя Демонов. Людям не суждено жить так же долго, как эльфам, поэтому со сменой поколений даже такие героические подвиги из прошлого постепенно забываются.
Одной из целей нынешнего путешествия Фрирен — посетить места, в которых она побывала с командой героев во время своего прошлого путешествия. Карта материка представляет из себя дерево, то есть между любыми двумя из $$$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