Dawno temu, przedszkolanka zabrała dzieci do parku na zabawę w głuchy telefon. Każde z $N$ dzieci zna ten sam zbiór $M$ słów, które oznaczymy liczbami od $1$ do $M$. Gra przebiega w następujący sposób: przedszkolanka ustawia dzieci w szeregu i szepcze pierwszemu dziecku słowo numer $1$. Następnie pierwsze dziecko szepcze usłyszane słowo drugiemu dziecku, drugie dziecko szepcze usłyszane słowo trzeciemu i tak dalej, aż do ostatniego dziecka. Wtedy ostatnie dziecko wypowiada na głos słowo, które usłyszało.

Ponieważ młodzi informatycy głośno kodowali w pobliskim stowarzyszeniu, dzieci nie mogły się skoncentrować na grze i często słyszały słowo zupełnie inne od tego, które im wyszeptano. Wiadomo jednak, co następuje: dane dziecko zawsze usłyszy dane słowo w ten sam sposób, tzn. jeśli dziecku $D$ wyszeptano słowo $A$, przekaże ono dalej (lub wypowie na głos, jeśli jest ostatnie w szeregu) zawsze to samo słowo, niezależnie od tego, gdzie znajduje się w szeregu lub kto wyszeptał mu słowo $A$.

Aby urozmaicić zabawę, przedszkolanka postanowiła przeprowadzić eksperyment: powtórzyła tę grę $N!$ razy, po jednym razie dla każdej możliwej kolejności dzieci. Zauważyła, że istnieje słowo, które dokładnie $K$ razy pojawiło się jako słowo wypowiedziane na głos przez ostatnie dziecko. Jest ciekawa, jak to możliwe i prosi o zrekonstruowanie takiej sytuacji.

Dane są liczby $N$ i $K$. Określ wielkość słownika $M$ oraz słowo $X$ ($1 \le X \le M$) z tego słownika, a dla każdego z $N$ dzieci i każdego z $M$ słów określ słowo, które to dziecko przekaże dalej, jeśli usłyszy dane słowo, tak aby wybrane słowo $X$ było wypowiadane na głos przez ostatnie dziecko w dokładnie $K$ (z łącznej liczby $N!$) ustawieniach. Twoje rozwiązanie jest oceniane w zależności od wielkości wybranego słownika, przy czym mniejszy słownik daje więcej punktów. Szczegóły znajdują się w sekcji Podzadania.

Wejście

W pierwszym wierszu podano numer podzadania $P$ ($1 \le P \le 2$) z sekcji Podzadania, a w drugim wierszu liczbę scenariuszy testowych $T$ ($1 \le T \le 10$). Scenariusze są od siebie niezależne, tzn. jest to kilka przypadków testowych w jednym pliku wejściowym.

W każdym z kolejnych $T$ wierszy znajdują się dwie liczby całkowite $N$ i $K$ ($1 \le N \le 12$, $0 \le K \le N!$), odpowiadające jednemu scenariuszowi testowemu.

Wyjście

Dla każdego z $T$ scenariuszy w pierwszym wierszu wypisz dwie liczby: $M$ i $X$ ($1 \le X \le M \le 10\,000$), wielkość słownika oraz słowo, które ostatnie dziecko wypowiedziało w $K$ grach. W kolejnych $N$ wierszach wypisz po $M$ liczb: $j$-ta liczba w $i$-tym z tych wierszy oznacza słowo, które $i$-te dziecko przekaże dalej, jeśli wyszeptano mu słowo $j$.

Podzadania

Przypadki testowe podzielono na dwa podzadania. Jeśli twój program jest niepoprawny dla któregokolwiek z przykładów, otrzymasz 0 punktów za to podzadanie.

Podzadanie 1 jest warte łącznie 30 punktów i obowiązuje w nim $1 \le N \le 7$. W tym podzadaniu można uzyskać 0 lub wszystkie punkty. Pod warunkiem, że program jest poprawny dla wszystkich przykładów, jedynym dodatkowym warunkiem jest $M \le 10\,000$.

Podzadanie 2 jest warte łącznie 70 punktów i obowiązuje w nim $1 \le N \le 12$. W tym podzadaniu można uzyskać punkty częściowe. Dla każdego scenariusza każdego przykładu wyznaczana jest liczba punktów zdobytych przez twój algorytm. Twój algorytm otrzyma $70 \cdot B$ punktów, gdzie $B$ to minimalna liczba punktów ze wszystkich scenariuszy w podzadaniu. Punkty za pojedynczy scenariusz $B_S$ oblicza się w następujący sposób:

• jeśli $M \le N + 1$, to $B_S = 1$
• w przeciwnym razie, jeśli $M \le N + 5$, to $B_S = 0.7 + 0.15 / (M - N - 1)$ (obowiązuje $0.7 \le B_S \le 0.85$)
• w przeciwnym razie, jeśli $M \le 5N$, to $B_S = 0.5 + 0.05 \cdot (5 - M/N)$ (obowiązuje $0.5 \le B_S \le 0.7$)
• w przeciwnym razie, jeśli $M \le 10\,000$, to $B_S = 0.5 / (\log_{10}(M / 5N) + 1)$ (obowiązuje $0.0 \le B_S \le 0.5$)

Przykład

Wejście 1

1
2
3 2
2 1

Wyjście 1

3 3
2 1 3
3 2 2
1 3 2
2 1
1 1
2 2

Wejście 2

2
2
3 3
4 0

Wyjście 2

6 2
1 2 3 4 5 6
6 5 4 3 2 1
2 4 1 4 3 2
2 2
1 1
1 1
1 1
1 1

Uwagi

Wyjaśnienie pierwszego przykładu: w pierwszej grze, jeśli kolejność dzieci to $(1, 2, 3)$, wydarzy się następujące: przedszkolanka szepcze pierwszemu dziecku słowo $1$. Ono szepcze drugiemu dziecku słowo $2$. Drugie dziecko szepcze trzeciemu dziecku słowo $2$, a ono wypowiada na głos słowo $3$. Drugą odpowiednią kolejnością dzieci jest $(3, 2, 1)$, dla której wypowiedziane słowa to kolejno $1$ (przedszkolanka), $1$ (dziecko nr $3$), $3$ (dziecko nr $2$), $3$ (dziecko nr $1$). Dla pozostałych czterech ustawień ostatnie dziecko wypowiada słowo inne niż $3$.

Wyjaśnienie drugiego przykładu: jest to przykład z drugiego podzadania, które posiada punktację częściową. Dla pierwszego scenariusza zachodzi $N + 1 < M \le N + 5$, więc wynik wynosi $0.77$ (zaokrąglone do dwóch miejsc po przecinku). Dla drugiego scenariusza zachodzi $M \le N + 1$, więc wynik wynosi $1$. Ponieważ bierze się minimum ze wszystkich scenariuszy testowych, to rozwiązanie otrzymałoby $0.77$ całkowitej liczby punktów za ten przykład.