小明有 $m$ 颗糖，编号为 $1,2,⋯ ,m$。他打算发给 $n$ 个小朋友。发完糖之后，为了促进小朋友之间纯洁的友谊，他会安排 $r$ 次互换活动。每次互换活动，会让第 $x$ 个小朋友和第 $y$ 个小朋友交换手里的糖果。现在小明想知道最终每个小朋友含有哪些糖果。

输入格式

第一行两个整数 $n,m,r（2≤n≤1000，1≤m,r≤10^6）$，表示 $n$ 个小朋友，$m$ 颗糖，$r$ 次互换安排。

第二行 $m$ 个整数, $a_i$ 表示编号为 $i$ 的糖发给了第 $a_i$ 个小朋友。

接下来 $r$ 行，每行两个整数 $x,y$，表示第 $x$ 个小朋友和第 $y$ 个小朋友互换手中的糖果。

数据保证 $1≤a_i,x,y≤n$，$x≠y$。

输出格式

$n$ 行，每行以一个整数 $c_i$ 开头，表示第 $i$ 个小朋友含有的糖果数，接下来是一个长度为 $c_i$ 的递增编号序列，整数之间用空格隔开。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

3 6 1
1 3 2 1 3 2
2 3

样例输出

2 1 4
2 2 5
2 3 6