F. Trees and XOR Queries Againtime limit per test6.5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou are given a tree consisting of n vertices. There is an integer written on each vertex; the i-th vertex has integer a_i written on it.You have to process q queries. The i-th query consists of three integers x_i, y_i and k_i. For this query, you have to answer if it is possible to choose a set of vertices v_1, v_2, \dots, v_m (possibly empty) such that:  every vertex v_j is on the simple path between x_i and y_i (endpoints can be used as well);  a_{v_1} \oplus a_{v_2} \oplus \dots \oplus a_{v_m} = k_i, where \oplus denotes the bitwise XOR operator. InputThe first line contains one integer n (2 \le n \le 2 \cdot 10^5).The second line contains n integers a_1, a_2, \dots, a_n (0 \le a_i \le 2^{20} - 1).Then n-1 lines follow. Each of them contains two integers u and v (1 \le u, v \le n; u \ne v) denoting an edge of the tree.The next line contains one integer q (1 \le q \le 2 \cdot 10^5) — the number of queries.Then q lines follow. The i-th of them contains three integers x_i, y_i and k_i (1 \le x_i, y_i \le n; 0 \le k_i \le 2^{20} - 1).OutputFor each query, print YES if it is possible to form a set of vertices meeting the constraints. Otherwise, print NO.You can print each letter in any case.ExampleInput
40 1 2 102 13 24 283 3 03 4 13 4 71 3 11 3 21 3 101 4 101 4 11Output
YES
YES
NO
YES
YES
NO
YES
YES

40 1 2 102 13 24 283 3 03 4 13 4 71 3 11 3 21 3 101 4 101 4 11
YES YES NO YES YES NO YES YES 
['data structures', 'dfs and similar', 'divide and conquer', 'graphs', 'implementation', 'math', 'trees', '*2400']