1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include<stdio.h>
#include<vector>
#include<climits>
#include<algorithm>

using namespace std;

const int M=1 << 17; // rozmiar drzewa

struct node {
    int index, key;
    node () {
        key=-INT_MAX;
        index=-1;
    }

    node (int i, int k) {
        key=k;
        index=i;
    }

};

node maxNode(node a, node b) {
    return a.key < b.key ? b : a;
}

node Tree[2*M];

void insert(int i, int key) {
    node x(i,key); i+=M;
    Tree[i]=x;
    while((i/=2)>0)
        Tree[i]=maxNode(x,Tree[i]);
}

node removeMax(int i) {
    i+=M; node maxx=Tree[i];
    while(i>1) {
        if(i%2==1) maxx=maxNode(maxx,Tree[i-1]);
        i=i/2;
    }

    if(maxx.index > -1) {
        i=maxx.index+M;
        Tree[i]=node();
        while((i/=2)>0) {
            Tree[i]=maxNode(Tree[2*i],Tree[2*i+1]);
        }
    }

    return maxx;
}

int main() {

    int n; long long life;
    scanf("%d%lld",&n,&life);

    vector< pair< pair<int,int> ,int> > monsters(n);

    for(int i=0; i<n; ++i) {
        scanf("%d%d",&monsters[i].first.first,&monsters[i].first.second);
        monsters[i].second=i+1;
    }

    sort(monsters.begin(),monsters.end());

    int address[100001]; fill(address,address+100001,-1);
    int number[n];

    for(int i=0; i<n; ++i) {
        address[monsters[i].first.first]=i;
        number[i]=monsters[i].second;
        insert(i,monsters[i].first.second-monsters[i].first.first);
    }

    int addr = -1;
    for (int i = 0; i < 100001; ++i)
        if (address[i] < 0)
            address[i] = addr;
        else
            addr = address[i];
    /*int addr=0;
    while(address[addr]==-1) addr++;
    while(addr < 100001) {
        int j=addr+1;
        while( j < 100001 && address[j]==-1) address[j++]=addr;
        addr=j;
    }*/

    vector<int> output;

    while(true) {
        addr=address[min(life,100000LL)];
        if(addr<0) break;
        node no = removeMax(addr);
        //fprintf(stderr, "used %d, index=%d, life=%lld, addr=%d\n", number[no.index], no.index, life, addr);
        int diffr=no.key;
        if (diffr == -INT_MAX) break;
        life+=diffr;
        if (life < 0) break;
        output.push_back(number[no.index]);
    }

    if(output.size()==n) {
        printf("TAK\n"); for(int i=0; i<n; ++i) printf("%d ", output[i]); printf("\n"); }
    else printf("NIE\n");

return 0;
}