CF1583H.Omkar and Tours

Omkar is hosting tours of his country, Omkarland! There are $n$ cities in Omkarland, and, rather curiously, there are exactly $n-1$ bidirectional roads connecting the cities to each other. It is guaranteed that you can reach any city from any other city through the road network.

Every city has an enjoyment value $e$. Each road has a capacity $c$, denoting the maximum number of vehicles that can be on it, and an associated toll $t$. However, the toll system in Omkarland has an interesting quirk: if a vehicle travels on multiple roads on a single journey, they pay only the highest toll of any single road on which they traveled. (In other words, they pay $\max t$ over all the roads on which they traveled.) If a vehicle traverses no roads, they pay $0$ toll.

Omkar has decided to host $q$ tour groups. Each tour group consists of $v$ vehicles starting at city $x$. (Keep in mind that a tour group with $v$ vehicles can travel only on roads with capacity $\geq v$.) Being the tour organizer, Omkar wants his groups to have as much fun as they possibly can, but also must reimburse his groups for the tolls that they have to pay. Thus, for each tour group, Omkar wants to know two things: first, what is the enjoyment value of the city $y$ with maximum enjoyment value that the tour group can reach from their starting city, and second, how much per vehicle will Omkar have to pay to reimburse the entire group for their trip from $x$ to $y$? (This trip from $x$ to $y$ will always be on the shortest path from $x$ to $y$.)

In the case that there are multiple reachable cities with the maximum enjoyment value, Omkar will let his tour group choose which one they want to go to. Therefore, to prepare for all possible scenarios, he wants to know the amount of money per vehicle that he needs to guarantee that he can reimburse the group regardless of which city they choose.

Omkar 正在为他的国家 Omkarland 举办旅游活动！Omkarland 共有 $n$ 座城市，且非常有趣的是，这些城市之间恰好由 $n-1$ 条双向道路连接。保证任意两座城市之间均可通过道路网络相互到达。

每座城市都有一个娱乐值 $e$。每条道路都有一个容量 $c$（表示该道路上最多可同时通行的车辆数）以及一个关联的过路费 $t$。然而，Omkarland 的收费系统有一个有趣的特性：若一辆车在单次行程中经过多条道路，则它只需支付所经道路中最高的过路费（即，支付 $\max t$，其中最大值取遍该行程所经的所有道路）。若一辆车未经过任何道路，则其过路费为 $0$。

Omkar 决定组织 $q$ 个旅游团。每个旅游团由 $v$ 辆车组成，均从城市 $x$ 出发。（请注意：一个含 $v$ 辆车的旅游团仅能行驶在容量 $c \geq v$ 的道路上。）作为旅游活动组织者，Omkar 希望他的旅游团尽可能玩得开心，同时也必须为旅游团报销他们所支付的过路费。因此，对于每个旅游团，Omkar 想要知道两件事：第一，该旅游团从出发城市出发所能到达的所有城市中，娱乐值最大的城市 $y$ 的娱乐值是多少；第二，Omkar 为报销整个旅游团从 $x$ 到 $y$ 的行程所需向每辆车支付的金额是多少？（该 $x$ 到 $y$ 的行程将始终沿 $x$ 与 $y$ 之间的最短路径进行。）

若存在多个可达城市具有相同的最大娱乐值，Omkar 将允许旅游团自由选择前往其中任一城市。因此，为应对所有可能情况，他希望知道：为确保无论旅游团选择哪座城市，他都能完成报销，他每辆车最多需准备多少金额？

The first line contains two integers $n$ and $q$ ($2 \leq n \leq 2 \cdot 10^5$, $1 \leq q \leq 2 \cdot 10^5$), representing the number of cities and the number of groups, respectively.

The next line contains $n$ integers $e_1, e_2, \ldots, e_n$ ($1 \leq e_i \leq 10^9$), where $e_i$ represents the enjoyment value for city $i$.

The next $n-1$ lines each contain four integers $a$, $b$, $c$, and $t$ ($1 \leq a,b \leq n$, $1 \leq c \leq 10^9$, $1 \leq t \leq 10^9$), representing an road between city $a$ and city $b$ with capacity $c$ and toll $t$.

The next $q$ lines each contain two integers $v$ and $x$ ($1 \leq v \leq 10^9$, $1 \leq x \leq n$), representing the number of vehicles in the tour group and the starting city, respectively.

第一行包含两个整数 $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$），分别表示该旅行团的车辆数和出发城市。

Output $q$ lines. The $i$-th line should contain two integers: the highest possible enjoyment value of a city reachable by the $i$-th tour group, and the amount of money per vehicle Omkar needs to guarantee that he can reimburse the $i$-th tour group.

输出 $q$ 行。第 $i$ 行应包含两个整数：第 $i$ 个旅游团可达城市的最高可能娱乐值，以及 Omkar 为确保能向第 $i$ 个旅游团报销费用而每辆车所需准备的金额。

A map of the first sample is shown below. For the nodes, unbolded numbers represent indices and bolded numbers represent enjoyment values. For the edges, unbolded numbers represent capacities and bolded numbers represent tolls.

For the first query, a tour group of size $1$ starting at city $3$ can reach cities $1$, $2$, $3$, $4$, and $5$. Thus, the largest enjoyment value that they can reach is $3$. If the tour group chooses to go to city $4$, Omkar will have to pay $8$ per vehicle, which is the maximum.

For the second query, a tour group of size $9$ starting at city $5$ can reach only city $5$. Thus, the largest reachable enjoyment value is still $3$, and Omkar will pay $0$ per vehicle.

For the third query, a tour group of size $6$ starting at city $2$ can reach cities $2$ and $4$. The largest reachable enjoyment value is again $3$. If the tour group chooses to go to city $4$, Omkar will have to pay $2$ per vehicle, which is the maximum.

A map of the second sample is shown below:

For the first query, a tour group of size $5$ starting at city $1$ can only reach city $1$. Thus, their maximum enjoyment value is $1$ and the cost Omkar will have to pay is $0$ per vehicle.

For the second query, a tour group of size $4$ starting at city $1$ can reach cities $1$ and $2$. Thus, their maximum enjoyment value is $2$ and Omkar will pay $1$ per vehicle.

For the third query, a tour group of size $3$ starting at city $1$ can reach cities $1$, $2$, and $3$. Thus, their maximum enjoyment value is $3$ and Omkar will pay $1$ per vehicle.

For the fourth query, a tour group of size $2$ starting at city $1$ can reach cities $1$, $2$, $3$ and $4$. Thus, their maximum enjoyment value is $4$ and Omkar will pay $1$ per vehicle.

For the fifth query, a tour group of size $1$ starting at city $1$ can reach cities $1$, $2$, $3$, $4$, and $5$. Thus, their maximum enjoyment value is $5$ and Omkar will pay $1$ per vehicle.

第一个样例的地图如下所示。对于节点，非粗体数字表示索引，粗体数字表示愉悦值；对于边，非粗体数字表示容量，粗体数字表示通行费。

对于第一个查询：一个规模为 $1$、从城市 $3$ 出发的旅行团可到达城市 $1$、$2$、$3$、$4$ 和 $5$。因此，他们能到达的最大愉悦值为 $3$。若该旅行团选择前往城市 $4$，Omkar 每辆车需支付 $8$ 的费用，这是最大值。

对于第二个查询：一个规模为 $9$、从城市 $5$ 出发的旅行团仅能到达城市 $5$。因此，其可达的最大愉悦值仍为 $3$，而 Omkar 每辆车需支付的费用为 $0$。

对于第三个查询：一个规模为 $6$、从城市 $2$ 出发的旅行团可到达城市 $2$ 和 $4$。其可达的最大愉悦值仍为 $3$。若该旅行团选择前往城市 $4$，Omkar 每辆车需支付 $2$ 的费用，这是最大值。

第二个样例的地图如下所示：

对于第一个查询：一个规模为 $5$、从城市 $1$ 出发的旅行团仅能到达城市 $1$。因此，其最大愉悦值为 $1$，而 Omkar 每辆车需支付的费用为 $0$。

对于第二个查询：一个规模为 $4$、从城市 $1$ 出发的旅行团可到达城市 $1$ 和 $2$。因此，其最大愉悦值为 $2$，而 Omkar 每辆车需支付 $1$ 的费用。

对于第三个查询：一个规模为 $3$、从城市 $1$ 出发的旅行团可到达城市 $1$、$2$ 和 $3$。因此，其最大愉悦值为 $3$，而 Omkar 每辆车需支付 $1$ 的费用。

对于第四个查询：一个规模为 $2$、从城市 $1$ 出发的旅行团可到达城市 $1$、$2$、$3$ 和 $4$。因此，其最大愉悦值为 $4$，而 Omkar 每辆车需支付 $1$ 的费用。

对于第五个查询：一个规模为 $1$、从城市 $1$ 出发的旅行团可到达城市 $1$、$2$、$3$、$4$ 和 $5$。因此，其最大愉悦值为 $5$，而 Omkar 每辆车需支付 $1$ 的费用。