Ngày nay, việc sử dụng các phần mềm ứng dụng trở nên rất phổ biến. Người dùng thường có xu hướng sử dụng tiếp các ứng dụng có liên quan với ứng dụng mà họ vừa dùng.

Một công ty cung cấp ứng dụng trực tuyến đang theo dõi \(N\) ứng dụng, được đánh số từ \(1\) đến \(N\).

Ứng dụng thứ \(i\) hiện có số lượt tải là \(a_i\).

Ban đầu, chưa có thông tin nào về việc hai ứng dụng có liên quan với nhau.

Có \(Q\) truy vấn thuộc hai loại:

• 1 u v: ghi nhận rằng có người dùng đã tải cả ứng dụng \(u\) và ứng dụng \(v\). Khi đó, hai ứng dụng này được xem là có liên quan. Nếu ứng dụng \(x\) liên quan với \(y\), và \(y\) liên quan với \(z\), thì \(x\) cũng được xem là liên quan với \(z\).
• 2 u c: hỏi có bao nhiêu ứng dụng có đúng \(c\) lượt tải và liên quan với ứng dụng \(u\).

Nói cách khác, với truy vấn loại 2 u c, cần đếm số ứng dụng nằm trong cùng nhóm liên quan với \(u\) và có giá trị lượt tải bằng \(c\).

Yêu cầu

Hãy thực hiện \(Q\) truy vấn và in kết quả cho mỗi truy vấn loại \(2\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N \le 10^5, 1 \le Q \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le N\)).
• \(Q\) dòng tiếp theo, mỗi dòng là một trong hai dạng:
  • 1 u v (\(1 \le u, v \le N, u \ne v\)).
  • 2 u c (\(1 \le u, c \le N\)).

Output

• Với mỗi truy vấn loại \(2\), in ra một số nguyên trên một dòng là kết quả tương ứng.

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