[HEOI2013] 钙铁锌硒维生素
题目描述
银河队选手名单出来了!小林,作为特聘的营养师,将负责银河队选手参加宇宙比赛的饮食。
众所周知,前往宇宙的某个星球,通常要花费好长好长的时间,人体情况在这之间会发生变化,因此,需要根据每天的情况搭配伙食,来保证营养。
小林把人体需要的营养分成了 $n$ 种,这些营养包括但不限于铁,钙。他准备 了 $2$ 套厨师机器人,一套厨师机器人有 $n$ 个,每个厨师机器人只会做一道菜,这道菜一斤能提供第 $i$ 种营养 $x_i$ 微克。想要吃这道菜的时候,只要输入一个数,就 能吃到对应数量的这道菜了。为防止摄入过量对身体造成的伤害,每个机器人还有防过量摄入药,只要输入一个数,就能生成一定剂量的药,吃了这些药,就能 减少相当于食用对应数目的这道菜提供的营养。
小林之所以准备 $2$ 套厨师机器人,正是因为旅途漫漫,难以预计,也许某一 个厨师机器人在途中坏掉,要是影响了银河队选手的身体,就不好了。因此,第 $2$ 套厨师机器人被用来做第 $1$ 套的备用。小林需要为每一个第 $1$ 套厨师机器人选 一个第 $2$ 套厨师机器人作备份,使得当这个机器人坏掉时,用备份顶替,整套厨师机器人仍然能搭配出任何营养需求,而且,每个第 $2$ 套厨师机器人只能当一个第 $1$ 套厨师机器人的备份。
输入输出格式
输入格式
输入文件的第一行包含一个正整数 $n$。接下来 $n$ 行,每行 $n$ 个整数,表示第 $1$ 套厨师机器人做的菜每一斤提供的每种营养。再接下来 $n$ 行,每行 $n$ 个整数, 表示第 $2$ 套厨师机器人做的菜每一斤提供的每种营养。
输出格式
输出文件的第一行是一个字符串,如果无法完成任务,输出 `NIE`,否则输出 `TAK`,并跟着 $n$ 行,第 $i$ 行表示第 $i$ 个第 $1$ 套机器人的备份是哪一个第 $2$ 套机器人。
为了避免麻烦,如果有多种可能的答案,请给出字典序最小的那一组。
输入输出样例
输入样例 #1
3
1 0 0
0 1 0
0 0 1
2 3 0
0 7 8
0 0 9
输出样例 #1
TAK
1
2
3
输入样例 #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
输出样例 #2
TAK
3
4
1
2
说明
- 对于 $10\%$ 的数据,$n = 2$;
- 对于 $20\%$ 的数据,$n \leq 10$;
- 对于 $40\%$ 的数据,$n \leq 30$;
- 对于 $60\%$ 的数据,$n \leq 50$;
- 对于 $80\%$ 的数据,$n \leq 100$;
- 对于 $100\%$ 的数据,$1 \leq n \leq 300$,所有出现的整数均非负,且不超过 $10\,000$。