QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#523509#2363. Dragon BallsOMoonStarsAC ✓2ms3808kbC++172.7kb2024-08-18 12:35:492024-08-18 12:35:49

Judging History

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

  • [2024-08-18 12:35:49]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3808kb
  • [2024-08-18 12:35:49]
  • 提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define endl '\n'
using namespace std;
using ll=long long;
using db=double;
using pii=pair<int,int>;
const db eps=1e-9;//??
inline int sign(db a){return a<-eps?-1:a>eps;}//?????eps??0
inline int cmp(db a,db b){return sign(a-b);}//a=b??0,a>b??1,a<b??-1
struct P{//??
    db x,y;//??
    P(){}//??????
    P(db _x,db _y):x(_x),y(_y){}//????
    P operator+(P p){return {x+p.x,y+p.y};}//???
    P operator-(P p){return {x-p.x,y-p.y};}//???
    P operator*(db d){return {x*d,y*d};}//??
    P operator/(db d){return {x/d,y/d};}//?????
    bool operator==(P o)const{//?????,??????
        return cmp(x,o.x)==0&&cmp(y,o.y)==0;
    }
    db distTo(P p){return (*this-p).abs();}
    db abs(){return sqrt(abs2());}
    db abs2(){return x*x+y*y;}
    P rot90(){return P(-y,x);}
    P unit(){return *this/abs();}
};
vector<P>isCC(P o1,db r1,P o2,db r2){//???????????
    db d=o1.distTo(o2);
    if(cmp(d,r1+r2)==1)return {};
    if(cmp(d,fabs(r1-r2))==-1)return{};
    d=min(d,r1+r2);
    db y=(r1*r1+d*d-r2*r2)/(2*d),x=sqrt(r1*r1-y*y);
    P dr=(o2-o1).unit();
    P q1=o1+dr*y,q2=dr.rot90()*x;
    return {q1-q2,q1+q2}; 
}
int n;
// vector<P>dbp;
ll query(int x,int y)
{
    cout << x << ' ' << y << endl;
    ll d;
    cin >> d;
    if(!d)n--;
    if(!n)exit(0);
    return d;
    // P cur={(db)x,(db)y};
    // ll res=2e12;
    // for(auto it:dbp)
    //     res=min(res,(ll)(cur.distTo(it)*cur.distTo(it)));
    // cout << x << ' ' << y << ' ' << res << endl;
    // if(!res)
    // {
    //     n--;
    //     dbp.erase(find(dbp.begin(),dbp.end(),P((db)x,(db)y)));
    // }
    // if(!n)exit(0);
    // return res;
}
void solve()
{
    vector<pair<P,db>>rd;
    for(int i=0;i<=1e6;i+=5e5)
        for(int j=0;j<=1e6;j+=5e5)
            if(i!=5e5||j!=5e5)
                rd.pb({{(db)i,(db)j},sqrt(query(i,j))});
    for(int i=0;i<8;i++)
        for(int j=i+1;j<8;j++)
            for(auto [x,y]:isCC(rd[i].fi,rd[i].se,rd[j].fi,rd[j].se))
            {
                if(x<0||x>1e6||y<0||y>1e6)continue;
                ll d=query(x,y);
                if(d<5)
                {
                    for(int dx=-2;dx<=2;dx++)
                        for(int dy=-2;dy<=2;dy++)
                            if(dx||dy)
                            {
                                int nx=x+dx,ny=y+dy;
                                if(nx<0||nx>1e6||ny<0||ny>1e6)continue;
                                query(nx,ny);
                            }
                }
            }
}
int main()
{
    cin >> n;
    // for(int i=0;i<n;i++)
    // {
    //     int x,y;
    //     cin >> x >> y;
    //     dbp.pb({(db)x,(db)y});
    // }
    while(true)
        solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3608kb

input:

2
115075346069
177820346069
740565346069
15430198450
707703346069
386579198450
609136198450
1174841346069
0
34753508181
34753827802
34754147425
34754467050
34754786677
34753316200
34753635821
34753955444
34754275069
34754594696
34753124221
34753443842
34754083090
34754402717
34752932244
34753251865
...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
282862 187255
282860 187253
282860 187254
282860 187255
282860 187256
282860 187257
282861 187253
282861 187254
282861 187255
282861 187256
282861 187257
282862 187253
282862 187254
282862 187256
282862 187257
28...

result:

ok Queries used 68

Test #2:

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

input:

7
67217950469
221554950469
365381492489
46595294269
27973492489
92416679560
88985549749
4947294312
1
13
10
9
10
13
8
5
4
5
8
5
2
2
5
4
1
0
7793579545
7793520464
7793590417
7793531330
7793472245
7793413162
7793354081
78135739205
1
13
8
5
4
5
10
5
2
1
2
9
4
0
16200613897
16199748794
16199917385
162000...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
240969 95663
240967 95661
240967 95662
240967 95663
240967 95664
240967 95665
240968 95661
240968 95662
240968 95663
240968 95664
240968 95665
240969 95661
240969 95662
240969 95664
240969 95665
240970 95661
2409...

result:

ok Queries used 230

Test #3:

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

input:

7
106609651105
30680651105
161484896410
2493533200
30789662221
51456586905
87040586905
40050632617
0
52117149577
52117073780
52116997985
52116922192
52116846401
52116699330
52116623533
52116547738
52116471945
52116396154
52116249085
52116173288
52116021700
52115945909
52115798842
52115723045
5211564...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
19492 325929
19490 325927
19490 325928
19490 325929
19490 325930
19490 325931
19491 325927
19491 325928
19491 325929
19491 325930
19491 325931
19492 325927
19492 325928
19492 325930
19492 325931
19493 325927
1949...

result:

ok Queries used 194

Test #4:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

1
450371040181
44986040181
139601040181
556005040181
245235040181
1161639040181
756254040181
850869040181
0

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
144366 655385

result:

ok Queries used 9

Test #5:

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

input:

7
174257131880
82676628074
360919628074
127651131880
271364190210
313430251385
5617251385
197804251385
5497852868
41071399697
0
24510354925
24510082402
24509809881
24509537362
24509264845
24510200744
24509928221
24509655700
24509383181
24509110664
24510046565
24509774042
24509229002
24508956485
2450...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
239958 341580
94221 406668
296606 293738
296604 293736
296604 293737
296604 293738
296604 293739
296604 293740
296605 293736
296605 293737
296605 293738
296605 293739
296605 293740
296606 293736
296606 293737
296...

result:

ok Queries used 218

Test #6:

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

input:

5
80741738512
14162303522
71491446100
46737738512
76591446100
230666783525
67364783525
404062783525
0
150507791776
150507069497
150506347220
150505624945
150504902672
150508075225
150507352946
150506630669
150505908394
150505186121
150508358676
150507636397
150506191845
150505469572
150508642129
150...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
284004 9136
284002 9134
284002 9135
284002 9136
284002 9137
284002 9138
284003 9134
284003 9135
284003 9136
284003 9137
284003 9138
284004 9134
284004 9135
284004 9137
284004 9138
284005 9134
284005 9135
284005 9...

result:

ok Queries used 129

Test #7:

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

input:

7
118225786066
80250159601
16662593025
98546786066
42959589264
503407627042
140486627042
277565627042
861394817
0
12778190633
12778000138
12777809645
12777619154
12777428665
12778312388
12778121893
12777931400
12777740909
12777550420
12778434145
12778243650
12777862666
12777672177
12778555904
127783...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
187871 287975
269679 213305
269677 213303
269677 213304
269677 213305
269677 213306
269677 213307
269678 213303
269678 213304
269678 213305
269678 213306
269678 213307
269679 213303
269679 213304
269679 213306
26...

result:

ok Queries used 275

Test #8:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

7
167450188805
86632207649
43764207649
28904188805
15260136541
139103522050
160219099156
105935582285
62793337381
0
74090087845
74090039490
74089991137
74089942786
74089894437
74089545608
74089497253
74089448900
74089400549
74089352200
74089003373
74088955018
74088858314
74088809965
74088461140
7408...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
240851 330817
388546 128383
388544 128381
388544 128382
388544 128383
388544 128384
388544 128385
388545 128381
388545 128382
388545 128383
388545 128384
388545 128385
388546 128381
388546 128382
388546 128384
38...

result:

ok Queries used 225

Test #9:

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

input:

4
7851264122
10338408985
342794408985
25717042765
533301408985
32475871850
115760871850
699045871850
0
135659234873
135659970980
135660707089
135661443200
135662179313
135659206858
135659942965
135660679074
135661415185
135662151298
135659178845
135659914952
135661387172
135662123285
135659150834
13...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
59493 417544
59491 417542
59491 417543
59491 417544
59491 417545
59491 417546
59492 417542
59492 417543
59492 417544
59492 417545
59492 417546
59493 417542
59493 417543
59493 417545
59493 417546
59494 417542
5949...

result:

ok Queries used 108

Test #10:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

1
635213397133
115626397133
96039397133
677971397133
138797397133
1220729397133
701142397133
681555397133
0

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
207242 769587

result:

ok Queries used 9

Test #11:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

4
0
250000000000
0
250000000000
250000000000
0
250000000000
0

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000

result:

ok Queries used 8

Test #12:

score: 0
Accepted
time: 1ms
memory: 3740kb

input:

2
169
249988000169
999976000169
249993000170
1249971000169
999986000170
1249975000170
1999964000170
0
17
16
17
20
25
10
9
10
13
18
5
4
8
13
2
1
2
5
10
1
0

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
5 12
3 10
3 11
3 12
3 13
3 14
4 10
4 11
4 12
4 13
4 14
5 10
5 11
5 13
5 14
6 10
6 11
6 12
6 13
6 14
7 10
7 11

result:

ok Queries used 30

Test #13:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

7
0
249999000001
1
249999000001
249999000001
1
249999000001
1
0
10
5
1
9
4
1
0
999994000018
999994000013
999994000010
999994000009
999998000002
999996000005
499999000005
500000000002
999996000008
999996000004
999996000004
0
10
9
10
5
4
5
1
2
1
0
999994000009
999998000002
999996000008
500000000002
49...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
0 999999
0 999997
0 999998
0 1000000
1 999997
1 999998
1 999999
1 1000000
2 999997
2 999998
2 999999
2 1000000
0 999999
1 1
499998 499998
499998 500001
1 999998
1 1000000
1 1000000
999999 0
999997 0
999997 1
9999...

result:

ok Queries used 55

Test #14:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

3
50
249994000052
999988000052
249993000050
1249981000085
999986000050
1249980000085
1999974000085
2
18
13
10
9
10
13
8
5
4
5
10
5
1
2
9
4
1
0
10
8
8
5
4
5
17
0
40
40
29
20
13
37
37
26
17
10
36
36
16
9
37
37
26
17
10
40
40
29
20
13
25
9
0

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
3 5
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 3
3 4
3 6
3 7
4 3
4 4
4 5
4 6
4 7
5 3
5 4
5 5
5 6
5 7
3 5
7 1
5 0
5 0
5 1
5 2
5 3
6 0
6 0
6 1
6 2
6 3
7 0
7 0
7 2
7 3
8 0
8 0
8 1
8 2
8 3
9 0
9 0
9 1
9 2
9 3
7 1
4 6
...

result:

ok Queries used 62

Test #15:

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

input:

2
61
249992000065
999984000065
249994000061
1249983000065
999988000061
1249983000061
1999978000061
1
13
8
5
4
5
10
5
2
1
2
9
4
0
29
72
61
52
45
40
85
74
65
58
53
25
1
10
5
2
1
2
10
5
2
1
2
9
4
0

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
6 4
4 2
4 3
4 4
4 5
4 6
5 2
5 3
5 4
5 5
5 6
6 2
6 3
6 5
6 6
7 2
7 3
7 4
7 5
7 6
8 2
8 3
8 4
8 5
8 6
5 5
1 7
0 5
0 6
0 7
0 8
0 9
0 5
0 6
0 7
0 8
0 9
1 5
1 6
1 8

result:

ok Queries used 48

Test #16:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

1
100
249990000100
999980000100
250000000100
1249980000100
1000000000100
1249990000100
1999980000100
0

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
0 10

result:

ok Queries used 9

Test #17:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

2
36
249996000052
999992000052
249994000036
1249986000052
999988000036
1249984000052
1999980000052
5
5
0
20
13
8
17
10
5
9
4
17
10
5
20
13
8
16
16
16
0

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
4 3
4 3
6 0
4 0
4 1
4 2
5 0
5 1
5 2
6 1
6 2
7 0
7 1
7 2
8 0
8 1
8 2
6 0
6 0
6 0
6 4

result:

ok Queries used 29

Test #18:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

3
41
249992000145
999984000145
249990000101
1249975000145
999980000101
1249974000145
1999966000145
0
10
13
18
25
34
17
20
25
32
41
26
29
41
50
25
36
45
52
61
26
37
50
65
74
45
499969000505
29
45
799967200349
29
999974000194
20
45
799959200554
34
45
1999938000505
29
34
999958000477
36
0
41
32
25
20
5...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
9 8
7 6
7 7
7 8
7 9
7 10
8 6
8 7
8 8
8 9
8 10
9 6
9 7
9 9
9 10
10 6
10 7
10 8
10 9
10 10
11 6
11 7
11 8
11 9
11 10
10 8
499991 499989
9 7
10 8
399999 799987
9 7
9 999992
8 7
10 8
799987 399996
9 8
10 8
999991 999...

result:

ok Queries used 100

Test #19:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

4
25
249994000136
999988000136
249990000136
1249978000136
999980000136
1249974000136
1999968000136
0
0
34
45
58
73
32
41
52
65
80
41
50
74
89
52
61
72
85
100
65
74
85
98
113
41
499979000221
50
41
799973600290
50
999978000221
41
41
799970400281
61
41
1999958000221
41
61
999970000261
52
61
52
41
50
41...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
10 6
8 4
8 5
8 6
8 7
8 8
9 4
9 5
9 6
9 7
9 8
10 4
10 5
10 7
10 8
11 4
11 5
11 6
11 7
11 8
12 4
12 5
12 6
12 7
12 8
9 5
499994 499990
10 5
9 5
400001 799988
10 5
10 999994
9 5
9 5
799989 399995
10 6
9 5
999994 999...

result:

ok Queries used 86

Test #20:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

7
428518727937
111543113817
102607113817
196934727937
4684945204
67795889705
1699465777
142323788185
39108659600
1
13
8
5
4
5
10
5
2
1
2
9
4
0
172816731961
172819797620
172819166525
172818535432
172817904341
172817273252
172820338913
172819707818
172819076725
172818445634
172817814545
1
13
10
9
10
1...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
327196 566975
481584 443390
481582 443388
481582 443389
481582 443390
481582 443391
481582 443392
481583 443388
481583 443389
481583 443390
481583 443391
481583 443392
481584 443388
481584 443389
481584 443391
48...

result:

ok Queries used 214

Test #21:

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

input:

7
157163452745
18587452745
380011452745
100859452745
521073452745
544555452745
542878452745
1037417452745
0
597304954
597316109
597327266
597338425
597349586
597257365
597268520
597279677
597290836
597301997
597209778
597220933
597243249
597254410
597162193
597173348
597184505
597195664
597206825
59...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
78563 388576
78561 388574
78561 388575
78561 388576
78561 388577
78561 388578
78562 388574
78562 388575
78562 388576
78562 388577
78562 388578
78563 388574
78563 388575
78563 388577
78563 388578
78564 388574
7856...

result:

ok Queries used 229

Test #22:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

7
101206452745
165374452745
113526452745
50654452745
66814452745
108434452745
25231452745
168970452745
0
174169514410
174169599089
174169683770
174169768453
174169853138
174168684045
174168768724
174168853405
174168938088
174169022773
174167853682
174167938361
174168107725
174168192410
174167023321
...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
258211 185832
258209 185830
258209 185831
258209 185832
258209 185833
258209 185834
258210 185830
258210 185831
258210 185832
258210 185833
258210 185834
258211 185830
258211 185831
258211 185833
258211 185834
25...

result:

ok Queries used 231

Test #23:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

5
273194767090
29687767090
53340825700
351015767090
20412445325
236044691010
917691010
142079445325
0
92594380738
92593810385
92593240034
92592669685
92592099338
92594593045
92594022692
92593452341
92592881992
92592311645
92594805354
92594235001
92593094301
92592523954
92595017665
92594447312
925938...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
172179 493507
172177 493505
172177 493506
172177 493507
172177 493508
172177 493509
172178 493505
172178 493506
172178 493507
172178 493508
172178 493509
172179 493505
172179 493506
172179 493508
172179 493509
17...

result:

ok Queries used 148

Test #24:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

7
26903541044
46209025117
82955025117
114115541044
46826428820
5606064721
38880117737
254398428820
0
498903093781
498901707450
498900321121
498898934794
498897548469
498903365252
498901978921
498900592592
498899206265
498897819940
498903636725
498902250394
498899477738
498898091413
498903908200
4989...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
162788 20090
162786 20088
162786 20089
162786 20090
162786 20091
162786 20092
162787 20088
162787 20089
162787 20090
162787 20091
162787 20092
162788 20088
162788 20089
162788 20091
162788 20092
162789 20088
1627...

result:

ok Queries used 207

Test #25:

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

input:

7
420094974505
217904673482
162241036634
21947974505
9588332921
123800974505
62505910162
24238903210
35995904397
71611351157
0
242428885597
242427922420
242426959245
242425996072
242425032901
242428680650
242427717473
242426754298
242425791125
242424827954
242428475705
242427512528
242425586180
2424...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
464347 452190
156671 628926
648147 664
648145 662
648145 663
648145 664
648145 665
648145 666
648146 662
648146 663
648146 664
648146 665
648146 666
648147 662
648147 663
648147 665
648147 666
648148 662
648148 6...

result:

ok Queries used 242

Test #26:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

3
9061
249902015688
999804015688
249900019216
1249708019216
999800019216
1249704019216
1999608019216
0
576
577
580
585
592
529
530
533
538
545
484
485
493
500
441
442
445
450
457
400
401
404
409
416
4
4
5
8
13
20
1
2
5
10
17
0
8840
8852
8861
9026
9029
9034
9041
9050
9217
9220
9225
9232
9241
49969904...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
78 98
76 96
76 97
76 98
76 99
76 100
77 96
77 97
77 98
77 99
77 100
78 96
78 97
78 99
78 100
79 96
79 97
79 98
79 99
79 100
80 96
80 97
80 98
80 99
80 100
100 98
98 96
98 97
98 98
98 99
98 100
99 96
99 97
99 98
9...

result:

ok Queries used 109

Test #27:

score: 0
Accepted
time: 1ms
memory: 3472kb

input:

1
0

output:

0 0

result:

ok Queries used 1

Test #28:

score: 0
Accepted
time: 1ms
memory: 3476kb

input:

4
0
249999000001
999998000001
249999000001
1249997000002
999998000001
1249997000002
1999996000002
0
1
2
5
0
0

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
0 1
0 0
0 2
0 3
1 0
1 1

result:

ok Queries used 14

Test #29:

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

input:

7
0
249998000005
999996000005
249998000004
1249994000008
999996000004
1249994000008
1999992000008
0
1
0
4
5
8
0
1
2
5
0
0
0

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
1 2
0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 3
1 4
2 0
2 1
2 2

result:

ok Queries used 21

Test #30:

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

input:

7
16
249990000116
999980000116
249990000101
1249976000116
999980000101
1249975000125
1999970000125
1
4
9
9
10
13
5
5
4
5
8
5
2
2
5
4
1
0
25
36
5
10
17
26
37
25
499963000697
17
25
799957600569
25
999966000298
16
25
799953600689
16
25
1999926000697
25
16
999958000442
1
0
4
5
8
13
2
1
2
5
10
1
0
36
40
...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
3 10
1 8
1 9
1 10
1 11
1 12
2 8
2 9
2 10
2 11
2 12
3 8
3 9
3 11
3 12
4 8
4 9
4 10
4 11
4 12
5 8
5 9
5 10
5 11
5 12
10 10
499989 499989
3 10
10 10
399997 799985
7 10
7 999989
4 10
10 10
799985 399997
4 10
10 10
99...

result:

ok Queries used 149

Test #31:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

2
25
249997000025
999994000025
249995000034
1249989000034
999990000034
1249987000034
1999984000034
1
13
8
5
4
5
10
5
2
1
2
9
4
0
2
9
4
1
0

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
4 2
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 3
4 4
5 0
5 1
5 2
5 3

result:

ok Queries used 27

Test #32:

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

input:

4
1
249995000034
999990000034
249995000029
1249987000034
999990000029
1249988000029
1999984000034
1
1
2
5
10
13
0
5
4
5
8
5
2
2
5
4
1
0
20
29
2
5
10
17
26
9
499981000185
13
9
799978400149
13
999984000068
18
9
799976000185
13
9
1999962000185
13
18
999978000122
1
5
4
5
8
13
2
1
2
5
10
1
0
34
41
36
37
...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
2 5
0 3
0 4
0 5
0 6
0 7
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 6
2 7
3 3
3 4
3 5
3 6
3 7
4 3
4 4
4 5
4 6
4 7
5 5
499994 499994
3 5
5 5
399998 799992
3 5
3 999994
2 5
5 5
799992 399998
3 5
5 5
999994 999994
3 5
2 5
999994 ...

result:

ok Queries used 92

Test #33:

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

input:

7
5506
249911010625
999822010625
249901013282
1249770010625
999802013282
1249743013282
1999684013282
0
265
290
317
346
377
244
269
296
325
356
225
250
306
337
208
233
260
289
320
193
218
245
274
305
900
499652061002
296
900
799604049185
680
999670027709
245
900
799564060125
277
900
1999304061002
680...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
52 89
50 87
50 88
50 89
50 90
50 91
51 87
51 88
51 89
51 90
51 91
52 87
52 88
52 90
52 91
53 87
53 88
53 89
53 90
53 91
54 87
54 88
54 89
54 90
54 91
99 89
499910 499900
51 89
99 89
399988 799867
83 89
83 999910
...

result:

ok Queries used 260

Test #34:

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

input:

7
34121
249088832768
998176832768
249293133289
1247703133289
998585133289
1247790133289
1996995133289
0
58210
58445
58682
58921
59162
57789
58024
58261
58500
58741
57370
57605
58081
58322
56953
57188
57425
57664
57905
56538
56773
57010
57249
57490
13689
496879889657
45029
13689
796139072477
17170
99...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
32 912
30 910
30 911
30 912
30 913
30 914
31 910
31 911
31 912
31 913
31 914
32 910
32 911
32 913
32 914
33 910
33 911
33 912
33 913
33 914
34 910
34 911
34 912
34 913
34 914
708 912
499087 499291
473 912
708 912...

result:

ok Queries used 258

Test #35:

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

input:

7
4118481
240994645568
981906645568
240834298756
1231674645568
981568298756
1227768298756
1973968298756
2
18
13
10
9
10
13
8
5
4
5
10
5
1
2
9
4
1
0
17592581
17560836
17567497
17574160
17580825
17587492
28906417
468931751293
17584340
28902601
764785256738
18810640
970460367440
12610960
28424461
76041...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
231 9087
229 9085
229 9086
229 9087
229 9088
229 9089
230 9085
230 9086
230 9087
230 9088
230 9089
231 9085
231 9086
231 9088
231 9089
232 9085
232 9086
232 9087
232 9088
232 9089
233 9085
233 9086
233 9087
233 9...

result:

ok Queries used 227

Test #36:

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

input:

7
1551882757
190039153225
870863153225
170145229385
1054306153225
828677229385
1021696229385
1714715229385
1
13
10
9
10
13
8
5
4
5
8
5
2
2
5
4
1
0
769300337
769324730
769177349
769201736
769226125
769250516
769274909
310639249
233277902549
769301380
292351816
482902100650
286938578
758258808709
3991...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
66556 69176
66554 69174
66554 69175
66554 69176
66554 69177
66554 69178
66555 69174
66555 69175
66555 69176
66555 69177
66555 69178
66556 69174
66556 69175
66556 69177
66556 69178
66557 69174
66557 69175
66557 69...

result:

ok Queries used 258

Test #37:

score: 0
Accepted
time: 1ms
memory: 3476kb

input:

4
606657143573
231369843601
8024843601
306410143573
148678159977
506163143573
141705159977
12378730825
12848970122
0
19567400576
19567210897
19567021220
19566831545
19566641872
19567194929
19567005250
19566815573
19566625898
19566436225
19566989284
19566799605
19566420253
19566230580
19566783641
195...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
464406 625287
550247 551258
550245 551256
550245 551257
550245 551258
550245 551259
550245 551260
550246 551256
550246 551257
550246 551258
550246 551259
550246 551260
550247 551256
550247 551257
550247 551259
55...

result:

ok Queries used 107

Test #38:

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

input:

7
11881
249001144400
998001144400
249001092416
1247443606841
998001092416
1247222606841
1996443606841
0
9805
9802
9801
9802
9805
9608
9605
9604
9605
9608
9413
9410
9410
9413
9220
9217
9216
9217
9220
9029
9026
9025
9026
9029
48841
496226172401
2116
48841
795557394801
61162
996002146885
71289
48841
79...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
380 1000
378 998
378 999
378 1000
378 1001
378 1002
379 998
379 999
379 1000
379 1001
379 1002
380 998
380 999
380 1001
380 1002
381 998
381 999
381 1000
381 1001
381 1002
382 998
382 999
382 1000
382 1001
382 10...

result:

ok Queries used 223

Test #39:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

7
91441526449
39048526449
185864454400
21767166369
4744454400
19137125569
2601102001
71318025
0
196073804722
196074409505
196075619077
196076223866
196073157781
196073762564
196074367349
196074972136
196075576925
196072510842
196073115625
196073720410
196074325197
196074929986
196075014290
226418021...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
0 302393
0 302391
0 302392
0 302394
0 302395
1 302391
1 302392
1 302393
1 302394
1 302395
2 302391
2 302392
2 302393
2 302394
2 302395
0 302393
168527 603184
431120 1000000
431118 999998
431118 999999
431118 1000...

result:

ok Queries used 207

Test #40:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

7
396792907225
16877907225
15053081481
473792386489
26599000464
223792386489
725386489
49521381156
0
30972128121
30971776144
30971072196
30970720225
30972128122
30971776145
30971424170
30971072197
30970720226
30972128125
30971776148
30971424173
30971072200
30970720229
30971424169
70013044100
2301586...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
0 629915
0 629913
0 629914
0 629916
0 629917
1 629913
1 629914
1 629915
1 629916
1 629917
2 629913
2 629914
2 629915
2 629916
2 629917
0 629915
173000 605692
586500 229805
110844 567759
1000000 473066
999998 4730...

result:

ok Queries used 166

Test #41:

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

input:

7
43483926784
84955926784
37534025169
206116
34340537344
882208804
221180208804
99028537344
0
112054275997
112054693050
112055527162
112055944221
112053752276
112054169329
112054586384
112055003441
112055420500
112053228557
112053645610
112054062665
112054479722
112054896781
112055110105
0
241644014...

output:

0 0
0 500000
0 1000000
500000 0
500000 1000000
1000000 0
1000000 500000
1000000 1000000
0 208528
0 208526
0 208527
0 208529
0 208530
1 208526
1 208527
1 208528
1 208529
1 208530
2 208526
2 208527
2 208528
2 208529
2 208530
0 208528
685312 1000000
685310 999998
685310 999999
685310 1000000
685311 999...

result:

ok Queries used 162