Description

并不是天下所有的算法都是你见过的；有的时候，你必须自己造轮子。

---

小强喜欢看连环画书，但是它作为一种昆虫，是无法看懂画的内容的；不过，它可以看画的颜色。颜色从 $1$ 编号到 $P$ 。

小强看完书之后，会产生某种行为（行为从 $1$ 编号到 $M$）。小强看书的时候，心情是十分复杂多变的。它的心情由一套“心情系统”来控制。准确地说，它总是从“空白”的心情来开始看书，每看一页，画的颜色对小强的心情产生影响。影响的规律可以用一个 $N\times P$ 的数组 $A$ 来表示，其中，$A[i][j]$ 表示小强当前心情是 $i$ ，看了一页颜色为 $j$ 的画之后的心情（心情从 $1$ 编号到 $N$，“空白”心情的编号总是 $1$） 。小强看完书之后，会根据它此刻的心情产生对应的行为，这个对应关系也是心情系统的一部分，可以用一个长度为 $N$ 的数组 $B$ 来表示。空白”心情对应行为的编号永远是 $1$ 。

举个例子：小强有六种心情：空白（1），迷惑（2），怅然（3），醒悟（4），满意（5），开心（6）；画有两种颜色：蓝色（1），红色（2）；看完书，小强有两种行为：垂头丧气（1），开心一笑（2）；那么，$N=6,P=2,M=2$ 。我们让数组 $A$ 为 :

$$\begin{array}{|c|c|} \hline 2 &3\\ \hline 4 &6\\ \hline 4 &5\\ \hline 6 &5\\ \hline 5 &2\\ \hline 6 &3\\ \hline \end{array} $$

数组 $B$ 为 :

$$\begin{array}{|c|c|c|c|c|c|} \hline 1 &1&1&1&2&2\\ \hline \end{array} $$

于是，小强看一本颜色依次为红色（2）、蓝色（1）、红色（2）、红色（2）、蓝色（1）、蓝色（1）的书，心情依次为空白（1）、怅然（3）、醒悟（4）、满意（5）、迷惑（2）、醒悟（4）、开心（6），最终引发开心一笑的行为。

突然有一天，小强发现了另一套心情系统：

$N=4$ （空白（1），低调（2），等待（3），高兴（4）），$A$ 为

$$\begin{array}{|c|c|} \hline 2 &2\\ \hline 3 &4\\ \hline 4 &4\\ \hline 4 &2\\ \hline \end{array} $$

$B$ 为

$$\begin{array}{|c|c|c|c|} \hline 1 &1&1&2\\ \hline \end{array} $$

小强发现，对于任何一本书，小强在这两种心情系统的控制下，最终产生的行为是相同的。于是，小强认为，这两个心情系统是等效的。注意：一个心情系统包括：心情数 $N~(N\ge 1)$ 、数组 $A$ （$N$ 行 $P$ 列，每个数都是 $1\sim N$ 的正整数）以及数组 $B$ （$N$ 个介于 $1\sim M$ 之间的正整数）。

小强不想成为一个多愁善感的动物，于是它想知道，和它目前心情系统等效的心情系统中，心情数量最少的心情系统是什么？

Input Format

第一行两个整数P，M，表示书的颜色数、小强的行为数。接下来描述 了一个心情䇣统。'第一行是心情数 $\mathrm{N}$, 接下来 $\mathrm{N}$ 行每行 P个正整数表示数组 $\mathrm{A}$ ，接下来一 行 $N$ 个正整数表示数组 $B 。 P>=1, M>=1, N>=1$ 。注意: 某些心情或者某些行为可能是小强永远也不会达到或者做出的。

Output Format

描述了和输入等效的心情数最少的心情系统。第一行一个正整数，表示 心情数，接下来按照输入文件的格式描述这个心情系统的数组A和数组B。如果有多种可能的心情系统的心情数都是最小的，你要输出字典序最小的，即， $A[1][1]$ 最小，在此前提下， $\mathrm{A}[1][2] . . .$. 最小在 $A$ 数组相同的情况下，B[1]最小，在此前提下， $\mathrm{B}[2]$...... 最小。注意，你要满足 "空白" (即小强开始看书的心情) 的心情编号是 1 。

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

4 
2 2 
3 4 
4 4 
4 2 
1 1 1 2

Hint

对于100%的数据，N<=1000，P<=26，M<=1000