Tin học trẻ C1 - Vòng Khu vực miền Bắc và miền Nam 2023

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.

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.

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

3 4
-1
2 4
1 5

Alice có một dãy số nguyên không âm \(a_1, a_2, \dots, a_n\) và định nghĩa một cách chia dãy \(k\) đoạn \((l_1, r_1), (l_2, r_2), \dots, (l_k, r_k)\) được gọi là cách chia \(x\)-đẹp thỏa mãn:

• Mỗi vị trí \(i\) (\(1 \le i \le n\)) thuộc đúng một đoạn. Cụ thể, tồn tại đúng một đoạn (\(l_t, r_t\)) mà \(l_t \le i \le r_t\).
• Số nguyên không âm nhỏ nhất không xuất hiện trong mỗi dãy con liên tiếp \(a_{l_t}, a_{l_t+1}, \dots, a_{r_t}\) không vượt quá \(x\).

Yêu cầu: Cho dãy số nguyên không âm \(n\) phần tử, hãy giúp Alice xác định mỗi giá trị \(x\) (\(0 \le x \le n-1\)) thì cách chia \(x\)-đẹp có số đoạn \(k\) nhỏ nhất là bao nhiêu?

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) (\(0 \le a_i \le 10^6\)).

Output

• Ghi ra \(n\) dòng tương ứng và kết quả cách chia \(x\)-đẹp với \(x\) từ \(0\) đến \(n-1\). Nếu không có cách chia thỏa mãn thì in ra -1.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 3000\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 2 \cdot 10^5\).
• Subtask \(4\) (\(20\%\) số điểm): \(k \le 20\) với mọi \(0 \le x \le n-1\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

5
2 0 1 0 3

-1
3
2
2
1

Alice có một bảng màu kích thước \(m \times n\), các hàng được đánh số từ \(1\) đến \(m\) theo chiều từ trên xuống, các hàng được đánh số từ \(1\) đến \(n\) theo chiều từ trái qua phải. Ô nằm giao giữa hàng \(i\) (\(1 \le i \le m\)) và cột \(j\) (\(1 \le j \le n\)) gọi là ô \((i,j)\). Ban đầu, toàn bộ bảng là màu trắng (màu \(0\)), Alice thực hiện \(k\) thao tác tô màu như sau:

• Chọn một hình chữ nhật nằm trong bảng chiếm nguyên các ô và một màu \(c\) (\(1 \le c \le 30\)).
• Tô đè tất cả các ô trong hình chữ nhật vừa chọn thành màu \(c\).

Sau khi thực hiện \(k\) thao tác, Alice nhận được một bảng màu. Bob cũng muốn tạo ra bảng màu giống như ALice nhưng không biết các thao tác mà Alice đã thực hiện. Điều này không dễ thực hiện được, nên Bob mong muốn sử dụng không quá \(k\) thao tác để nhận được bảng màu càng giống với bảng màu của Alice càng tốt.

Yêu cầu: Cho bảng màu của Alice và số nguyên dương \(k\), hãy giúp Bob tìm ra dãy không quá \(k\) thao tác để nhận được bảng màu càng giống bảng màu của Alice càng tốt.

Input

• Dòng đầu tiên gồm ba số nguyên \(m,n,k\) (\(k \le 100\)).
• Dòng thứ \(i\) (\(1 \le i \le m\)) trong \(m\) dòng sau chứa số nguyên \(a_{i,1},a_{i,2},...,a_{i,n}\) mô tả màu trên hàng \(i\) của bảng màu Alice.

Output

• Dòng đầu chứa số nguyên không âm \(h\) (\(h \le k\)).
• Dòng thứ \(s\) (\(1 \le s \le h\)) chứa năm số nguyên \(x_s,y_s,u_s,v_s,c_s\) trong đó \((x_s,y_s)\) và \((u_s,v_s)\) tương ứng là ô góc trái trên và ô góc phải dưới của hình chữ nhật được chọn ở thao tác tô màu thứ \(s\), \(c_s\) là màu sẽ tô cho hình chữ nhật đó.

Scoring

• Có \(20\) test, mỗi test \(5.0\) điểm. Gọi \(d\) là số ô trong bảng màu xây dựng được giống với của Alice, khi đó số điểm bạn đạt được cho mỗi test là \(5.0 \times (\frac{d}{m \times n})^5\).
• Subtask \(1\) (\(30\%\) số điểm): \(m,n,k \le 5\).
• Subtask \(2\) (\(50\%\) số điểm): \(m,n \le 50\).
• Subtask \(3\) (\(20\%\) số điểm): \(m,n \le 500\).

Example

3 3 2
2 2 0
2 2 1
0 1 1

2
1 1 2 2 2
2 2 3 3 1