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

Cho \(𝑞\) thao tác thuộc một trong hai dạng:

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

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

Dữ liệu vào

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

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

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

Dữ liệu ra

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

Subtask 1 (20 điểm): 𝑘 = 0 với mọi thao tác loại 2;

Subtask 2 (20 điểm): \(n, q \le 5000\);

Subtask 3 (30 điểm): Không có thao tác loại 1;

Subtask 4 (30 điểm): Không có ràng buộc gì thêm.

Input

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

Output

3 4
-1
2 4
1 5