Thành phố bí ẩn

Bạn đang làm việc với một mạng lưới các thành phố bí ẩn, mỗi thành phố được tô bằng một màu nhất định. Ban đầu, tất cả các thành phố hoàn toàn bị cô lập, chưa có con đường nào nối giữa chúng. Tuy nhiên, theo thời gian, bạn có thể xây dựng các con đường để kết nối các thành phố và khám phá thêm thông tin về chúng.

Bạn được cung cấp \(q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• Loại 1 \((1 \ u \ v)\): Xây dựng một con đường mới giữa hai thành phố \(u\) và \(v\), giúp mở rộng mạng lưới giao thông.

• Loại 2 \((2 \ u \ c)\): Điều tra thành phố \(u\) để tìm ra số lượng thành phố có màu \(c\) trong thành phần liên thông chứa \(u\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\) \((1 \leq n \leq 10^5, 1 \leq q \leq 2 \times 10^5)\) --- số thành phố và số truy vấn.

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq n)\), mỗi số mô tả màu sắc của thành phố thứ \(i\).

• \(q\) dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại:

• Truy vấn loại \(1\) có dạng \(1 \ u \ v\) \((1 \leq u, v \leq n, u \neq v)\), biểu thị việc xây dựng một con đường giữa \(u\) và \(v\).

• Truy vấn loại \(2\) có dạng \(2 \ u \ c\) \((1 \leq u, c \leq n)\), yêu cầu đếm số lượng thành phố có màu \(c\) trong thành phần liên thông chứa \(u\).

Output

• Với mỗi truy vấn loại \(2\), in ra một số nguyên trên một dòng duy nhất --- số lượng thành phố có màu \(c\) trong thành phần liên thông chứa \(u\) tại thời điểm truy vấn.

Example

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

1
0
3
1

Scoring

• \(1 \leq n \leq 10^5\)
• \(1 \leq q \leq 2 \times 10^5\)
• \(1 \leq a_i \leq n\)
• \(1 \leq u, v, c \leq n\)