给定一棵有N个结点的树（N<=100000)，每个结点上有一个点权，每条边上有一个边权，再给一个数M（M<=100000)，表示有M个询问,每个询问形如a,b，表示询问树上结点a,到结点b,的路径上的所有点权的最大公约数的值，和路径上所有边权的最小值。点权和边权均是小于10^9的正整数。
输入第一行3个数，N，M，S，分别表示点数，询问数和树的根。
接下来N-1行，每行三个数，表示一条边和边权。
接下来一行N个数，分别表示每个点的点权。
输出M行，每行两个数，分别表示最大公约数，和边权的最小值(没有边输出$2^{31}-1$)。
输入
10 51 8 2 1 9170 3 1 9359 4 3 5706 5 2 6828 6 2 2996 7 1 5437 8 5 3903 9 5 2383 10 4 9719 46656 93312 41472 5832 9216 23328 108 1296 2592 2916 7 9 10 8 10 9 1 7 1 9 9 1 1 1 4 3 3 5 1 7 3 5 2 5 9 4 6 3 1 9 7 1 1 4 2 3 1 1 6 5 1 1 5 1 8 10 2 6 2 9 7 7 1 1 3 1 7 7 6 3 1 5 1 9 3 5 3 3 1 7 7 5 2 1 2 7 1 1 2 9 3 3 2 1 6 10 9 5 1 1 9 10 3 5 7 7 1 7 6 9 3 9输出：
36 2383 36 3903 36 2383 108 5437 288 2383 288 2383 46656 2147483647 648 5706 576 6828 108 5437 576 6828 1152 6828 72 2383 2592 2996 288 2383 108 5437 648 5706 5184 9170 46656 2147483647 288 2996 46656 2147483647 576 6828 36 3903 23328 2996 288 2383 108 2147483647 46656 2147483647 5184 9359 108 2147483647 2592 2996 576 6828 288 2383 576 6828 41472 2147483647 108 5437 36 5437 46656 9170 108 5437 46656 2147483647 288 2383 41472 2147483647 46656 9170 324 2996 288 2383 46656 2147483647 36 2383 576 6828 108 2147483647 108 5437 288 2383 288 2383