CF1902F Trees and XOR Queries Again

You 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.

The 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 $ ).

For 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.