Đây là bài toán với hai lần chạy. Trên mỗi bộ kiểm thử, lời giải của bạn sẽ được chạy hai lần.
Trong giờ tin học, Алеся và Борис đang học về mật mã học. Hai bạn quyết định tự nghĩ ra một cách mã hóa thông điệp.
Алеся chọn $k$ số nguyên khác nhau từ $1$ đến $n$ và gọi tập hợp thu được là $T$. Алеся muốn gửi cho Борис tập hợp $T$ dưới dạng mã hóa như một thông điệp. Để làm điều đó, từ tập hợp $T$, Алеся sẽ xây dựng và gửi cho Борис một tập hợp khác $R$, cũng gồm các số nguyên từ $1$ đến $n$.
Hai bạn không muốn kích thước thông điệp thay đổi sau khi mã hóa, nên $R$ cũng phải chứa đúng $k$ số. Họ còn cho rằng nếu $T$ và $R$ có ít nhất một phần tử chung thì cách mã hóa của họ sẽ không đủ an toàn. Vì vậy, không được có số nào thuộc cả $T$ lẫn $R$, tức là hai tập hợp $T$ và $R$ phải rời nhau. Bảo đảm rằng $k\le n/2$, nên từ tập hợp $T$ luôn có thể xây dựng ít nhất một tập hợp $R$.
Khi Борис nhận được thông điệp đã mã hóa $R$, bạn ấy phải giải mã nó để thu được thông điệp ban đầu $T$.
Hãy giúp Алеся và Борис nghĩ ra và cài đặt các thuật toán mã hóa và giải mã. Trong lần chạy thứ nhất, chương trình của bạn đóng vai Алеся; trong lần chạy thứ hai, chương trình đóng vai Борис.
Dữ liệu vào
Dòng đầu tiên chứa một số $a$, bằng $1$ hoặc $2$, là số thứ tự lần chạy của chương trình.
Dòng thứ hai chứa một số $m$, là số lượng thông điệp ($1\le m\le300\,000$) mà chương trình phải mã hóa (trong lần chạy thứ nhất) hoặc giải mã (trong lần chạy thứ hai).
$2m$ dòng tiếp theo mô tả $m$ thông điệp, mỗi thông điệp gồm hai dòng.
Dòng đầu tiên của mỗi thông điệp chứa hai số nguyên $n_i$ và $k_i$ ($2\le n_i\le10^9$, $1\le k_i\le300\,000$, $k_i\le\frac{n_i}{2}$). Dòng thứ hai của thông điệp chứa $k_i$ số nguyên khác nhau từ $1$ đến $n_i$ theo thứ tự tăng dần.
Bảo đảm rằng tổng tất cả các giá trị $k_i$ trong một bộ kiểm thử không vượt quá $300\,000$.
Nếu $a=1$, các số được cho là thông điệp ban đầu. Nếu $a=2$, các số được cho là kết quả mà chương trình của bạn tạo ra khi mã hóa một thông điệp nào đó trong lần chạy thứ nhất.
Dữ liệu ra
Chương trình phải in $m$ dòng; dòng thứ $i$ phải chứa $k_i$ số nguyên khác nhau từ $1$ đến $n_i$ theo thứ tự tăng dần.
Trong lần chạy thứ nhất, với mỗi thông điệp ban đầu $T_i$, chương trình phải in tập hợp $R_i$, không được có phần tử chung với $T_i$.
Trong lần chạy thứ hai, với mỗi thông điệp đã mã hóa $R_i$, chương trình phải khôi phục thông điệp ban đầu $T_i$.
Ví dụ
Lần chạy thứ nhất
Dữ liệu vào 1
1 2 2 1 1 5 2 1 4
Dữ liệu ra 1
2 2 3
Lần chạy thứ hai
Dữ liệu vào 2
2 2 5 2 2 3 2 1 2
Dữ liệu ra 2
1 4 1
Ghi chú
Lưu ý rằng ví dụ đưa ra những lựa chọn cụ thể cho dữ liệu ra của lần chạy thứ nhất và dữ liệu vào của lần chạy thứ hai. Nếu chương trình của bạn in một tập hợp $R$ khác thì dữ liệu vào của lần chạy thứ hai cũng sẽ khác.
Ngoài ra, trong lần chạy thứ hai, các thông điệp đã mã hóa không nhất thiết được đưa cho chương trình của thí sinh theo cùng thứ tự như trong lần chạy thứ nhất.
Nhiệm vụ con
Để nêu các giới hạn bổ sung cho dữ liệu vào, gọi dãy các số tạo nên tập hợp $T_i$ là $t_1,t_2,\ldots,t_{k_i}$. Các số này được sắp xếp theo thứ tự tăng dần.
Gọi tổng các giá trị $n_i$ trong một bộ kiểm thử là $N$.
Gọi tổng các giá trị $k_i$ trong một bộ kiểm thử là $K$.
| Nhiệm vụ con | Điểm | Giới hạn bổ sung: $n_i,N$ | Giới hạn bổ sung: $k_i,K$ | Giới hạn bổ sung: $t_j$ | Nhiệm vụ con cần thiết | Thông tin kiểm tra |
|---|---|---|---|---|---|---|
| $1$ | $9$ | $N\le5000$ | $k_i=1$ | Lỗi đầu tiên | ||
| $2$ | $11$ | $N\le5000$ | $k_i=2$ | Lỗi đầu tiên | ||
| $3$ | $9$ | $N\le300\,000$ | $k_i=\frac{n_i}{2}$ | Lỗi đầu tiên | ||
| $4$ | $7$ | $n_i\le7$, $N\le5000$ | Ví dụ | Lỗi đầu tiên | ||
| $5$ | $9$ | $t_{j+1}-t_j\ge2$, $t_{k_i}\le n_i-1$ | Lỗi đầu tiên | |||
| $6$ | $9$ | $t_{k_i}-t_1\le\frac{n_i}{2}-1$ | Lỗi đầu tiên | |||
| $7$ | $10$ | $N \le 5000$ | $t_{k_i}\le n_i-k_i$ | Lỗi đầu tiên | ||
| $8$ | $12$ | $N\le100$ | Ví dụ | Lỗi đầu tiên | ||
| $9$ | $3$ | $N\le5000$ | Ví dụ, $1$–$2$, $4$, $7$–$8$ | Lỗi đầu tiên | ||
| $10$ | $7$ | $N \le 300\,000$ | Ví dụ, $1$–$4$, $7$–$9$ | Lỗi đầu tiên | ||
| $11$ | $7$ | $K\le5000$ | Ví dụ, $1$–$2$, $4$, $7$–$9$ | Lỗi đầu tiên | ||
| $12$ | $7$ | Không có giới hạn bổ sung | Ví dụ, $1$–$11$ | Lỗi đầu tiên |