在周六的上午，"Bajtusie"体育俱乐部的球场上将聚集 $n$ 个男孩。幸运的是，男孩的数量是偶数。这样一来，所有的男孩就都能愉快地度过这个周六，一起踢球玩耍。

Bajtazar 是俱乐部的教练，他负责为各场比赛挑选队伍阵容。Bajtazar 知道男孩们非常喜欢竞争，因此他决定安排队伍的方式要确保每一对男孩都有机会在某场比赛中彼此对抗（也就是说，至少有一场比赛中他们分别在对立的两队中）。

考虑到男孩们的能力，Bajtazar 已经为接下来的 $m$ 场比赛提出了队伍阵容。在每场比赛中，所有的男孩都会出场，并被分为两个队伍，每队有 $n/2$ 名球员。请你帮 Bajtazar 判断，是否每一对男孩至少在某一场计划中的比赛中彼此对抗过。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$4 \le n \le 40\,000$, $1 \le m \le 50$），分别表示男孩的数量和计划中的比赛场数。每个男孩的球衣上都有一个号码，是一个介于 1 到 $n$ 的整数。每个男孩的号码互不相同。

接下来的 $m$ 行中，每行包含 $n$ 个互不相同的 1 到 $n$ 之间的整数，描述了每场比赛的队伍阵容。每行的前 $n/2$ 个数字是第一支队伍的球员号码，后 $n/2$ 个数字是第二支队伍的球员号码。

输出格式

你的程序应输出一个单词 TAK 或 NIE，分别表示是否每一对男孩至少在一场比赛中彼此对抗过。

示例

输入

6 3
4 6 1 3 5 2
1 4 5 2 3 6
1 2 6 4 5 3

输出

TAK

输入 2

6 3
4 6 1 3 5 2
1 4 5 2 3 6
1 2 3 4 5 6

输出 2

NIE

在第一个例子中，每一对球员都至少在一场比赛中分属对立队伍（例如号码为 1 和 6 的球员），有的甚至在两场（例如 1 和 2）或三场比赛中对抗过（例如 1 和 3）。在第二个例子中，号码为 2 和 3 的球员始终在同一队。