Xiao Dou has signed up for a quiz competition and brought $n$ friends along to form a team. The rules of the competition are as follows:

There are $m$ questions in total. Each person can answer one question. After answering a question, they can choose one of the subsequent questions of that question to answer, and so on, until they answer a question that has no subsequent questions.

Each question has a value. The final reward for the team is equal to the minimum value among all the questions that Xiao Dou and his friends have answered.

We now know the questions and the conditions for subsequent questions, and they are capable of answering all the questions in this competition.

Xiao Dou wants to know, given the questions and the subsequent question conditions, what is the maximum reward he can obtain?

Input

The first line contains two integers $n, m$ ($n \le 50, m \le 500$).

The next $m$ lines contain information about the questions, where the $(i+1)$-th line describes question $i$: The format is $v_i, k_i, a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$, where $v_i$ is the value of the question, $k_i$ is the number of subsequent questions for this question, and $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$ are the indices of the $k_i$ subsequent questions.

Output

If all questions can be answered, output "AK". Otherwise, output the maximum reward Xiao Dou can obtain.

Examples

Input 1

1 3
1 0
2 1 3
3 0

Output 1

AK

Input 2

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

Output 2

5

Constraints

For 10% of the data, $1 < n, m \le 10$. For 20% of the data, $1 < n, m \le 100$. For 100% of the data, $1 < n \le 50, 1 < m \le 500, v_i \le 10^9, k_i, a_{i,j} \le m$.