---
# System prepended metadata

title: BN01

---

# BN01

## A. Tenzing and Balls

Tenzing có $n$ quả bóng trên một đường thẳng. Từ trái qua phải, quả bóng $i$ có màu $a_i$.
Tenzing có thể thực hiện thao tác sau nhiều lần:
- Chọn $i$ và $j$ sao cho $1 \le i < j \le n$ và $a_i = a_j$,
- Xóa $a_i, a_{i + 1}, ..., a_j$ khỏi dãy (và giảm chỉ số của các quả bóng bên phải quả bóng $j$ đi $j - i + 1$).

Tenzing muốn biết số lượng bóng lớn nhất anh có thể xóa là bao nhiêu.

### Input
Dòng đầu tiên chứa $t$ $(1 \le t \le 10^3)$ - số test. Với mỗi test:
Dòng đầu chứa $n$ $(1 \le n \le 2 . 10^5)$ - số quả bóng.
Dòng tiếp theo chứa $n$ số $a_1, a_2, ..., a_n$ $(1 \le  a_i \le n)$ - màu của các quả bóng.
Đảm bảo rằng tổng $n$ của tất cả các test không vượt quá $2 . 10^5$.

### Output
Với mỗi test, in ra số lượng quả bóng lớn nhất mà Tenzing có thể xóa được.

---

## B. Tennis Game

Petya và Gena thích chơi bóng bàn. Một trận đấu được diễn ra theo các quy tắc sau:
- Một **trận đấu** gồm nhiều **hiệp**
- Một **hiệp** gồm nhiều lần **giao bóng**
- Một lần **giao bóng** được thắng bởi một người chơi, người này nhận được $1$ điểm.
- Ngay khi một người chơi ghi được $t$ điểm, anh ta sẽ thắng **hiệp** đó; Sau đó **hiệp** tiếp theo bắt đầu và điểm của cả hai người chơi được đặt về $0$.
- Ngay khi một người chơi thắng $s$ **hiệp**, anh ta sẽ thắng **trận đấu** và **trận đấu** kết thúc.

Để thêm phần thú vị, Petya và Gena chọn $s$ và $t$ trước **trận đấu**. Bên cạnh đó họ cũng ghi lại diễn biến **trận đấu**: nghĩa là với mỗi lần **giao bóng**, họ ghi lại người chiến thắng. 
Chú ý, **hiệp đấu** sẽ kết thúc ngay khi một trong hai người chơi ghi được $t$ điểm, **trận đấu** sẽ kết thúc ngay khi một trong hai người chơi thắng $s$ **hiệp**.

Cho diễn biến **trận đấu**, tìm tất cả cặp $s$ và $t$ có thể.

### Input
Dòng đầu tiên chứa $n$ $(1 \le n \le 10^5)$ - số lần **giao bóng** của trận đấu.
Dòng thứ hai chứa $n$ số nguyên $a_i$. Nếu $a_i = 1$, Petya thắng lần **giao bóng** thứ $i$, $a_i = 2$ thì Gena thắng.
Không đảm bảo rằng  tồn tại ít nhất $1$ cặp $s, t$ thỏa mãn diễn biến trận đấu.

### Output
Dòng đầu chứa $k$ - số cặp $s, t$ thỏa mãn diễn biến trận đấu.
$k$ dòng sau mỗi dòng chứa $s_i$ và $t_i$.
In ra theo thứ tự tăng dần của $s$, nếu $s$ bằng nhau thì theo thứ tự tăng dần của $t$.

---

## C. Ntarsis' Set
Ntasis có một dãy $S$, ban đầu chứa các số nguyên $1, 2, 3, ..., 10^{1000}$ sắp xếp tăng dần. Mỗi ngày, anh ấy xóa các số nhỏ nhất thứ $a_1, a_2, ..., a_n$ cùng lúc.
Tìm số nhỏ nhất trong dãy $S$ sau $k$ ngày.
### Input
Dòng đầu tiên chứa $t$ $(1 \le t \le 10^5)$ - số test. Với mỗi test:
Dòng đầu chứa $n$ và $k$ $(1 \le n, k \le 2 . 10^5)$ - số quả bóng.
Dòng tiếp theo chứa $n$ số $a_1, a_2, ..., a_n$ $(1 \le  a_i \le 10^9)$.
Đảm bảo rằng:
- tổng $n$ của tất cả các test không vượt quá $2 . 10^5$.
- tổng $k$ của tất cả các test không vượt quá $2 . 10^5$.
- $a_1 < a_2 < ... < a_n$ mọi test.
### Output
In ra số nhỏ nhất trong dãy $S$ sau $k$ ngày.

---

## D. Inverse of Rows and Columns
Bạn được cho ma trận nhị phân $a$ size $n$ x $m$.
Bạn có thể thực hiện một vài (có thể không thực hiện) **thao tác** với ma trận này. Trong một **thao tác** bạn có thể **reverse** (biến $0$ thành $1$ và ngược lại) **một cột** hoặc **một hàng** của ma trận.

Nhiệm vụ của bạn là **sort** lại ma trận ban đầu bằng các thao tác trên. Một ma trận được coi là **sorted** nếu dãy $[a_{1, 1}, a_{1, 2}, ..., a_{1, m}, a_{2, 1}, a_{2, 2}, ..., a_{2, m}, ..., a_{n, m - 1}, a_{n, m}]$ không giảm.

### Input
Dòng đầu tiên chứa $n$ và $m$ $(1 \le n, m \le 200)$ - số hàng và số cột của ma trận.
$n$ dòng sau, mỗi dòng chứa $m$ số nguyên $a_{i, j}$ $(0 \le a_{i, j} \le 1)$.
### Output
Nếu không thể **sort** lại ma trận, in ra "NO".
Ngược lại, in ra "YES". Dòng thứ hai in xâu $r$ độ dài $n$, trong đó $r_i = 1$ khi thực hiện **thao tác** lên hàng $i$, ngược lại $r_i = 0$.
Dòng thứ ba in ra xâu $c$ độ dài $n$, trong đó $c_i = 1$ khi thực hiện **thao tác** lên cột $i$, ngược lại $c_i = 0$.
Nếu có nhiều đáp án, in ra bất kỳ.