QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167768#4092. 진화Lynkcat#100 ✓927ms279060kbC++202.1kb2023-09-07 17:16:212024-07-04 02:41:35

Judging History

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

  • [2024-07-04 02:41:35]
  • 评测
  • 测评结果：100
  • 用时：927ms
  • 内存：279060kb
查看
  • [2023-09-07 17:16:21]
  • 提交

answer

#include "evolution.h"
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
// #define int ll
#define N 500005
using namespace std;
namespace 
{
    int n;
    multiset<int>S[N],all,S1[N];
    int dis[N],ans[N];
    int ffa[N];
}
inline int mx(multiset<int>&s)
{
    if (s.empty()) return 0;
    return (*--s.end());
}
inline int smx(multiset<int>&s)
{
    if (s.size()<=1) return 0;
    return (*(--(--s.end())))+1;
}
inline int ssmx(multiset<int>&s)
{
    if (s.size()<=2) return 0;
    return (*(--(--(--s.end()))))+1;
}
inline int qry(int k)
{
    return max(mx(S[k]),smx(S[k]));
}
inline int qry1(int k)
{
    return max({mx(S[k])+smx(S[k]),smx(S[k])+ssmx(S[k])});
}
void init()
{
    n=1;
    all.insert(qry1(1));
}
void work(int k,int x)
{
    int fa=ffa[k];
    if (k!=1)
    {
        S[fa].insert(dis[k]);
        S1[fa].insert(ans[k]);
    }
    bool bl=1;
    all.insert(ans[fa]);

    if (k==1) return;
    bl&=(ans[fa]==max({x,qry1(fa),mx(S1[fa])}));
    bl&=(dis[fa]==qry(fa));

    all.insert(ans[fa]);
    // 
    if (bl) return;
    if (fa!=1) S[ffa[fa]].erase(S[ffa[fa]].find(dis[fa]));
    if (fa!=1) S1[ffa[fa]].erase(S1[ffa[fa]].find(ans[fa]));
    ans[fa]=max({x,qry1(fa),mx(S1[fa])});
    dis[fa]=qry(fa);
    work(fa,max(x,ans[fa]));
}

void observation(int P)
{
    ++n;
    ffa[n]=P;
    all.insert(qry1(n));
    work(n,0);
    // cout<<P<<" "<<n<<endl;
    // // cout<<endl;
    // for (int i=1;i<=n;i++) cout<<ans[i]<<' ';
    // cout<<endl;
    // for (int i=1;i<=n;i++) cout<<dis[i]<<' ';
    // cout<<endl;
    // for (int i=1;i<=n;i++) cout<<mx(S[i])<<' ';
    // cout<<endl;
    // for (int i=1;i<=n;i++) cout<<smx(S[i])<<' ';
    // cout<<endl;
    // for (int i=1;i<=n;i++) cout<<ssmx(S[i])<<' ';
    // cout<<endl;
}
int analyze(int R)
{
    // cout<<"qry "<<R<<endl;
    return ans[R];
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 3ms
memory: 51500kb

input:

30
1 1
2 1
2 1
2 1
2 2
1 1
1 3
2 1
2 4
2 3
1 3
1 5
1 4
1 2
2 5
1 7
1 4
2 7
2 7
2 3
1 3
2 6
1 10
1 1
2 13
2 2
1 6
1 1
2 12
1 3

output:

3989776153
7481903423
6741079408

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 3ms
memory: 50860kb

input:

30
2 1
1 1
2 1
1 1
2 3
2 2
2 2
1 3
1 3
1 5
2 3
2 6
2 5
1 5
2 3
1 1
1 5
2 5
1 6
2 10
1 8
1 1
2 7
1 4
2 1
2 12
1 5
1 10
2 15
1 14

output:

4085837229
8898398677
7224337819

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 4ms
memory: 52216kb

input:

30
2 1
1 1
2 2
2 1
2 1
1 2
1 3
2 1
2 3
1 3
1 3
1 6
2 7
1 7
1 8
2 5
2 8
2 8
2 8
2 1
2 3
1 2
1 7
2 8
1 3
1 1
2 9
1 2
1 13
1 10

output:

3655449673
6979384347
7116385622

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 4ms
memory: 52472kb

input:

29
1 1
2 1
2 1
1 1
1 2
2 1
2 1
1 4
2 2
1 1
2 5
2 6
2 1
1 2
2 7
2 2
1 2
1 7
2 8
1 3
2 5
2 6
2 10
1 9
1 10
2 2
1 7
1 11
1 8

output:

5020315711
8126182581
7528146226

result:

ok 3 lines

Test #5:

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

input:

28
1 1
1 1
1 2
1 1
2 5
2 4
2 2
1 4
2 5
1 3
1 7
1 8
2 7
2 4
2 2
2 1
2 9
1 3
2 9
1 4
1 8
2 7
2 5
2 9
2 8
1 6
2 6
1 6

output:

3863214647
9004572285
6917008405

result:

ok 3 lines

Test #6:

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

input:

30
2 1
2 1
2 1
2 1
1 1
2 1
1 2
1 2
2 4
2 2
1 1
1 4
1 4
1 6
1 7
2 5
2 2
1 9
1 9
2 6
1 9
2 1
1 12
1 13
2 6
1 8
2 1
2 7
1 15
2 11

output:

3652881517
6273534925
8008251562

result:

ok 3 lines

Test #7:

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

input:

29
1 1
2 2
1 1
1 2
1 4
2 2
1 5
2 2
1 6
2 4
2 4
2 5
2 1
2 2
1 7
1 2
1 7
1 4
2 5
1 11
2 3
2 5
1 11
2 1
1 11
2 8
1 14
2 5
2 1

output:

3725140493
7344134703
8142212909

result:

ok 3 lines

Test #8:

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

input:

30
2 1
2 1
2 1
1 1
2 2
2 2
1 2
2 1
2 2
1 2
1 4
1 4
1 3
1 4
1 4
1 9
1 3
2 3
2 9
2 2
1 10
2 5
2 2
2 9
1 12
2 2
1 9
2 10
1 14
1 15

output:

4216385963
6981773419
9451704565

result:

ok 3 lines

Test #9:

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

input:

29
2 1
2 1
1 1
2 2
2 1
1 1
1 3
2 3
2 2
1 4
1 1
2 1
1 6
1 3
1 5
1 5
1 7
1 8
1 9
2 4
2 6
1 13
2 9
2 11
2 11
2 2
1 8
2 1
1 15

output:

2671636536
8087981266
7681836138

result:

ok 3 lines

Test #10:

score: 0
Accepted
time: 4ms
memory: 51528kb

input:

30
2 1
1 1
1 1
2 1
2 3
2 1
1 3
2 3
2 1
1 1
1 5
2 5
1 2
1 7
2 7
2 1
1 7
2 7
1 5
1 9
2 5
1 10
2 5
2 3
1 12
1 10
2 3
2 5
1 9
1 10

output:

5734571725
8303927063
9400323222

result:

ok 3 lines

Test #11:

score: 0
Accepted
time: 4ms
memory: 52112kb

input:

30
1 1
1 1
1 1
1 2
1 2
1 2
1 7
1 4
1 3
1 7
1 9
1 6
1 7
1 7
1 10
2 7
2 1
2 1
2 1
2 2
2 1
2 1
2 1
2 3
2 4
2 1
2 4
2 1
2 1
2 1

output:

7775546089
5981974793
8038532257

result:

ok 3 lines

Test #12:

score: 0
Accepted
time: 3ms
memory: 52128kb

input:

30
1 1
1 2
1 2
1 4
1 2
1 6
1 4
1 8
1 8
1 8
1 7
1 12
1 11
1 14
1 12
2 5
2 1
2 1
2 3
2 2
2 4
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1

output:

6133216433
6334176229
10274413981

result:

ok 3 lines

Test #13:

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

input:

30
1 1
1 2
1 2
1 2
1 5
1 4
1 7
1 3
1 6
1 2
1 6
1 10
1 12
1 12
1 14
2 1
2 1
2 2
2 3
2 3
2 3
2 1
2 1
2 1
2 1
2 6
2 2
2 1
2 2
2 1

output:

7011904871
7447892923
7896128456

result:

ok 3 lines

Test #14:

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

input:

30
1 1
1 1
1 2
1 4
1 5
1 2
1 5
1 6
1 2
1 8
1 8
1 12
1 11
1 13
1 11
2 1
2 3
2 1
2 1
2 9
2 8
2 1
2 1
2 3
2 9
2 1
2 4
2 1
2 1
2 1

output:

7235939759
6270114761
8318033369

result:

ok 3 lines

Test #15:

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

input:

30
1 1
1 1
1 2
1 1
1 1
1 5
1 6
1 3
1 7
1 6
1 5
1 5
1 9
1 6
1 10
2 1
2 1
2 1
2 4
2 1
2 1
2 5
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 7

output:

6065360561
6104872627
10436812948

result:

ok 3 lines

Test #16:

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

input:

30
2 1
1 1
2 1
2 2
1 2
2 1
2 2
1 3
1 4
1 4
1 4
1 7
2 2
2 2
2 3
1 7
1 7
1 4
2 1
1 10
1 5
2 13
2 12
2 6
1 8
1 13
2 13
2 15
1 9
2 16

output:

3738213511
6482823973
8216824708

result:

ok 3 lines

Test #17:

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

input:

30
1 1
2 1
2 1
1 2
1 3
2 3
2 4
2 1
2 2
2 4
1 4
1 5
1 4
2 2
2 1
2 3
1 4
1 6
1 9
2 9
2 10
2 7
1 9
2 1
1 6
2 11
1 2
1 4
1 14
1 12

output:

4693745583
7742558919
7646775389

result:

ok 3 lines

Test #18:

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

input:

30
1 1
1 2
1 3
1 4
2 1
2 5
2 2
2 4
2 1
1 4
2 1
1 6
1 4
2 1
1 1
2 8
2 2
2 8
1 6
2 4
2 9
2 6
1 2
1 5
1 4
1 5
2 3
1 2
1 2
2 4

output:

4570815573
5702629941
7848389807

result:

ok 3 lines

Test #19:

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

input:

30
1 1
1 2
2 1
2 2
2 1
2 1
1 3
2 2
2 1
1 4
1 4
2 6
2 5
1 4
2 5
2 4
2 2
2 2
2 1
1 1
1 2
1 5
1 3
1 4
1 6
2 11
1 8
1 10
1 7
2 3

output:

5214538151
7726306013
7485674391

result:

ok 3 lines

Test #20:

score: 0
Accepted
time: 3ms
memory: 51168kb

input:

30
1 1
1 2
1 3
2 3
2 1
1 4
1 4
2 4
2 6
2 1
1 6
1 7
2 6
2 3
2 7
2 2
2 5
2 8
2 7
1 7
1 9
2 1
1 9
1 2
2 8
1 2
1 13
1 2
2 5
1 5

output:

4806816967
7308341709
6988462606

result:

ok 3 lines

Test #21:

score: 0
Accepted
time: 4ms
memory: 52380kb

input:

30
1 1
2 2
2 2
1 2
1 2
2 1
1 3
1 5
1 6
2 5
1 6
2 8
2 1
1 7
2 3
2 4
1 8
1 8
2 3
1 6
2 4
2 8
1 10
2 3
2 5
2 10
2 8
1 7
1 2
1 7

output:

5702183321
7697492445
6404427529

result:

ok 3 lines

Test #22:

score: 0
Accepted
time: 3ms
memory: 51976kb

input:

30
2 1
2 1
1 1
2 1
2 1
1 2
1 3
1 4
1 4
1 6
2 2
1 6
2 3
2 1
1 2
2 3
2 2
1 8
2 8
1 4
2 4
2 8
1 1
1 11
2 2
1 10
1 4
1 15
2 6
2 10

output:

5747397881
6661658357
8996758003

result:

ok 3 lines

Test #23:

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

input:

30
2 1
2 1
2 1
1 1
1 2
1 3
2 4
1 3
1 3
1 5
1 7
1 4
1 6
2 3
2 1
1 1
2 11
1 9
2 3
1 11
2 10
2 13
2 3
2 3
1 2
1 6
2 14
2 12
2 6
1 6

output:

4675237001
7243073851
9074221286

result:

ok 3 lines

Test #24:

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

input:

30
2 1
1 1
2 1
2 2
2 2
1 2
2 2
2 3
1 3
1 1
2 1
1 4
1 6
2 4
1 5
1 2
1 2
2 4
2 2
2 7
1 6
2 10
1 2
1 11
1 13
1 6
1 10
2 5
2 7
2 3

output:

4325089139
6920647293
7948900553

result:

ok 3 lines

Test #25:

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

input:

30
2 1
1 1
2 1
1 1
1 1
1 1
1 2
2 3
1 5
2 1
2 1
1 6
1 7
1 9
2 10
2 1
1 8
2 7
2 5
2 4
1 8
1 3
2 3
1 7
2 3
1 12
1 12
2 2
2 11
2 13

output:

3833877395
7849657363
7425325851

result:

ok 3 lines

Test #26:

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

input:

30
2 1
2 1
1 1
1 2
2 3
1 3
2 2
1 3
2 4
1 5
1 6
2 6
1 4
1 6
2 9
1 5
1 3
2 1
2 3
2 5
2 7
2 6
1 8
1 10
2 1
1 12
2 6
1 8
1 3
2 14

output:

5090644709
8207166119
7214047711

result:

ok 3 lines

Test #27:

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

input:

30
1 1
2 2
1 2
2 2
2 1
2 2
1 3
1 4
2 3
1 4
1 1
1 4
2 8
1 1
1 1
2 1
2 6
1 5
2 2
2 3
2 1
1 9
2 12
1 7
1 4
2 9
2 14
1 13
1 11
2 15

output:

5178034157
8107774363
7080979268

result:

ok 3 lines

Test #28:

score: 0
Accepted
time: 4ms
memory: 52080kb

input:

30
1 1
2 2
2 2
2 2
2 2
1 2
2 3
2 3
1 3
1 4
1 4
2 3
1 4
2 2
2 7
2 6
1 5
2 2
1 5
2 9
1 7
1 9
2 6
1 2
1 3
1 11
1 4
2 1
2 5
1 5

output:

4211069353
8168855675
8911723060

result:

ok 3 lines

Test #29:

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

input:

30
2 1
1 1
1 1
2 2
2 1
1 2
1 1
1 4
1 6
2 7
1 3
2 7
2 3
1 1
2 1
2 2
1 6
1 1
1 6
1 10
2 2
1 3
1 7
2 2
2 8
2 8
1 11
2 2
2 7
2 11

output:

4096414487
7265766149
8171354152

result:

ok 3 lines

Test #30:

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

input:

30
1 1
1 2
1 3
1 3
1 4
1 3
1 5
1 5
1 4
1 6
1 11
1 9
1 13
1 14
1 13
2 3
2 1
2 3
2 2
2 1
2 1
2 3
2 1
2 1
2 1
2 6
2 1
2 1
2 2
2 1

output:

6208849637
6397786567
10847712031

result:

ok 3 lines

Test #31:

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

input:

30
1 1
1 1
1 3
1 1
1 4
1 6
1 6
1 4
1 6
1 10
1 8
1 12
1 11
1 11
1 7
2 1
2 1
2 1
2 1
2 1
2 1
2 2
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1

output:

8630760759
6645585839
7499274594

result:

ok 3 lines

Test #32:

score: 0
Accepted
time: 4ms
memory: 52212kb

input:

30
1 1
1 1
1 3
1 3
1 2
1 6
1 6
1 4
1 8
1 6
1 11
1 11
1 10
1 10
1 13
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1

output:

7848960625
8197325795
7613386658

result:

ok 3 lines

Test #33:

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

input:

30
1 1
1 2
1 3
1 1
1 3
1 4
1 7
1 8
1 9
1 10
1 10
1 7
1 13
1 13
1 14
2 3
2 1
2 1
2 3
2 4
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 2
2 1

output:

6641072129
6480327839
11121578914

result:

ok 3 lines

Test #34:

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

input:

30
1 1
1 1
1 2
1 3
1 5
1 3
1 7
1 8
1 7
1 9
1 8
1 11
1 10
1 14
1 15
2 1
2 1
2 7
2 1
2 1
2 3
2 10
2 5
2 1
2 1
2 4
2 1
2 1
2 1
2 1

output:

7663312763
7556579533
7044923063

result:

ok 3 lines

Test #35:

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

input:

30
1 1
1 2
1 2
1 1
1 3
1 6
1 4
1 5
1 9
1 8
1 10
1 11
1 5
1 14
1 13
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 1
2 4
2 1
2 6
2 1

output:

5761711633
7367929517
10205437603

result:

ok 3 lines

Test #36:

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

input:

29
2 1
1 1
1 1
2 1
1 3
2 3
1 4
2 1
1 2
2 1
1 5
1 2
2 1
1 4
1 9
1 9
1 10
2 3
2 1
2 3
2 3
2 6
2 1
1 10
1 8
2 8
2 2
1 13
1 14

output:

6252442258
5055070144
7607858420

result:

ok 3 lines

Test #37:

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

input:

28
1 1
2 1
2 2
1 1
2 3
2 2
1 2
2 4
2 1
1 3
2 4
1 5
2 4
1 3
2 1
1 7
1 7
2 3
2 3
2 3
1 8
2 1
1 9
2 2
1 11
2 7
1 12
1 10

output:

4575912253
7564835103
7440019979

result:

ok 3 lines

Test #38:

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

input:

26
2 1
1 1
2 1
2 1
2 2
2 2
2 1
1 1
1 1
1 3
2 1
1 4
1 2
2 5
2 1
1 2
2 3
1 6
1 3
1 9
1 11
1 6
1 10
2 4
2 4
1 3

output:

2698850804
6609353536
5086904239

result:

ok 3 lines

Test #39:

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

input:

30
1 1
2 2
2 1
1 2
1 2
2 2
2 2
2 2
1 3
2 1
2 1
2 1
2 2
1 4
2 4
1 6
1 4
1 4
2 1
1 9
2 3
1 4
2 1
1 10
1 10
1 5
2 1
1 1
1 9
2 2

output:

7413943993
8110462931
7555990679

result:

ok 3 lines

Test #40:

score: 0
Accepted
time: 3ms
memory: 51228kb

input:

30
1 1
2 1
2 2
2 1
2 1
2 1
1 1
2 2
1 2
1 2
1 3
2 3
1 3
2 1
1 4
2 3
2 7
1 4
1 5
1 5
1 6
2 4
1 12
1 13
1 14
2 1
2 2
2 4
1 15
2 6

output:

4683630535
5923048231
9341976550

result:

ok 3 lines

Test #41:

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

input:

29
2 1
1 1
1 1
1 2
2 4
1 2
1 3
2 1
2 1
2 2
2 3
2 2
2 2
2 2
1 3
1 4
1 4
2 2
1 9
1 10
2 1
1 11
2 3
1 12
2 1
2 5
1 13
2 5
1 14

output:

5402194083
8220084679
8034822586

result:

ok 3 lines

Test #42:

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

input:

30
1 1
2 1
2 1
2 2
2 1
1 1
1 2
2 1
2 3
2 2
1 2
1 1
1 1
1 2
2 6
1 2
1 2
2 2
2 4
2 4
1 1
2 5
1 2
1 2
2 2
2 7
1 2
1 2
2 4
1 2

output:

4408158587
8574650327
7855430431

result:

ok 3 lines

Test #43:

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

input:

30
2 1
1 1
2 1
1 1
2 2
2 1
2 1
1 1
1 1
1 1
2 1
2 2
2 1
1 1
2 2
1 2
1 1
2 6
1 2
2 7
1 1
1 2
2 7
1 1
2 1
2 2
1 1
1 2
2 10
1 1

output:

4991313051
7858485995
6619364293

result:

ok 3 lines

Test #44:

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

input:

30
2 1
2 1
2 1
2 1
2 1
1 1
2 2
2 2
2 2
1 2
1 2
2 1
2 3
1 3
1 4
1 5
1 1
1 1
1 7
1 9
2 10
1 2
1 9
2 6
1 4
2 2
2 12
1 11
2 5
1 12

output:

3638320765
8918971937
8185731020

result:

ok 3 lines

Test #45:

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

input:

30
1 1
1 2
1 3
1 2
1 4
2 6
2 6
1 5
2 1
1 1
2 1
1 1
2 9
2 7
1 6
2 1
1 5
2 7
1 1
2 7
2 1
1 2
1 8
1 6
2 13
2 1
1 5
2 1
2 3
2 11

output:

4913879207
7116642941
6413091141

result:

ok 3 lines

Test #46:

score: 0
Accepted
time: 4ms
memory: 52756kb

input:

20
1 1
2 2
2 1
1 2
1 3
2 3
1 4
2 1
2 2
2 2
2 5
1 2
1 6
1 3
2 8
2 7
1 6
1 1
1 9
2 1

output:

2173193534
5693784896
5225829218

result:

ok 3 lines

Test #47:

score: 0
Accepted
time: 4ms
memory: 51376kb

input:

30
2 1
1 1
2 1
2 2
1 2
2 2
1 2
1 1
1 4
2 4
1 4
1 3
1 7
2 7
2 6
1 6
2 7
2 2
1 3
2 2
1 2
1 1
1 2
1 1
2 1
2 9
2 1
2 1
1 9
2 16

output:

3738649353
7300858859
9229259764

result:

ok 3 lines

Test #48:

score: 0
Accepted
time: 3ms
memory: 51584kb

input:

30
1 1
1 2
2 2
2 2
1 2
2 3
2 1
1 3
2 4
2 3
2 4
1 4
1 2
2 1
1 7
1 8
1 4
2 8
2 8
2 7
1 7
1 3
1 6
1 4
2 4
2 2
1 1
2 1
2 6
1 4

output:

5178350073
5813923461
7735393460

result:

ok 3 lines

Test #49:

score: 0
Accepted
time: 4ms
memory: 51676kb

input:

30
2 1
2 1
1 1
1 1
1 2
2 3
1 2
1 5
2 5
1 4
2 2
1 2
2 3
2 4
1 5
2 9
1 7
1 2
2 3
2 11
2 5
1 3
2 6
1 10
2 2
2 13
1 4
1 10
2 3
1 2

output:

4248552345
8835646427
7653571538

result:

ok 3 lines

Test #50:

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

input:

30
2 1
2 1
1 1
2 2
1 1
2 2
2 1
2 3
2 2
2 3
1 3
1 1
1 5
1 2
1 6
2 4
2 3
2 1
2 3
1 2
1 4
1 10
2 1
2 9
1 5
1 6
1 1
1 3
2 14
1 2

output:

4386022965
5782499067
9482880110

result:

ok 3 lines

Test #51:

score: 0
Accepted
time: 4ms
memory: 51376kb

input:

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

output:

1619655175
1460517425
2220931278

result:

ok 3 lines

Test #52:

score: 0
Accepted
time: 4ms
memory: 51956kb

input:

12
1 1
1 1
1 2
1 2
1 2
1 3
2 1
1 6
2 2
1 6
2 6
2 1

output:

2016439266
2224141548
2273063622

result:

ok 3 lines

Subtask #2:

score: 11
Accepted

Dependency #1:

100%
Accepted

Test #53:

score: 11
Accepted
time: 6ms
memory: 53616kb

input:

3015
1 1
1 1
1 1
1 1
1 4
1 5
1 3
1 2
1 7
1 6
1 11
1 4
1 4
1 1
1 13
1 1
1 4
1 3
1 7
1 2
1 17
1 6
1 11
1 19
1 24
1 16
1 21
1 4
1 2
1 29
1 12
1 26
1 32
1 5
1 9
1 30
1 35
1 12
1 21
1 29
1 27
1 28
1 40
1 10
1 26
1 24
1 14
1 15
1 45
1 26
1 32
1 41
1 24
1 5
1 34
1 47
1 32
1 21
1 44
1 35
1 20
1 60
1 10
1 57...

output:

3812378205
7124002119
7385843022

result:

ok 3 lines

Test #54:

score: 0
Accepted
time: 8ms
memory: 51932kb

input:

3015
1 1
1 1
1 1
1 3
1 4
1 3
1 6
1 5
1 2
1 5
1 9
1 10
1 5
1 13
1 15
1 8
1 3
1 12
1 5
1 6
1 4
1 20
1 18
1 1
1 25
1 22
1 15
1 19
1 13
1 14
1 11
1 26
1 31
1 16
1 31
1 7
1 25
1 9
1 37
1 29
1 39
1 14
1 16
1 22
1 17
1 37
1 6
1 17
1 14
1 50
1 29
1 42
1 28
1 5
1 24
1 9
1 48
1 51
1 44
1 3
1 51
1 13
1 47
1 52...

output:

3205033017
8690673449
7728275406

result:

ok 3 lines

Test #55:

score: 0
Accepted
time: 8ms
memory: 53404kb

input:

2915
1 1
1 2
1 2
1 3
1 3
1 2
1 1
1 6
1 2
1 7
1 5
1 5
1 7
1 12
1 11
1 6
1 7
1 7
1 15
1 2
1 10
1 21
1 17
1 14
1 15
1 26
1 2
1 5
1 23
1 11
1 17
1 3
1 19
1 31
1 24
1 36
1 20
1 29
1 38
1 35
1 28
1 41
1 39
1 23
1 10
1 33
1 9
1 10
1 29
1 25
1 5
1 37
1 38
1 50
1 47
1 53
1 4
1 6
1 20
1 41
1 3
1 37
1 60
1 2
1...

output:

3827264693
7806373447
8705403388

result:

ok 3 lines

Test #56:

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

input:

2965
1 1
1 1
1 2
1 1
1 2
1 4
1 6
1 1
1 5
1 5
1 11
1 6
1 2
1 14
1 3
1 15
1 14
1 10
1 3
1 17
1 5
1 12
1 13
1 16
1 10
1 4
1 17
1 13
1 19
1 29
1 6
1 27
1 19
1 16
1 30
1 1
1 23
1 11
1 39
1 3
1 15
1 27
1 14
1 20
1 41
1 12
1 44
1 13
1 45
1 24
1 25
1 21
1 5
1 16
1 5
1 15
1 54
1 1
1 32
1 4
1 10
1 8
1 38
1 62...

output:

4548716203
8104224579
8639034524

result:

ok 3 lines

Test #57:

score: 0
Accepted
time: 4ms
memory: 52788kb

input:

2815
1 1
1 2
1 1
1 1
1 2
1 5
1 7
1 2
1 2
1 5
1 2
1 4
1 8
1 4
1 5
1 12
1 10
1 14
1 5
1 17
1 17
1 6
1 6
1 21
1 11
1 1
1 25
1 22
1 16
1 11
1 5
1 6
1 29
1 11
1 28
1 15
1 37
1 19
1 32
1 32
1 31
1 38
1 26
1 18
1 35
1 2
1 47
1 19
1 33
1 28
1 26
1 39
1 27
1 24
1 47
1 18
1 29
1 21
1 35
1 31
1 41
1 40
1 34
1 ...

output:

4950594213
6124328575
7459155982

result:

ok 3 lines

Test #58:

score: 0
Accepted
time: 4ms
memory: 51908kb

input:

1515
1 1
1 1
1 2
1 2
1 5
1 4
1 7
1 2
1 6
1 5
1 1
1 4
1 1
1 8
1 15
1 2
1 15
1 18
1 1
1 7
1 19
1 9
1 19
1 18
1 18
1 14
1 14
1 17
1 18
1 28
1 10
1 22
1 19
1 7
1 7
1 25
1 11
1 18
1 19
1 3
1 26
1 41
1 28
1 33
1 41
1 22
1 13
1 47
1 44
1 21
1 14
1 34
1 50
1 9
1 32
1 47
1 19
1 9
1 20
1 25
1 46
1 4
1 16
1 55...

output:

4323824491
9574111045
8752771679

result:

ok 3 lines

Test #59:

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

input:

1315
1 1
1 2
1 2
1 2
1 2
1 1
1 2
1 3
1 5
1 1
1 5
1 8
1 10
1 6
1 6
2 8
1 10
1 13
1 14
1 12
1 12
1 2
1 16
1 15
1 9
1 6
1 22
1 2
1 14
1 10
1 5
1 5
1 27
1 4
1 7
1 35
1 12
1 12
1 22
1 18
1 35
1 5
1 12
1 6
1 19
1 20
1 15
1 43
2 32
1 11
1 7
1 1
1 23
1 2
1 14
1 40
1 47
1 29
1 47
1 18
1 17
1 28
1 41
1 45
1 3...

output:

3936826949
6011294393
7487868885

result:

ok 3 lines

Test #60:

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

input:

815
1 1
1 2
1 3
1 2
1 4
1 2
1 7
1 5
1 5
1 6
1 5
1 1
1 13
1 3
1 3
1 8
1 16
1 1
1 19
1 17
1 21
1 6
1 1
1 1
1 18
1 6
1 21
1 10
1 17
1 11
1 8
1 19
1 31
1 18
1 13
1 23
1 29
1 29
1 35
1 13
2 5
1 31
1 27
1 38
1 18
1 40
1 12
1 8
1 4
1 44
1 49
1 25
1 5
1 49
1 28
1 37
1 19
1 19
1 45
1 27
1 1
1 36
1 60
1 45
1 ...

output:

4514408221
7913831329
7956386472

result:

ok 3 lines

Test #61:

score: 0
Accepted
time: 4ms
memory: 52052kb

input:

2915
1 1
1 2
1 3
1 2
1 3
1 4
1 3
1 5
1 1
1 10
1 7
1 11
1 5
1 6
1 8
1 12
1 15
1 5
1 16
1 14
1 19
1 9
1 17
1 24
1 20
1 24
1 4
1 12
1 9
1 30
1 23
1 31
1 8
1 15
1 24
1 24
1 33
1 22
1 26
2 4
2 28
1 38
1 32
1 9
1 9
1 24
1 26
1 6
1 18
1 17
1 23
1 27
1 44
1 34
1 40
1 15
1 16
1 36
1 32
1 20
2 35
1 10
1 45
1 ...

output:

3599125575
7076397899
6238649710

result:

ok 3 lines

Test #62:

score: 0
Accepted
time: 3ms
memory: 52596kb

input:

1815
1 1
1 2
1 1
1 1
1 4
1 5
1 1
1 4
1 6
1 9
1 1
1 5
1 5
1 6
1 14
1 12
1 16
1 1
1 3
1 7
1 8
1 19
1 21
1 16
1 20
1 13
1 3
1 11
1 24
1 4
1 29
1 2
1 23
1 14
1 11
1 1
1 32
1 22
1 31
1 17
1 16
1 32
1 26
1 41
1 8
1 23
1 23
1 32
1 8
1 50
1 10
1 37
1 9
1 17
1 10
1 40
1 5
1 1
1 11
1 30
1 3
1 5
1 32
1 32
1 51...

output:

3818060631
7340868249
7537900225

result:

ok 3 lines

Test #63:

score: 0
Accepted
time: 13ms
memory: 52532kb

input:

3015
1 1
1 2
1 1
1 3
1 4
1 4
1 4
1 7
1 7
1 10
1 10
1 5
1 11
1 14
1 15
1 10
1 15
1 13
1 19
1 16
1 17
1 20
1 22
1 24
1 11
1 26
1 23
1 21
1 28
1 24
1 26
1 32
1 25
1 25
1 33
1 32
1 35
1 32
1 34
1 35
1 36
1 41
1 35
1 42
1 39
1 45
1 34
1 48
1 47
1 44
1 48
1 49
1 47
1 41
1 53
1 55
1 54
1 55
1 59
1 60
1 50
...

output:

3130283937
8492729883
9183989000

result:

ok 3 lines

Test #64:

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

input:

3015
1 1
1 1
1 1
1 3
1 2
1 5
1 4
1 8
1 9
1 9
1 11
1 12
1 12
1 5
1 15
1 12
1 17
1 9
1 16
1 19
1 21
1 11
1 22
1 22
1 25
1 25
1 20
1 27
1 26
1 27
1 17
1 32
1 27
1 33
1 30
1 36
1 27
1 37
1 39
1 26
1 41
1 37
1 43
1 42
1 44
1 42
1 45
1 45
1 48
1 50
1 48
1 51
1 52
1 54
1 55
1 54
1 51
1 52
1 58
1 57
1 57
1 ...

output:

5691236667
9132561699
9108165625

result:

ok 3 lines

Test #65:

score: 0
Accepted
time: 3ms
memory: 53348kb

input:

3015
1 1
1 1
1 1
1 2
1 5
1 6
1 4
1 4
1 8
1 10
1 7
1 11
1 6
1 14
1 15
1 14
1 17
1 9
1 16
1 13
1 19
1 17
1 22
1 24
1 18
1 24
1 18
1 26
1 28
1 29
1 30
1 32
1 32
1 34
1 31
1 34
1 28
1 35
1 27
1 37
1 39
1 35
1 41
1 36
1 37
1 45
1 42
1 40
1 45
1 50
1 45
1 36
1 51
1 45
1 52
1 52
1 55
1 54
1 57
1 59
1 59
1 ...

output:

6438765891
8469233791
6941286241

result:

ok 3 lines

Test #66:

score: 0
Accepted
time: 4ms
memory: 52200kb

input:

2915
1 1
1 1
1 1
1 2
1 2
1 6
1 7
1 7
1 4
1 5
1 9
1 11
1 13
1 12
1 14
1 8
1 11
1 14
1 17
1 20
1 19
1 20
1 18
1 19
1 25
1 22
1 21
1 24
1 28
1 21
1 27
1 26
1 24
1 31
1 35
1 30
1 35
1 29
1 37
1 40
1 40
1 32
1 28
1 42
1 39
1 34
1 47
1 48
1 40
1 45
1 49
1 49
1 53
1 45
1 47
1 47
1 46
1 58
1 56
1 58
1 58
1 ...

output:

6915950111
7963718417
5934181997

result:

ok 3 lines

Test #67:

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

input:

2815
1 1
1 1
1 1
1 2
1 2
1 5
1 5
1 8
1 4
1 10
1 9
1 11
1 12
1 11
1 14
1 14
1 17
1 14
1 12
1 11
1 19
1 22
1 20
1 23
1 21
1 25
1 27
1 27
1 29
1 24
1 31
1 23
1 28
1 20
1 33
1 33
1 36
1 37
1 36
1 40
1 35
1 39
1 42
1 42
1 41
1 34
1 40
1 43
1 47
1 49
1 48
1 51
1 53
1 53
1 54
1 56
1 56
1 58
1 55
1 60
1 53
...

output:

5874782401
8982130927
6400812298

result:

ok 3 lines

Test #68:

score: 0
Accepted
time: 8ms
memory: 53208kb

input:

2715
1 1
1 2
1 1
1 3
1 5
1 5
1 3
1 7
1 8
1 10
1 11
1 8
1 13
1 11
1 13
1 13
1 15
2 8
2 2
1 16
1 18
1 15
1 20
1 20
2 5
1 21
1 23
1 20
1 21
1 18
1 27
1 29
1 26
1 20
1 29
1 28
1 29
1 31
1 30
1 36
1 29
1 32
1 28
1 39
1 38
1 42
1 39
1 41
1 44
1 35
1 48
1 44
1 48
1 49
1 47
1 52
1 54
1 49
1 56
1 56
1 58
1 5...

output:

8728367729
8302038551
9373485874

result:

ok 3 lines

Test #69:

score: 0
Accepted
time: 3ms
memory: 52404kb

input:

1215
1 1
1 1
1 3
1 1
1 5
1 3
1 7
1 6
1 9
1 10
1 7
1 9
1 13
1 12
1 13
1 12
1 15
1 17
1 16
1 20
1 21
1 22
1 22
1 17
1 23
1 23
1 22
1 23
1 26
1 25
1 22
1 32
1 27
1 33
1 33
1 32
1 37
1 38
1 34
1 38
1 41
1 42
1 37
1 44
1 44
1 42
1 42
1 46
1 45
1 46
1 51
1 52
1 46
1 50
1 47
1 54
1 48
1 57
1 57
1 60
1 58
1...

output:

6752456231
4729175127
7299976398

result:

ok 3 lines

Test #70:

score: 0
Accepted
time: 4ms
memory: 52516kb

input:

1515
1 1
1 2
1 3
1 4
1 5
1 6
1 3
1 8
1 7
1 10
1 10
1 10
1 11
1 13
1 11
1 9
1 13
1 12
1 18
1 20
1 16
1 22
1 19
1 24
1 21
1 26
1 24
1 24
1 23
1 28
1 29
1 30
1 24
1 34
1 25
1 33
1 34
1 36
1 37
1 40
1 40
1 40
1 41
1 40
1 40
1 44
1 44
1 33
1 41
1 49
1 43
1 44
1 48
1 54
1 52
1 45
1 53
1 54
1 59
1 60
1 61
...

output:

8302091387
7902444721
7452757244

result:

ok 3 lines

Test #71:

score: 0
Accepted
time: 12ms
memory: 52328kb

input:

1415
1 1
1 1
1 3
1 3
1 4
1 5
1 5
1 7
1 9
1 9
1 10
1 9
1 9
1 8
1 12
1 10
1 8
1 12
1 16
1 13
1 17
1 22
1 21
2 12
1 20
1 13
1 26
1 27
1 26
1 27
1 29
1 30
1 24
1 28
1 33
1 30
1 30
1 35
1 35
1 36
1 36
1 27
1 41
1 41
1 40
1 42
1 46
1 40
1 47
1 40
1 45
1 48
1 49
1 48
1 50
1 50
1 53
1 56
1 55
1 56
1 60
1 56...

output:

4998662923
5736163283
7538384672

result:

ok 3 lines

Test #72:

score: 0
Accepted
time: 3ms
memory: 51568kb

input:

1315
1 1
1 1
1 3
1 4
1 5
1 5
1 7
1 7
1 9
1 4
1 9
1 8
1 7
1 11
1 13
1 16
1 13
1 14
1 16
1 20
1 20
1 10
1 18
1 13
1 24
1 21
1 23
1 10
1 14
1 20
1 31
1 28
1 24
1 34
1 34
1 32
1 37
1 36
1 26
1 40
1 35
1 41
1 40
1 44
1 44
1 46
1 38
1 43
1 48
1 46
1 43
1 42
1 48
1 54
1 54
1 49
1 57
1 55
1 56
1 54
1 61
1 5...

output:

5651338735
6796880393
8494476404

result:

ok 3 lines

Test #73:

score: 0
Accepted
time: 14ms
memory: 53336kb

input:

3015
1 1
1 2
1 3
1 1
1 2
1 5
1 6
1 6
1 9
1 6
1 4
1 12
1 8
1 14
1 5
1 16
1 17
1 11
1 17
1 20
1 20
1 16
1 20
1 21
1 17
1 12
1 23
1 27
1 29
1 30
1 26
1 25
1 33
1 28
1 27
1 36
1 36
1 37
1 35
1 40
1 38
1 33
1 42
1 43
1 42
1 44
1 47
1 33
1 49
1 41
1 51
1 51
1 53
1 47
1 45
1 53
1 48
1 58
1 57
1 58
1 59
1 6...

output:

7078005045
7213369225
8731941582

result:

ok 3 lines

Test #74:

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

input:

3015
1 1
1 1
1 1
1 2
1 2
1 4
1 6
1 6
1 9
1 8
1 11
1 5
1 7
1 14
1 15
1 12
1 16
1 5
1 13
1 17
1 20
1 17
1 15
1 21
1 20
1 26
1 25
1 22
1 13
1 29
1 26
1 30
1 33
1 32
1 33
1 33
1 35
1 36
1 36
1 40
1 27
1 39
1 41
1 40
1 38
1 44
1 44
1 44
1 49
1 49
1 49
1 51
1 52
1 49
1 53
1 39
1 56
1 35
1 50
1 55
1 61
1 6...

output:

6457389329
7205538321
6904560468

result:

ok 3 lines

Test #75:

score: 0
Accepted
time: 8ms
memory: 52344kb

input:

3015
1 1
1 2
1 2
1 3
1 5
1 6
1 3
1 6
1 3
1 7
1 5
1 10
1 6
1 11
1 12
1 12
1 17
1 11
1 15
1 16
1 17
1 15
1 14
1 19
1 24
1 25
1 24
1 22
1 29
1 18
1 31
1 28
1 33
1 34
1 33
1 25
1 34
1 38
1 36
1 40
1 34
1 40
1 43
1 26
1 37
1 38
1 44
1 42
1 49
1 46
1 51
1 51
1 49
1 51
1 47
1 48
1 57
1 55
1 58
1 60
1 58
1 ...

output:

6442784765
6476469765
9527475400

result:

ok 3 lines

Test #76:

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

input:

3015
1 1
1 1
1 3
1 3
1 5
1 5
1 6
1 7
1 3
1 9
1 10
1 7
1 9
1 10
1 13
1 10
1 17
1 18
1 19
1 18
1 16
1 19
1 22
1 22
1 21
1 24
1 23
1 27
1 28
1 30
1 28
1 29
1 26
1 27
1 31
1 34
1 34
1 34
1 37
1 35
1 34
1 38
1 43
1 39
1 44
1 43
1 39
1 47
1 46
1 46
1 51
1 51
1 48
1 50
1 53
1 55
1 45
1 47
1 51
1 58
1 58
1 ...

output:

6709192235
6945134003
9861269943

result:

ok 3 lines

Test #77:

score: 0
Accepted
time: 8ms
memory: 53588kb

input:

3015
1 1
1 2
1 2
1 4
1 3
1 4
1 3
1 7
1 8
1 9
1 11
1 12
1 7
1 8
1 15
1 16
1 15
1 18
1 15
1 18
1 14
1 21
1 21
1 24
1 23
1 21
1 22
1 27
1 27
1 29
1 30
1 31
1 23
1 28
1 26
1 35
1 24
1 32
1 37
1 37
1 41
1 39
1 35
1 43
1 41
1 40
1 40
1 47
1 43
1 50
1 51
1 49
1 43
1 52
1 51
1 55
1 55
1 54
1 56
1 48
1 61
1 ...

output:

6033127417
7323762555
6584940106

result:

ok 3 lines

Test #78:

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

input:

3015
1 1
1 2
1 2
1 1
1 4
1 2
1 7
1 7
1 7
1 8
1 7
1 12
1 12
1 14
1 15
1 11
1 15
1 18
1 19
1 19
1 19
1 18
1 18
1 24
1 18
1 19
1 24
1 22
1 29
1 29
1 31
1 30
1 32
1 33
1 34
1 30
1 32
1 37
1 33
1 32
1 26
1 39
1 29
1 39
1 41
1 45
1 47
1 32
1 48
1 50
1 49
1 51
1 53
1 52
1 53
1 55
1 53
1 58
1 54
1 58
1 60
1...

output:

8620033407
8197325795
8221508562

result:

ok 3 lines

Test #79:

score: 0
Accepted
time: 3ms
memory: 53788kb

input:

3015
1 1
1 1
1 3
1 2
1 5
1 4
1 5
1 8
1 8
1 9
1 8
1 10
1 11
1 11
1 12
1 12
1 10
1 17
1 15
1 19
1 18
1 15
1 18
1 22
1 25
1 24
1 27
1 24
1 22
1 28
1 27
1 32
1 33
1 30
1 29
1 33
1 30
1 38
1 37
1 38
1 35
1 37
1 39
1 41
1 45
1 37
1 42
1 41
1 45
1 50
1 51
1 52
1 51
1 46
1 50
1 53
1 43
1 58
1 59
1 45
1 60
1...

output:

6178085437
6834924493
9542260857

result:

ok 3 lines

Test #80:

score: 0
Accepted
time: 11ms
memory: 53480kb

input:

3015
1 1
1 2
1 2
1 3
1 5
1 6
1 7
1 8
1 7
1 10
1 7
1 12
1 13
1 14
1 15
1 15
1 10
1 16
1 17
1 17
1 13
1 20
1 21
1 20
1 23
1 17
1 25
1 28
1 26
1 28
1 26
1 32
1 26
1 31
1 31
1 35
1 36
1 28
1 39
1 37
1 34
1 39
1 33
1 41
1 37
1 46
1 44
1 45
1 43
1 45
1 51
1 50
1 41
1 48
1 54
1 52
1 52
1 50
1 59
1 57
1 61
...

output:

8620033407
8197325795
8221508562

result:

ok 3 lines

Test #81:

score: 0
Accepted
time: 4ms
memory: 52260kb

input:

3015
1 1
1 1
1 3
1 4
1 3
1 6
1 7
1 8
1 5
1 10
1 6
1 6
1 9
1 4
1 13
1 13
1 10
1 13
1 19
1 19
1 14
1 16
1 17
1 13
1 23
1 20
1 24
1 27
1 24
1 26
1 31
1 29
1 29
1 32
1 33
1 31
1 37
1 35
1 38
1 40
1 29
1 42
1 40
1 43
1 36
1 45
1 39
1 42
1 37
1 49
1 51
1 48
1 44
1 49
1 54
1 52
1 46
1 46
1 45
1 47
1 61
1 5...

output:

4922397657
6868358999
8628088410

result:

ok 3 lines

Test #82:

score: 0
Accepted
time: 8ms
memory: 53152kb

input:

3015
1 1
1 2
1 3
1 2
1 5
1 2
1 6
1 3
1 5
1 9
1 7
1 12
1 13
1 5
1 9
1 15
1 17
1 17
1 16
1 20
1 21
1 13
1 21
1 24
1 21
1 24
1 22
1 27
1 24
1 27
1 31
1 32
1 33
1 30
1 30
1 32
1 28
1 38
1 31
1 34
1 34
1 42
1 35
1 42
1 44
1 37
1 39
1 48
1 46
1 42
1 51
1 52
1 47
1 54
1 55
1 55
1 49
1 48
1 59
1 55
1 58
1 6...

output:

6177292403
6764010543
10013703780

result:

ok 3 lines

Test #83:

score: 0
Accepted
time: 11ms
memory: 53648kb

input:

3015
1 1
1 1
1 3
1 3
1 3
1 4
1 6
1 7
1 4
1 9
1 11
1 6
1 8
1 12
1 12
1 16
1 13
1 14
1 17
1 17
1 20
1 17
1 18
1 18
1 24
1 24
1 23
1 27
1 27
1 19
1 27
1 27
1 28
1 31
1 27
1 26
1 36
1 38
1 33
1 38
1 41
1 41
1 42
1 39
1 43
1 41
1 35
1 48
1 47
1 48
1 51
1 42
1 53
1 53
1 52
1 49
1 55
1 52
1 58
1 53
1 51
1 ...

output:

8126713637
8195779439
7232988302

result:

ok 3 lines

Test #84:

score: 0
Accepted
time: 4ms
memory: 53436kb

input:

3015
1 1
1 2
1 1
1 4
1 5
1 6
1 4
1 2
1 8
1 10
1 11
1 7
1 13
1 14
1 12
1 16
1 16
1 18
1 19
1 18
1 18
1 20
1 13
1 23
1 20
1 22
1 27
1 28
1 25
1 30
1 28
1 32
1 28
1 33
1 33
1 29
1 36
1 34
1 31
1 32
1 38
1 39
1 37
1 43
1 38
1 39
1 43
1 48
1 42
1 47
1 48
1 35
1 42
1 52
1 41
1 56
1 55
1 56
1 59
1 59
1 54
...

output:

7278969105
6438246795
7220925775

result:

ok 3 lines

Test #85:

score: 0
Accepted
time: 8ms
memory: 53048kb

input:

3015
1 1
1 2
1 2
1 4
1 5
1 4
1 5
1 6
1 7
1 4
1 10
1 7
1 8
1 14
1 13
1 16
1 15
1 11
1 13
1 19
1 21
1 22
1 19
1 22
1 25
1 26
1 24
1 19
1 27
1 22
1 30
1 31
1 30
1 34
1 32
1 36
1 33
1 37
1 35
1 34
1 25
1 42
1 43
1 42
1 40
1 30
1 26
1 44
1 43
1 49
1 47
1 51
1 53
1 51
1 51
1 55
1 53
1 57
1 56
1 58
1 56
1 ...

output:

8338939457
7210943857
7456549185

result:

ok 3 lines

Test #86:

score: 0
Accepted
time: 8ms
memory: 53704kb

input:

3015
1 1
1 1
1 1
1 1
1 3
1 3
1 3
1 2
1 9
1 8
1 10
1 9
1 12
1 11
1 15
1 9
1 16
1 17
1 19
1 20
1 16
1 18
1 19
1 18
1 17
1 25
1 25
1 21
1 29
1 27
1 28
1 32
1 20
1 31
1 32
1 34
1 35
1 38
1 38
1 40
1 40
1 42
1 39
1 38
1 45
1 41
1 42
1 44
1 47
1 42
1 39
1 34
1 40
1 50
1 47
1 52
1 52
1 58
1 55
1 52
1 61
1 ...

output:

8090132963
7064503793
8871617394

result:

ok 3 lines

Test #87:

score: 0
Accepted
time: 8ms
memory: 52372kb

input:

3015
1 1
1 2
1 2
1 2
1 3
1 2
1 7
1 5
1 9
1 5
1 9
1 7
1 12
1 12
1 13
1 11
1 12
1 17
1 19
1 17
1 15
1 18
1 19
1 20
1 24
1 24
1 23
1 26
1 19
1 28
1 20
1 28
1 18
1 32
1 26
1 36
1 37
1 34
1 37
1 35
1 41
1 34
1 42
1 41
1 42
1 37
1 42
1 45
1 44
1 48
1 50
1 50
1 50
1 52
1 48
1 53
1 55
1 50
1 56
1 59
1 48
1 ...

output:

6276193721
7093423133
8109461732

result:

ok 3 lines

Test #88:

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

input:

3015
1 1
1 2
1 1
1 1
1 2
1 1
1 7
1 5
1 9
1 2
1 3
1 10
1 5
1 9
1 7
1 14
1 13
1 14
1 14
1 19
1 11
1 11
1 10
1 3
1 16
1 14
1 19
1 10
1 10
1 26
1 2
1 3
1 20
1 18
1 7
1 2
1 25
1 20
1 29
1 37
1 9
1 38
1 1
1 12
1 28
1 13
1 47
1 7
1 11
1 7
1 25
1 52
1 49
1 24
1 43
1 47
1 40
1 19
1 15
1 56
1 50
1 15
1 4
1 52...

output:

7699125969
6242676435
9249225426

result:

ok 3 lines

Test #89:

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

input:

3015
1 1
1 1
1 1
1 1
1 5
1 5
1 4
1 3
1 8
1 8
1 6
1 9
1 12
1 12
1 6
1 8
1 1
1 10
1 17
1 2
1 20
1 8
1 10
1 12
1 5
1 25
1 25
1 6
2 5
1 24
1 14
1 9
1 7
1 18
1 25
1 21
1 36
1 22
1 5
1 5
1 38
1 11
1 34
1 40
1 16
1 12
1 9
1 31
1 40
1 20
1 25
1 48
1 2
1 2
1 53
1 44
1 52
1 46
1 8
1 22
1 13
1 54
1 36
1 52
1 1...

output:

8319653131
8299037797
8166018763

result:

ok 3 lines

Test #90:

score: 0
Accepted
time: 4ms
memory: 52244kb

input:

2515
1 1
1 1
1 3
1 3
1 2
1 6
1 5
1 2
1 5
1 10
1 1
1 11
1 3
1 6
1 4
1 16
1 8
1 4
1 12
1 1
1 14
1 2
1 20
1 7
1 5
1 17
1 9
1 9
1 1
1 21
1 30
1 3
1 16
1 29
1 15
2 5
1 26
1 35
1 1
1 29
1 32
1 37
1 13
1 28
1 40
1 45
1 9
1 44
1 46
1 35
1 5
1 35
1 43
1 11
1 17
1 50
1 45
1 29
1 49
1 44
1 35
1 21
1 39
1 40
1 ...

output:

7224786909
8128167293
8059469655

result:

ok 3 lines

Test #91:

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

input:

2215
1 1
1 2
1 1
1 2
1 4
1 6
1 1
1 5
1 1
1 9
1 8
1 6
2 3
1 9
1 5
1 6
1 13
1 2
1 10
1 8
1 20
1 6
1 16
1 22
1 11
1 16
1 4
2 1
1 20
2 8
1 27
1 1
1 9
1 8
1 13
1 6
1 4
1 2
1 26
1 25
1 17
1 3
1 10
1 5
1 12
1 35
1 29
1 34
1 33
1 4
1 24
1 22
1 46
1 13
1 50
1 23
1 24
1 41
1 14
1 20
1 3
1 54
1 57
1 7
1 36
1 5...

output:

7236502379
8177526405
6126611886

result:

ok 3 lines

Test #92:

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

input:

1415
1 1
1 2
1 1
1 4
1 5
1 6
1 1
1 4
1 4
1 10
1 6
1 1
1 9
1 13
1 12
1 16
1 17
1 6
1 16
1 11
1 17
1 2
1 17
2 3
1 1
1 16
1 14
1 16
1 7
1 11
1 20
1 17
1 2
1 32
1 30
1 33
1 13
1 8
1 34
1 12
1 7
1 40
1 13
1 2
1 30
1 38
1 21
1 10
1 40
1 16
1 45
1 10
1 39
1 7
1 42
1 46
1 6
1 43
1 21
1 6
1 50
1 51
1 2
1 17
...

output:

5343676953
7269310663
8620229955

result:

ok 3 lines

Test #93:

score: 0
Accepted
time: 8ms
memory: 53724kb

input:

3015
1 1
1 2
1 3
1 2
1 3
1 6
1 7
1 7
1 8
1 4
1 11
1 12
1 12
1 11
1 10
1 10
1 8
1 18
1 15
1 15
1 21
1 22
1 20
1 17
1 21
1 26
1 20
1 27
1 24
1 30
1 25
1 29
1 31
1 34
1 34
1 36
1 32
1 35
1 37
1 32
1 39
1 29
1 37
1 41
1 36
1 40
1 38
1 47
1 47
1 50
1 51
1 50
1 53
1 48
1 54
1 55
1 57
1 58
1 58
1 57
1 52
1...

output:

5053426651
6291565399
8873448245

result:

ok 3 lines

Test #94:

score: 0
Accepted
time: 3ms
memory: 52652kb

input:

3015
1 1
1 1
1 3
1 2
1 3
1 5
1 6
1 5
1 8
1 9
1 11
1 8
1 13
1 9
1 15
1 14
1 17
1 17
1 14
1 19
1 21
1 21
2 1
1 22
1 24
1 24
1 18
1 27
1 28
1 18
1 30
1 25
1 26
1 29
1 33
1 32
1 34
1 33
1 28
1 31
1 40
1 36
1 42
1 37
1 34
1 45
1 45
1 47
1 42
1 40
1 49
1 49
1 52
1 43
1 36
1 55
1 47
1 57
1 57
1 58
1 53
1 6...

output:

7089506695
5970454331
9889199781

result:

ok 3 lines

Test #95:

score: 0
Accepted
time: 13ms
memory: 53164kb

input:

2915
1 1
1 1
1 3
1 3
1 5
1 2
1 7
1 7
1 6
1 8
1 6
1 12
1 12
1 10
1 15
1 16
1 16
1 18
1 17
1 18
1 20
1 15
1 20
1 24
1 24
1 22
1 23
1 28
1 27
1 29
1 31
1 30
1 32
1 27
1 31
1 32
1 37
1 37
1 39
1 29
1 39
1 42
1 41
1 41
1 45
1 46
1 47
1 46
1 42
1 49
1 45
1 47
1 44
1 49
1 51
1 52
1 56
1 58
1 59
1 50
1 59
1...

output:

5859937655
7323846571
7621771807

result:

ok 3 lines

Test #96:

score: 0
Accepted
time: 12ms
memory: 53260kb

input:

3015
1 1
1 1
1 2
1 2
1 3
1 3
1 4
1 4
1 5
1 5
1 6
1 6
1 7
1 7
1 8
1 8
1 9
1 9
1 10
1 10
1 11
1 11
1 12
1 12
1 13
1 13
1 14
1 14
1 15
1 15
1 16
1 16
1 17
1 17
1 18
1 18
1 19
1 19
1 20
1 20
1 21
1 21
1 22
1 22
1 23
1 23
1 24
1 24
1 25
1 25
1 26
1 26
1 27
1 27
1 28
1 28
1 29
1 29
1 30
1 30
1 31
1 31
1 3...

output:

8974356933
7350581307
9341541551

result:

ok 3 lines

Test #97:

score: 0
Accepted
time: 8ms
memory: 52536kb

input:

2915
1 1
1 1
1 2
1 2
1 3
1 3
1 4
1 4
1 5
1 5
1 6
1 6
1 7
1 7
1 8
1 8
1 9
2 3
1 9
1 10
1 10
1 11
1 11
1 12
1 12
1 13
1 13
1 14
1 14
1 15
1 15
1 16
1 16
1 17
1 17
1 18
1 18
1 19
1 19
1 20
1 20
1 21
1 21
1 22
1 22
1 23
1 23
1 24
1 24
1 25
1 25
1 26
1 26
1 27
1 27
1 28
1 28
1 29
1 29
1 30
1 30
1 31
1 31...

output:

7983897037
7659068869
9066958093

result:

ok 3 lines

Subtask #3:

score: 5
Accepted

Test #98:

score: 5
Accepted
time: 897ms
memory: 243076kb

input:

1000000
2 1
1 1
1 1
1 2
2 4
1 2
2 1
1 3
1 3
1 4
2 1
1 4
1 5
1 5
2 3
2 4
2 2
1 6
1 6
2 9
1 7
2 2
1 7
2 2
2 3
1 8
2 4
2 9
2 2
1 8
1 9
1 9
2 1
2 4
2 1
2 4
2 6
2 3
2 4
1 10
1 10
2 3
1 11
2 2
2 13
1 11
2 1
1 12
1 12
1 13
1 13
2 1
2 5
1 14
2 3
2 4
1 14
1 15
2 5
1 15
1 16
1 16
1 17
1 17
1 18
1 18
2 10
2 7
...

output:

226384484418682
252721864385826
254136704849695

result:

ok 3 lines

Test #99:

score: 0
Accepted
time: 72ms
memory: 67124kb

input:

69000
1 1
2 2
1 1
1 2
1 2
2 2
2 1
1 3
2 4
2 4
1 3
2 1
2 1
2 4
2 3
1 4
2 6
2 1
1 4
1 5
1 5
1 6
2 5
1 6
1 7
2 3
1 7
1 8
2 5
1 8
2 10
1 9
1 9
1 10
2 1
2 6
2 7
2 2
2 3
1 10
2 2
2 2
1 11
1 11
2 1
1 12
1 12
2 5
1 13
1 13
1 14
2 1
1 14
1 15
1 15
2 4
2 3
2 1
1 16
1 16
1 17
2 3
1 17
1 18
1 18
1 19
1 19
1 20
...

output:

14784500253954
14669250414504
15283613553821

result:

ok 3 lines

Test #100:

score: 0
Accepted
time: 38ms
memory: 59840kb

input:

35000
1 1
2 1
1 1
2 1
1 2
1 2
2 3
2 1
2 2
2 1
1 3
1 3
2 1
1 4
2 8
2 4
1 4
1 5
2 3
2 5
1 5
1 6
2 2
2 5
1 6
1 7
1 7
2 5
1 8
2 5
2 1
2 4
2 9
1 8
1 9
1 9
1 10
1 10
1 11
2 3
2 6
2 3
2 5
2 1
1 11
2 4
1 12
2 3
2 8
1 12
1 13
1 13
2 3
2 7
2 1
1 14
1 14
1 15
2 5
1 15
2 3
1 16
1 16
1 17
1 17
2 2
1 18
1 18
2 18...

output:

6096455559752
6054967272968
6357768376585

result:

ok 3 lines

Test #101:

score: 0
Accepted
time: 346ms
memory: 128888kb

input:

450000
2 1
1 1
2 2
2 2
2 1
1 1
2 3
1 2
2 2
2 1
1 2
1 3
1 3
1 4
1 4
2 6
1 5
2 3
1 5
2 6
1 6
2 4
2 5
2 4
2 1
2 2
2 4
1 6
2 3
2 1
1 7
2 1
2 2
1 7
2 5
2 1
1 8
2 5
1 8
2 2
2 3
1 9
2 6
1 9
2 4
1 10
1 10
2 1
2 3
1 11
2 2
2 9
2 5
1 11
1 12
2 10
1 12
2 3
2 12
2 11
2 4
1 13
2 4
1 13
1 14
2 14
1 14
2 1
1 15
2 ...

output:

121665563089444
126544857831942
129761372078861

result:

ok 3 lines

Test #102:

score: 0
Accepted
time: 86ms
memory: 70004kb

input:

97000
2 1
1 1
2 2
1 1
2 2
2 2
2 1
2 1
2 2
1 2
2 2
1 2
1 3
1 3
2 4
2 3
1 4
2 3
2 3
2 2
2 1
2 1
1 4
2 4
2 3
2 4
1 5
1 5
2 3
1 6
1 6
1 7
1 7
2 1
2 8
1 8
2 3
2 2
1 8
1 9
2 3
2 6
2 9
1 9
2 2
2 2
2 6
1 10
1 10
1 11
1 11
1 12
1 12
2 2
2 6
1 13
2 2
1 13
2 6
1 14
2 2
1 14
2 4
1 15
2 1
1 15
2 1
2 1
2 1
1 16
2...

output:

25220690929170
25344636746902
26447936619463

result:

ok 3 lines

Test #103:

score: 0
Accepted
time: 624ms
memory: 185812kb

input:

840000
2 1
2 1
2 1
1 1
2 1
2 1
1 1
2 2
1 2
1 2
2 3
1 3
2 4
1 3
2 5
1 4
2 1
2 2
1 4
2 5
2 2
2 2
2 4
2 2
2 3
1 5
2 2
1 5
2 2
2 2
2 5
2 1
1 6
2 1
2 2
2 8
1 6
2 1
2 5
1 7
2 2
2 1
2 1
2 1
2 10
2 5
2 3
1 7
2 2
2 11
2 1
2 9
1 8
2 1
2 2
1 8
2 2
1 9
2 4
1 9
1 10
1 10
1 11
2 2
1 11
1 12
1 12
2 4
2 3
1 13
1 13...

output:

228116240634290
247830472818950
249540875626368

result:

ok 3 lines

Test #104:

score: 0
Accepted
time: 53ms
memory: 65296kb

input:

60000
1 1
2 1
1 1
1 2
2 2
1 2
1 3
1 3
2 2
2 2
1 4
1 4
1 5
2 2
2 2
1 5
1 6
1 6
1 7
2 7
1 7
2 3
1 8
1 8
1 9
2 7
2 10
1 9
1 10
1 10
1 11
1 11
1 12
1 12
2 2
2 4
2 1
2 3
1 13
1 13
2 1
2 1
2 3
1 14
2 3
1 14
2 4
2 8
2 5
1 15
1 15
1 16
2 11
1 16
2 3
1 17
2 7
2 5
1 17
1 18
1 18
1 19
1 19
2 2
1 20
2 2
2 10
2 ...

output:

13192477991316
13159119140522
13696711811391

result:

ok 3 lines

Test #105:

score: 0
Accepted
time: 4ms
memory: 52716kb

input:

6800
2 1
2 1
2 1
1 1
1 1
2 2
1 2
1 2
1 3
1 3
2 1
1 4
2 3
1 4
2 3
1 5
2 3
1 5
1 6
1 6
2 3
1 7
1 7
2 9
1 8
1 8
1 9
2 3
2 1
1 9
1 10
2 6
1 10
1 11
1 11
1 12
1 12
2 2
1 13
1 13
1 14
1 14
2 2
1 15
1 15
1 16
1 16
2 1
1 17
1 17
2 1
1 18
1 18
1 19
1 19
2 3
1 20
1 20
1 21
2 2
1 21
1 22
1 22
2 1
1 23
1 23
1 2...

output:

1180474027890
1141458473508
1221476654564

result:

ok 3 lines

Test #106:

score: 0
Accepted
time: 12ms
memory: 53224kb

input:

9800
2 1
2 1
2 1
2 1
2 1
1 1
1 1
1 2
2 3
2 4
1 2
1 3
2 2
1 3
2 4
2 3
1 4
1 4
1 5
1 5
2 2
1 6
2 3
1 6
2 1
2 3
1 7
2 4
2 2
1 7
1 8
2 3
1 8
1 9
2 1
2 1
2 2
2 3
2 9
1 9
1 10
2 6
1 10
2 11
1 11
2 13
1 11
1 12
1 12
2 8
2 2
2 5
2 7
1 13
2 5
2 11
2 4
2 5
2 7
1 13
2 7
2 2
1 14
2 11
2 9
1 14
1 15
1 15
1 16
1 ...

output:

2522281844666
2559303105128
2646473666443

result:

ok 3 lines

Test #107:

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

input:

10000
2 1
2 1
2 1
1 1
1 1
1 2
2 4
1 2
1 3
2 1
2 1
1 3
2 1
2 6
1 4
1 4
1 5
1 5
2 3
1 6
1 6
1 7
2 4
2 7
1 7
1 8
2 2
1 8
1 9
2 1
1 9
1 10
2 1
2 8
2 1
1 10
1 11
2 1
2 5
2 1
1 11
1 12
2 2
1 12
2 2
2 3
1 13
1 13
1 14
1 14
2 2
1 15
2 1
2 4
1 15
1 16
2 1
1 16
2 1
1 17
2 8
2 1
1 17
2 6
2 17
1 18
2 1
2 5
1 18...

output:

2489817197164
2536287789128
2651483685195

result:

ok 3 lines

Subtask #4:

score: 21
Accepted

Test #108:

score: 21
Accepted
time: 891ms
memory: 278956kb

input:

1000000
2 1
2 1
1 1
1 1
2 1
1 2
1 4
2 1
2 3
2 1
1 5
1 3
1 6
2 2
2 2
2 2
2 2
1 8
2 1
1 5
2 3
1 8
1 11
1 12
1 13
1 12
2 3
2 5
1 14
2 3
2 4
1 16
2 2
1 17
1 18
2 10
2 3
1 19
2 4
1 10
1 17
2 1
2 4
2 5
1 19
2 9
1 15
1 24
2 8
1 25
2 2
2 3
2 2
2 5
1 25
2 5
1 20
1 26
1 29
2 7
2 2
2 6
2 1
1 30
2 3
1 30
2 3
2 ...

output:

212888413200404
252999291073822
268758073967755

result:

ok 3 lines

Test #109:

score: 0
Accepted
time: 880ms
memory: 279060kb

input:

1000000
1 1
1 2
2 2
2 2
2 1
1 2
2 2
2 4
2 3
2 1
1 3
1 3
1 6
2 4
1 6
1 7
1 8
2 4
1 10
1 10
2 5
2 1
2 6
2 6
2 1
2 3
2 2
1 12
1 7
1 14
2 2
1 13
1 9
2 6
2 10
2 6
2 4
2 1
2 1
2 4
2 3
2 2
2 2
2 7
1 13
2 4
1 17
2 5
1 17
1 18
2 2
2 8
2 4
2 6
1 20
1 15
1 22
1 22
1 19
2 1
1 19
2 2
1 24
1 24
1 29
1 30
2 11
2 1...

output:

216652818522776
252512151299728
264334796237779

result:

ok 3 lines

Test #110:

score: 0
Accepted
time: 853ms
memory: 274396kb

input:

950000
1 1
1 2
2 3
2 3
2 1
2 2
2 1
1 3
1 2
2 3
1 5
1 5
1 7
1 7
1 8
2 2
2 2
2 1
2 2
1 8
1 10
1 10
2 4
1 12
1 13
1 11
2 1
2 1
1 13
1 11
1 14
1 15
1 15
2 10
1 18
2 3
2 1
2 4
2 2
1 20
1 16
2 9
1 16
1 20
2 4
1 26
1 19
1 26
1 28
1 28
1 25
1 29
2 12
2 5
1 22
1 30
2 2
1 33
1 25
1 37
2 2
2 6
2 12
1 34
2 3
2 ...

output:

183007317550094
232592077066068
242935152728547

result:

ok 3 lines

Test #111:

score: 0
Accepted
time: 870ms
memory: 270084kb

input:

980000
2 1
2 1
1 1
1 1
1 2
1 4
1 5
1 5
1 6
1 6
2 1
2 5
1 8
1 10
2 2
2 1
2 1
1 11
2 1
2 7
2 2
2 8
1 7
1 13
2 3
2 4
1 13
1 10
1 15
1 17
2 15
2 1
1 16
2 8
2 11
1 12
2 6
1 16
1 20
1 20
2 1
2 1
1 15
1 24
2 2
1 24
2 1
1 23
2 3
1 25
2 6
1 25
2 5
1 27
1 29
2 1
2 7
2 3
2 1
2 2
2 6
2 1
1 29
1 30
2 1
2 15
1 32...

output:

221416376201390
252867939843982
264949199527408

result:

ok 3 lines

Test #112:

score: 0
Accepted
time: 89ms
memory: 73120kb

input:

96000
2 1
2 1
2 1
1 1
2 1
2 1
1 1
1 2
2 1
1 3
2 1
2 1
1 5
1 5
2 2
1 6
2 2
1 4
2 7
1 8
1 10
1 11
1 7
2 9
2 7
2 5
2 3
2 6
1 10
1 14
2 3
1 15
1 14
1 17
1 12
1 19
1 18
2 7
2 9
1 21
2 3
1 13
1 20
2 5
2 6
2 7
2 6
2 8
1 24
1 20
1 26
1 27
1 28
2 2
2 1
1 27
1 29
1 29
1 32
2 5
2 1
1 31
1 21
2 13
2 1
2 1
1 34
...

output:

18815724775190
24813196073346
25874741354392

result:

ok 3 lines

Test #113:

score: 0
Accepted
time: 71ms
memory: 72824kb

input:

94000
1 1
2 1
2 2
1 2
1 3
1 4
2 4
1 2
2 5
2 2
1 4
2 3
2 1
2 4
1 6
1 5
1 9
1 6
2 4
2 6
2 3
2 4
2 7
1 11
1 8
2 8
1 12
2 7
2 3
2 1
1 14
1 15
1 12
2 1
2 5
1 16
1 16
1 11
1 10
2 2
1 21
2 6
1 17
1 19
1 24
2 3
1 23
2 2
1 20
1 24
2 3
1 14
1 22
1 20
1 31
2 3
2 9
1 31
1 28
1 32
2 8
1 32
2 1
1 34
2 3
1 34
1 38...

output:

19869823846930
24319436189068
24925563190330

result:

ok 3 lines

Test #114:

score: 0
Accepted
time: 58ms
memory: 65376kb

input:

78000
1 1
2 1
2 1
1 1
2 2
2 1
2 1
1 2
2 4
1 2
2 2
2 3
1 4
1 5
2 6
2 2
1 6
2 2
2 4
1 8
1 4
2 3
2 1
1 10
2 1
1 8
2 11
1 10
1 13
2 9
2 8
1 12
2 11
2 7
2 2
1 14
2 3
2 1
1 16
2 2
2 12
2 1
1 14
1 17
2 3
1 15
2 5
2 3
2 1
2 1
2 5
2 9
2 2
1 19
1 21
2 5
1 7
2 2
1 22
1 22
2 10
2 6
2 3
2 10
2 7
2 8
1 24
1 23
1 ...

output:

20912474411470
23709193057924
24829752720547

result:

ok 3 lines

Test #115:

score: 0
Accepted
time: 577ms
memory: 197320kb

input:

820000
2 1
1 1
1 2
2 3
1 1
2 2
2 2
1 3
2 1
2 2
2 1
1 5
2 2
2 2
2 1
2 2
2 1
1 4
2 5
1 4
2 5
2 1
2 2
2 2
1 3
2 6
2 6
2 3
2 2
1 8
2 6
2 4
2 3
2 2
2 1
1 7
1 9
1 5
2 7
2 2
2 4
1 9
2 2
2 1
2 4
1 11
2 4
2 1
2 2
1 15
2 11
1 14
2 2
1 14
2 1
1 17
2 10
1 19
2 9
1 18
2 3
1 21
2 2
1 19
2 13
1 21
2 2
1 22
2 5
2 5...

output:

207280564659982
252718401626124
262828853170875

result:

ok 3 lines

Test #116:

score: 0
Accepted
time: 168ms
memory: 97328kb

input:

150000
1 1
1 1
1 2
1 2
1 3
2 4
2 1
1 6
1 7
2 6
1 4
2 6
2 1
1 6
1 7
1 9
2 7
2 4
1 10
1 13
1 12
1 12
1 9
1 16
1 17
1 19
1 19
1 21
2 2
2 1
1 16
2 10
2 7
1 23
1 22
1 23
1 25
1 20
2 2
1 24
1 28
2 4
1 27
2 1
1 29
2 4
1 25
2 3
1 33
1 34
2 4
1 34
1 32
1 31
2 10
2 3
2 19
2 1
1 33
2 6
2 3
1 39
1 38
1 38
2 1
2...

output:

21656009746666
25268160422762
25744035927314

result:

ok 3 lines

Test #117:

score: 0
Accepted
time: 250ms
memory: 120660kb

input:

200000
2 1
1 1
1 2
2 3
1 3
1 3
2 2
2 3
1 5
2 1
1 4
1 5
1 8
2 3
1 8
2 2
1 9
1 7
2 2
1 11
1 13
1 12
2 4
2 2
2 2
2 2
1 13
1 16
2 2
1 16
1 15
1 17
2 1
2 6
1 15
2 16
1 20
1 21
1 23
2 1
1 21
1 19
1 25
1 25
1 27
2 3
1 22
1 30
1 30
1 31
1 32
1 34
1 28
2 4
2 1
1 34
1 20
1 38
1 36
1 38
1 31
1 40
1 42
1 40
1 4...

output:

23213148977150
25367178543244
26055403134620

result:

ok 3 lines

Test #118:

score: 0
Accepted
time: 201ms
memory: 102172kb

input:

370000
1 1
2 2
2 1
2 2
2 1
1 2
2 2
1 1
1 4
2 3
2 2
2 3
2 2
2 2
2 1
2 2
1 3
1 4
2 2
2 5
2 1
2 7
2 2
2 4
2 1
2 6
2 1
2 2
2 4
2 3
2 1
1 6
2 2
2 2
2 2
1 7
2 2
1 7
2 2
2 6
2 7
2 4
2 2
2 2
2 7
2 3
2 2
1 8
2 3
1 11
1 8
2 3
1 12
1 11
2 1
2 5
1 15
1 16
1 17
1 13
2 7
2 5
2 7
2 4
2 1
1 15
1 20
2 3
2 2
1 14
2 8...

output:

111952754781846
131463422858176
135653613656541

result:

ok 3 lines

Test #119:

score: 0
Accepted
time: 365ms
memory: 148420kb

input:

410000
2 1
2 1
1 1
2 2
2 2
1 2
1 2
2 2
2 2
1 3
2 4
2 2
1 4
1 5
1 6
2 1
1 8
1 9
2 2
1 10
1 3
2 5
2 2
1 11
2 1
1 8
1 14
1 15
2 3
1 14
1 17
1 9
1 11
2 1
1 17
1 15
2 4
1 21
2 3
2 11
1 21
2 6
1 20
2 1
2 9
1 22
1 26
1 27
2 1
2 2
1 28
2 4
1 27
2 1
2 4
2 8
2 1
1 30
1 30
1 32
2 4
1 32
2 3
2 7
1 33
2 8
1 31
1...

output:

88274311580206
101132097226452
105086878401260

result:

ok 3 lines

Test #120:

score: 0
Accepted
time: 250ms
memory: 120628kb

input:

550000
2 1
2 1
1 1
2 1
2 2
2 2
1 2
2 3
2 3
2 3
2 1
1 2
2 2
1 1
2 2
2 1
1 3
2 2
2 2
2 1
2 2
2 5
2 2
2 2
1 4
1 5
1 7
2 1
1 3
2 3
2 2
1 10
2 4
1 7
1 12
2 1
2 6
2 4
2 8
1 12
2 1
1 14
2 2
2 1
1 9
2 2
2 6
1 16
1 10
1 18
2 1
1 19
2 2
2 3
2 5
2 1
1 19
1 21
2 5
1 20
2 6
1 18
2 9
2 8
2 1
2 3
1 23
1 25
2 1
2 2...

output:

161661913357544
202368530694518
207144218365022

result:

ok 3 lines

Test #121:

score: 0
Accepted
time: 290ms
memory: 125132kb

input:

360000
2 1
2 1
2 1
2 1
2 1
1 1
2 1
2 1
2 1
1 1
2 3
2 1
1 2
2 4
2 3
1 3
1 5
1 6
1 5
1 2
2 4
1 7
2 2
2 5
1 9
1 3
2 4
2 1
2 1
1 4
1 13
1 12
2 6
1 10
2 1
1 15
2 2
1 17
1 14
1 18
1 19
1 15
2 6
1 22
2 3
2 1
2 3
2 1
1 17
1 16
1 24
1 26
1 27
2 12
2 6
1 24
2 6
2 9
2 1
2 3
2 14
2 3
2 13
2 2
1 22
2 7
2 4
2 1
2...

output:

84886227141042
101183173507148
105730653305369

result:

ok 3 lines

Test #122:

score: 0
Accepted
time: 262ms
memory: 119944kb

input:

450000
2 1
2 1
2 1
2 1
2 1
2 1
2 1
1 1
2 1
2 2
2 2
1 2
1 1
1 4
2 1
2 4
2 5
2 5
1 2
2 1
2 1
1 3
2 2
2 4
2 1
1 7
2 2
1 6
2 8
2 2
1 9
2 6
1 6
2 6
1 8
1 12
2 2
2 1
2 5
1 9
2 12
1 14
1 15
2 3
2 1
2 2
1 16
2 1
2 9
2 5
1 17
1 14
1 19
2 3
1 15
2 1
1 20
1 19
2 3
2 8
2 7
2 1
2 9
1 23
2 1
1 24
1 22
2 7
2 9
2 4...

output:

101769364802942
151719632819002
157050038243212

result:

ok 3 lines

Test #123:

score: 0
Accepted
time: 383ms
memory: 156916kb

input:

480000
1 1
2 1
1 2
1 2
1 1
1 5
1 6
2 1
2 4
1 7
2 1
2 3
1 6
1 9
1 7
1 11
1 12
2 4
1 11
2 2
1 12
1 14
2 1
1 16
1 17
2 7
1 15
1 16
2 1
2 2
2 1
2 9
2 4
2 10
2 1
2 1
1 19
1 21
1 22
2 6
1 19
2 1
2 3
2 5
1 23
1 25
1 22
1 26
1 26
2 7
1 29
2 3
2 2
1 24
1 27
1 23
2 1
1 33
2 5
1 34
1 33
2 2
1 36
1 25
1 34
1 38...

output:

97009825440726
126332341758490
131180186840641

result:

ok 3 lines

Test #124:

score: 0
Accepted
time: 185ms
memory: 101672kb

input:

220000
2 1
2 1
1 1
1 1
1 2
2 4
2 3
1 2
2 2
2 1
1 5
2 2
2 4
1 5
1 7
2 5
2 5
2 2
1 7
2 4
1 3
2 1
2 1
2 1
2 2
1 8
1 10
1 6
1 10
1 11
1 13
1 13
2 7
1 11
1 14
2 4
2 1
1 18
1 18
1 21
2 1
1 22
2 1
2 2
1 20
1 16
2 4
1 25
2 1
1 26
1 21
2 1
1 24
2 4
1 25
1 23
2 2
2 1
1 27
1 30
1 32
2 1
2 1
2 1
2 5
2 3
2 1
2 1...

output:

48398808279498
55776602966614
57129151897680

result:

ok 3 lines

Test #125:

score: 0
Accepted
time: 281ms
memory: 124972kb

input:

360000
2 1
2 1
1 1
2 2
1 1
1 3
2 3
1 4
1 4
1 5
1 7
2 3
2 8
2 5
2 1
1 7
2 1
2 5
2 1
1 9
2 5
1 8
2 1
2 2
1 8
2 1
1 12
1 12
1 14
2 6
2 3
1 15
2 3
2 2
1 15
1 10
2 1
2 6
1 14
2 6
1 19
2 9
2 5
1 18
1 21
2 3
2 4
2 3
2 1
2 5
1 13
1 23
1 24
2 1
1 21
1 26
1 18
2 5
1 26
1 23
2 3
1 25
1 25
1 29
1 28
2 1
2 3
2 8...

output:

83984777491434
101002143862162
107652134193034

result:

ok 3 lines

Test #126:

score: 0
Accepted
time: 631ms
memory: 197212kb

input:

1000000
2 1
1 1
2 2
1 1
1 2
1 2
1 3
1 3
2 5
2 1
2 2
1 4
2 3
2 2
2 4
2 6
1 4
2 1
1 5
2 2
1 5
1 6
1 6
2 6
1 7
1 7
2 10
2 9
1 8
1 8
2 1
1 9
2 9
2 3
1 9
1 10
1 10
2 3
2 5
1 11
1 11
2 1
2 10
1 12
1 12
2 7
1 13
1 13
2 1
1 14
1 14
1 15
2 17
2 3
2 1
1 15
1 16
2 8
2 4
1 16
1 17
2 2
2 10
1 17
2 2
1 18
2 6
2 5...

output:

232029820165550
252599887943204
254031602734437

result:

ok 3 lines

Test #127:

score: 0
Accepted
time: 681ms
memory: 207556kb

input:

990000
1 1
2 1
2 2
1 1
1 2
1 2
1 3
2 3
1 3
2 1
1 4
2 1
2 1
2 3
2 4
1 4
2 4
1 5
2 3
2 4
2 5
1 5
1 6
2 3
2 6
2 5
2 2
2 2
1 6
2 5
1 7
1 7
1 8
2 10
2 2
2 3
1 8
1 9
1 9
1 10
2 1
1 10
1 11
2 1
1 11
1 12
2 9
2 4
1 12
1 13
2 6
1 13
2 2
1 14
2 1
1 14
1 15
1 15
1 16
1 16
1 17
1 17
2 3
1 18
2 3
1 18
1 19
2 13
...

output:

225936593244440
252962041429676
252125432335985

result:

ok 3 lines

Subtask #5:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #128:

score: 15
Accepted
time: 7ms
memory: 52036kb

input:

6000
1 1
1 1
1 1
2 3
1 4
2 2
2 4
2 5
2 2
1 5
1 5
1 6
1 8
2 4
2 7
1 3
2 4
2 1
1 2
1 1
2 6
2 10
2 8
1 8
2 11
1 6
1 13
1 15
1 3
2 7
2 15
2 4
1 17
1 11
2 17
2 18
1 18
1 17
2 16
2 3
1 18
2 19
1 2
2 17
2 9
2 13
2 3
1 9
2 23
1 10
2 25
2 14
1 20
1 6
1 25
2 12
2 10
2 28
2 18
2 11
1 10
2 11
1 25
2 19
2 27
1 2...

output:

823737019116
1499517357274
1519445402863

result:

ok 3 lines

Test #129:

score: 0
Accepted
time: 8ms
memory: 51984kb

input:

6000
1 1
2 2
1 2
2 2
1 2
2 4
1 2
1 2
2 6
2 3
2 1
1 2
2 7
1 7
2 7
2 1
1 2
1 8
2 3
2 10
1 10
1 1
2 4
1 10
2 13
2 2
1 4
2 10
2 7
2 8
1 7
1 12
1 6
2 4
1 6
1 16
1 3
1 7
1 17
1 4
2 12
1 21
1 17
2 9
2 14
2 14
2 2
1 22
2 25
1 13
1 15
2 9
1 4
1 7
1 17
2 20
1 21
1 17
1 18
1 7
1 27
1 3
1 33
1 13
1 12
1 14
2 31...

output:

855844798490
1505791125218
1515902806017

result:

ok 3 lines

Test #130:

score: 0
Accepted
time: 13ms
memory: 53040kb

input:

6000
2 1
2 1
1 1
1 1
2 1
2 1
2 1
1 2
1 4
2 3
1 5
1 6
1 6
1 7
1 1
1 1
2 10
1 2
1 9
2 1
1 1
1 8
2 5
1 6
1 5
2 15
1 12
1 13
1 16
1 10
1 2
2 6
1 12
2 17
2 19
1 4
2 7
1 10
2 17
2 22
2 5
1 10
2 12
2 5
2 5
2 8
1 26
1 8
2 15
2 24
1 21
2 10
1 12
1 8
1 24
2 10
2 29
1 18
1 21
1 19
2 28
1 20
2 36
1 33
1 24
2 22...

output:

865724941508
1520218382970
1528304921737

result:

ok 3 lines

Test #131:

score: 0
Accepted
time: 4ms
memory: 52068kb

input:

6000
1 1
2 1
2 2
2 2
1 1
2 3
1 3
1 3
2 3
2 2
2 1
1 5
2 6
1 3
2 4
1 6
2 3
1 3
1 1
2 10
2 6
2 6
2 9
1 3
1 5
2 9
1 9
2 7
2 8
2 2
1 1
1 9
1 5
1 7
1 3
1 11
2 4
2 9
2 16
1 14
1 14
2 13
1 2
1 4
1 14
2 17
2 21
1 12
2 6
1 13
1 18
2 25
2 21
2 23
1 16
1 26
1 27
1 29
2 3
1 20
2 12
2 3
1 8
2 30
1 19
1 24
1 3
1 2...

output:

836884784674
1510537900958
1516341207403

result:

ok 3 lines

Test #132:

score: 0
Accepted
time: 12ms
memory: 52404kb

input:

6000
2 1
1 1
1 1
1 3
1 2
1 3
1 5
2 3
2 4
2 4
2 5
2 2
2 1
1 4
2 1
2 8
1 7
1 4
1 1
2 10
1 7
2 10
2 3
2 1
2 2
2 11
2 3
1 7
2 10
2 4
2 10
2 13
2 4
2 2
2 8
2 7
1 3
2 3
1 10
2 1
2 2
2 15
2 2
1 13
2 6
1 2
2 8
1 10
1 12
2 15
2 16
1 17
1 16
2 12
1 21
2 7
2 6
2 2
2 17
1 5
1 20
1 5
1 25
1 19
2 23
1 8
1 4
1 23
...

output:

838000526974
1510444018124
1518170989459

result:

ok 3 lines

Test #133:

score: 0
Accepted
time: 3ms
memory: 51776kb

input:

4300
2 1
1 1
2 1
2 2
2 2
2 1
2 2
1 1
1 2
2 2
2 2
2 2
2 4
1 4
2 3
2 4
2 2
2 5
1 4
2 2
2 3
2 3
1 4
2 6
2 2
2 1
1 3
1 8
1 6
2 6
1 8
2 10
2 10
1 7
2 7
2 8
2 5
2 1
2 4
2 7
2 2
1 8
1 8
1 8
1 5
1 14
2 10
2 16
2 11
2 7
2 4
1 5
2 4
1 18
2 12
1 4
2 18
2 7
1 10
2 19
1 9
1 19
1 10
2 3
1 21
1 22
1 20
1 2
1 11
2 ...

output:

839529594412
1532620558968
1533023733765

result:

ok 3 lines

Test #134:

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

input:

6000
1 1
2 1
1 1
2 2
2 2
1 2
1 1
2 2
1 5
1 4
1 4
1 1
1 9
2 6
1 5
1 9
2 12
2 3
2 6
1 6
2 5
2 9
2 1
1 11
2 14
1 12
2 8
2 14
2 3
1 13
2 2
2 16
2 1
1 2
1 17
2 11
1 3
2 11
1 16
2 16
2 6
2 17
1 18
2 6
2 11
1 11
2 2
1 21
1 14
2 3
2 16
2 15
1 17
1 2
2 20
1 1
1 14
2 26
1 14
2 11
1 23
2 11
2 9
1 29
1 1
2 22
1...

output:

841055165128
1523956677146
1533424106779

result:

ok 3 lines

Test #135:

score: 0
Accepted
time: 3ms
memory: 52632kb

input:

5500
2 1
1 1
2 1
2 1
2 1
1 1
2 3
1 3
1 2
2 2
2 3
1 1
1 1
2 6
2 5
2 7
2 7
1 6
2 8
2 5
2 8
1 2
1 4
1 2
1 1
2 7
2 1
2 4
1 12
2 13
1 12
2 11
1 14
2 14
1 5
2 1
1 8
2 6
1 1
2 11
1 11
1 6
1 4
2 18
1 16
1 11
2 12
1 13
2 17
2 7
1 24
1 17
1 24
1 6
1 24
1 25
1 10
2 14
2 27
2 29
2 8
1 1
1 19
2 19
2 27
1 13
2 8
...

output:

847839556904
1503590026184
1554150109447

result:

ok 3 lines

Test #136:

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

input:

6000
1 1
1 2
2 3
1 3
1 4
2 4
2 4
2 1
1 4
1 5
2 7
1 4
1 7
2 5
1 3
1 1
1 10
1 12
1 10
1 12
2 9
2 3
1 9
2 9
2 1
1 13
2 4
1 15
2 9
2 16
2 9
1 6
1 9
1 16
2 4
2 12
1 18
1 17
1 9
2 18
1 2
1 2
1 4
2 27
1 13
2 26
2 5
1 9
2 14
2 28
1 22
2 18
1 25
2 15
1 10
2 30
1 5
1 4
1 13
1 22
1 22
1 37
1 34
1 25
2 28
1 37
...

output:

815343358644
1488538809094
1542843282128

result:

ok 3 lines

Test #137:

score: 0
Accepted
time: 13ms
memory: 52000kb

input:

6000
1 1
1 2
1 2
2 1
1 1
1 4
1 2
1 2
1 7
1 7
2 8
2 4
2 1
2 1
2 6
2 3
1 9
2 8
2 5
1 3
2 3
1 10
1 10
1 9
1 12
2 2
2 3
1 5
1 4
2 7
2 11
2 14
2 12
1 6
2 16
2 17
2 16
2 5
1 12
1 9
1 3
2 17
1 18
1 3
2 17
2 13
2 1
2 9
1 14
2 4
1 2
2 12
1 26
1 14
2 22
1 12
1 6
1 19
2 5
1 31
1 21
1 6
2 31
2 2
1 23
1 2
1 5
1 ...

output:

836323745800
1518226766386
1517844083854

result:

ok 3 lines

Test #138:

score: 0
Accepted
time: 11ms
memory: 53092kb

input:

6000
1 1
1 1
1 1
2 1
2 2
1 3
2 3
1 5
2 4
1 4
2 2
1 6
1 7
2 1
1 7
2 5
2 1
1 8
1 10
1 11
2 9
2 4
2 5
1 10
1 10
2 7
2 5
2 2
1 15
2 4
2 1
2 1
2 2
1 11
1 13
2 3
2 9
2 5
2 3
2 4
2 2
1 16
1 19
1 20
1 21
1 16
2 2
1 21
1 23
1 24
2 6
1 24
2 1
2 2
2 3
2 1
1 26
1 11
1 19
2 6
2 5
2 1
1 28
2 6
2 5
2 3
1 30
1 26
1...

output:

1276287418242
1517033910908
1530296465683

result:

ok 3 lines

Test #139:

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

input:

6000
1 1
2 1
2 2
1 2
2 2
1 1
1 3
1 5
2 2
2 3
1 5
1 7
2 4
1 7
1 5
1 6
2 5
1 6
1 11
2 5
1 11
1 14
2 10
1 14
1 16
1 11
1 17
1 17
2 2
2 9
1 20
1 19
1 17
2 2
1 15
1 24
1 25
2 1
2 3
2 2
1 25
1 25
1 21
2 3
1 29
2 7
1 29
2 4
1 28
2 2
2 1
2 4
2 2
2 7
2 7
2 7
1 28
1 30
2 2
1 29
1 26
2 1
2 10
2 5
1 31
1 37
2 1...

output:

1252915315652
1522970875514
1558760293718

result:

ok 3 lines

Test #140:

score: 0
Accepted
time: 4ms
memory: 52976kb

input:

6000
2 1
1 1
2 2
1 1
2 3
2 3
1 1
2 1
1 2
2 2
1 4
1 2
1 7
1 4
1 5
2 2
2 7
2 3
2 1
1 10
1 9
1 10
2 3
1 12
1 9
2 2
2 5
1 15
2 6
1 15
1 12
1 15
2 2
1 14
2 8
1 11
1 19
1 21
2 9
2 2
1 23
2 11
2 6
1 22
1 25
2 2
1 23
1 23
2 1
1 28
1 20
1 29
2 5
2 15
2 4
2 3
1 31
2 9
2 5
2 7
2 2
1 32
2 2
2 1
2 10
2 3
1 31
2 ...

output:

1202809717000
1502345633548
1520197669749

result:

ok 3 lines

Test #141:

score: 0
Accepted
time: 8ms
memory: 53464kb

input:

5500
2 1
1 1
1 2
1 3
1 4
2 4
1 2
1 5
1 7
2 2
1 4
1 6
2 6
1 9
1 9
2 4
1 10
1 8
1 12
1 11
2 9
2 2
1 11
1 10
1 15
1 19
2 2
2 1
1 16
2 4
1 13
1 22
2 7
2 7
2 3
2 6
2 3
1 22
2 8
2 7
2 3
1 19
1 25
1 23
2 6
2 3
1 21
2 1
2 4
1 23
2 5
2 7
2 4
2 6
1 26
1 28
2 10
2 11
2 4
1 31
2 2
2 11
1 27
1 28
2 17
1 31
1 25
...

output:

1314018288980
1518493249886
1530057958864

result:

ok 3 lines

Test #142:

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

input:

6000
2 1
2 1
2 1
1 1
1 2
1 2
1 3
2 3
2 1
2 1
1 3
1 6
2 2
2 6
2 3
1 5
2 3
2 4
1 6
1 5
2 3
2 4
2 4
1 5
1 10
1 5
2 8
2 2
2 1
1 13
2 10
1 13
1 14
2 7
1 14
2 5
2 1
2 2
2 5
1 16
1 18
2 6
2 1
1 17
2 4
2 1
2 4
1 20
1 20
2 1
2 4
2 12
1 15
2 16
2 7
2 2
1 22
2 3
2 5
2 2
2 6
2 9
1 22
2 12
2 2
2 1
1 25
2 11
1 23...

output:

1207335493306
1519528735802
1544428196865

result:

ok 3 lines

Test #143:

score: 0
Accepted
time: 14ms
memory: 52612kb

input:

6000
1 1
2 2
1 1
2 1
2 1
2 3
2 2
1 2
2 2
1 4
2 1
1 5
1 5
2 1
2 3
2 2
1 3
2 3
1 6
1 4
1 9
2 4
1 8
1 6
1 10
1 11
1 11
2 4
2 1
1 16
1 8
2 3
2 1
1 17
1 19
1 18
1 20
1 16
1 23
1 22
1 22
2 5
2 2
2 3
2 3
1 23
1 25
1 27
1 29
2 6
2 1
1 28
1 31
2 1
2 5
1 29
2 11
1 31
2 2
1 33
2 2
1 35
1 25
1 37
1 30
2 20
2 8
...

output:

1376211057848
1548907367236
1606242160369

result:

ok 3 lines

Test #144:

score: 0
Accepted
time: 13ms
memory: 53056kb

input:

6000
1 1
1 1
1 3
1 4
2 3
1 4
1 2
2 2
1 6
1 6
2 3
2 8
2 8
2 7
1 5
1 9
2 2
1 10
2 7
2 1
2 4
1 7
2 5
1 11
1 14
2 3
2 1
2 3
1 14
1 16
1 10
1 10
2 3
1 15
1 12
2 1
2 5
2 3
1 17
2 8
2 5
2 4
2 3
1 21
1 21
2 4
2 4
2 4
2 10
1 24
2 5
1 25
2 8
1 11
2 2
2 2
1 27
2 6
1 23
1 28
2 5
2 1
1 26
1 26
1 31
2 8
1 18
1 31...

output:

1233937491296
1519199458782
1631835929906

result:

ok 3 lines

Test #145:

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

input:

6000
1 1
2 1
2 2
1 2
2 2
2 2
1 3
2 4
1 1
2 2
2 4
1 4
1 5
1 6
1 7
2 5
2 1
2 3
1 5
1 9
1 6
2 1
2 6
1 12
1 13
2 1
2 5
1 11
1 14
1 16
1 11
2 8
2 8
2 1
1 13
2 4
2 3
1 17
1 15
1 21
1 21
2 9
1 14
2 6
2 1
2 5
1 23
2 8
1 25
1 26
1 25
1 28
1 27
1 19
2 2
2 1
2 9
1 28
2 2
2 3
1 28
2 1
1 32
2 5
2 6
1 32
1 35
1 3...

output:

1430700042854
1509201117246
1488986891909

result:

ok 3 lines

Test #146:

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

input:

6000
2 1
1 1
1 2
2 2
2 2
2 1
1 2
1 1
2 2
2 1
2 3
2 1
2 2
1 2
2 3
1 6
1 7
2 2
1 2
2 5
1 5
1 10
1 11
2 3
1 7
2 6
1 12
1 14
1 14
2 4
1 16
1 15
2 1
1 13
2 9
1 17
2 3
1 18
2 2
1 19
1 21
1 18
2 4
2 3
2 2
1 17
2 7
1 25
2 4
1 26
2 4
1 25
1 28
2 2
1 27
2 7
1 26
2 6
1 30
2 5
1 28
1 25
2 4
1 27
2 5
1 29
2 3
2 ...

output:

1195809434392
1478807854336
1580184520986

result:

ok 3 lines

Test #147:

score: 0
Accepted
time: 4ms
memory: 53544kb

input:

5200
2 1
1 1
2 1
2 1
2 2
2 1
2 1
2 1
2 1
2 1
2 1
1 1
2 3
2 2
2 2
2 1
2 1
2 1
1 2
2 4
2 2
2 4
2 2
1 1
2 1
1 2
1 6
1 6
1 5
1 8
1 5
1 10
2 4
1 9
2 7
2 4
2 3
2 4
1 9
2 7
1 14
2 2
2 2
1 11
1 15
2 1
2 2
2 5
2 3
1 16
2 3
2 4
2 1
2 5
2 7
1 8
2 1
2 1
1 18
2 1
1 19
2 6
1 19
2 3
1 15
1 23
2 1
1 24
2 8
2 1
2 6
...

output:

1112175008592
1529439897262
1509713669278

result:

ok 3 lines

Test #148:

score: 0
Accepted
time: 3ms
memory: 53108kb

input:

6000
1 1
1 2
1 3
1 3
1 5
1 6
1 7
1 4
1 3
1 9
1 9
1 11
1 10
1 9
1 11
1 14
1 16
1 16
1 17
1 20
1 21
1 18
1 12
1 24
1 25
1 20
1 21
1 12
1 28
1 29
1 26
1 25
1 25
1 26
1 35
1 29
1 32
1 35
1 30
1 38
1 41
1 36
1 38
1 44
1 45
1 44
1 47
1 42
1 44
1 46
1 48
1 46
1 47
1 50
1 52
1 55
1 51
1 58
1 56
1 60
1 58
1 ...

output:

1428818008394
1507517744396
1499141316716

result:

ok 3 lines

Test #149:

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

input:

6000
1 1
1 2
1 3
1 4
1 5
1 4
1 4
1 8
1 8
1 7
1 5
1 11
1 7
1 12
1 11
1 16
1 16
1 18
1 19
1 15
1 21
1 19
1 23
1 22
1 22
1 23
1 21
1 27
1 27
1 27
1 29
1 32
1 32
1 34
1 33
1 32
1 35
1 34
1 39
1 40
1 31
1 42
1 42
1 29
1 44
1 45
1 41
1 48
1 45
1 45
1 51
1 48
1 43
1 53
1 52
1 52
1 40
1 47
1 52
1 60
1 60
1 ...

output:

1453878462236
1518747843440
1518675177107

result:

ok 3 lines

Test #150:

score: 0
Accepted
time: 8ms
memory: 52332kb

input:

6000
1 1
1 1
1 1
1 1
1 4
1 3
1 6
1 3
1 4
1 3
1 6
1 11
1 12
1 8
1 12
1 15
1 13
1 14
1 13
1 13
1 18
1 18
1 21
1 23
1 18
1 22
1 23
1 26
1 24
1 30
1 22
1 31
1 31
1 30
1 35
1 35
1 36
1 32
1 34
1 40
1 40
1 40
1 36
1 40
1 44
1 43
1 45
1 47
1 47
1 45
1 47
1 49
1 52
1 52
1 53
1 56
1 54
1 50
1 59
1 55
1 61
1 ...

output:

1370369095434
1517773166612
1578149956692

result:

ok 3 lines

Test #151:

score: 0
Accepted
time: 19ms
memory: 53456kb

input:

6000
1 1
1 1
1 1
1 2
1 4
1 6
1 4
1 7
1 2
1 6
1 10
1 11
1 8
1 11
1 13
1 13
1 14
1 12
1 18
1 19
1 17
1 21
1 19
1 20
1 23
1 19
1 26
1 24
1 19
1 26
1 24
1 31
1 31
1 29
1 35
1 34
1 28
1 32
1 38
1 35
1 40
1 39
1 41
1 38
1 41
1 39
1 47
1 48
1 49
1 49
1 49
1 42
1 47
1 43
1 53
1 56
1 55
1 52
1 58
1 60
1 49
1...

output:

1386667588286
1531206561192
1481636351681

result:

ok 3 lines

Test #152:

score: 0
Accepted
time: 11ms
memory: 52804kb

input:

6000
1 1
1 2
1 2
1 3
1 5
1 5
1 5
1 2
1 9
1 8
1 9
1 9
1 12
1 14
1 13
1 16
1 14
1 17
1 16
1 19
1 16
1 19
1 17
1 19
1 20
1 24
1 23
1 21
1 24
1 29
1 24
1 32
1 26
1 30
1 29
1 30
1 37
1 38
1 32
1 39
1 35
1 39
1 40
1 44
1 45
1 46
1 46
1 37
1 47
1 46
1 46
1 51
1 50
1 53
1 55
1 50
1 57
1 42
1 55
1 53
1 59
1 ...

output:

1391265981592
1499848616506
1718291140042

result:

ok 3 lines

Test #153:

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

input:

6000
1 1
1 2
1 2
1 4
1 5
1 5
1 6
1 6
1 9
1 10
1 11
1 10
1 10
1 8
1 14
1 16
1 8
1 18
1 16
1 17
1 21
1 22
1 20
1 19
1 22
1 18
1 20
1 23
1 29
1 30
1 22
1 23
1 33
1 32
1 25
1 36
1 36
1 33
1 31
1 35
1 37
1 39
1 43
1 41
1 43
1 33
1 47
1 48
1 47
1 45
1 51
1 47
1 48
1 51
1 37
1 54
1 56
1 55
1 55
1 55
1 61
1...

output:

1434997454324
1503020536258
1516517667215

result:

ok 3 lines

Test #154:

score: 0
Accepted
time: 15ms
memory: 52112kb

input:

6000
1 1
1 2
1 2
1 1
1 5
1 3
1 5
1 2
1 8
1 10
1 11
1 5
1 11
1 14
1 14
1 16
1 17
1 17
1 11
1 19
1 21
1 21
1 16
1 24
1 12
1 26
1 25
1 26
1 25
1 27
1 29
1 32
1 31
1 32
1 25
1 35
1 37
1 32
1 38
1 35
1 36
1 42
1 43
1 35
1 42
1 31
1 41
1 39
1 47
1 48
1 48
1 51
1 51
1 47
1 53
1 52
1 52
1 58
1 59
1 45
1 60
...

output:

1380903257296
1522189629176
1514579557977

result:

ok 3 lines

Test #155:

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

input:

6000
1 1
1 1
1 2
1 2
1 4
1 1
1 7
1 5
1 8
1 9
1 7
1 11
1 12
1 13
1 15
1 16
1 13
1 17
1 13
1 19
1 18
1 13
1 23
1 23
1 17
1 25
1 26
1 25
1 24
1 30
1 28
1 26
1 25
1 34
1 32
1 32
1 34
1 32
1 37
1 38
1 39
1 39
1 36
1 39
1 29
1 46
1 44
1 47
1 38
1 47
1 51
1 50
1 52
1 46
1 54
1 53
1 54
1 58
1 58
1 57
1 52
1...

output:

1380729201722
1511260997086
1741034944143

result:

ok 3 lines

Test #156:

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

input:

6000
1 1
1 1
1 2
1 3
1 1
1 6
1 5
1 7
1 6
1 10
1 11
1 7
1 9
1 11
1 15
1 16
1 15
1 18
1 16
1 20
1 18
1 21
1 23
1 22
1 25
1 20
1 18
1 22
1 19
1 29
1 23
1 32
1 31
1 34
1 31
1 36
1 37
1 36
1 37
1 33
1 35
1 39
1 43
1 41
1 45
1 41
1 47
1 46
1 47
1 43
1 46
1 48
1 49
1 53
1 53
1 49
1 57
1 50
1 33
1 56
1 61
1...

output:

1337267636888
1511345904474
1721094162232

result:

ok 3 lines

Test #157:

score: 0
Accepted
time: 11ms
memory: 53328kb

input:

6000
1 1
1 1
1 1
1 3
1 2
1 3
1 5
1 5
1 8
1 9
1 11
1 11
1 9
1 12
1 14
1 13
1 14
1 15
1 16
1 20
1 17
1 16
1 18
1 24
1 23
1 25
1 25
1 28
1 16
1 22
1 24
1 28
1 31
1 32
1 32
1 36
1 35
1 38
1 39
1 27
1 41
1 33
1 37
1 44
1 42
1 42
1 41
1 37
1 43
1 44
1 49
1 52
1 52
1 49
1 50
1 50
1 55
1 47
1 53
1 56
1 58
1...

output:

1358402430644
1522693642422
1746464164941

result:

ok 3 lines

Test #158:

score: 0
Accepted
time: 11ms
memory: 52796kb

input:

6000
1 1
1 1
1 1
1 4
1 5
1 3
1 7
1 8
1 8
1 4
1 8
1 11
1 11
1 13
1 13
1 15
1 13
1 14
1 16
1 12
1 21
1 22
1 21
1 23
1 25
1 22
1 19
1 23
1 15
1 22
1 27
1 30
1 32
1 34
1 32
1 33
1 34
1 35
1 32
1 39
1 27
1 39
1 39
1 39
1 41
1 45
1 40
1 43
1 49
1 49
1 48
1 50
1 46
1 54
1 44
1 55
1 50
1 50
1 52
1 58
1 60
1...

output:

1396670620832
1519543902402
1504449960085

result:

ok 3 lines

Test #159:

score: 0
Accepted
time: 8ms
memory: 52836kb

input:

6000
1 1
1 1
1 2
1 1
1 5
1 1
1 6
1 8
1 7
1 8
1 9
1 8
1 11
1 11
1 13
1 7
1 5
1 17
1 15
1 16
1 20
1 22
1 16
1 23
1 18
1 21
1 25
1 19
1 21
1 30
1 23
1 32
1 27
1 23
1 32
1 32
1 36
1 26
1 39
1 40
1 41
1 34
1 41
1 39
1 45
1 46
1 33
1 40
1 46
1 45
1 51
1 49
1 43
1 54
1 51
1 50
1 55
1 56
1 57
1 54
1 60
1 57...

output:

1373075597108
1506620407832
1608280453820

result:

ok 3 lines

Test #160:

score: 0
Accepted
time: 13ms
memory: 53424kb

input:

6000
1 1
1 2
1 2
1 2
1 4
1 6
1 5
1 7
1 7
1 7
1 10
1 6
1 10
1 9
1 14
1 15
1 14
1 18
1 19
1 18
1 21
1 15
1 20
1 21
1 24
1 23
1 24
1 28
1 29
1 26
1 28
1 30
1 32
1 32
1 33
1 35
1 35
1 23
1 39
1 33
1 36
1 41
1 41
1 39
1 42
1 41
1 46
1 41
1 49
1 46
1 46
1 51
1 53
1 46
1 51
1 56
1 51
1 58
1 58
1 60
1 49
1 ...

output:

1418871756378
1514699280744
1741175506892

result:

ok 3 lines

Test #161:

score: 0
Accepted
time: 3ms
memory: 52052kb

input:

6000
1 1
1 2
1 2
1 3
1 1
1 5
1 1
1 7
1 6
1 7
1 7
1 7
1 13
1 8
1 14
1 14
1 13
1 17
1 19
1 16
1 19
1 21
1 13
1 21
1 25
1 26
1 27
1 26
1 29
1 29
1 31
1 32
1 33
1 33
1 35
1 36
1 31
1 34
1 36
1 40
1 26
1 39
1 40
1 42
1 44
1 46
1 43
1 37
1 41
1 49
1 51
1 51
1 50
1 54
1 51
1 56
1 57
1 58
1 55
1 55
1 53
1 6...

output:

1405993577922
1505561621240
1521581292348

result:

ok 3 lines

Test #162:

score: 0
Accepted
time: 4ms
memory: 53972kb

input:

6000
1 1
1 1
1 3
1 4
1 5
1 3
1 6
1 5
1 5
1 7
1 11
1 5
1 10
1 11
1 15
1 16
1 15
1 12
1 14
1 20
1 17
1 17
1 23
1 23
1 24
1 26
1 26
1 23
1 27
1 24
1 30
1 31
1 29
1 14
1 26
1 35
1 35
1 30
1 36
1 34
1 40
1 40
1 43
1 40
1 38
1 44
1 39
1 47
1 48
1 47
1 49
1 50
1 53
1 48
1 52
1 52
1 57
1 57
1 54
1 58
1 61
1...

output:

1399674892332
1516055342322
1725832184719

result:

ok 3 lines

Test #163:

score: 0
Accepted
time: 8ms
memory: 52144kb

input:

6000
2 1
2 1
1 1
2 1
2 2
2 1
1 2
2 1
1 1
2 4
2 2
2 4
1 1
2 2
1 5
2 2
2 1
1 5
1 3
2 2
1 5
2 2
2 5
1 5
1 3
2 2
2 2
1 8
2 4
2 2
2 1
2 6
1 11
2 7
2 4
2 1
2 1
1 11
1 8
2 5
1 1
2 8
1 11
2 7
2 2
2 3
1 15
1 5
2 2
2 4
1 14
1 2
1 5
2 2
2 2
2 6
2 3
2 3
1 15
1 21
1 8
1 17
2 1
1 16
2 2
2 1
2 4
1 25
1 18
2 1
1 16...

output:

1486267888632
1525484543004
1600354042252

result:

ok 3 lines

Test #164:

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

input:

6000
2 1
1 1
2 2
2 2
2 1
2 2
2 2
1 1
2 3
2 1
2 3
2 3
2 2
1 2
2 3
1 3
2 1
2 1
1 1
1 6
1 2
1 4
1 5
1 7
2 1
2 3
1 6
1 6
2 3
2 2
2 1
2 1
2 5
1 9
1 6
2 7
1 8
1 13
2 7
2 6
2 10
1 10
1 1
2 1
2 1
1 10
1 5
2 2
2 3
2 6
1 14
2 4
2 6
2 6
1 21
2 4
1 16
1 17
2 6
1 22
2 5
1 8
1 27
2 3
1 24
1 27
1 14
1 4
2 5
1 27
2...

output:

1494768788740
1512712079892
1601177149233

result:

ok 3 lines

Test #165:

score: 0
Accepted
time: 4ms
memory: 52500kb

input:

6000
1 1
1 2
1 3
2 2
1 2
1 3
1 3
1 6
1 7
2 6
2 6
2 2
1 9
2 3
2 3
1 8
2 1
1 2
2 4
2 6
1 4
2 10
1 4
2 2
2 9
1 3
2 1
2 2
1 8
2 2
1 3
2 2
2 4
1 15
2 3
2 9
1 6
1 16
2 1
2 1
2 1
1 6
1 12
2 8
1 12
1 16
2 2
2 1
1 12
1 1
2 4
1 21
2 4
2 5
1 6
1 20
1 20
2 6
2 8
1 25
2 2
2 1
2 4
2 5
2 1
1 12
2 2
1 23
1 10
1 18
...

output:

1497251852208
1515315114692
1589448743144

result:

ok 3 lines

Test #166:

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

input:

4500
2 1
2 1
1 1
1 2
2 2
2 1
2 1
2 2
2 3
2 3
2 2
2 1
2 1
1 3
2 1
2 3
2 1
2 1
2 2
1 3
1 5
2 3
2 2
1 6
2 1
2 1
2 3
2 3
2 2
1 1
2 1
2 6
2 1
2 4
2 2
1 7
2 3
2 2
2 6
1 7
1 6
2 1
1 1
2 6
1 1
1 11
1 2
2 2
1 13
2 4
2 2
2 9
1 7
2 6
1 1
1 10
1 13
2 4
2 6
2 9
2 4
1 5
1 11
2 2
2 1
1 21
2 6
1 22
2 11
2 5
2 2
2 3...

output:

1438831318244
1523897555552
1620147048075

result:

ok 3 lines

Test #167:

score: 0
Accepted
time: 4ms
memory: 51844kb

input:

6000
1 1
2 1
1 1
1 3
1 1
1 3
1 3
1 3
2 4
1 2
1 8
1 8
2 7
1 4
2 2
2 3
2 2
1 4
1 4
1 2
2 4
1 5
2 6
1 14
1 4
2 4
1 17
1 2
1 7
1 8
1 15
1 11
2 1
2 12
1 10
2 4
2 3
1 15
2 1
2 6
1 21
2 6
2 4
2 1
1 21
1 25
2 4
1 4
1 15
1 27
2 7
2 17
2 8
2 1
1 4
1 23
2 2
1 21
2 1
2 3
2 5
2 1
2 1
1 16
1 3
2 4
1 2
1 31
2 7
2 ...

output:

1500913994494
1540214565800
1602992764944

result:

ok 3 lines

Test #168:

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

input:

6000
1 1
1 2
2 2
1 1
1 2
2 1
1 3
2 2
1 6
1 6
1 7
1 5
2 3
1 4
1 5
2 2
2 5
1 12
2 4
2 2
1 11
1 14
2 5
2 1
2 1
1 10
2 5
2 3
1 16
1 13
2 5
1 18
2 2
1 13
1 15
1 17
1 18
1 20
2 2
1 22
1 20
1 24
2 7
2 1
2 1
2 4
1 26
1 25
1 25
2 2
1 24
1 28
2 1
2 3
2 9
1 27
1 30
2 4
1 27
2 2
2 2
1 29
2 11
2 8
2 2
1 36
1 32
...

output:

1241517838668
1527091385388
1631319843261

result:

ok 3 lines

Test #169:

score: 0
Accepted
time: 4ms
memory: 52400kb

input:

4400
1 1
2 1
1 2
2 2
1 1
2 4
1 4
2 2
1 5
2 1
1 6
1 7
1 4
2 3
1 8
1 8
2 7
1 10
1 12
2 5
2 1
2 4
1 12
1 14
2 6
2 3
2 4
2 2
1 15
2 2
1 15
2 2
2 10
2 2
2 6
1 17
1 14
2 3
1 16
2 6
1 20
2 3
2 1
2 1
1 20
1 19
2 2
2 14
2 11
2 1
2 8
2 4
2 4
2 3
2 3
2 2
2 1
2 4
2 2
2 5
2 7
2 16
1 23
2 4
2 2
2 7
1 18
2 6
1 24
...

output:

1175742555456
1517512187656
1656090114200

result:

ok 3 lines

Test #170:

score: 0
Accepted
time: 4ms
memory: 52688kb

input:

4300
1 1
2 1
1 2
2 1
2 3
2 2
2 3
1 2
2 3
1 3
2 1
2 1
2 2
1 3
1 6
2 3
1 5
1 4
2 4
1 8
2 3
2 3
2 1
2 1
1 6
1 9
2 5
1 11
1 13
1 8
2 5
2 1
2 4
2 4
1 5
1 16
2 4
2 10
1 15
1 14
1 16
2 7
2 8
1 20
1 17
2 12
2 8
2 2
1 13
1 17
1 12
2 6
2 4
1 25
2 1
1 22
2 5
1 25
2 5
2 5
1 20
2 1
2 4
2 2
2 1
2 2
2 1
2 2
2 13
2...

output:

1402031571028
1518699650578
1531316633193

result:

ok 3 lines

Test #171:

score: 0
Accepted
time: 8ms
memory: 51808kb

input:

6000
2 1
1 1
1 1
1 2
1 2
2 2
1 3
1 3
1 4
2 2
1 4
1 5
1 5
2 7
1 6
2 2
1 6
2 5
1 7
2 7
1 7
1 8
1 8
1 9
2 2
2 6
1 9
1 10
1 10
1 11
2 3
2 6
2 7
1 11
2 5
1 12
1 12
2 5
2 1
2 4
2 3
2 7
1 13
1 13
2 3
2 10
1 14
1 14
2 11
1 15
2 8
2 6
1 15
1 16
1 16
1 17
2 12
2 9
2 9
2 7
2 6
2 1
1 17
2 1
1 18
1 18
2 5
1 19
1...

output:

1526943148708
1485929845428
1611062864766

result:

ok 3 lines

Test #172:

score: 0
Accepted
time: 8ms
memory: 53100kb

input:

5900
2 1
1 1
1 1
1 2
2 1
1 2
2 1
1 3
1 3
2 1
2 2
2 5
2 2
1 4
2 2
2 1
2 4
1 4
2 4
1 5
1 5
1 6
1 6
2 3
2 10
2 2
1 7
2 10
1 7
2 1
1 8
2 5
1 8
1 9
1 9
2 3
2 1
1 10
1 10
2 3
2 14
1 11
1 11
2 5
1 12
1 12
1 13
2 1
2 5
1 13
1 14
2 6
2 7
2 3
1 14
2 1
1 15
2 7
2 5
2 5
1 15
2 3
1 16
2 2
2 5
2 4
1 16
1 17
2 2
1...

output:

1522426310434
1522480893932
1595361465732

result:

ok 3 lines

Test #173:

score: 0
Accepted
time: 3ms
memory: 52672kb

input:

6000
1 1
1 1
1 1
2 1
1 2
2 4
2 2
2 5
2 3
1 2
1 2
1 2
1 2
2 2
2 2
1 2
2 1
2 2
1 1
1 1
2 10
2 2
2 4
1 1
2 2
1 1
1 1
1 2
1 2
2 1
2 3
2 3
1 2
1 2
2 5
2 11
1 2
1 1
2 4
2 1
1 2
2 4
1 1
2 4
2 4
2 2
2 2
1 2
2 5
1 2
2 1
2 10
1 1
1 2
1 1
2 2
2 5
2 6
2 5
2 8
1 2
2 1
1 2
2 7
2 1
1 1
2 7
1 1
2 1
2 2
1 1
1 1
1 2
...

output:

861856949340
1519247516832
1463040243916

result:

ok 3 lines

Test #174:

score: 0
Accepted
time: 12ms
memory: 51932kb

input:

6000
1 1
2 2
1 1
2 3
1 2
2 2
1 2
1 1
2 2
2 2
2 2
1 1
2 3
1 1
2 3
2 2
1 1
1 1
2 2
2 2
1 2
1 2
2 4
1 2
2 1
2 1
1 2
2 1
2 2
2 5
1 2
1 2
1 1
2 1
1 2
1 2
1 1
1 2
1 1
1 2
2 4
1 1
1 1
2 6
2 1
2 4
2 1
1 2
2 1
1 2
1 2
2 9
1 2
1 2
1 2
2 2
1 1
1 2
1 1
1 2
1 2
1 2
1 2
1 2
1 2
1 1
2 3
1 2
1 1
2 2
2 5
1 2
1 2
2 4...

output:

895882542282
1497130587232
1472468989643

result:

ok 3 lines

Subtask #6:

score: 41
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #175:

score: 41
Accepted
time: 920ms
memory: 203256kb

input:

1000000
1 1
2 1
2 1
2 2
2 2
2 2
1 2
2 3
1 3
2 4
2 2
1 3
2 4
2 2
1 1
2 1
2 4
2 4
1 5
1 4
1 6
1 6
2 8
2 2
1 3
2 2
1 8
1 7
2 4
2 5
1 8
2 7
1 6
1 9
1 6
2 1
2 11
1 4
1 2
2 3
1 13
2 5
2 19
2 2
2 7
1 8
1 13
1 18
2 6
1 8
1 24
1 5
1 19
1 7
1 12
1 9
2 3
1 23
1 11
1 5
2 10
2 20
2 15
2 17
2 7
1 12
1 34
1 24
2 3...

output:

139454817623770
252717232932302
255189224048332

result:

ok 3 lines

Test #176:

score: 0
Accepted
time: 336ms
memory: 112908kb

input:

500000
1 1
2 2
2 2
2 1
2 2
2 1
2 1
1 1
1 3
2 3
2 2
2 2
2 1
2 4
2 3
2 2
1 1
2 2
1 3
2 6
1 3
1 7
2 3
1 4
2 4
2 2
2 2
2 1
2 6
1 8
2 4
2 5
2 3
2 9
1 8
2 8
1 9
2 8
2 9
2 6
2 8
1 3
2 1
1 3
2 1
1 9
2 12
1 14
2 16
2 5
1 3
1 11
1 13
1 15
1 16
2 3
1 13
2 14
2 10
1 22
1 22
2 17
2 8
2 17
1 5
1 15
2 19
2 5
2 23
...

output:

83443305065372
151702258602688
153307097043889

result:

ok 3 lines

Test #177:

score: 0
Accepted
time: 927ms
memory: 203084kb

input:

1000000
2 1
2 1
1 1
2 2
1 2
2 3
1 1
1 2
1 2
2 6
2 3
2 2
1 4
2 1
1 5
1 3
2 7
1 8
2 9
2 1
1 8
2 8
1 1
1 10
2 4
1 5
2 9
1 6
1 15
1 3
1 4
2 5
1 4
2 11
1 16
1 3
1 18
2 5
2 7
2 22
1 8
1 12
1 10
1 24
1 9
2 1
1 14
1 6
2 19
2 24
2 10
2 24
2 2
1 11
1 17
2 6
2 21
1 10
2 21
1 25
1 17
2 8
1 32
1 1
1 9
2 3
1 10
1...

output:

139067725286520
252963535668334
255159222422960

result:

ok 3 lines

Test #178:

score: 0
Accepted
time: 195ms
memory: 81892kb

input:

600000
2 1
2 1
1 1
2 1
2 1
2 2
2 2
2 2
2 1
2 2
2 1
2 1
2 1
1 2
2 1
2 3
1 3
1 4
2 1
2 3
2 3
1 4
2 4
2 2
2 4
2 3
2 6
2 5
2 2
1 3
2 2
2 7
2 1
2 4
2 7
2 6
2 3
2 4
2 7
2 7
2 6
2 4
2 3
2 4
2 7
2 6
2 7
1 2
1 6
2 9
1 3
1 9
1 7
2 10
2 7
2 6
2 4
1 9
2 2
2 1
2 2
2 4
2 2
2 1
1 3
2 12
2 1
2 11
2 8
2 13
2 4
2 1
2...

output:

139207264123104
252923491966652
254942280560624

result:

ok 3 lines

Test #179:

score: 0
Accepted
time: 827ms
memory: 257712kb

input:

980000
2 1
1 1
1 1
2 2
2 2
2 1
2 1
2 2
1 2
2 3
2 4
1 4
1 2
1 3
2 7
2 3
2 4
2 1
2 3
1 2
2 7
1 7
1 8
2 5
1 10
2 5
2 1
2 3
1 11
2 4
1 11
1 12
2 8
1 9
1 9
2 4
2 1
2 3
2 3
1 16
2 11
1 15
1 12
2 1
2 4
1 15
1 18
2 3
2 1
2 7
1 14
1 21
2 3
1 23
2 3
1 24
2 7
1 10
1 23
2 4
1 16
2 4
2 3
1 18
1 26
1 26
2 7
2 6
2...

output:

204854987900984
252777827060256
256657900810310

result:

ok 3 lines

Test #180:

score: 0
Accepted
time: 858ms
memory: 266604kb

input:

1000000
1 1
1 2
1 2
1 1
2 3
2 3
1 3
1 3
2 1
2 1
1 7
1 3
2 2
2 6
2 1
1 5
1 10
1 9
1 12
2 2
1 13
1 9
1 12
1 14
1 17
2 3
1 14
2 3
1 17
1 19
1 17
2 9
2 15
1 19
1 15
2 12
1 21
1 24
1 26
1 27
1 27
2 9
1 28
1 28
2 5
2 8
2 7
1 24
2 2
1 32
2 4
1 29
1 28
2 2
2 8
1 18
2 4
2 2
1 26
1 26
2 8
2 2
2 2
2 1
1 29
2 1...

output:

184448577754840
252833373065584
265494832559346

result:

ok 3 lines

Test #181:

score: 0
Accepted
time: 859ms
memory: 266592kb

input:

1000000
1 1
2 2
2 1
2 2
1 1
1 3
1 4
2 2
2 2
2 2
1 2
1 5
1 4
1 8
1 7
1 5
1 8
2 3
2 1
1 12
2 5
2 3
2 6
2 4
1 12
2 3
1 9
2 1
1 12
1 15
1 14
2 1
2 1
2 7
2 1
2 5
1 15
2 2
2 1
2 11
2 2
2 1
1 15
2 4
2 7
1 16
2 7
2 4
1 20
2 9
2 10
2 1
2 5
1 18
2 7
2 5
2 3
1 22
2 3
2 6
2 1
2 12
1 24
2 7
2 2
1 24
2 1
2 8
2 1
...

output:

195008282311094
252636415890068
261255104895202

result:

ok 3 lines

Test #182:

score: 0
Accepted
time: 866ms
memory: 266352kb

input:

1000000
2 1
1 1
1 1
2 3
1 3
1 4
2 1
2 3
1 4
1 2
1 5
2 1
2 7
1 5
2 3
1 9
2 6
2 1
1 10
2 5
1 11
2 4
1 12
2 2
2 7
2 5
2 5
2 1
2 4
1 10
2 2
2 6
1 7
1 13
1 12
1 10
1 17
1 11
2 4
1 19
2 5
2 8
1 17
1 17
2 10
2 8
2 4
1 21
2 2
1 20
1 24
1 26
1 24
2 5
2 8
1 26
1 27
1 22
1 27
1 32
2 4
1 32
1 30
2 7
1 25
1 30
1...

output:

192427721599692
252473900239046
263807059920014

result:

ok 3 lines

Test #183:

score: 0
Accepted
time: 838ms
memory: 265980kb

input:

1000000
1 1
1 2
1 2
1 1
2 3
1 3
1 6
2 3
2 2
2 3
1 5
1 8
2 1
1 6
1 4
1 6
2 1
1 11
1 5
1 13
1 14
1 11
2 11
2 3
2 6
2 2
2 6
2 3
2 8
1 15
2 2
2 9
2 2
2 2
2 3
1 16
1 18
2 1
1 20
1 17
2 12
2 4
1 22
2 1
1 22
1 24
1 24
2 2
1 24
1 26
2 5
1 24
2 3
2 8
2 3
2 11
2 11
2 1
2 8
2 2
2 5
2 4
2 5
1 23
2 11
1 29
2 10
...

output:

211433090224428
252668217771702
257412220405520

result:

ok 3 lines

Test #184:

score: 0
Accepted
time: 879ms
memory: 266404kb

input:

1000000
1 1
1 1
1 1
1 3
1 5
1 5
1 7
1 7
1 7
1 9
1 8
1 12
1 13
1 8
1 8
1 16
1 10
1 17
1 17
1 20
1 11
1 21
1 23
1 23
1 13
1 23
1 23
1 19
1 25
1 30
1 24
1 30
1 32
1 24
1 35
1 32
1 37
1 36
1 31
1 39
1 41
1 42
1 43
1 43
1 42
1 41
1 44
1 46
1 48
1 50
1 47
1 47
1 52
1 52
1 51
1 54
1 56
1 46
1 59
1 59
1 58
...

output:

229240424060576
252873471341682
266452711760184

result:

ok 3 lines

Test #185:

score: 0
Accepted
time: 854ms
memory: 266068kb

input:

1000000
1 1
1 2
1 1
1 1
1 2
1 6
1 4
1 8
1 7
1 10
1 4
1 12
1 10
1 14
1 12
1 8
1 16
1 17
1 18
1 20
1 10
1 20
1 23
1 23
1 14
1 26
1 24
1 21
1 28
1 30
1 23
1 30
1 31
1 34
1 29
1 36
1 34
1 32
1 32
1 40
1 34
1 34
1 43
1 37
1 44
1 45
1 47
1 43
1 49
1 48
1 50
1 42
1 49
1 52
1 48
1 53
1 53
1 51
1 59
1 58
1 5...

output:

236265382792556
252792176989282
263517240083907

result:

ok 3 lines

Test #186:

score: 0
Accepted
time: 866ms
memory: 266268kb

input:

1000000
1 1
1 2
1 3
1 3
1 5
1 4
1 6
1 6
1 6
1 8
1 5
1 12
1 11
1 10
1 9
1 16
1 12
1 14
1 15
1 19
1 20
1 17
1 12
1 23
1 19
1 25
1 20
1 27
1 24
1 28
1 29
1 31
1 27
1 34
1 24
1 36
1 32
1 37
1 36
1 40
1 29
1 33
1 43
1 38
1 41
1 46
1 38
1 40
1 40
1 49
1 47
1 50
1 49
1 53
1 52
1 50
1 56
1 56
1 59
1 51
1 50...

output:

242878412208642
252869515020544
266241028159346

result:

ok 3 lines

Test #187:

score: 0
Accepted
time: 920ms
memory: 203244kb

input:

1000000
2 1
1 1
1 2
2 2
1 3
2 2
2 1
1 1
1 1
1 5
1 4
1 5
2 1
1 5
2 5
2 1
1 9
1 9
2 1
2 3
2 1
2 4
2 1
2 9
2 8
1 12
1 3
1 8
1 12
2 4
1 10
2 3
2 2
1 8
2 10
1 17
2 7
1 2
2 1
2 2
2 1
1 11
2 1
2 1
1 1
1 6
2 8
2 14
2 1
1 10
1 14
1 19
1 19
2 4
1 21
1 25
1 14
2 3
1 19
1 13
1 14
2 2
1 26
1 34
1 33
2 2
2 3
1 36...

output:

252672295323102
252838272143780
264870125372330

result:

ok 3 lines

Test #188:

score: 0
Accepted
time: 384ms
memory: 122008kb

input:

490000
1 1
1 1
2 1
2 3
1 3
2 2
2 3
1 3
2 1
2 2
1 4
1 3
2 3
1 2
2 7
1 1
1 2
1 9
1 7
2 3
2 5
1 8
2 4
2 4
1 1
2 6
2 2
2 2
1 7
2 1
2 9
1 14
2 3
1 8
2 4
1 10
2 6
1 12
2 6
2 9
1 17
1 15
1 6
2 3
1 10
1 8
1 19
2 3
2 4
2 11
2 9
2 5
2 1
2 5
2 1
2 10
1 10
1 4
2 8
1 5
2 4
1 13
1 23
1 9
2 1
1 27
1 24
1 9
1 11
2 ...

output:

131313419146730
131491533106308
139653579885577

result:

ok 3 lines

Test #189:

score: 0
Accepted
time: 619ms
memory: 170808kb

input:

1000000
1 1
2 1
2 2
2 2
2 2
2 2
1 2
2 3
1 2
2 3
2 2
1 1
2 3
2 4
1 2
2 4
2 2
2 1
1 1
1 1
1 2
1 2
2 2
2 7
1 1
2 2
1 2
1 2
2 4
2 6
1 1
2 4
1 1
1 2
1 1
2 1
2 2
1 2
1 1
2 1
1 1
2 6
2 3
2 8
2 7
1 1
1 2
1 1
2 6
1 1
1 2
1 1
1 1
1 2
1 2
1 1
2 3
1 1
1 2
1 1
2 4
2 8
2 9
2 15
2 11
1 1
1 2
1 1
2 3
1 2
1 2
1 1
1 ...

output:

146807820522434
253023541659518
247643254143183

result:

ok 3 lines

Test #190:

score: 0
Accepted
time: 629ms
memory: 170840kb

input:

1000000
2 1
1 1
2 1
1 1
2 3
2 3
1 2
1 1
1 1
2 3
1 2
1 1
2 5
2 4
1 1
1 2
2 2
1 2
2 3
2 1
2 3
1 1
2 5
2 3
1 2
2 4
1 2
1 2
1 1
2 6
1 1
1 1
2 1
2 3
1 1
1 1
2 4
2 2
1 2
2 6
2 3
2 8
2 2
1 2
2 2
2 4
1 1
1 2
2 6
1 1
1 1
1 2
1 2
1 2
1 2
2 4
2 2
1 1
1 1
1 1
2 8
1 1
1 1
1 1
1 1
1 2
2 1
2 3
1 2
1 2
1 2
1 1
2 13...

output:

146788883428766
252904347222182
247886031962925

result:

ok 3 lines
English 繁體中文 简体中文

Server Time: 2024-11-30 01:40:46 | OpenSource Project