Десантна операція

Limits: 3 sec., 256 MiB

Українські війська продовжують активний контрнаступ! Наші десантники щодня планують нові атакувальні операції.

Зараз під контролем ворога знаходиться \(n\) сіл, які з’єднанні \((n-1)\)-ою дорогами довжиною 1 кілометр так, що з кожного села можна дістатися до будь-якого іншого (можливо через інші села). У \(i\)-тому селі є \(a_i\) окупантів. Село з номером один знаходиться найзахідніше, усі села, що безпосередньо з’єднані з ним, знаходяться трішки східніше, ті, що з’єднані з ними (окрім села з номером 1) ще східніше і так далі.

Десант розглядає \(q\) варіантів наступної атаки. \(і\)-й варіант передбачає висадку у селі з номером \(v_i\) та швидку нейтралізацію усіх противників у селах, що знаходяться на відстані не більшій ніж \(d_i\) кілометрів від місця висадки. Зауважте, що наш десант рухається лише вперед, а тому він нейтралізовує противників лише у селах, що знаходяться східніше від місця висадки. Допоможіть знайти точне число нейтралізованих противників для кожного з варіантів атаки.

Input

У першому рядку задано два цілих числа \(n\) та \(q\) — кількість сіл та кількість варіантів атаки.

У другому рядку задано \(n\) цілих чисел \(a_i\) — кількість окупантів в \(і\)-тому селі.

У наступних \(n-1\) рядках задано по два цілих числа \(u_i\) та \(w_i\) — дороги між селами.

У наступних \(q\) рядках задано по два цілих числа \(v_i\) і \(d_i\) — місце висадки та максимальна відстань, на якій нейтралізовуватиме противників десант.

Output

У \(q\) рядках виведіть по одному числу — кількості нейтралізованих противників для кожного з варіантів атаки.

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\).

Оцiнювання задачi складається iз наступних блокiв:

1 бал — приклад з умови,

4 бали — блок тестів у яких \(n, q\le 10^{3}\).

5 балів — блок тестів у яких \(d_i = n\).

15 балів — блок тестів без додаткових обмежень.

Бали за блок ви отримаєте, лише якщо дасте правильну вiдповiдь на всi тести з блоку.

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

• відповідь на перший запит \(9\), бо десант нейтралізує ворогів у селах \(2,3,4,5\)

• відповідь на другий запит \(8\), бо десант нейтралізує ворогів у селах \(3,4,5,6\)

• відповідь на третій запит \(7\), бо десант нейтралізує ворогів у селах \(3,4,5\)

• відповідь на четвертий запит \(2\), бо десант нейтралізує ворогів у селі \(5\)