Truy vấn Đơn giản

Trong không khí Tết đến xuân về, FullHouse Dev được giao một bài toán thú vị về xử lý mảng và truy vấn. Với tinh thần làm việc hăng say để đón một năm mới thật tốt đẹp, nhóm bắt tay vào giải quyết bài toán này.

Bài toán

FullHouse Dev được cung cấp 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\). Nhóm cần xử lý hai loại truy vấn:

• Truy vấn loại \(0\): Tìm phần tử \(1\) gần nhất bên trái và bên phải của vị trí \(p\) trong mảng.
• Truy vấn 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ó giá trị \(1\) nào ở bên trái của vị trí đang xét, in ra -1. Tương tự, nếu không có giá trị \(1\) nào ở bên phải, cũng 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ả một truy vấn.

OUTPUT FORMAT:

• Với mỗi truy vấn, 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, 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 (0 1): Phần tử 1 gần nhất bên trái của vị trí 1 là tại vị trí 0, bên phải là tại vị trí 4.
• Truy vấn thứ hai (0 5): Phần tử 1 gần nhất bên trái của vị trí 5 là tại vị trí 4, bên phải là tại vị trí 6.
• Truy vấn thứ ba (1 2): Thay đổi giá trị tại vị trí 2 thành 1.
• Truy vấn thứ tư (0 2): Phần tử 1 gần nhất bên trái của vị trí 2 là tại vị trí 0, bên phải là tại vị trí 4.