Dãy số tổng k

Cho dãy \(a\) gồm \(n\) số \(1\) và \(-1\), các phần tử được đánh số từ \(1\) đến \(n\).

Cho \(q\) thao tác gồm một trong hai dạng:

• Thao tác loại \(1\) có dạng "\(1\) \(i\) \(v\)" (\(1 \le i \le n\) và \(v \in \{1,-1\}\)), thao tác này sẽ gán \(a_i = v\).

• Thao tác loại \(2\) có dạng "\(2\) \(l\) \(r\) \(k\)" (\(1 \le l \le r\ le n\) và \(|k| \le n\)), thao tác này cần tìm hai số nguyên \(x,y\) thỏa mãn \(l \le x \le y \le r\) và tổng các phần tử từ \(x\) đến \(y\) của dãy \(a\) đúng bằng \(k\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n,q\) (\(1 \le n,q \le 10^5\)).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\) (\(a_i \in \{1,-1\}\)).

• Mỗi dòng trong \(q\) dòng tiếp theo chứa một thao tác theo định dạng như trên đề bài.

Output

• Với mỗi thao tác loại \(2\), in ra hai số \(x,y\) bất kì thỏa mãn điều kiện. Nếu không tồn tại đáp án, in ra "-1".

Example

5 8
1 -1 -1 1 1
2 1 4 0
2 1 4 -3
1 4 -1
2 1 5 -3
1 3 1
1 1 -1
1 5 -1
2 1 5 -3

1 2
-1
2 4
1 5

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(k = 0\) với mọi thao tác loại \(2\).

• Subtask \(2\) (\(20\%\) số điểm): \(n,q \le 5000\).

• Subtask \(3\) (\(30\%\) số điểm): không có thao tác loại \(1\).

• Subtask \(4\) (\(30\%\) số điểm): không có ràng buộc gì thêm.