Đất nước HNAms gồm ~n~ thành phố được đánh số từ ~1~ tới ~n~. Đất nước HNAms rất thích bóng đá, ở thành phố thứ ~i~ có số sân vận động là ~a_i~. Do một vài chính sách đặc biệt của Bộ Thể Thao mà số sân vận động của các thành phố là không quá ~m~. Các thành phố của HNAms cũng có ~n - 1~ con đường hai chiều để kết nối các thành phố lại. Con đường thứ ~i~ sẽ nối hai thành phố ~u_i~ và ~v_i~, đảm bảo rằng mọi cặp thành phố đều có lộ trình di chuyển tới nhau. Nói cách khác, HNAms có thể ví như một đồ thị dạng cây.

Bộ Xây Dựng đã tạo ra một phương pháp để đánh giá độ hiệu quả trong giao thông của một tổ hợp các thành phố:

• Giả sử ta có một tập thành phố ~u_1, u_2, \dots, u_k~, độ hiệu quả trong giao thông của tập hợp thành phố này chính bằng đường đi ngắn nhất nếu có thể xuất phát tại một thành phố tùy ý và đi qua hết các thành phố trong tập. Đường đi ở HNAms được tính theo số con đường mà lộ trình này đi qua.

Đối với tập thành phố rỗng hoặc có số thành phố bằng ~1~, độ hiệu quả được đánh giá là bằng ~0~.

Vào ngày thứ ~x~ (~1 \le x \le m~), các trận đấu bóng đá sẽ được tổ chức tại các thành phố có số sân vận động chia hết cho ~x~.

Yêu cầu: Đối với mỗi ngày thứ ~x~ (~1 \le x \le m~), hãy đánh giá độ hiệu quả của tập thành phố ~[u_1, u_2, \dots, u_k]~ thỏa mãn ~x \mid a_{u_i}~ (~\forall 1 \le i \le k~).

Input

• Dòng thứ nhất chứa hai số nguyên dương ~n, m~ (~1 \le n \le 2 \times 10^5, 1 \le m \le 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương, số thứ ~i~ là ~a_i~, miêu tả số sân vận động ở thành phố ~i~ (~1 \le a_i \le m~).
• ~n - 1~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~u_i~ và ~v_i~ miêu tả con đường hai chiều nối từ thành phố ~u_i~ tới thành phố ~v_i~.

Output

• In ra ~m~ dòng, dòng thứ ~x~ là độ hiệu quả của tổ hợp thành phố được sử dụng trong ngày thứ ~x~.

Sample Input 1

5 1
1 1 1 1 1
1 3 
3 2
1 4
3 5

Sample Output 1

5

Sample Input 2

6 5
2 2 3 4 3 1
1 3 
3 2
3 4
1 5
1 6

Sample Output 2

7
4
2
0
0