Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p_i\) \(x_i\): Thay giá trị ở vị trí \(p_i\) thành \(x_i\) (tức gán \(A_{p_i} = x_i\)).
• \(2\) \(u_i\) \(v_i\): Đếm số phần tử phân biệt và tính tổng các giá trị phân biệt trong đoạn từ \(u_i\) tới \(v_i\).

Yêu cầu: Thực hiện tất cả \(Q\) thao tác, và in ra \(2\) kết quả của thao tác loại \(2\).

Input

Gồm \(Q+2\) dòng:

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên dương \(p_i\), và \(x_i\) \((1 \leq p_i\leq N\), \(1 \leq x_i \leq 10^9)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra \(2\) kết quả lần lượt là số phần tử phân biệt và tính tổng các giá trị phân biệt trong đoạn từ \(u\) tới \(v\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(30\)% số điểm có \(N \leq 2.10^3\), \(Q \leq 2.10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 5.10^4\), \(Q \leq 5.10^4\), chỉ có các thao tác loại \(2\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \leq 5.10^4\), \(Q \leq 5.10^4\).

Example

 3 3
1 2 3
2 1 3
1 3 2
2 2 3 

3 6
1 2