E. Employees Bonus
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a large global corporation, Acme Corp, with $$$N$$$ employees, each employee has a clearly defined hierarchy in the company's organizational chart. Each employee is the head of a department and may have a variable number of subordinates working directly or indirectly under their supervision.

Acme Corp has a peculiar way of distributing bonuses: when an employee receives a bonus intended for their department, they divide it evenly among all employees who are directly or indirectly under their command (including themselves in the distribution). If the bonus amount does not divide evenly among all subordinates, the department head keeps the remainder.

The company has received $$$Q$$$ bonuses that will be distributed among the employees according to the aforementioned policy.

Each employee has a specific amount of money that they perceive as financial success.

Your task is to determine, for each employee, the first bonus (i.e., the order number of the bonus in the sequence of $$$Q$$$ bonuses) at which they achieved financial success.

Input

The input consists of several lines:

The first line contains two integers, $$$N$$$ and $$$Q$$$ $$$(1 \leq N \leq 10^5; 1 \leq Q \leq 10^5)$$$, the number of employees in the company and the number of bonuses respectively.

The second line contains N integers, $$$a_1$$$, $$$a_2$$$, ..., $$$a_N$$$ $$$(1 \leq a_i \leq 10^9)$$$, where $$$a_i$$$ represents the amount of money that the i-th employee perceives as financial success.

The next N-1 lines each contain two integers, u and v $$$(1 \leq u, v \leq N; u \neq v)$$$, which represent that employee v is a direct subordinate of employee u.

The next Q lines each contain two integers, x and b $$$(1 \leq x \leq N; 1 \leq b \leq 10^9)$$$, where x represents the employee to whom the bonus is given and b the amount of the bonus.

Output

Print N lines, where the i-th line contains an integer indicating the first bonus at which the i-th employee achieved their financial success. If the i-th employee does not achieve their financial success, print -1.

Example
Input
5 3
100 200 300 400 500
1 2
1 3
2 4
2 5
1 1000
2 1500
3 2000
Output
1
1
3
2
2