Фрирен и память о героях
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Прошло уже множество десятилетий с того дня, как Химмель, Хайтер, Айзен и Фрирен вместе победили Повелителя Демонов. Людям не суждено жить так же долго, как эльфам, поэтому со сменой поколений даже такие героические подвиги из прошлого постепенно забываются.

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

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
111$$$n \le 10, q \le 20, t \le 20$$$полная
217$$$n \le 5000, q \le 2000$$$1первая ошибка
316$$$n \le 10000, q \le 30000$$$1, 2первая ошибка
49 $$$t_i = 0$$$, типы запросов только '?' первая ошибка
515 типы запросов только '?' 4первая ошибка
616 типы запросов только '-', '?' 4, 5первая ошибка
716 без дополнительных ограничений 1 – 6 полная, потестовая оценка

Примеры

Входные данные
3 9
5 7 4
1 2
1 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 9
5 7 4 0 0
1 2
1 3
3 4
3 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