A Full-fill-ing Problem

Suppose we have a $0$-indexed array $a$ of integers like this:

$7$

$2$

$2$

$1$

$1$

$1$

$1$

$2$

$3$

$5$

$0$

$1$

$2$

$3$

$4$

$5$

$6$

$7$

$8$

$9$

We can define a fill operation that, starting at an index $i$, replaces the value at $i$, and any contiguous positions containing that same value, with a new value $x$. For example, performing the fill operation on the above array with $i=4$ and $x=0$ would result in the following new array:

$7$

$2$

$2$

$0$

$0$

$0$

$0$

$2$

$3$

$5$

$0$

$1$

$2$

$3$

$4$

$5$

$6$

$7$

$8$

$9$

And performing the fill operation on the original array with $i=1$ and $x=0$ would result in the following new array:

$7$

$0$

$0$

$1$

$1$

$1$

$1$

$2$

$3$

$5$

$0$

$1$

$2$

$3$

$4$

$5$

$6$

$7$

$8$

$9$

Notice how, in this case, the element at index $7$ (with value $2$) is unaffected because the fill operation only affects positions contiguous to position $i$ that have the same value contained in position $i$.

The fill operation is commonly used in two-dimensional arrays representing images, to replace some contiguous region of one color with a different color. For simplicity, we will only deal with one-dimensional arrays and, in particular, we will implement the fill operation recursively as follow:

Given a $0$-indexed array $a$ with $N$ elements, an index $i$, an original value $v$ and a new value $x$:

  • If $i<0$ or $i\geqslant N$, do nothing and return (the index is out of bounds).

  • If $a[i] \neq v$, do nothing and return (we’ve encountered a value that is not the one we want to replace).

  • If $a[i] = x$, do nothing and return (we’ve already changed the value at this index).

  • Otherwise, set $a[i]$ to $x$ and call fill recursively two times: one with $i-1$ and another with $i+1$ ($a$, $v$, and $x$ remain the same in the recursive calls)

Note that fill does not return anything. Its purpose is to modify an array in-place. Also, take into account that the initial call to the fill function should pass $a[i]$ as the value for $v$.

Your solution must use a RECURSIVE function, using the definition presented above.

On the exam, any other type of solution will receive zero points!

EVEN IF KATTIS JUDGES IT AS CORRECT!

Input

The input contains the specification of an array of integers. The first line contains three integers, $N$, $i$, $x$ as defined above, each separated by a single space. The second line contains the $N$ integers in the array, each separated by a single space.

You may assume the following bounds:

  • $1 \leqslant N \leqslant 100$

  • $0 \leqslant i \leqslant 99$

  • $0 \leqslant x \leqslant 9$

You may also assume that the integers specified in the second line are single-digit positive integers (i.e., for each integer $n$ in the second line, $0\leqslant n \leqslant 9$).

Note: The first two sample inputs correspond to the two examples shown above.

Output

You must output the array resulting from applying the fill operation on the input array, using $a[i]$ as the value for $v$. You must print the array in a single line, with each element of the array separated by a single space.

Sample Input 1 Sample Output 1
10 4 0
7 2 2 1 1 1 1 2 3 5
7 2 2 0 0 0 0 2 3 5
Sample Input 2 Sample Output 2
10 1 0
7 2 2 1 1 1 1 2 3 5
7 0 0 1 1 1 1 2 3 5
Sample Input 3 Sample Output 3
10 7 1
1 0 0 1 1 0 0 0 1 1
1 0 0 1 1 1 1 1 1 1