QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#585442#9260. Raiffeisenbank Logisticsucup-team3474#TL 614ms4112kbC++201.5kb2024-09-23 20:50:592024-09-23 20:51:04

Judging History

你现在查看的是最新测评结果

  • [2024-09-23 20:51:04]
  • 评测
  • 测评结果:TL
  • 用时:614ms
  • 内存:4112kb
  • [2024-09-23 20:50:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1919810,mod=998244353;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];

typedef struct{
    int to,val,w;
}Node;

vector<Node> e[N];
int q[N];

map<PII,ll> mp;


void __(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) e[i].clear();
    mp.clear();
    deque<PII> q;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[u].push_back({v,w,0});
        e[v].push_back({u,w,1});
    }
    mp[{1,-1}]=0;
    q.push_back({1,-1});
    while(q.size()){
        PII t=q.front();
        // cout<<t.first<<" "<<t.second<<" "<<mp[t]<<endl;
        q.pop_front();
        for(auto [to,val,w]:e[t.first]){
            if(val<=t.second) continue;
            if(w==0){
                PII tt={to,val};
                // if(mp.count(tt)) continue;
                if(!mp.count(tt)||mp[tt]>mp[t]){
                    
                mp[tt]=mp[t];
                q.push_front(tt);
                }
            }else{
                PII tt={to,val};
                
                if(!mp.count(tt)||mp[tt]>mp[t]+1){
                    
                mp[tt]=mp[t]+1;
                q.push_front(tt);
                }
            }
        }
    }
    ll ans=1e18;
    for(auto [u,v]:mp){
        if(u.first==n) ans=min(v,ans);
    }
    if(ans>1e10) puts("-1");
    else printf("%lld\n",ans);

}


int main(){
    int _;
    cin>>_;
    while(_--){
        __();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3800kb

input:

1
4 3
2 1 1
2 3 2
4 3 3

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3796kb

input:

2
4 3
2 1 1
2 3 2
4 3 2
8 9
1 2 5
2 3 10
4 3 15
4 5 20
5 8 25
1 6 2
6 5 30
7 6 3
8 7 4

output:

-1
1

result:

ok 2 number(s): "-1 1"

Test #3:

score: 0
Accepted
time: 2ms
memory: 4080kb

input:

8
2 1
1 2 1
2 1
2 1 1
2 1
1 1 1
2 1
2 2 1
2 1
1 2 1000000000
2 1
2 1 1000000000
2 1
1 1 1000000000
2 1
2 2 1000000000

output:

0
1
-1
-1
0
1
-1
-1

result:

ok 8 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 3776kb

input:

1
2 1
1 2 1

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3800kb

input:

1000
10 10
1 2 1
2 4 1
6 1 1
3 8 1
7 2 1
3 2 1
1 4 1
2 6 1
9 4 1
10 7 1
10 10
4 7 1
10 2 1
8 2 1
9 1 1
1 9 1
4 4 1
10 2 1
4 7 1
8 2 1
9 9 1
10 10
7 5 1
2 2 1
8 7 1
10 9 1
2 7 1
4 6 1
4 1 1
1 2 1
3 8 1
2 1 1
10 10
6 10 1
4 7 1
10 9 1
4 8 1
1 1 1
1 1 1
1 7 1
2 1 1
6 9 1
3 10 1
10 10
6 1 1
9 8 1
8 8 1
...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
0
1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
1
-1
-1
0
-1
1
-1
-1
-...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

1000
10 10
4 10 2
2 3 2
6 8 2
4 5 2
7 3 2
3 7 1
4 4 2
1 9 2
2 4 1
8 2 2
10 10
2 4 1
7 1 1
8 3 1
3 1 2
6 1 2
8 4 1
2 9 2
6 9 1
5 7 1
10 4 1
10 10
9 6 2
9 6 1
5 8 1
10 1 1
9 2 2
3 5 1
6 9 2
1 2 2
5 10 1
8 7 1
10 10
5 7 1
9 2 1
7 7 1
8 6 1
4 6 2
8 8 1
5 10 2
2 10 2
9 1 2
7 7 1
10 10
2 7 2
10 2 1
5 1 2
...

output:

-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
1
-1
0
0
-1
-1
-1
-1
1
1
-1
-1
-1
1
1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
0
-1
-1
1
0
0
1
-1
-1
-1
-1
1
-1
-1
-1
-1
...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 5ms
memory: 3776kb

input:

1000
10 10
7 10 3
5 5 1
4 9 2
3 4 2
1 4 3
9 6 3
10 1 2
5 10 1
10 8 1
1 7 1
10 10
10 1 1
4 7 3
10 7 2
10 10 2
3 10 1
5 10 2
6 2 3
2 1 3
5 1 1
1 6 2
10 10
6 2 2
7 3 3
5 5 3
5 6 2
6 5 1
7 10 3
9 9 1
5 6 3
4 9 3
4 1 1
10 10
6 4 1
9 7 1
6 7 3
7 10 3
8 8 2
3 1 1
6 7 1
10 3 2
1 2 1
8 1 1
10 10
2 9 2
8 3 3
...

output:

0
1
-1
2
-1
-1
1
0
0
-1
1
-1
0
-1
1
-1
-1
-1
-1
1
-1
-1
-1
2
-1
-1
-1
-1
-1
1
1
2
-1
1
-1
-1
2
1
-1
-1
-1
1
-1
1
-1
-1
-1
0
-1
-1
-1
-1
0
-1
0
1
1
-1
1
-1
-1
1
2
-1
-1
1
-1
-1
0
-1
0
-1
0
-1
-1
-1
-1
1
-1
0
-1
0
-1
1
0
0
-1
-1
-1
-1
-1
1
1
-1
2
-1
-1
0
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
0
-1
1
-1
0
-1
0
-...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 5ms
memory: 3736kb

input:

1000
10 10
1 7 1
9 7 4
10 8 4
8 1 10
7 8 6
1 6 8
10 9 10
4 4 8
3 6 8
1 2 10
10 10
5 9 5
3 7 7
4 6 3
1 7 4
2 7 10
6 4 2
7 6 4
8 3 3
2 10 1
7 8 2
10 10
7 8 3
7 8 5
4 9 7
4 2 6
5 10 4
4 6 3
4 1 4
4 10 4
2 7 4
9 2 1
10 10
4 6 8
8 10 2
5 6 8
5 7 9
5 10 6
6 7 5
7 9 2
8 7 10
10 10 5
10 9 10
10 10
9 9 10
1 ...

output:

2
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
1
2
-1
0
-1
-1
-1
-1
0
2
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
0
-1
0
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
0
2
-1
-1
-1
3
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
...

result:

ok 1000 numbers

Test #9:

score: 0
Accepted
time: 5ms
memory: 3860kb

input:

1000
10 10
5 3 21
1 6 60
3 10 31
7 9 51
10 7 64
5 6 85
3 4 85
5 1 7
5 3 52
1 7 17
10 10
1 1 90
2 9 78
9 2 82
9 9 29
2 7 67
8 8 44
7 9 87
8 3 3
9 5 32
5 8 15
10 10
2 8 22
3 2 97
7 7 34
1 6 43
5 9 24
4 7 35
3 3 48
9 4 33
5 10 93
1 7 65
10 10
5 4 85
5 1 40
8 9 48
7 1 57
10 10 69
2 2 69
6 4 14
8 4 43
10...

output:

1
-1
-1
-1
0
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
2
0
0
-1
1
-1
-1
-1
0
-1
3
-1
-1
1
0
-1
-1
-1
-1
0
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
1
1
-1
-1
-1
1
0
-1
2
0
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
0
-1
...

result:

ok 1000 numbers

Test #10:

score: 0
Accepted
time: 6ms
memory: 3804kb

input:

1000
10 10
10 10 268155137
5 10 540061009
1 10 110627680
1 4 533692575
3 5 10438095
6 7 730490278
6 2 985939776
8 10 500039201
1 9 185735931
4 2 729538420
10 10
8 1 326383784
5 3 726281100
4 6 279162422
4 4 243297959
1 2 984988531
3 10 856724546
2 4 627158366
4 5 880246199
9 1 675003875
7 7 76366643...

output:

0
-1
-1
-1
-1
0
-1
2
1
-1
2
-1
-1
-1
-1
1
-1
1
-1
0
-1
2
1
2
-1
-1
0
-1
1
-1
-1
1
-1
-1
-1
-1
-1
-1
0
0
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
-1
0
-1
-1
-1
-1
-1
1
1
1
-1
0
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
0
-1
-1
-1
0
1
-1
2
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
-1
1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
1
0
-1
0
-1...

result:

ok 1000 numbers

Test #11:

score: 0
Accepted
time: 6ms
memory: 3788kb

input:

1000
10 20
8 8 1
5 1 1
5 3 1
2 4 1
6 9 1
10 7 1
6 10 1
4 4 1
7 7 1
2 10 1
1 8 1
7 6 1
4 1 1
6 4 1
6 1 1
8 6 1
4 6 1
9 3 1
4 2 1
4 10 1
10 20
9 10 1
8 1 1
3 1 1
3 6 1
7 1 1
2 2 1
2 10 1
8 5 1
8 2 1
2 1 1
4 9 1
3 8 1
2 10 1
1 7 1
7 2 1
3 6 1
10 1 1
9 6 1
7 5 1
4 3 1
10 20
9 3 1
9 1 1
9 3 1
10 10 1
9 1...

output:

-1
1
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
-1
-1
0
1
-1
-1
-1
-1
-1
0
1
-1
0
-1
-1
-1
-1
0
0
1
1
-1
1
-1
-1
-1
0
-1
0
-1
-1
-1
1
-1
-1
1
-1
-1
1
0
-1
-1
0
0
-1
-1
-1
0
-1
-1
-1
-1
-1
1
-1
-1
-1
1
1
1
0
-1
-1
-1
-1
-1
1
1
-1
1
-1
-1
-1
0
1
1
0
-1
-1
-1
-1
-1
0
0
-1
-1
-1
-1
0
-1
0
...

result:

ok 1000 numbers

Test #12:

score: 0
Accepted
time: 7ms
memory: 4068kb

input:

1000
10 20
6 1 2
6 7 2
9 3 2
2 6 2
1 5 2
9 8 2
2 2 1
5 10 2
8 5 2
4 2 1
2 10 2
8 7 1
8 7 2
8 10 1
3 8 2
3 10 2
4 9 2
5 8 1
8 7 2
7 4 2
10 20
6 9 1
10 6 2
7 9 1
8 1 1
4 7 2
10 10 1
9 8 2
3 1 2
2 2 1
5 7 2
8 7 1
1 8 2
8 2 1
5 5 2
5 1 2
3 1 2
4 9 1
7 2 2
1 6 2
3 1 1
10 20
10 3 2
9 4 2
10 6 2
8 7 1
8 6 ...

output:

-1
-1
2
0
0
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
0
-1
-1
2
-1
-1
-1
-1
1
-1
0
0
1
1
1
1
1
0
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
1
-1
2
0
2
1
-1
-1
1
-1
-1
-1
-1
-1
1
0
-1
-1
-1
-1
0
1
-1
0
2
0
-1
0
-1
2
1
-1
0
-1
-1
2
-1
-1
-1
-1
2
-1
1
-1
-1
0
0
-1
0
0
2
-1
0
0
-1
0
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
1
1
-1
1...

result:

ok 1000 numbers

Test #13:

score: 0
Accepted
time: 7ms
memory: 4068kb

input:

1000
10 20
8 3 1
7 8 3
8 5 3
3 10 3
4 10 2
3 3 3
7 4 1
8 5 1
4 8 3
6 9 3
2 3 1
10 8 1
5 9 3
4 4 3
9 8 2
8 3 1
6 4 1
10 8 1
10 3 1
1 7 2
10 20
1 10 3
9 3 3
1 7 1
2 2 2
8 6 2
9 6 2
3 8 3
8 1 2
7 4 1
7 9 3
10 1 3
9 6 2
6 3 2
6 8 2
8 3 1
2 4 2
5 4 1
3 10 1
5 3 1
2 3 3
10 20
7 6 2
2 2 2
9 6 1
3 8 2
5 7 1...

output:

-1
0
-1
0
0
-1
-1
-1
-1
-1
2
1
-1
-1
-1
-1
-1
0
-1
1
-1
-1
-1
0
-1
-1
-1
2
1
-1
-1
1
-1
-1
2
-1
0
1
1
-1
-1
-1
-1
-1
0
1
1
-1
-1
2
-1
-1
2
2
0
1
-1
0
-1
-1
0
1
-1
1
-1
0
-1
-1
0
1
2
0
0
-1
1
-1
1
0
-1
-1
-1
-1
0
0
-1
-1
0
2
1
0
1
-1
-1
2
1
1
0
0
2
2
1
1
-1
0
0
0
1
0
-1
1
-1
1
0
0
-1
-1
-1
-1
1
-1
-1...

result:

ok 1000 numbers

Test #14:

score: 0
Accepted
time: 9ms
memory: 3784kb

input:

1000
10 20
4 4 7
8 2 9
9 8 2
4 4 7
9 4 8
4 2 10
2 1 8
3 5 10
8 8 8
5 7 9
5 3 2
4 9 7
5 3 2
1 6 5
3 1 10
4 7 4
9 3 4
4 7 7
5 8 8
8 10 1
10 20
6 1 10
8 2 10
4 5 2
6 4 10
1 6 8
8 9 8
6 7 10
8 2 9
1 3 4
6 4 1
5 1 3
4 8 4
1 7 7
5 3 7
1 9 2
9 2 5
5 6 3
2 5 8
1 4 10
3 9 5
10 20
2 7 6
4 8 3
6 4 9
1 4 10
10 ...

output:

-1
-1
1
-1
0
0
-1
-1
0
0
-1
0
0
1
1
2
-1
1
2
0
-1
-1
-1
0
1
-1
-1
-1
-1
-1
1
0
-1
1
0
0
0
1
0
-1
-1
0
0
-1
1
1
1
1
-1
-1
1
0
0
-1
-1
0
1
-1
1
1
1
1
0
1
1
0
1
1
-1
-1
2
-1
0
1
-1
0
2
-1
0
1
0
0
-1
-1
-1
1
1
-1
-1
0
-1
1
1
-1
-1
1
-1
2
1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
0
-1
0
-1
-1
0
-1
-1
3...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 5ms
memory: 3812kb

input:

1000
10 20
2 4 98
7 8 21
7 1 36
6 1 61
4 2 77
1 3 60
5 4 6
6 6 9
4 4 7
7 10 76
4 6 49
6 3 44
3 10 23
9 4 12
7 5 15
2 1 7
3 3 83
4 7 79
8 1 93
10 6 96
10 20
5 5 31
3 8 37
8 8 59
1 8 33
1 9 94
7 7 73
1 9 24
10 3 97
9 5 36
3 1 73
6 3 46
4 2 83
4 4 98
7 7 96
5 10 60
5 2 76
5 2 61
6 4 29
1 10 99
6 3 92
1...

output:

1
0
-1
-1
0
0
-1
1
1
0
0
-1
1
0
0
0
0
1
0
1
-1
0
0
-1
-1
-1
-1
0
1
0
0
1
-1
0
1
-1
-1
1
1
1
2
1
0
-1
-1
0
1
1
1
1
-1
2
0
1
-1
1
1
0
-1
-1
0
-1
0
0
0
1
-1
1
-1
-1
-1
1
0
-1
2
1
-1
1
-1
-1
1
0
-1
1
0
0
-1
0
1
0
1
0
-1
0
0
0
0
1
0
-1
0
0
0
1
2
0
0
1
-1
1
2
0
0
1
-1
1
3
0
-1
0
0
1
0
0
-1
0
1
1
1
1
-1
-1...

result:

ok 1000 numbers

Test #16:

score: 0
Accepted
time: 10ms
memory: 3808kb

input:

1000
10 20
9 8 326353980
1 10 321178299
4 8 970616710
4 9 550923176
8 9 682488932
10 6 752852755
5 10 399703822
10 10 207683413
7 9 84451826
7 8 820433227
7 5 97884128
6 7 1405220
1 5 287655030
8 9 868446569
4 1 421832399
9 4 913601101
2 9 361785960
9 3 425625400
3 9 1891923
8 1 112588430
10 20
6 9 ...

output:

0
-1
0
1
-1
-1
-1
-1
0
-1
1
1
0
2
0
1
0
1
1
-1
-1
2
-1
0
0
1
-1
1
0
2
-1
1
1
1
1
0
0
-1
0
-1
0
0
1
1
1
0
2
-1
2
1
-1
0
0
-1
0
2
3
-1
-1
2
1
0
0
1
3
0
1
1
-1
-1
0
0
-1
1
0
1
1
1
1
0
1
0
1
1
3
0
-1
0
1
-1
-1
1
-1
-1
0
1
1
1
0
-1
0
0
-1
0
1
1
2
1
0
1
0
0
0
0
0
0
-1
-1
-1
-1
-1
1
1
-1
-1
0
1
0
1
-1
2
1
...

result:

ok 1000 numbers

Test #17:

score: 0
Accepted
time: 10ms
memory: 3808kb

input:

1000
10 50
10 1 1
1 5 1
4 1 1
2 7 1
8 4 1
2 10 1
1 4 1
1 10 1
9 6 1
10 6 1
7 7 1
1 6 1
4 3 1
1 5 1
5 4 1
9 10 1
9 4 1
2 6 1
10 10 1
2 10 1
8 1 1
4 6 1
4 4 1
3 6 1
6 1 1
6 5 1
2 7 1
9 6 1
7 3 1
5 4 1
3 10 1
3 1 1
7 7 1
1 5 1
5 7 1
4 8 1
1 6 1
4 3 1
2 10 1
6 3 1
2 1 1
2 6 1
2 3 1
3 4 1
4 1 1
9 6 1
7 1...

output:

0
0
-1
0
-1
0
1
0
-1
-1
0
0
1
0
-1
0
-1
-1
-1
-1
0
0
0
0
0
-1
1
0
1
0
0
1
-1
-1
0
0
1
-1
0
-1
0
0
0
0
0
-1
0
-1
-1
1
1
0
1
0
-1
1
0
0
1
1
0
0
-1
-1
0
1
0
0
0
-1
-1
0
0
1
0
-1
0
0
1
-1
0
-1
-1
-1
-1
1
1
1
-1
-1
1
-1
0
1
1
-1
-1
0
0
0
-1
0
1
0
0
1
1
-1
0
1
-1
0
-1
-1
1
0
1
-1
-1
1
0
-1
1
-1
-1
-1
1
-1...

result:

ok 1000 numbers

Test #18:

score: 0
Accepted
time: 9ms
memory: 3804kb

input:

1000
10 50
8 2 2
4 7 2
1 10 1
1 6 1
3 8 2
9 2 2
10 3 1
5 2 2
5 8 1
8 4 1
7 2 2
1 3 2
1 9 2
6 5 1
1 9 2
8 7 1
6 8 2
5 4 2
5 2 1
3 10 1
1 9 2
5 1 2
10 8 1
7 5 2
4 6 2
6 4 2
3 6 2
3 8 2
4 10 1
5 3 2
7 9 2
9 3 2
8 1 2
3 4 1
9 6 2
4 8 2
7 9 1
6 9 2
10 3 1
7 2 2
6 5 1
7 5 2
10 3 1
9 8 1
10 9 2
10 5 2
3 9 ...

output:

0
0
-1
0
0
1
0
1
0
0
0
0
2
1
0
0
-1
0
1
1
0
-1
0
0
0
1
0
1
1
-1
-1
1
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
1
1
1
0
0
0
0
1
0
0
1
1
1
2
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
2
1
1
1
0
0
0
1
1
1
1
0
0
1
0
0
1
1
1
1
0
0
1
1
1
1
0
1
0
0
1
-1
0
0
1
1
0
0
0
1
1
0
-1
0
0
0
-1
0
0
2
0
-1
0
0
0
1
0
0
0
0
1
0
-1
0
1
0
0
0
1
...

result:

ok 1000 numbers

Test #19:

score: 0
Accepted
time: 16ms
memory: 3784kb

input:

1000
10 50
6 6 3
10 3 3
1 3 1
7 10 2
10 8 1
8 4 3
8 4 2
9 4 1
1 5 3
3 3 2
7 3 1
8 4 2
1 3 3
5 9 3
2 7 1
9 4 2
4 6 1
8 9 1
7 10 3
2 8 1
1 5 3
3 8 2
4 4 3
7 3 2
2 4 2
6 1 2
1 7 1
9 1 1
1 5 3
10 1 3
7 10 2
2 10 3
6 4 2
8 1 3
4 2 2
3 5 3
9 3 1
9 8 1
3 8 3
5 2 2
7 10 1
6 4 3
10 3 2
1 4 1
7 8 2
8 4 2
9 8 ...

output:

0
0
2
0
1
1
0
0
0
0
0
0
0
0
0
0
0
-1
1
0
0
0
1
0
2
0
0
0
0
0
1
0
1
1
1
0
0
0
0
1
0
0
2
0
1
0
0
0
0
0
0
1
0
2
2
0
0
0
0
1
1
0
1
0
0
1
0
2
0
1
0
0
0
0
0
0
0
-1
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
1
1
0
1
0
0
0
0
1
0
...

result:

ok 1000 numbers

Test #20:

score: 0
Accepted
time: 30ms
memory: 3816kb

input:

1000
10 50
5 4 5
4 7 8
10 9 4
6 7 10
9 2 3
2 3 9
5 7 10
2 6 4
4 4 8
9 3 9
1 9 6
2 3 6
8 6 4
2 9 9
9 9 7
4 2 6
9 6 9
5 2 6
1 6 9
6 5 6
5 6 1
4 5 7
6 8 9
2 2 4
3 5 3
6 8 2
4 5 5
2 1 9
3 4 7
10 8 5
1 2 10
9 9 7
4 10 5
10 1 8
10 1 6
7 10 8
10 4 10
9 5 2
10 4 9
8 8 5
3 1 7
6 10 5
4 8 1
6 8 6
6 2 7
5 6 5
...

output:

1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
...

result:

ok 1000 numbers

Test #21:

score: 0
Accepted
time: 57ms
memory: 4076kb

input:

1000
10 50
6 5 76
2 8 63
7 8 83
4 9 100
7 3 28
7 7 60
10 7 8
10 1 49
8 4 16
3 5 51
6 9 84
6 1 43
7 7 36
9 4 97
7 2 39
4 10 41
3 6 68
4 3 1
7 8 53
4 2 74
8 5 5
3 7 63
3 5 38
6 7 25
5 9 83
7 3 85
1 5 72
5 2 15
5 1 51
7 8 56
7 5 13
1 7 98
1 1 17
3 3 26
3 3 19
1 9 10
5 4 17
10 10 56
3 1 90
1 10 42
3 1 2...

output:

0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000 numbers

Test #22:

score: 0
Accepted
time: 63ms
memory: 3792kb

input:

1000
10 50
2 2 954153759
1 3 283444488
8 10 897162377
6 2 701352810
5 8 872948443
6 10 320895294
10 9 697730752
5 4 375661090
3 4 673334850
6 9 215515206
10 7 977251708
6 1 888046403
5 2 292147356
9 9 840382008
3 10 430429980
6 8 921004331
4 10 298467905
7 1 160104863
10 3 444341972
10 4 653051505
9...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
0
0
0
1
0
0
0
1
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
1
1
0
0
1
...

result:

ok 1000 numbers

Test #23:

score: 0
Accepted
time: 59ms
memory: 3852kb

input:

1000
10 500
9 9 1
5 1 1
3 3 1
1 1 1
2 1 1
6 10 1
4 6 1
2 4 1
3 7 1
8 5 1
8 4 1
7 10 1
6 2 1
3 5 1
8 9 1
5 3 1
5 1 1
4 2 1
10 8 1
3 8 1
6 3 1
5 2 1
5 3 1
6 3 1
4 6 1
8 1 1
6 8 1
10 7 1
1 5 1
9 2 1
6 10 1
8 6 1
8 10 1
3 10 1
3 2 1
1 3 1
2 8 1
9 3 1
8 8 1
8 1 1
3 2 1
10 8 1
1 1 1
1 7 1
4 7 1
8 3 1
6 10...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000 numbers

Test #24:

score: 0
Accepted
time: 102ms
memory: 4112kb

input:

1000
10 500
5 7 1
6 2 1
7 3 1
4 7 1
5 9 1
7 4 1
7 6 2
4 10 2
7 4 1
9 3 2
9 5 1
1 9 1
9 4 2
6 7 1
2 3 2
7 7 2
2 4 2
8 8 2
10 8 2
9 7 2
8 10 2
4 4 2
2 7 2
8 7 2
4 6 2
7 9 2
6 8 1
4 3 2
6 1 2
6 2 2
3 5 2
3 10 2
8 2 2
5 9 2
3 6 1
9 10 2
3 5 2
10 1 2
4 10 2
8 8 2
10 4 1
4 5 1
4 9 1
6 1 1
1 7 2
7 1 2
9 5 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000 numbers

Test #25:

score: 0
Accepted
time: 155ms
memory: 3848kb

input:

1000
10 500
5 8 1
5 9 1
10 1 2
5 3 3
1 10 3
10 2 3
4 7 3
4 5 2
2 6 3
6 5 2
8 1 2
3 6 3
7 6 3
2 1 2
1 1 2
9 3 3
10 1 2
2 4 2
6 5 1
10 6 3
5 10 3
2 9 2
2 5 2
7 10 2
1 10 1
8 9 3
9 8 3
2 5 3
7 5 1
1 7 3
4 10 3
9 6 1
5 9 1
8 7 2
9 4 1
10 9 2
2 10 3
3 9 2
4 1 1
9 8 2
10 9 1
4 3 1
8 9 3
2 10 1
5 9 1
6 5 3...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000 numbers

Test #26:

score: 0
Accepted
time: 614ms
memory: 3928kb

input:

1000
10 500
3 8 7
2 6 10
9 1 10
6 7 1
10 10 6
7 1 6
1 5 10
1 8 9
8 1 7
8 1 3
3 7 8
8 10 1
3 1 1
2 9 10
7 9 9
1 4 10
7 5 9
8 10 2
9 9 9
9 10 7
6 5 7
9 4 8
9 3 3
5 4 5
1 9 3
8 5 9
10 5 10
5 4 4
2 4 10
7 6 9
1 6 4
6 10 10
10 10 4
8 7 8
4 4 9
5 7 4
5 10 9
2 2 8
8 8 3
7 7 1
1 6 4
7 8 1
5 2 10
4 9 1
9 10 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000 numbers

Test #27:

score: -100
Time Limit Exceeded

input:

1000
10 500
4 6 30
2 6 44
4 4 52
5 3 43
7 4 18
1 9 46
3 7 9
3 6 83
9 6 58
3 6 58
9 8 100
10 7 62
3 5 64
5 5 53
6 8 95
1 6 12
1 1 72
10 9 93
4 2 82
8 8 73
4 8 32
9 3 92
5 2 75
4 1 92
10 2 83
10 3 57
9 10 13
3 7 37
6 1 100
9 3 12
7 3 67
6 6 14
4 8 86
8 2 4
4 3 8
7 6 15
10 8 56
6 8 98
4 5 30
7 7 36
1 6...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result: