给定一棵 个节点的树，每个点有一个权值。有 个询问，每次给你 ，你需要回答 和 这两个节点间第 小的点权。
其中 是上一个询问的答案，定义其初始为 ，即第一个询问的 是明文。
第一行两个整数 。
第二行有 个整数，其中第 个整数表示点 的权值。
后面 行每行两个整数 ，表示点 到点 有一条边。
最后 行每行两个整数 ，表示一组询问。
行，每行一个正整数表示每个询问的答案。
样例输入
8 5 105 2 9 3 8 5 7 7 1 2 1 3 1 4 3 5 3 6 3 7 4 8 2 5 1 0 5 2 10 5 3 11 5 4 110 8 2
样例输出
2 8 9 105 7
对于 的数据，，点权在 之间。