Il était une fois, une institutrice qui emmena des enfants au parc pour jouer au téléphone arabe. Chacun des $N$ enfants connaît le même ensemble de $M$ mots, que nous numéroterons de $1$ à $M$. Le jeu se déroule comme suit : l'institutrice aligne les enfants dans une rangée et murmure le mot numéro $1$ au premier enfant. Ensuite, le premier enfant murmure le mot qu'il a entendu au deuxième enfant, puis le deuxième enfant murmure le mot qu'il a entendu au troisième, et ainsi de suite jusqu'au dernier enfant. À ce moment-là, le dernier enfant prononce à voix haute le mot qu'il a entendu.

Comme les jeunes informaticiens codaient bruyamment dans le club voisin ce jour-là, les enfants ne pouvaient pas se concentrer sur le jeu et entendaient souvent un mot très différent de celui qui leur était murmuré. Cependant, le fait suivant est connu : un enfant donné entendra toujours un mot donné de la même manière, c'est-à-dire que si le mot $A$ est murmuré à l'enfant $D$, il murmurera ensuite (ou prononcera à voix haute s'il est le dernier de la rangée) toujours le même mot, peu importe où il se trouve dans la rangée ou qui lui a murmuré le mot $A$.

Pour s'amuser elle aussi, l'institutrice a décidé de mener une expérience : elle a répété ce jeu $N!$ fois, une fois pour chaque ordre possible des enfants. Elle a remarqué qu'il existe un mot qui est apparu exactement $K$ fois comme le mot que le dernier enfant a prononcé à voix haute. Elle se demande comment cela est possible et vous demande de reconstruire une telle situation.

Les nombres $N$ et $K$ sont donnés. Déterminez la taille du vocabulaire $M$ et un mot $X$ ($1 \le X \le M$) de ce vocabulaire, et pour chacun des $N$ enfants et chacun des $M$ mots, déterminez le mot que cet enfant transmettra s'il entend le mot donné, de telle sorte que le mot choisi $X$ soit prononcé à voix haute par le dernier enfant dans exactement $K$ (sur un total de $N!$) ordres. Votre solution est notée en fonction de la taille du vocabulaire choisi, un vocabulaire plus petit rapportant plus de points. Pour plus de détails, consultez la section Notation.

Entrée

La première ligne contient le numéro de la sous-tâche $P$ ($1 \le P \le 2$) de la section Notation, et la deuxième ligne contient le nombre de scénarios de test $T$ ($1 \le T \le 10$). Les scénarios sont indépendants les uns des autres, c'est-à-dire qu'il s'agit de plusieurs exemples de test dans un seul fichier d'entrée.

Chacune des $T$ lignes suivantes contient deux entiers $N$ et $K$ ($1 \le N \le 12$, $0 \le K \le N!$) correspondant à un scénario de test.

Sortie

Pour chaque scénario parmi les $T$, imprimez sur la première ligne deux nombres : $M$ et $X$ ($1 \le X \le M \le 10\,000$), la taille du vocabulaire et le mot que le dernier enfant a prononcé dans $K$ jeux. Dans les $N$ lignes suivantes, imprimez $M$ nombres chacune : le $j$-ième nombre dans la $i$-ième de ces lignes indique le mot que le $i$-ième enfant transmettra si le mot $j$ lui est murmuré.

Notation

Les exemples de test sont divisés en deux sous-tâches, lisez attentivement les descriptions de chacune. Si votre programme est incorrect sur l'un des exemples, vous obtiendrez $0$ point pour cette sous-tâche.

La sous-tâche 1 vaut au total $30$ points et $1 \le N \le 7$. Pour cette sous-tâche, il est possible d'obtenir $0$ ou tous les points. À condition que votre programme soit correct sur tous les exemples, la seule condition supplémentaire est $M \le 10\,000$.

La sous-tâche 2 vaut au total $70$ points et $1 \le N \le 12$. Pour cette sous-tâche, il est possible d'obtenir des points partiels. Pour chaque scénario de chaque exemple, le nombre de points que votre algorithme a remportés est déterminé. Votre algorithme recevra $70 \cdot B$ points, où $B$ est le nombre minimum de points sur tous les scénarios de la sous-tâche. Les points pour un scénario individuel $B_S$ sont calculés comme suit :

• si $M \le N + 1$, alors $B_S = 1$
• sinon, si $M \le N + 5$, alors $B_S = 0.7 + 0.15 / (M - N - 1)$ (valable $0.7 \le B_S \le 0.85$)
• sinon, si $M \le 5N$, alors $B_S = 0.5 + 0.05 \cdot (5 - M/N)$ (valable $0.5 \le B_S \le 0.7$)
• sinon, si $M \le 10\,000$, alors $B_S = 0.5 / (\log_{10}(M / 5N) + 1)$ (valable $0.0 \le B_S \le 0.5$)

Exemples

Entrée 1

1
2
3 2
2 1

Sortie 1

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

Entrée 2

2
2
3 3
4 0

Sortie 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

Remarque

Pojašnjenje prvog primjera : dans la première partie, si l'ordre des enfants est (1, 2, 3), il se passera ce qui suit : l'institutrice murmure le mot 1 au premier enfant. Il murmure le mot 2 au deuxième enfant. Le deuxième enfant murmure le mot 2 au troisième enfant, qui prononce alors le mot 3 à voix haute. L'autre ordre d'enfants correspondant est (3, 2, 1), pour lequel les mots prononcés sont, dans l'ordre : 1 (institutrice), 1 (enfant numéro 3), 3 (enfant numéro 2), 3 (enfant numéro 1). Pour les quatre ordres restants, le dernier enfant prononce un mot différent de 3.

Pojašnjenje drugog primjera : ceci est un exemple de la deuxième sous-tâche qui comporte un système de notation partielle. Pour le premier scénario, $N + 1 < M \le N + 5$ est vérifié, donc ce résultat vaut 0,77 (arrondi à deux décimales). Pour le deuxième scénario, $M \le N + 1$ est vérifié, donc ce résultat vaut 1. Comme on prend le minimum sur tous les scénarios de test, cette solution obtiendrait 0,77 du nombre total de points pour cet exemple.