Whisper Transmission

Consider the following telephone game: A teacher brings (N) children and they all know the same (M) words, numbered from 1 to (M). The game is played as follows:

1. The children are arranged in a line.
2. The teacher whispers word 1 to the first child.
3. For (1 \le i < N), the (i)th child whispers the word he heard to the ((i+1))th child.
4. The (N)th child says the word he heard out loud.

However, due to distractions, children may mishear. The amazing fact is that every child (i) has a fixed function (f_i:\ [1,M] \to [1,M]) so that no matter who whispers to him (or where he appears in the line), whenever he is whispered a word (A) he always hears (B = f_i(A)) (it is allowed that (A = B)).

The teacher runs the game for every permutation (p=(p_1,p_2,\dots,p_N)) of ({1,2,\dots,N}) (a total of (N!) games). For each permutation, she records the final announced word [ S(p)=f_{p_N}(f_{p_{N-1}}(\cdots f_{p_1}(1)\cdots )). ] She observed that there is a word (X) which is announced exactly (K) times among all (N!) games.

Your task is: given integers (N) and (K), construct a positive integer (M) and an integer (X\in[1,M]) as well as functions (f_1,f_2,\dots,f_N:\ [1,M]\to[1,M]) (each given by listing the images of (1,2,\dots,M)) such that in the multiset [ S={ S(p) : p \text{ is a permutation of } {1,2,\dots,N} }, ] there is at least one word (X) which appears exactly (K) times.

A simple way to think about the problem: you must design (N) functions (f_1, f_2,\dots,f_N:\ [1,M]\to[1,M]) with your choice of (M) so that if we collect the value [ f_{p_N}(f_{p_{N-1}}(\cdots f_{p_1}(1)\cdots)) ] over all (N!) permutations (p) of ({1,2,\dots,N}), some particular word (X) appears exactly (K) times.

Note: Smaller (M) get higher scores. In our sample solution we use a very simple construction under the assumption that (K) is a multiple of ((N-1)!). Specifically, if we set (M=2) and choose some of the functions to be constant functions always returning 1 and the rest as constant functions always returning 2, then the final output in any game is the value of the function that appears last. In a permutation the last function among the (N) functions appears in exactly ((N-1)!) games. Hence, if we let (a=K/(N-1)!) (assuming (K) is divisible by ((N-1)!) and (0\le a\le N)), then by defining the first (a) functions as [ f_i(x)=1,\quad \forall x\in{1,2}, \quad 1\le i\le a, ] and the remaining functions as [ f_i(x)=2,\quad \forall x\in{1,2}, \quad a+1\le i\le N, ] the word 1 appears exactly (a\times (N-1)! = K) times (and word 2 appears in the other games). For the special case (K=0) we take (a=0) and output all functions with the constant value 2 (and then choose (X=1) so that it appears 0 times).

This simple construction is used in the solutions below. It is assumed that the input (K) satisfies (K\in {0,(N-1)!,2\times (N-1)!,\dots,N!}).

inputFormat

The first and only line of input contains two integers (N) and (K) separated by a space. It is assumed that (K) is a multiple of ((N-1)!) (with the convention that (0! = 1)) and \n(0 \le K \le N!).

outputFormat

On the first line, output two integers (M) and (X) separated by a space. Then output (N) lines; the (i)th of these lines should contain (M) integers separated by spaces, representing the values of (f_i(1), f_i(2), \dots, f_i(M)). In our construction we use (M=2).

sample

3 4

2 1
1 1
1 1
2 2