Козак Вус і країна

Козак Вус нещодавно потрапив до дуже цікавої країни. У країні $n$ міст, причому місто під номером $1$ "— столиця країни. Між цими містами є рівно $n-1$ дорога, дорога під номером $i$ сполучає міста $v_i$ та $u_i$. Також відомо, що з кожного міста можна дістатися будь-якого іншого, рухаючись лише цими дорогами.

Кожне місто є центром деякого регіону. Регіоном називають множину всіх вершин $v$ таких, що будь-який шлях між столицею та $v$ проходить через центр регіону (одне місто може належати декільком регіонам).

У місті під номером $i$ проживають рівно $a_i$ громадян, причому всі $a_i$ різні. Вус дізнався, що уряд країни має право виконувати операцію «переселення» "— вибрати пару міст $x$ і $y$ та переселити всіх жителів міста $x$ в місто $y$, а всіх жителів міста $y$ "— в місто $x$. Наш Козак може не більше $k$ разів попросити уряд виконати «переселення». Пару міст при «переселенні» також вибирає Вус.

Кожного дня Козак вибирає собі деяке число, яке стає його улюбленим. Якщо $x$ "— улюблене число Вуса, то він вважає регіон «гарним», якщо можна здійснити не більше $k$ «переселень» таким чином, щоб медіана кількостей населення міст регіону була рівна $x$. Тобто, якщо виписати кількості населення міст регіону у порядку зростання, то значення елементу, що знаходиться посередині (медіана) отриманої послідовності, повинно бути рівне $x$. Якщо кількість міст регіону парна, то з двох елементів посередині, рівним $x$ повинно бути значення елементу, що стоїть правіше (тобто більше). Наприклад, медіаною множини $\{1,10,2,8,4\}$ є число $4$, а медіаною множини $\{1,2,10,8\}$ є $8$.

Козак буде перебувати в цій країні ще рівно $m$ днів. Кожного ранку він буде повідомлювати своє улюблене число, а ви повинні будете сказати йому кількість «гарних» регіонів.

Вхідні дані

Перший рядок містить три цілі числа $n$, $k$ та $g$ ($1\le n\le 10^5$, $0\le k\le n$, $0\le g\le 11$) "— кількість міст в країні, максимальну кількість «переселень» та номер блоку, до якого належить тест відповідно.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$), де $a_i$ "— кількість населення в місті $i$. Гарантується, що всі числа різні.

Кожен з наступних $n-1$ рядків містить по два цілі числа $v_i$ та $u_i$ ($1\le v_i,u_i\le n$) "— номери міст між якими є дорога.

Наступний рядок містить одне ціле число $m$ ($1\le m\le 10^5$) "— кількість днів, які Козак проживатиме у цікавій країні.

Наступний рядок містить $m$ цілих чисел $x_1,x_2,...,x_m$ ($1\le x_i\le 10^9$), де $x_i$ "— улюблене число Вуса в день $i$.

Вихідні дані

Виведіть $m$ цілих чисел "— кількості «гарних» регіонів у кожен з $m$ днів.

Приклади

Оцінювання

1. ($5$ балів) $n,m\le 10^3$, $k=0$.

2. ($12$ балів) $n,m\le 10^5$, $k=0$.

3. ($5$ балів) $n,m\le 10^3$, між містами $i$ та $i+1$ є дорога ($1\le i\le n-1$).

4. ($9$ балів) $n,m\le 10^5$, між містами $i$ та $i+1$ є дорога ($1\le i\le n-1$).

5. ($5$ балів) $n,m\le 10^3$, $k=n$.

6. ($11$ балів) $n,m\le 10^5$, $k=n$.

7. ($8$ балів) $n,m\le 10^2$.

8. ($9$ балів) $n,m\le 10^3$.

9. ($11$ балів) $n\le 10^5$, $m\le 500$.

10. ($25$ балів) $n,m\le 10^5$.