#37 「 轮换 」

统计

温馨提示:本题质量较低,请不要浪费时间。

长度为n的置换可以用一些更短的轮换的乘积来表示。

轮换可以用类似(a,b,c)形式来表示,表示a变成b,b变成c,c变成a。

比如{1,2,3,4} -> {2,3,4,1}可以表示为(1,2,3,4),也可以表示为$(4 1) (3 1)(2 1)$ 。

轮换的乘积是右结合的(从右到左进行)。

现在给你p个长度小于等于k的轮换,他们表示的是长度为n的置换,求他们的乘积的置换。

输入格式

第一行三个整数,n,p,k。

接下来p行,每行第一个数字m,表示这个轮换有m个数,接下来有m个数字。

输出格式

n个数字,表示1,2,3..n分别对应的数字。

样例数据

input

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

output

2 3 4 1

样例解释

(4 1) (3 1) (2 1) = (1 2 3 4)

数据规模与约定

$1 \le n,k,p \le 1000$。

时间限制:1s

空间限制:512MB

Author: zrt