問題文
頂点数 n 和顶点 i (i = 1, ..., n) 是正整数 写入 a_i 。 回答 q问题。
每个问题由三个整数组成, j 第一个问题是
它由 x_j, v_j, w_j 给出。
树顶
写入到 v_j 它们的编号最大为 w_j 的最短路径的顶点处的数字 a_i 按顺序打印除 x_j 的余数。
换句话说,
到v_j 它们的编号最大为 w_j 的最短路径是
p_1, ..., p_k (頂点数 k , p_1 = v_j, p_k = w_j ),然后
((...((x_j % a_{p_1}) % a_{p_2}) ...) % a_{p_{k-1}} ) % a_{p_k} 输出。
但是 这是除以 x % y 表示 x 的 y 后取余数的运算。
入力
第一行是序列的长度 n 和问题数量 给出 q 。 第二行是一个数字序列 代表 a 代表 n 正整数以空格分隔。 继续 n-1 每行包含树边的端点。 b_i, c_i 用空格分隔。 继续 每个问题都在 q 行中给出。 每个问题由 3 个整数组成 x_j, v_j, w_j 用空格分隔。n q
a_1 ... a_n
b_1 c_1
:
b_{n-1} c_{n-1}
x_1 v_1 w_1
:
x_q v_q w_q
- 1 \leq n \leq 100000
- 1 \leq q \leq 100000
- 1 \leq a_i \leq 10^{9}
- 1 \leq b_i, c_i \leq n
- 0 \leq x_j \leq 10^{9}
- 1 \leq v_j, w_j \leq n
- 所有输入值均为整数
- 给定的图是一棵树
出力
输出是 第 q 行组成。 j 在线 一个整数,表示住在 j 将问题的答案打印为整数。
部分点
如果满足以下约束的数据集的所有答案都是正确的, 30 给出了点的部分点。
- 全部 i (1 \leq i \leq n-1) , b_i = i, c_i = i+1 ,即图是一条路径
- 全部 j (1 \leq j \leq q) , v_j \leq w_j 是
入力例1
5 2 8 6 4 3 2 1 2 2 3 3 4 4 5 15 1 5 15 2 5
出力例1
1 0图具有路径结构。 关于第一个问题, 15 % 8 = 7, 7 % 6 = 1, 1 % 4 = 1, 1 % 3 = 1, 1 % 2 = 1 答案是 1 。 关于第二个问题, 15 % 6 = 3, 3 % 4 = 3, 3 % 3 = 0, 0 % 2 = 0 答案是 0 。从
入力例2
8 5 18 29 52 64 4 59 89 15 1 2 1 3 1 4 2 5 3 6 3 7 4 8 99 6 7 102 5 8 15 2 6 84 7 8 19 1 1
出力例2
40 2 15 14 1