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

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 100\)).
• Tô đè tất cả các ô trong hình chữ nhật vừa chọn thành màu \(c\).

Yêu cầu: Cho \(m,n\) là kích thước bảng và dãy gồm \(k\) thao tác tô màu, hãy xác định bảng màu mà Alice nhận được.

Input

• Dòng đầu tiên gồm ba số nguyên \(m,n,k\) (\(m,n,k \le 100\)).
• Dòng thứ \(s\) (\(1 \le s \le k\)) 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 đó.

Output

• Dòng thứ \(i\) (\(1 \le i \le m\)) trong \(m\) dòng sau chứa \(n\) 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.

Example

3 3 2
1 1 2 2 2
2 2 3 3 1

2 2 0
2 1 1
0 1 1

An và Bình đang có một số nguyên dương \(X\) và muốn tách nó thành tổng hai số nguyên dương \(A\) và \(B\). Giá trị thực sự của một số nguyên dương không nằm ở độ lớn mà được quyết định bởi tổng chữ số. Hai bạn sẽ cảm thấy vui nếu \(A\) và \(B\) có tổng chữ số giống nhau.

Yêu cầu: Có \(T\) giả định, mỗi giả định cung cấp số nguyên dương \(X\). Với mỗi giả định, hãy giúp An và Bình tìm hai số nguyên dương \(A\) và \(B\) có tổng bằng \(X\) và tổng chữ số của hai số bằng nhau.

Input

• Dòng đầu tiên chứa một số nguyên dương \(T\) (\(1 \le T \le 10000\)).
• Mỗi dòng trong \(T\) dòng tiếp theo chứa một số nguyên dương \(X\) (\(X \ge 2\)).

Output

• Với mỗi giả định, in ra hai số nguyên \(A\) và \(B\) bất kì thỏa mãn đề bài trên một dòng. Nếu không tồn tại đáp án, in ra -1.

Scoring

Gọi \(C(X)\) và \(S(X)\) là số chữ số và tổng chữ số của số nguyên dương \(X\).

• Subtask \(1\) (\(20\%\) số điểm): \(X \le 10000\) với mọi giả định.
• Subtask \(2\) (\(30\%\) số điểm): Tổng \(C(X)\) của các giả định không vượt quá \(1000\).
• Subtask \(3\) (\(20\%\) số điểm): Tổng \(C(X)\) của các giả định không vượt quá \(10^6\) và \(S(X)\) chẵn với mọi giả định.
• Subtask \(4\) (\(30\%\) số điểm): Tổng \(C(X)\) của các giả định không vượt quá \(10^6\).

Example

4
4
33
243
29

2 2
12 21
117 126
-1

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