Description

The Galaxy Team roster is out. As a specially hired nutritionist, Kobayashi will take charge of the team’s diet for the interstellar competition.

As we all know, traveling to a certain planet usually takes a very long time. The human body changes during the journey, so meals must be adjusted daily to ensure adequate nutrition.

Kobayashi divides the required nutrients into $n$ kinds, including but not limited to iron and calcium. He prepares $2$ sets of chef robots, with $n$ robots in each set. Each robot can cook exactly one dish, and this dish provides $x_i$ micrograms of the $i$-th nutrient per jin (jin). Whenever you want to eat this dish, you can enter a number to get the corresponding amount of this dish. To prevent harm from overdosing, each robot also has anti-overdose medicine. By entering a number, it generates a certain dose of medicine; after taking it, it reduces the nutrients by the same amount as eating the corresponding amount of this dish would provide.

Kobayashi prepares $2$ sets precisely because the journey is long and uncertain; a robot may fail during the trip, and it would be bad if that affected the Galaxy Team’s health. Therefore, the second set is used as a backup for the first set. Kobayashi needs to choose, for each robot in the first set, one robot from the second set as its backup, so that if a robot fails, replacing it with its backup still allows the entire set of chef robots to meet any nutritional requirement. Moreover, each robot in the second set can serve as the backup for at most one robot in the first set.

Input Format

The first line contains a positive integer $n$. The next $n$ lines each contain $n$ integers, describing how much of each nutrient is provided per jin by the dishes made by the first set of chef robots. The following $n$ lines each contain $n$ integers, describing the same for the second set of chef robots.

Output Format

The first line contains a string. If the task is impossible, output NIE. Otherwise, output TAK, followed by $n$ lines; the $i$-th line indicates which robot in the second set is the backup for the $i$-th robot in the first set.

To avoid trouble, if there are multiple possible answers, output the lexicographically smallest one.

3 
1 0 0 
0 1 0 
0 0 1 
2 3 0 
0 7 8 
0 0 9

TAK 
1 
2 
3

4 
2 0 1 3 
0 1 0 4 
1 9 9 4 
0 4 1 7 
1 10 9 8 
1 13 10 11 
1 2 1 5 
2 1 1 7

TAK 
3 
4 
1 
2

Hint

• For $10\%$ of the testdata, $n = 2$.
• For $20\%$ of the testdata, $n \leq 10$.
• For $40\%$ of the testdata, $n \leq 30$.
• For $60\%$ of the testdata, $n \leq 50$.
• For $80\%$ of the testdata, $n \leq 100$.
• For $100\%$ of the testdata, $1 \leq n \leq 300$. All integers that appear are non-negative and do not exceed $10\,000$.

Translated by ChatGPT 5