题目描述

给定 $n$ 个非负整数，请你按照它们除以 $3$ 的余数分成三组，并按输入顺序输出每一组中的数字。

三组分别是：

• 余数为 $0$ 的数字；
• 余数为 $1$ 的数字；
• 余数为 $2$ 的数字。

如果某一组中没有数字，输出 None。

本题适合练习 vector<int> group[3]。每一组中的数字个数不一定相同，用 vector 分组会比普通二维数组更方便。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出三行。

第一行输出余数为 $0$ 的所有数字；

第二行输出余数为 $1$ 的所有数字；

第三行输出余数为 $2$ 的所有数字。

每一行中的数字按照输入顺序输出，数字之间用一个空格隔开。如果这一组为空，输出 None。

样例

8
1 2 3 4 5 6 7 8

3 6
1 4 7
2 5 8

数据范围与提示

对于 $100\%$ 的数据，$1 \le n \le 1000$，$0 \le a_i \le 10^9$。

提示：可以定义 vector<int> group[3];，然后把数字 $x$ 放入 group[x % 3]。