Запити між серверами

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

Зеник не розуміє, чому ще досі не запровадили ЗНО з інформатики. Він щиро сподівається, що наступного року його таки введуть. Тому Зеник вирішив почати готуватися вже зараз. Його вуйко Сергій працює в Міністерстві освіти і науки України й повідомив юнакові проєкт програми ЗНО з інформатики.

Однією з тем були «Комп’ютерні мережі». Зеник добре в ній орієнтується. Він з упевненістю може сказати, що HTTP — це мережевий протокол прикладного рівня, а TCP — транспортного. Ви, мабуть, також це знаєте. Ні?! Не знаєте? Що ж... Не хвилюйтеся, я теж не знав, поки мені Зеник не сказав.

Зеник розглядає мережу, що складається з \(n\) серверів, пронумерованих від 1 до \(n\). Цими серверами володіють \(m\) IT-компаній, пронумерованих від 1 до \(m\). \(i\)-ий сервер у мережі належить компанії \(c_i\).

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

Один сервер може надсилати іншому запити. Пересилання запиту між з’єднаними напряму серверами займає одну одиницю часу. Сервер, який прийняв запит, може переслати його сусідньому серверу. Якщо треба надіслати запит між серверами, що не мають прямого зв’язку, то пересилання відбувається найкоротшим шляхом у дереві.

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

Покажіть, що ви готові складати ЗНО з інформатики хоч уже. Дайте відповіді на Зеникові питання.

Вхідні дані

Перший рядок містить два цілих числа \(n\) і \(m\) — кількості серверів у мережі та IT-компаній, які ними володіють, відповідно.

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

Кожен з наступних \(n-1\) рядків містить два цілих числа \(u_i\) й \(v_i\) — номери серверів, що мають прямий зв’язок.

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

Наступні \(q\) рядків містять по три цілих числа \(x_i\), \(y_i\), \(t_i\) — номер компанії, яка хоче надіслати запит, номер сервера, куди його потрібно надіслати, та кількість одиниць часу, за які це треба зробити.

Вихідні дані

В одному рядку для кожного запиту виведіть 1, якщо компанія може надіслати запит, уклавшись у час, і 0 — якщо ні.

Обмеження

\(1 \le n \le 2 \cdot 10^4\),

\(1 \le c_i, x_i \le m \le 5\),

\(1 \le q \le 10^5\),

\(1 \le u_i, v_i, y_i \le n\),

\(0 \le t_i \le n - 1\),

кожна компанія володіє хоча б одним сервером,

для 10 тестів виконуються додаткові обмеження:

\(1 \le n, q \le 10^3\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 4 2 1 2 1 3 4 4 1 5 3 6 3 4 5 7 2 1 1 4 7 1 2 0 3 4 1 3 4 1 2 6 0 4 4 2 2 1 1 1 7 3	1000111

Примітки

У прикладі компанія 1 володіє серверами 2 та 4, компанія 2 — серверами 1 і 3, компанія 3 — сервером 5, компанія 4 — серверами 6 і 7.