A new computer game has just appeared on the shelves of Byteotian supermarkets, in which we control the actions of the brave hero Bitor, whose task is to defeat $n$ monsters inhabiting the dungeons of Byteograd. For simplicity, we will number the monsters from $1$ to $n$.

During a fight with monster $i$, Bitor sustains damage that costs him $d_i$ health points. This monster guards a chest with a health potion, which, after the fight is won, restores $a_i$ health points to Bitor.

Bitor defeats monsters easily, but he cannot allow his health points to drop to zero (or below) at any moment. Can Bitor fight the opponents in such an order that he defeats all the monsters?

Input

The first line of input contains two integers $n$ and $z$ ($1 \le n, z \le 100\,000$), representing the number of monsters and Bitor's initial health points. The next $n$ lines contain descriptions of the monsters: the $i$-th of these lines contains two integers $d_i$ and $a_i$ ($0 \le d_i, a_i \le 100\,000$), representing the damage dealt by monster $i$ and the power of the potion that can be consumed after defeating it.

Output

The first line of output should contain one word TAK or NIE, depending on whether Bitor is able to defeat all the monsters. If it is possible to defeat all the monsters, you must also print a second line containing a sequence of $n$ distinct integers from $1$ to $n$, separated by single spaces. This sequence should describe an example order of battles, and its successive terms should correspond to the numbers of the monsters defeated in order. If there is more than one correct answer, your program should print any one of them.

Examples

Input 1

3 5
3 1
4 8
8 3

Output 1

TAK
2 3 1