Problem G - Summing Numbers

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 2 1 4 | 6 2 1 4 | 6 2 1 4 | 6 2 1 4 | 6 2 1 4 |
    ^       ^         ^ ^           ^       ^ ^

6 2 1 4 | 6 2 1 4 | 6 2 1 4 | 6 2 1 4
^           ^ ^ ^   ^ ^       ^ ^ ^

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?

The Problem

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.

Input

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.

Output

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.

Sample Input 1

4 1 1

Sample Output 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

Sample Input 2

4 2 5

Sample Output 2

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

CPUP 2007
Universidade do Porto
(10/10/2007)