Гра#501

Гра

1 second

256 megabytes

Hard

Недавно граючись зі своїми друзями, Василько придумав нову гру. Сьогодні він вирішив поділитися нею з тобою.

В цій грі потрібно збудувати масив $a$ довжини $n$ , у якого такі властивості:

кожне число має бути від $- m$ до $m$ ;
серед усіх можливих підвідрізків масиву є лише один, у якому сума чисел максимальна, і це підвідзок з $l$ до $r$ включно.

Вам потрібно побудувати такий масив, проте серед усіх таких можливих масивів вам потрібно побудувати саме той, у якому сума невід'ємних чисел максимальна.

Input

Перший рядок містить чотири цілі числа $n$ , $m$ , $l$ , $r$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5, $1 \leq m \leq 1 0^{9}$ 1 \le m \le 10^9, $1 \leq l \leq r \leq n$ 1 \le l \le r \le n) — довжина масиву, обмеження на значення масиву, краї відрізка.

Output

В одному рядку потрібно виписати побудований масив $a$ довжини $n$ .

Якщо відповідей декілька, то ви можете вивести будь-який масив.

Examples

Example 1

Loading

Note

Сума на кожному з відрізків з прикладу:

В відрізку від $1$ до $1$ сума $- 1$ .
В відрізку від $1$ до $2$ сума $2$ .
В відрізку від $1$ до $3$ сума $5$ .
В відрізку від $1$ до $4$ сума $2$ .
В відрізку від $1$ до $5$ сума $4$ .
В відрізку від $2$ до $2$ сума $3$ .
В відрізку від $2$ до $3$ сума $6$ .
В відрізку від $2$ до $4$ сума $3$ .
В відрізку від $2$ до $5$ сума $5$ .
В відрізку від $3$ до $3$ сума $3$ .
В відрізку від $3$ до $4$ сума $0$ .
В відрізку від $3$ до $5$ сума $2$ .
В відрізку від $4$ до $4$ сума $- 3$ .
В відрізку від $4$ до $5$ сума $- 1$ .
В відрізку від $5$ до $5$ сума $2$ .

тому на відрізку від $2$ до $3$ буде максимальна сума, і він єдиний з такою сумою.

1 \leq n \leq 1 0^{5}

1 \leq m \leq 1 0^{9}

1 \leq l \leq r \leq n