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

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

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