Problem Description

This problem is translated from PA 2020 Round 1 Wybór zadań.

For Matthew, preparing the online PA contest is quite a big challenge. During the contest, contestants take part in five rounds, numbered from $1$ to $5$. In each round, contestants solve tasks from three categories, called A, B, and C. In the first four rounds, there is one task in each category; in the last fifth round, there are two tasks in each category. Therefore, a total of $18$ tasks must be prepared and assigned to $15$ different positions, where three positions (5A, 5B, and 5C) must each be assigned two tasks. Here, a position means a combination of a round and a category.

Matthew knows he cannot just prepare any $18$ tasks. The difficulty of a task should match the round and category where it appears. Over the whole year, he has collected $n$ task ideas. For each idea, he knows which position it fits (it fits only this one position, and does not fit any other position).

Matthew wants to know whether it is possible to select $18$ tasks from his ideas and assign them to the correct positions. Given his notes, help him find a valid selection plan.

Input Format

The first line contains an integer $n$, which is the total number of Matthew's ideas.

The second line contains $n$ strings, describing the position that each of Matthew's ideas fits. Each string consists of exactly two characters: the first character is a digit from the set $\{1,2,3,4,5\}$, and the second character is a letter from the set $\{\texttt A,\texttt B,\texttt C\}$.

Output Format

If it is possible to build a full PA task set from Matthew's ideas, output TAK; otherwise output NIE.

19
3B 4B 5B 4C 5C 3C 1A 5A 5C 3A 5A 2C 1B 2A 5B 5C 2B 1C 4A

TAK

20
2B 4B 4C 5A 5C 5C 4A 1B 3A 4A 2A 3B 1B 1C 1A 5A 2C 1B 5B 3C

NIE

Hint

Explanation for Sample 1

In the first sample, Matthew has three task ideas that match position 5C. After removing any one of them, the remaining ideas form a suitable PA task set.

Explanation for Sample 2

In the second sample testdata, Matthew has only one task that matches position 5B, so he cannot build a full PA task set.

Constraints

This problem uses bundled tests.

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 100$.

Translated by ChatGPT 5