给定一棵 n 个节点的树，第 i 号节点的权值为 a_i。

现在给出 q 次询问：回答树上任意两点之间路径上的权值，其中出现次数恰好为素数的权值，这些权值的异或和为多少。

输入格式 第一行有一个整数 N，表示节点个数。

接下来一行，有 N 个整数 a_i。

接下来 N-1 行，每行有两个整数 u_i,v_i ，表示树上的一条边。

接下来一行有一个整数 q，表示询问次数。

接下来 q 行，每行有两个整数 x_i,y_i 。

输出格式 对于每次询问输出一行，一个整数，表示满足条件的数值的异或和。

样例输入

6 1 2 3 3 3 2 1 2 1 3 2 4 2 5 3 6 4 1 6 2 6 4 6 3 5

样例输出

0 2 1 3 N,Q小于等于5*10&4