#P986E. Prince's Problem
Prince's Problem
Description
Let the main characters of this problem be personages from some recent movie. New Avengers seem to make a lot of buzz. I didn't watch any part of the franchise and don't know its heroes well, but it won't stop me from using them in this problem statement. So, Thanos and Dr. Strange are doing their superhero and supervillain stuff, but then suddenly they stumble across a regular competitive programming problem.
You are given a tree with vertices.
In each vertex there is positive integer .
You have to answer queries.
Each query has a from .
You have to calculate , where is a set of vertices on path from to . In other words, you are to calculate the product of for all vertices on the path from to . As it might be large, compute it modulo . Here denotes the greatest common divisor of and .
Note that the numbers in vertices do not change after queries.
I suppose that you are more interested in superhero business of Thanos and Dr. Strange than in them solving the problem. So you are invited to solve this problem instead of them.
In the first line of input there is one integer () — the size of the tree.
In the next lines the edges of the tree are described. The -th edge is described with two integers and () and it connects the vertices and . It is guaranteed that graph with these edges is a tree.
In the next line there are integers ().
In the next line there is one integer () — the number of queries.
And in the next lines the queries are described. Each query is described with three integers , and (, ).
Print numbers — the answers to the queries in the order they are given in the input. Print each answer modulo . Print each number on a separate line.
Input
In the first line of input there is one integer () — the size of the tree.
In the next lines the edges of the tree are described. The -th edge is described with two integers and () and it connects the vertices and . It is guaranteed that graph with these edges is a tree.
In the next line there are integers ().
In the next line there is one integer () — the number of queries.
And in the next lines the queries are described. Each query is described with three integers , and (, ).
Output
Print numbers — the answers to the queries in the order they are given in the input. Print each answer modulo . Print each number on a separate line.