Truy vấn đơn giản

Trong một buổi phỏng vấn tuyển dụng, FullHouse Dev được đưa ra một bài toán về xử lý truy vấn trong mảng dữ liệu. Đây là một tình huống thực tế mà công ty thường gặp khi phân tích dữ liệu kinh doanh.

Bài toán

Cho một mảng có kích thước \(n\) trong đó giá trị của các phần tử là \(0\) hoặc \(1\). Tất cả các phần tử của mảng được đánh số từ vị trí \(0\) đến \(n-1\). Bạn được cho một số truy vấn thuộc một trong hai loại sau:

• Loại \(0\): Tìm phần tử gần nhất bên trái và bên phải từ vị trí \(p\) trong mảng có giá trị \(1\).
• Loại \(1\): Thay đổi giá trị tại vị trí \(p\) thành \(1\) nếu giá trị trước đó là \(0\), ngược lại giữ nguyên.

Lưu ý quan trọng: Nếu không có vị trí nào có giá trị \(1\) ở bên trái của chỉ số trong truy vấn, in ra -1. Tương tự, nếu không có giá trị \(1\) ở bên phải, in ra -1.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) - số lượng phần tử trong mảng và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên mô tả mảng ban đầu.
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả loại truy vấn.

OUTPUT FORMAT:

• Với mỗi truy vấn loại \(0\), in ra hai số nguyên là vị trí của phần tử \(1\) gần nhất bên trái và bên phải, cách nhau bởi dấu cách.

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(1 \leq q \leq 10^5\)

Ví dụ

INPUT

7 4
1 0 0 0 1 0 1
0 1
0 5
1 2
0 2

OUTPUT

0 4
4 6
0 4

Giải thích

• Truy vấn đầu tiên là 0 1: Phần tử \(1\) gần nhất bên trái của vị trí 1 nằm ở vị trí 0, bên phải nằm ở vị trí 4.
• Truy vấn thứ hai là 0 5: Phần tử \(1\) gần nhất bên trái của vị trí 5 nằm ở vị trí 4, bên phải nằm ở vị trí 6.
• Truy vấn thứ ba là 1 2: Thay đổi giá trị tại vị trí 2 thành 1.
• Truy vấn thứ tư là 0 2: Phần tử \(1\) gần nhất bên trái của vị trí 2 nằm ở vị trí 0, bên phải nằm ở vị trí 4.