With random thoughts running trough your mind, you could not stop noticing something special about the sequence of numbers you had written:

6 2 1 4

The special thing you notice was that by adding a contiguous set of numbers from this sequence you could obtain all numbers from 1 to 9! See how you could do this(the numbers to sum are marked with '^'):

6 214 | 621 4 | 62 14 | 6 2 14| 6 21 4| ^ ^ ^ ^ ^ ^ ^62 1 4 | 62 1 4|6 21 4 |6 2 14 ^ ^ ^ ^ ^ ^ ^ ^ ^

You became curious about this property, and decided to create a
program to help you discover sequences like this. However, you would
like to consider a more general case. You want sequences of size
**N**, which have **numbers (not digits)** bigger or equal than **K** that have
sums of contiguous numbers in the sequence that match all numbers from
**S** to **E**. Knowing N, K and S, you want to discover the
sequence that maximizes E, that is, the one that creates the biggest
consecutive sequence of numbers.

For example, if N=4, K=1 and S=1, the sequence above would give E=9, (since it produces the numbers from 1 to 9), and in that case 9 is also the maximum possible E. Could you solve the general case?

Given three integers **N**, **K** and **S**, you have to
find all sequences of N numbers bigger or equal to K that maximize E,
given that all integer numbers in the range S to E (inclusive) can be obtained by
adding contiguous numbers of the sequence.

The input will be formed by a single line with three integers **N**, **K**
and **S** separated by single spaces (*1 ≤ N,K,S < 7* and
*K≤S*). These integers indicate respectively the size of the
sequence to consider, the minimum value of a number in the sequence
and the start number to which we should discover consecutive
contiguous sums from the sequence.

The first line of output should contain a single integer **E**,
indicating the maximum possible E, such that the range S
to E (inclusive) can be constructed from the sequence as defined above.

The second line of output should contain a single integer
**NUM**, indicating that there are exactly NUM different sequences
which generate all numbers from S to E. Then follow exactly NUM lines,
each one with N integers indicating the maximizing sequence. The
numbers should be separated by single spaces, with no leading or
trailing spaces. These sequences should also come in lexicographical
order.

4 1 1

9 8 1 1 4 3 1 3 3 2 2 3 3 1 2 5 1 3 3 1 5 2 3 4 1 1 4 1 2 6 6 2 1 4

4 2 5

10 4 2 5 3 6 5 2 2 6 6 2 2 5 6 3 5 2

Universidade do Porto