Amphibious Operation

Limits: 3 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Ukrainian troops continue their active counteroffensive! Our paratroopers plan new attacking operations every day.

Currently, \(n\) villages are under enemy control, connected by \((n-1)\) roads of length 1 kilometer such that every village can be reached from any other (possibly through other villages). The \(i\)-th village contains \(a_i\) occupiers. The village numbered one is located furthest west, all villages directly connected to it are located slightly further east, those connected to them (except for village number 1) are even further east, and so on.

The paratroopers are considering \(q\) options for the next attack. The \(i\)-th option involves landing in the village numbered \(v_i\) and quickly neutralizing all enemies in the villages that are at a distance of no more than \(d_i\) kilometers from the landing site. Note that our paratroopers only move forward, and therefore they neutralize enemies only in the villages located further east than the landing site. Help find the exact number of neutralized enemies for each of the attack options.

Input

The first line contains two integers \(n\) and \(q\) — the number of villages and the number of attack options.

The second line contains \(n\) integers \(a_i\) — the number of occupiers in the \(i\)-th village.

The next \(n-1\) lines contain two integers \(u_i\) and \(w_i\) — the roads between the villages.

The next \(q\) lines contain two integers \(v_i\) and \(d_i\) — the landing site and the maximum distance at which the paratroopers will neutralize enemies.

Output

In \(q\) lines, output one number each — the number of neutralized enemies for each attack option.

Constraints

\(1 \le n, q \le 10^{5}\),

\(1 \le a_i \le 10^{9}\),

\(1 \le u_i, w_i \le n\),

\(1 \le v_i, d_i \le n\).

Problem scoring consists of the following subtasks:

1 point — example from the statement,

4 points — a block of tests in which \(n, q\le 10^{3}\).

5 points — a block of tests in which \(d_i = n\).

15 points — a block of tests without additional constraints.

Points for a subtask will be awarded only if you give the correct answer to all tests in the subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 3 2 4 1 2 1 5 1 2 2 3 3 4 3 5 4 6 1 7 2 2 3 2 3 1 5 3	9 8 7 2

Notes

• the answer to the first query is \(9\), because the paratroopers neutralize enemies in villages \(2,3,4,5\)

• the answer to the second query is \(8\), because the paratroopers neutralize enemies in villages \(3,4,5,6\)

• the answer to the third query is \(7\), because the paratroopers neutralize enemies in villages \(3,4,5\)

• the answer to the fourth query is \(2\), because the paratroopers neutralize enemies in village \(5\)