Multisets (4) P14098

Write a program that, given four natural numbers $n$, $x$, $y$ and $t$, prints all the multisets with $t$ numbers that can be made up with $\{1, \dots, n\}$, in such a way that every number appears between $x$ and $y$ times.

Input

Input consists of a natural number $n > 0$, followed by a natural number $x \ge 0$, followed by a natural number $y > x$, followed by a natural number $t \ge 0$. Assume $nx \le t \le ny$.

Output

Print all the multisets of size $t$ that can be made up with $\{1, \dots, n\}$, using each number between $x$ and $y$ times. The numbers inside each multiset must appear in non-decreasing order.

Information about the checker

You can print the solutions to this exercise in any order.