Cho mảng số nguyên \(n\) phần tử \(a_1, a_2, ..., a_n\), bảng sẽ được biến đổi sau mỗi thời điểm như sau: với mỗi số \(a_i\) ta sẽ đếm xem có bao nhiêu giá trị khác nhau trong mảng \(a\) mà giá trị lớn hơn \(a_i\) và tăng \(a_i\) lên đúng bằng số lượng giá trị khác nhau đó. Tại một thời điểm tất cả các phần tử đều biến đổi như trên.

Hãy trả lời các truy vấn trong 3 loại sau:

• \(1\ k\): đến thời điểm \(k\) thì có bao nhiêu giá trị khác nhau trong mảng
• \(2\ k\): tổng số giá trị tăng lên của tất cả các phẩn tử đến thời điểm \(k\) là bao nhiêu
• \(3\ k\ i\): giá trị của phần tử \(a_i\) đến thời điểm \(k\) bằng bao nhiêu

Input

• Dòng đầu chứa số \(n, q\) (\(1\le n, q\le 3\cdot 10^5\))

• Dòng thứ hai chứa \(n\) số \(a_i\) (\(1\le a_i \le 10^{12}\))

• \(q\) dòng tiếp theo mỗi dòng mô tả một trong ba truy vấn trên (\(0\le k\le 10^{12}, 1\le i\le n\))

Output

• Ghi ra kết quả trên \(q\) dòng.

Example

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

3
2
1
8
11
4

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

5
2
10
4