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

Limits: 2 sec., 256 MiB

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

Однією з тем були «Комп’ютерні мережі». Зеник добре в ній орієнтується. Він з упевненістю може сказати, що 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\), то вважаємо, що час пересилання дорівнює нулю.

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

Input

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

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

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

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

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

Output

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

Constraints

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

Samples

Input (stdin) сopy	Output (stdout) сopy
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

Notes

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