Thiết bị nghệ thuật tương tác "幻光留影" (tạm dịch: Ảnh ảo lưu quang) được trừu tượng hóa thành một cái cây gồm $n$ nút, mỗi nút đại diện cho một nút ảnh, nút $i$ ($1 \le i \le n$) có màu bộ lọc là $c_i$. Có tổng cộng $n-1$ chùm sáng kết nối các nút, được đánh số thứ tự từ $1$ đến $n-1$.

Trong quá trình khám phá quy luật, bạn đã ghi lại dữ liệu của $m$ lần kiểm tra hiệu ứng động. Với mỗi lần kiểm tra, bạn chỉ định một khoảng số hiệu chùm sáng $[l, r]$. Giả sử tại thời điểm đó chỉ các chùm sáng có số hiệu nằm trong khoảng này được kích hoạt (các chùm sáng khác nằm ngoài khoảng này bị ngắt kết nối), mạng lưới ảnh ban đầu sẽ bị chia cắt thành nhiều thành phần liên thông độc lập.

Để phân tích sâu hơn những thay đổi này, với mỗi lần kiểm tra, bạn cần tính toán: tổng số lượng các loại bộ lọc có thể nhìn thấy được (tức là các loại màu bộ lọc xuất hiện với số lần lẻ) trong tất cả các thành phần liên thông.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương $n, m$ ($1 \le n \le 3 \times 10^5, 1 \le m \le 10^6$), lần lượt là số lượng nút ảnh và số lần kiểm tra.
• Dòng thứ hai chứa $n$ số nguyên dương $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), lần lượt là màu bộ lọc của mỗi nút ảnh.
• $n-1$ dòng tiếp theo, dòng thứ $i$ ($1 \le i \le n-1$) chứa hai số nguyên dương $u_i, v_i$ ($1 \le u_i, v_i \le n$), biểu thị hai nút được kết nối bởi chùm sáng số hiệu $i$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $l, r$ ($1 \le l \le r \le n-1$), biểu thị khoảng số hiệu chùm sáng của một lần kiểm tra.

Dữ liệu ra

• Xuất ra $m$ dòng, mỗi dòng một số nguyên không âm, lần lượt là tổng số lượng các loại bộ lọc có thể nhìn thấy được trong tất cả các thành phần liên thông độc lập của mỗi lần kiểm tra.

Ví dụ

Dữ liệu vào 1

12 13
2 4 1 2 3 4 2 4 3 3 3 6
3 5
9 1
5 11
4 9
1 12
2 1
10 8
11 10
8 4
6 11
7 6
1 3
2 2
6 6
9 11
6 11
1 4
8 10
1 11
5 10
4 7
1 10
6 8
11 11

Dữ liệu ra 1

10
12
12
12
6
8
10
4
8
12
4
10
12