Mô phỏng danh sách tĩnh với Q lệnh insert/delete (Simulate a Fixed-Capacity List with Q Insert/Delete Commands)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có một mảng tĩnh có sức chứa tối đa $C$ phần tử và kích thước logic ban đầu là $n$, với

Các phần tử hiện có là $a_0,a_1,\ldots,a_{n-1}$. Sau đó có $Q$ lệnh, được xử lý đúng theo thứ tự xuất hiện.

Có hai loại lệnh:

• I p x: yêu cầu chèn giá trị $x$ tại chỉ số $p$. Lệnh hợp lệ khi đồng thời

Nếu hợp lệ, các phần tử cũ ở chỉ số $p,p+1,\ldots,n-1$ dịch sang phải một vị trí, $x$ được đặt tại chỉ số $p$, rồi $n$ tăng thêm $1$. Nếu không hợp lệ, lệnh bị bỏ qua và trạng thái không đổi.

• D p: yêu cầu xóa phần tử tại chỉ số $p$. Lệnh hợp lệ khi

Nếu hợp lệ, các phần tử ở bên phải $p$ dịch sang trái một vị trí rồi $n$ giảm $1$. Nếu không hợp lệ, lệnh bị bỏ qua.

Sau khi xử lý đủ $Q$ lệnh, hãy in kích thước logic cuối cùng và các phần tử còn lại.

Input

Dòng đầu chứa ba số nguyên $C,n,Q$. Dòng thứ hai chứa $n$ số nguyên ban đầu; nếu $n=0$, dòng này có thể rỗng. Mỗi trong $Q$ dòng tiếp theo chứa một lệnh I p x hoặc D p theo định nghĩa ở trên.

Output

Dòng đầu in kích thước logic cuối cùng $n$. Nếu $n>0$, dòng thứ hai in toàn bộ mảng hiện tại theo thứ tự.

Subtask

Subtask 1 (100 điểm): $1\le C\le2000$; $0\le n\le C$; $1\le Q\le5000$; $|a_i|,|x|\le10^9$; $|p|\le10^9$.

Ví dụ

Input

5 3 5
10 20 30
I 1 15
D 2
I 3 40
I 4 50
I 0 99

Output

5
10 15 30 40 50

Giải thích

Sau bốn lệnh đầu, mảng trở thành 10 15 30 40 50 và đã đầy vì $n=C=5$. Lệnh cuối I 0 99 bị bỏ qua do không còn sức chứa.