某竞赛系统包含 $n$ 套题，编号从 $1$ 到 $n$。每套题只能用于一场训练。有时，教练想为一支由三名学生组成的队伍进行一场训练。为此，教练必须为该训练分配一套题，使得该队伍中的任何学生此前都没有参加过使用同一套题的训练。如果无法做到这一点，则该训练无法进行。

考虑以下两种为学生队伍分配训练题的贪心策略。

第一种策略，我们称之为策略 A，是分配编号最小且该队伍中没有任何学生此前见过（即参加过使用该套题的训练）的题。

第二种策略，我们称之为策略 B，是分配在之前的训练中被学生见过总次数最多，且同时该队伍中没有任何学生此前见过的题。如果存在多套这样的题，策略 B 会分配其中编号最小的一套。

我们想找出其中一种策略是否严格优于另一种。首先，你需要报告不存在这种情况，或者找到一个整数 $n$ 和一组队伍组成序列，使得策略 A 可以为所有训练分配题，而策略 B 至少有一场训练无法分配题。其次，针对策略 B 可以为所有训练分配题而策略 A 不能的情况，提出同样的问题。

输入格式

输入仅包含一行，为一个整数 $t$ ($0 \le t \le 2$)。如果 $t = 0$，你可以输出 $-1$ 或任何有效的队伍组成序列。如果 $t = 1$，你需要找到一种策略 A 可以为所有训练分配题，而策略 B 不能的情况。如果 $t = 2$，你需要找到一种策略 B 可以为所有训练分配题，而策略 A 不能的情况。

测试用例 1 对应 $t = 0$，测试用例 2 对应 $t = 1$，测试用例 3 对应 $t = 2$。

输出格式

如果所需情况是不可能的，输出单个整数 $-1$。否则，输出两个整数 $n$ 和 $q$ ($1 \le n \le 100; 1 \le q \le 10^4$) —— 题目的数量和训练的场次。接下来的 $q$ 行，每行必须包含三个非空字符串 $a_i, b_i$ 和 $c_i$ —— 队伍中学生的标识符。这些行应按时间顺序对应参加训练的队伍。学生标识符必须由小写英文字母和数字组成。不同的标识符必须属于不同的学生，且每支队伍必须由三名不同的学生组成。保证如果所需情况是可能的，则一定存在满足 $n \le 100$ 且 $q \le 10^4$ 的解。

样例

输入 1

0

输出 1

5 4
eatmore maxbuzz winger
cerealguy eatmore niyaznigmatul
cerealguy niyaznigmatul tourist
qwerty787788 tourist vartem

说明

在样例测试用例中，如果教练遵循这两种策略中的任何一种，第一场和第三场训练将使用第 1 套题，而第二场和第四场训练将使用第 2 套题。