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

输入格式

第一行两个整数 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