[CTSC2006]歌唱王国Singleland

在歌唱王国，所有人的名字都是一个非空的、仅包含整数 $1\sim n$ 的字符串。王国里生活着一大群咕噜兵，他们靠不停地歌唱首领——牛人酋长们的名字来获取力量。

咕噜兵每一次歌唱过程是这样的：首先，他从整数生成器那儿获得一个数字，然后花一个时间单位将此数字唱出来；如果他发现某个牛人酋长的名字已经被歌唱出来（即此名字是歌唱序列的一个连续子串），那么这次歌唱过程就立即结束。

相关名词定义：

• 歌唱序列：如果某人歌唱了 $x$ 个数字，第 $i$ 次歌唱的数字为 $a_i$，那么歌唱序列 $=(a_1, a_2, \ldots, a_x)$；
• 整数生成器：歌唱王国的神物，它有一个按钮，如果你按一下按钮，将从 $1\sim n$ 的数字中等概率地随机返回一个整数；
• 歌唱时间：在一次歌唱过程中花费的时间。歌唱时间是随机的，无法预料；不过歌唱时间的期望值是固定的，此期望值即平均来说歌唱时间有多长，亦可称作平均歌唱时间。

王国里的人非常喜欢歌唱，他们希望歌唱的时间越长越好，所以他们决定罢免一些牛人酋长，使得平均歌唱时间变长。但是他们不能罢免掉所有的牛人酋长，否则他们每次歌唱都无法停止，无法获取力量；于是他们决定只保留一个牛人酋长而罢免其余的牛人酋长。

你的任务是：对于给定的 $n$、牛人酋长的个数 $t$ 以及每一个牛人酋长的名字，告诉王国里的人们，对于 $1\le i\le t$，如果保留第 $i$ 个牛人酋长、罢免掉其余的，那么平均歌唱时间将是多少。

提示：此数为一个非负整数。由于这个数字太大，所以你只需输出这个数的末 $4$ 位数字；如果不足 $4$ 位，则前面补 $0$（见样例）。

输入格式

第一行两个整数 $n, t$。

以下 $t$ 行描述 $t$ 个牛人酋长的名字：第 $i+1$（$1\le i\le t$）行的第一个数为 $m_i$，表示第 $i$ 个牛人酋长的名字的长度；在一个空格之后，接下来有 $m_i$ 个数，用来描述这个牛人酋长的名字，相邻两个整数之间用一个空格分开。

输出格式

共 $t$ 行，第 $i$ 行为一个整数，表示若保留第 $i$ 个牛人酋长而罢免其余的，平均歌唱时间的末四位数字。

样例输入

2 2
1 1
3 1 2 1

样例输出

0002
0010

样例解释

只保留名字为 $(1)$ 的牛人酋长时，平均歌唱时间为 $2$；只保留名字为 $(1, 2, 1)$ 的牛人酋长时，平均歌唱时间为 $10$。输出时不足四位，前面补 $0$。

数据范围

• $1\le n\le 10^5$；
• $t\le 50$；
• $1\le m_i\le 10^5$。

来源与许可

本题为 CTSC 2006 试题「歌唱王国 Singleland」，题面与测试数据整理自 BZOJ 1152。

样例 1

输入

2 2
1 1
3 1 2 1

输出

0002
0010