Final Array Clinic - Diagnose 12 Array Errors

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

This clinic turns 12 common array bugs into 12 exact diagnostic results.

Given a static array of capacity $C$ and logical size $n$, an integer $x$, and insertion index $p$ ($0\le p\le n$), compute:

1. $D_1=n$; 2. $D_2=n-1$; 3. $D_3=a_0$; 4. $D_4=a_{n-1}$; 5. the sum; 6. the minimum; 7. the maximum; 8. the first index of $x$ or $-1$; 9. the last index of $x$ or $-1$; 10. the frequency of $x$; 11. whether $n<C$; and 12. the final array after inserting $x$ at $p$ only when capacity allows it.

If insertion is possible, shift the suffix right and set $b_p=x$; otherwise keep the array unchanged.

Input

The first line contains $C$, $n$, $p$, and $x$. The second line contains $n$ integers $a_i$.

Output

Line 1 prints $D_1,\ldots,D_{11}$. Line 2 prints $m$. Line 3 prints the final array $b$.

Subtask

Subtask 1 (20 points): $1\le n\le C\le10$, $|a_i|,|x|\le10^3$.

Subtask 2 (30 points): $1\le n\le C\le5000$, $|a_i|,|x|\le10^6$.

Subtask 3 (50 points): $1\le n\le C\le2\cdot10^5$, $|a_i|,|x|\le10^9$.

Example

Input

7 5 2 4
4 1 4 9 2

Output

5 4 4 2 20 1 9 0 2 2 1
6
4 1 4 4 9 2

Explanation

The result follows directly from the mathematical definition above.