You are given a tree consisting of n vertices. Let's denote the function LCM(x,y) Least Common Multiple of (x,y) Also let's denote dist(x,y) as the number of vertices on the simple path between vertices x and y In path x to y, Neighbor verticles (a,b) all LCM(a,b)<a*b Input n number of verticles The second line contains n integers a1, a2, ..., an (1≤ai≤2⋅105) — the numbers written on vertices. Then n−1 lines follow, each containing two integers x and y (1≤x,y≤n,x≠y) denoting an edge connecting vertex x with vertex y. It is guaranteed that these edges form a tree.