Stipa i njegova proizvodnja ulja je stvorila velike profite i omogućila dodatni razvoj tvornice i opreme. Nakon uspješne modernizacije prve trake, Stipa je otvorio ogroman logistički centar za distribuciju ulja. Uljara se sada sastoji od \(n\) postaja koje su međusobno povezane transportnim trakama tako da tvore stablo (povezani graf bez ciklusa). Svaka postaja \(i\) ima svoj jedinstveni identifikacijski broj \(a_i\).

Nažalost Stipa nije pravilno prijavio financijsko stanje uljare pa sada podliježe novim pravilima proizvodnje. Inspektori podnose \(z\) zahtjeva, a za svaki zahtjev Stipa mora dokazati ispravnost poslovanja u realnom vremenu.

Pravila inspekcije

Za svaki zahtjev, inspektor odabire dvije postaje, \(u\) i \(v\), te jedan kontrolni broj \(k\). Stipa mora odgovoriti na sljedeće pitanje: Je li moguće odabrati podskup postaja koje se nalaze na najkraćem putu između \(u\) i \(v\) tako da je XOR suma njihovih identifikacijskih brojeva jednaka \(k\)?

Napomena: Podskup može sadržavati i samo jednu postaju s puta, a ako je \(k=0\), odgovor je uvijek potvrdan (odabirom praznog podskupa).

Ulazni podatci

U prvom je retku cijeli broj \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — broj postaja u logističkom centru.

U drugom je retku \(n\) cijelih brojeva \(a_1, a_2, \dots, a_n\) (\(0 \le a_i < 2^{20}\)) — identifikacijski kodovi svake postaje.

• Sljedećih \(n-1\) redova sadrži po dva cijela broja \(c\) i \(d\), koji označavaju da postoji transportna traka između postaja \(c\) i \(d\).
• U sljedećem je retku cijeli broj \(z\) (\(1 \le z \le 2 \cdot 10^5\)) — broj inspekcijskih upita.
• Svaki od sljedećih \(z\) redova sadrži tri cijela broja \(u\), \(v\) i \(k\) (\(1 \le u, v \le n\), \(0 \le k < 2^{20}\)).

Podzadatci

Izlazni podatci

Za svaki upit ispišite DA ako je moguće dobiti traženu XOR sumu \(k\) od postaja na putu, a NE u suprotnom.

Ulaz primjera 1

5
1 2 3 4 5
1 2
1 3
2 4
2 5
3
4 5 1
4 5 7
3 4 10

Izlaz primjera 1

DA
DA
NE

Objašnjenje primjera 1

1. Upit: 4 5 1 (Put: 4 → 2 → 5)

• Dostupni kodovi na putu: \(\{a_4, a_2, a_5\} = \{4, 2, 5\}\).
• XOR kombinacija: \(4 \oplus 5 = 1\).
• Odgovor: DA

2. Upit: 4 5 7 (Put: 4 → 2 → 5)

• Dostupni kodovi na putu: \(\{a_4, a_2, a_5\} = \{4, 2, 5\}\).
• XOR kombinacija: \(2 \oplus 5 = 7\).
• Odgovor: DA

3. Upit: 3 4 10 (Put: 3 → 1 → 2 → 4)

• Dostupni kodovi na putu: \(\{a_3, a_1, a_2, a_4\} = \{3, 1, 2, 4\}\).
• Ne postoji podskup koji u XOR sumi daje 10.
• Odgovor: NE