Stall layouts: hints, no solution

A market street has stalls numbered 0 to stalls - 1 in a row. A number of vendors must each take a different stall, and the organisers want breathing space: between any two neighbouring vendors there must be at least gap empty stalls. In other words, two consecutive chosen stall numbers differ by at least gap + 1.

Return every possible layout as an ascending list of the stall numbers taken by the vendors. List the layouts in ascending order, comparing them entry by entry from the first, so that [0, 3] comes before [1, 3]. If the vendors cannot all fit, return an empty list.

Examples

Input

vendors = 2, stalls = 5, gap = 1

Output

[[0, 2], [0, 3], [0, 4], [1, 3], [1, 4], [2, 4]]

Note

Chosen stalls must differ by at least 2.

Input

vendors = 3, stalls = 4, gap = 1

Output

[]

Note

Three vendors with a gap need at least five stalls.

Constraints

• 1 <= vendors <= 30 and 1 <= stalls <= 80
• 0 <= gap <= 10
• The result has at most 300 layouts

Hint 1: a nudge

After placing one vendor, which stalls are still possible for the next one, and is there a stall beyond which the remaining vendors can no longer fit?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing