Q的书房里有 n 个书架，编号依次为 1,2,3,…,n。可是光有书架显得文化程度不够，于是他又买了 m本书。Q制定了一个计划，打算第 i 本书放到第 $k_i$个书架上。现在请你输出计划实施后，每个书架上会有哪些书。

输入格式

第一行有两个整数n ($1<n≤10^4$)，m (1<m≤$10^5$)，分别表示书架的数量和书的数量。

接下来有 m行，每行有一个整数$k_i(1≤k_i≤n)$ 表示第 i 本书应该放在第 $k_i$ 个书架上，还有一个字符串 $s_i$（长度不超过 20）表示书的名字。

输出格式

输出一共 n行。

每行首先输出两个整数 id,cnt，表示书架的编号，以及该书架上一共有 cnt本书，后面跟着 cnt个书名（按照字典序排序），中间都用一个空格隔开。

格式说明

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

样例输入

4 3
3 mdl
1 jgm
3 kfc

样例输出

1 1 jgm
2 0
3 2 kfc mdl
4 0