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

Обмеження: 3 сек., 256 МіБ

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

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

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

Вхідні дані

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

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

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

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

Вихідні дані

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

Обмеження

$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 тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
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

Примітки

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

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

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

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