Problem Description

The roster for the Galactic Team is out! As the specially hired nutritionist, Xiao Lin will be responsible for the dietary needs of the Galactic Team during their intergalactic competition.

It is well-known that traveling to a distant planet usually takes a very long time, and the human body undergoes changes during this period. Therefore, it is necessary to adjust the diet daily to ensure proper nutrition.

Xiao Lin has divided the required nutrients into \( n \) types, including but not limited to iron and calcium. He has prepared 2 sets of cooking robots, each set containing \( n \) robots. Each robot in a set can only cook one specific dish, which provides \( x_i \) micrograms of the \( i \)-th nutrient per kilogram. To eat this dish, one simply inputs a number to get the corresponding amount. To prevent over-intake, each robot also has an over-intake prevention medicine. By inputting a number, a certain dose of medicine is generated, which can reduce the equivalent amount of nutrients provided by the corresponding amount of the dish.

Xiao Lin prepared 2 sets of robots because the journey is long and unpredictable. If one robot breaks down during the trip and affects the team's health, it would be problematic. Therefore, the second set of robots serves as a backup for the first set. Xiao Lin needs to assign each robot in the first set a backup from the second set, ensuring that if a robot breaks down, the backup can take its place and the entire set of robots can still meet any nutritional requirement. Moreover, each robot in the second set can only serve as a backup for one robot in the first set.

Input Format

The first line of the input file contains a positive integer \( n \). The next \( n \) lines, each containing \( n \) integers, represent the nutrients provided by the dishes cooked by the first set of robots. The following \( n \) lines, each containing \( n \) integers, represent the nutrients provided by the dishes cooked by the second set of robots.

Output Format

The first line of the output file is a string. If it is impossible to complete the task, 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 complications, if there are multiple possible answers, provide the one with the smallest lexicographical order.

Sample Input and Output

Input Sample #1

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

Output Sample #1

TAK 
1 
2 
3

Input Sample #2

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

Output Sample #2

TAK 
3 
4 
1 
2

Notes

• For \( 10\% \) of the data, \( n = 2 \);
• For \( 20\% \) of the data, \( n \leq 10 \);
• For \( 40\% \) of the data, \( n \leq 30 \);
• For \( 60\% \) of the data, \( n \leq 50 \);
• For \( 80\% \) of the data, \( n \leq 100 \);
• For \( 100\% \) of the data, \( 1 \leq n \leq 300 \), all integers are non-negative and do not exceed \( 10,000 \).

见题面 Input 部分

见题面 Output 部分