OpenKattis
University of Chicago

# 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