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)

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

A fixed array has capacity $C$ and initial logical size $n$, where

Its current elements are $a_0,a_1,\ldots,a_{n-1}$. Then $Q$ commands are processed in their given order.

There are two command types:

• I p x: insert $x$ at index $p$. The command is valid exactly when

If valid, old elements at indices $p,p+1,\ldots,n-1$ move one position right, $x$ is placed at $p$, and $n$ increases by $1$. Otherwise the command is ignored.

• D p: delete the element at index $p$. It is valid exactly when

If valid, elements to the right move one position left and $n$ decreases by $1$. Otherwise the command is ignored.

After all $Q$ commands, print the final logical size and the remaining elements.

Input

The first line contains integers $C,n,Q$. The second line contains the initial $n$ integers and may be empty when $n=0$. Each of the next $Q$ lines contains one command I p x or D p.

Output

Print the final logical size $n$ on the first line. If $n>0$, print the current array on the second line.

Subtask

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

Example

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

Explanation

After the first four commands, the array is 10 15 30 40 50 and is full because $n=C=5$. The final command I 0 99 is ignored because no capacity remains.