Problem Description
There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with N vertices, while each branch can be treated as a vertex). Today the students under the tree are considering a problem: Can we find such a chain on the tree so that the multiplication of all integers on the chain (mod 106 + 3) equals to K?
Can you help them in solving this problem?

Input
There are several test cases, please process till EOF.
Each test case starts with a line containing two integers N(1 <= N <= 105) and K(0 <=K < 106 + 3). The following line contains n numbers vi(1 <= vi < 106 + 3), where vi indicates the integer on vertex i. Then follows N – 1 lines. Each line contains two integers x and y, representing an undirected edge between vertex x and vertex y.

Output
For each test case, print a single line containing two integers a and b (where a < b), representing the two endpoints of the chain. If multiply solutions exist, please print the lexicographically smallest one. In case no solution exists, print “No solution”(without quotes) instead.

Sample Input
5 60 2 5 2 3 3 1 2 1 3 2 4 2 5 5 2 2 5 2 3 3 1 2 1 3 2 4 2 5

Sample Output
3 4 No solution

Hint

1. “please print the lexicographically smallest one.”是指: 先按照第一个数字的大小进行比较，若第一个数字大小相同，则按照第二个数字大小进行比较，依次类推。 2. 若出现栈溢出，推荐使用C++语言提交，并通过以下方式扩栈： #pragma comment(linker,”/STACK:102400000,102400000″)

Source