Description

有一棵摩天大树，在树的每个分支节点 上都有一个整数，可否在树上找到这样一个链，以便链上所有整数的乘 积（$mod$ $10^6$ $+3$）都等于$k$ ？

Format

Input

输入包含几个测试用例。每个测试用例的第1行都包含两个 整数$N （1≤N ≤10^5 ）$和$k （0≤k <10^6 +3）$。接下来的一行包含$N$ 个 数字$vi （1≤v_i <10^6 +3）$，其中$v_i$ 表示节点$i$ 上的整数。然后是$N -1$ 行，每行都包含两个整数$x$、$y$ ，表示节点$x$ 和节点$y$ 之间的无向边。

Output

对每个测试用例，都单行输出两个整数$a$ 和$b （a <b ）$， 表示满足条件的链的两个端点。若存在多个解决方案，则输出字典顺序 最小的解决方案。若不存在解决方案，则输出“No solution”。

Samples

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

3 4
No solution