Omkar and Tours

Description:

Input:

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.

Output:

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.

Sample Input:

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

Sample Output:

3 8
3 0
3 2

Sample Input:

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

Sample Output:

1 0
2 1
3 1
4 1
5 1

Sample Input:

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

Sample Output:

2 8
2 8
2 3
2 1
1 0

Note:

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.