H. Омкар и туры
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Омкар устраивает туры по своей стране, Омкарландии! В Омкарландии $$$n$$$ городов, и, что довольно любопытно, существует ровно $$$n-1$$$ двунаправленных дорог, соединяющих города друг с другом. Гарантируется, что вы можете добраться до любого города из любого другого города через сеть дорог.

Каждый город имеет значение удовольствия $$$e$$$. У каждой дороги есть пропускная способность $$$c$$$, обозначающее максимальное количество автомобилей, которое может на ней находиться, и соответствующая плата за проезд $$$t$$$. Однако система взимания платы в Омкарландии имеет интересную особенность: если автомобиль проезжает по нескольким дорогам за одну поездку, он платит только самую высокую плату за проезд по любой отдельной дороге, по которой он проехал. (Другими словами, он платит $$$\max t$$$ по всем дорогам, по которым они проехал). Если автомобиль не проезжает ни одной дороги, он платит $$$0$$$ за проезд.

Омкар решил принять $$$q$$$ туристических групп. Каждая туристическая группа состоит из $$$v$$$ автомобилей, стартующих из города $$$x$$$. (Следует помнить, что туристическая группа с $$$v$$$ автомобилями может передвигаться только по дорогам с пропускной способностью $$$\geq v$$$). Будучи организатором тура, Омкар хочет, чтобы его группы получили как можно больше удовольствия, но при этом он должен возместить своим группам расходы на проезд по дорогам, которые они должны заплатить. Таким образом, для каждой туристической группы Омкар хочет знать две вещи: во-первых, какое максимальное значение удовольствия имеет город $$$y$$$ — город с максимальным значением удовольствия среди тех, до которых туристическая группа может добраться из своего начального города, и, во-вторых, сколько Омкар должен будет заплатить с каждого автомобиля, чтобы возместить расходы всей группы на поездку из $$$x$$$ в $$$y$$$? (Эта поездка из $$$x$$$ в $$$y$$$ всегда будет проходить по кратчайшему пути из $$$x$$$ в $$$y$$$).

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

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$), обозначающих количество городов и количество групп, соответственно.

Следующая строка содержит $$$n$$$ целых чисел $$$e_1, e_2, \ldots, e_n$$$ ($$$1 \leq e_i \leq 10^9$$$), где $$$e_i$$$ представляет собой значение удовольствия для города $$$i$$$.

Следующие $$$n-1$$$ строки содержат по четыре целых числа $$$a$$$, $$$b$$$, $$$c$$$ и $$$t$$$ ($$$1 \leq a,b \leq n$$$, $$$1 \leq c \leq 10^9$$$, $$$1 \leq t \leq 10^9$$$), обозначающих дорогу между городом $$$a$$$ и городом $$$b$$$ с пропускной способностью $$$c$$$ и платой за проезд $$$t$$$.

Следующие $$$q$$$ строк содержат по два целых числа $$$v$$$ и $$$x$$$ ($$$1 \leq v \leq 10^9$$$, $$$1 \leq x \leq n$$$), обозначающих количество автомобилей в туристической группе и начальном городе, соответственно.

Выходные данные

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

Примеры
Входные данные
5 3
2 2 3 3 3
1 2 4 7
1 3 2 8
2 4 8 2
2 5 1 1
1 3
9 5
6 2
Выходные данные
3 8
3 0
3 2
Входные данные
5 5
1 2 3 4 5
1 2 4 1
1 3 3 1
1 4 2 1
2 5 1 1
5 1
4 1
3 1
2 1
1 1
Выходные данные
1 0
2 1
3 1
4 1
5 1
Входные данные
5 5
1 2 2 2 2
1 2 5 8
1 3 6 3
1 4 4 5
1 5 7 1
4 1
5 1
6 1
7 1
8 1
Выходные данные
2 8
2 8
2 3
2 1
1 0
Примечание

Карта с первого примера показана ниже. Для вершин нежирные числа представляют индексы, а жирные — значения удовольствия. Для ребер нежирные цифры обозначают пропускную способность, а жирные — стоимость проезда.

Для первого запроса туристическая группа размером $$$1$$$, стартующая из города $$$3$$$, может достичь городов $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$. Таким образом, наибольшее значение удовольствия, которого они могут достичь, равно $$$3$$$. Если туристическая группа решит поехать в город $$$4$$$, Омкар должен будет заплатить $$$8$$$ за машину, что является максимумом.

Для второго запроса туристическая группа размером $$$9$$$, стартующая из города $$$5$$$, может достичь только города $$$5$$$. Таким образом, наибольшее достижимое значение удовольствия по-прежнему составляет $$$3$$$, и Омкар заплатит $$$0$$$ за автомобиль.

Для третьего запроса туристическая группа размером $$$6$$$, стартующая из города $$$2$$$, может достичь городов $$$2$$$ и $$$4$$$. Наибольшее достижимое значение удовольствия снова равно $$$3$$$. Если туристическая группа решит поехать в город $$$4$$$, Омкар должен будет заплатить $$$2$$$ за машину, что является максимумом.

Карта второй выборки показана ниже:

Для первого запроса, туристическая группа размером $$$5$$$, стартующая из города $$$1$$$, может достичь только города $$$1$$$. Таким образом, их максимальная ценность удовольствия составляет $$$1$$$, а стоимость, которую придется заплатить Омкару, равна $$$0$$$ за автомобиль.

Для второго запроса туристическая группа размером $$$4$$$, стартующая из города $$$1$$$, может добраться до городов $$$1$$$ и $$$2$$$. Таким образом, их максимальная ценность удовольствия составляет $$$2$$$, а Омкар заплатит $$$1$$$ за автомобиль.

Для третьего запроса, туристическая группа размером $$$3$$$, стартующая из города $$$1$$$, может добраться до городов $$$1$$$, $$$2$$$ и $$$3$$$. Таким образом, их максимальная ценность удовольствия составляет $$$3$$$, и Омкар заплатит $$$1$$$ за автомобиль.

Для четвертого запроса туристическая группа размером $$$2$$$, стартующая из города $$$1$$$, может добраться до городов $$$1$$$, $$$2$$$, $$$3$$$ и $$$4$$$. Таким образом, их максимальная ценность удовольствия составляет $$$4$$$, и Омкар заплатит $$$1$$$ за автомобиль.

Для пятого запроса туристическая группа размером $$$1$$$, стартующая из города $$$1$$$, может добраться до городов $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$. Таким образом, их максимальное удовольствие составляет $$$5$$$, и Омкар заплатит $$$1$$$ за машину.