The Notched Measuring Rod

A carpenter wants a wooden rod with m notches cut at whole-number positions 0 .. L. With such a rod she measures a length by finding two notches that far apart, and she wants every pair of notches to measure a different length: no two pairs may be the same distance apart. A shorter rod is handier, so she has a limit L on its length.

Write notched_rod(m, L) that returns the notch positions as a list of m distinct integers between 0 and L (in any order) such that all m * (m - 1) / 2 distances between pairs of notches are different, or None if no such rod of length at most L exists. Any valid rod is accepted.

Examples

Input:  m = 4, L = 6
Output: [0, 1, 4, 6]   (or its mirror image [0, 2, 5, 6])
Explanation: the six distances are 1, 4, 6, 3, 5 and 2, all different.

Input:  m = 5, L = 10
Output: None
Explanation: every rod with 5 notches and all distances different is at least 11 long.

Input:  m = 1, L = 0
Output: [0]

Constraints

• 1 <= m <= 11 and 0 <= L <= 100
• each test must finish in well under a second; proving that no rod exists means exhausting a search, and without good pruning that takes far too long for 9 or more notches
• the tests include the shortest possible rod for 11 notches

Goals

• Search for a combinatorial object mark by mark, rejecting a branch the moment a property breaks
• Prune with a lower bound on the room the remaining choices still need
• Prove that no object exists by finishing a pruned search