题目描述

小泽初始有 $z$ 点生命，要挑战 $n$ 个关卡。挑战关卡 $i$ 会先失去 $d_i$ 点生命，再恢复 $a_i$ 点；生命在任何时刻都必须严格大于 $0$。每关恰好挑战一次。判断是否存在合法顺序，并在存在时给出任意一种。

输入格式

第一行两个整数 $n,z$，接下来 $n$ 行每行两个整数 $d_i,a_i$。

输出格式

若无解输出 NIE。若有解，第一行输出 TAK，第二行输出一个合法的关卡编号排列。

输入

6 60658
92456 29461
915 9796
22923 59304
95730 46023
32122 2851
96767 55859

输出

NIE

输入

5 100000
73591 72950
89139 82682
2126 83001
77465 60536
69139 99847

输出

TAK
3 5 2 1 4

输入

7 42781
28252 91281
12701 300
97538 4708
58370 56921
99381 54976
98680 45966
6638 27624

输出

NIE

数据范围

$1\le n,z\le10^5$，$0\le d_i,a_i\le10^5$。