Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

J. Purchasing Cereal
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Larry, a cereal connoisseur, is traveling around the country CerealLand!

CerealLand consists of $$$n$$$ different cities, and Larry is currently at city $$$1$$$. Larry wants to purchase CerealLand's famed cereal.

At city $$$i$$$ ($$$1 \le i \le n$$$), you can buy a box of cereal for $$$c_i$$$ dollars.

There is a system of $$$n-1$$$ directed flights such that Larry can fly from city $$$1$$$ to any other city via a certain set of flights. Each flight has a cost, and the cost to fly flight $$$i$$$ ($$$1 \le i \le n-1$$$) is $$$b_i$$$.

However, each flight charges more for luggage, so to go on a flight Larry will also have to pay an additional $$$a_i \cdot x^2$$$ dollars, where $$$x$$$ is the number of cereal boxes Larry has purchased already.

Larry has $$$q$$$ queries for you, each query asking for the minimum amount of money it takes to go from city $$$1$$$ to city $$$v$$$ while purchasing $$$p$$$ boxes of cereal.

Input

The first line of input contains two integers, $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 2 \cdot 10^5$$$).

On the next line there are $$$n$$$ integers, $$$c_1$$$ ... $$$c_n$$$ ($$$1 \le c_i \le 10^9$$$).

The next $$$n-1$$$ lines contain information on the flights. The $$$i$$$-th line will have four integers, $$$u_i$$$, $$$v_i$$$, $$$a_i$$$, and $$$b_i$$$ ($$$1 \le u_i, v_i \le n, 1 \le a_i, b_i \le 10^9$$$), meaning there is a flight from city $$$u_i$$$ to city $$$v_i$$$ that costs $$$a_i \cdot x^2+b_i$$$ dollars, if $$$x$$$ is the number of cereal boxes Larry has already bought.

Finally the next $$$q$$$ lines describe the queries. Each query will take the form of two integers, $$$v$$$ and $$$p$$$ ($$$1 \le v \le n, 1 \le p \le 10^9$$$).

Example
Input
5 2
1 2 3 4 5
1 2 1 2
1 3 1 3
2 4 1 1
3 5 1 1
4 1
5 100
Output
6
502
Note

In the first query Larry can buy a box of cereal at city $$$1$$$, spending $$$1$$$ dollar. His flight to city $$$2$$$ will then cost $$$1 \cdot 1 + 2 = 3$$$ dollars, and his flight from city $$$2$$$ to city $$$4$$$ will cost $$$1 \cdot 1 + 1 = 2$$$ dollars, meaning he spends $$$6$$$ dollars total. It can be shown there is no better cost.

Problem Credits: Larry Xing