eolymp
bolt
Try our new interface for solving problems
Problems

Большой сбор бобов

Большой сбор бобов

Time limit 1 second
Memory limit 64 MiB

И снова речь пойдет об игре с горошинами. Игра заключается в том, что имеется N=2^k+1 чаш, расставленных по кругу, и некоторое количество горошин в каждой из них. Каждый ход Петя берет все горошины из некоторой чаши и последовательно кладет их по одной в каждую последующую чашу. На первом ходу используются горошины из первой чаши, а в дальнейшем из той, в которую была помещена последняя горошина на предыдущем шаге. В начальном состоянии в каждой чаше лежит по одной горошине.

Требуется определить, сколько горошин будет в чашах c номерами от a до b включительно после T-го хода.

Input data

В единственной строке входного файла задаются четыре целых числа k, T, a и b.

1k63, 0T < 10^200, 1a b2^k+1.

Output data

В единственную строку выходного файла необходимо вывести b−a+1 чисел - количества горошин в чашах с номерами от a до b по прошествии T ходов.

Examples

Input example #1
2 2 1 5
Output example #1
0 0 2 2 1
Author Виталий Неспирный
Source Летняя школа Севастополь 2013, Волна 2, День 4