#P4100. [HEOI2013] 钙铁锌硒维生素

[HEOI2013] 钙铁锌硒维生素

题目描述

银河队选手名单出来了!小林,作为特聘的营养师,将负责银河队选手参加宇宙比赛的饮食。

众所周知,前往宇宙的某个星球,通常要花费好长好长的时间,人体情况在这之间会发生变化,因此,需要根据每天的情况搭配伙食,来保证营养。

小林把人体需要的营养分成了 nn 种,这些营养包括但不限于铁,钙。他准备 了 22 套厨师机器人,一套厨师机器人有 nn 个,每个厨师机器人只会做一道菜,这道菜一斤能提供第 ii 种营养 xix_i 微克。想要吃这道菜的时候,只要输入一个数,就 能吃到对应数量的这道菜了。为防止摄入过量对身体造成的伤害,每个机器人还有防过量摄入药,只要输入一个数,就能生成一定剂量的药,吃了这些药,就能 减少相当于食用对应数目的这道菜提供的营养。

小林之所以准备 22 套厨师机器人,正是因为旅途漫漫,难以预计,也许某一 个厨师机器人在途中坏掉,要是影响了银河队选手的身体,就不好了。因此,第 22 套厨师机器人被用来做第 11 套的备用。小林需要为每一个第 11 套厨师机器人选 一个第 22 套厨师机器人作备份,使得当这个机器人坏掉时,用备份顶替,整套厨师机器人仍然能搭配出任何营养需求,而且,每个第 22 套厨师机器人只能当一个第 11 套厨师机器人的备份。

输入格式

输入文件的第一行包含一个正整数 nn。接下来 nn 行,每行 nn 个整数,表示第 11 套厨师机器人做的菜每一斤提供的每种营养。再接下来 nn 行,每行 nn 个整数, 表示第 22 套厨师机器人做的菜每一斤提供的每种营养。

输出格式

输出文件的第一行是一个字符串,如果无法完成任务,输出 NIE,否则输出 TAK,并跟着 nn 行,第 ii 行表示第 ii 个第 11 套机器人的备份是哪一个第 22 套机器人。

为了避免麻烦,如果有多种可能的答案,请给出字典序最小的那一组。

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

提示

  • 对于 10%10\% 的数据,n=2n = 2
  • 对于 20%20\% 的数据,n10n \leq 10
  • 对于 40%40\% 的数据,n30n \leq 30
  • 对于 60%60\% 的数据,n50n \leq 50
  • 对于 80%80\% 的数据,n100n \leq 100
  • 对于 100%100\% 的数据,1n3001 \leq n \leq 300,所有出现的整数均非负,且不超过 1000010\,000