QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#24006	#2609. Number Guessing	Wu_Ren	AC ✓	100ms	3856kb	C++17	1.7kb	2022-03-24 21:47:35	2022-04-30 04:45:36

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-04-30 04:45:36]
评测

测评结果：AC
用时：100ms
内存：3856kb

查看

[2022-03-24 21:47:35]
提交

answer

#include <bits/stdc++.h>
typedef long long ll;
const ll inf=1e18;
using namespace std;
ll Sed,y;
struct Rng{
	ll seed,P;
	int n;
	Rng(ll sd,int _n,ll p){
		seed=sd,n=_n,P=p;
	}
	int rand(){
		seed=seed*n%P;
		return seed%n;
	}
}RR(0,0,0);
int qry(ll x){
	printf("? %lld\n",x),fflush(stdout);
	scanf("%lld",&x);
	return x;
//	int z=x>y?0:(x==y?1:2);
//	return RR.rand()^z;
}
bool cmp(int B,int *v,ll x,int n,ll P){
	for(int i=1;i<=B;i++){
		int w=x*n/P;
		x=x*n%P;
		if(w^v[i]) return w>v[i];
	}
	return 1;
}
ll getSeed(int B,int *v,int n,ll P){
	ll l=0,r=P-1,ans=P-1,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(cmp(B,v,mid,n,P)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
int T,n,v[40],v1[40],v2[40];
ll P;
void sol(){
	scanf("%d%lld",&n,&P);
	
//	scanf("%lld%lld",&Sed,&y);
//	RR=Rng(Sed,n,P);
	
	int B=n==3?38:32;
	for(int i=1;i<=B;i++){
		v[i]=v1[i]=v2[i]=qry(1);
		v1[i]^=1,v2[i]^=2;
	}
	if(P%n==1) for(int i=1;i<=B;i++){
		v1[i]=(n-v1[i])%n;
		v2[i]=(n-v2[i])%n;
	}
	Rng r1(getSeed(B,v1,n,P),n,P),r2(getSeed(B,v2,n,P),n,P);
	bool c1=1,c2=1;
	for(int i=1;i<=B;i++){
		if(r1.rand()^1^v[i]) c1=0;
		if(r2.rand()^2^v[i]) c2=0;
		if(v1[i]>=n) c1=0;
		if(v2[i]>=n) c2=0;
	}
	if(c1&&c2){
		int _1=r1.rand(),_2=r2.rand(),_3;
		if((_1^_2)==3){
			_3=qry(inf);
			if(_1^_3) c1=0;
			if((_2^_3)>1) c2=0;
		}
		else{
			_3=qry(1);
			if(_1^1^_3) c1=0;
			if(_2^2^_3) c2=0;
		}
	}
	assert(c1+c2==1);
	Rng R=c1?r1:r2;
	ll l=1,r=inf,ans=inf,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if((qry(mid)^R.rand())<=1) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("! %lld\n",ans),fflush(stdout);
	scanf("%lld",&ans);
}
int main(){
	scanf("%d",&T);
	while(T--) sol();
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 8ms

memory: 3688kb

input:

1
3 998244353
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 250000000000000000
? 125000000000000000
? 62500000000000000
? 31250000000000000
? 15625000000000000
? 7812500000000000
? 3906...

result:

ok ok  Ok, Accepted!

Test #2:

score: 0

Accepted

time: 23ms

memory: 3764kb

input:

100
3 277348367706764059
0
2
0
2
3
3
3
0
0
2
0
2
0
2
3
3
2
2
0
2
3
3
3
0
2
0
0
2
2
0
3
2
0
2
3
2
0
0
0
3
3
3
2
3
2
3
2
3
3
3
3
3
0
3
2
3
0
2
2
0
2
3
2
3
0
3
3
2
0
0
2
0
3
3
0
0
3
2
3
2
0
3
0
3
3
0
2
0
3
0
2
3
2
2
3
3
0
1
1
4 290720307961955567
2
0
0
3
1
2
2
0
0
3
1
3
2
0
1
2
1
3
0
1
1
2
1
3
2
0
2
3
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 968750000000000000
? 984375000000000000
? 992187500000000000
?...

result:

ok ok  Ok, Accepted!

Test #3:

score: 0

Accepted

time: 65ms

memory: 3776kb

input:

100
4 637973254263306593
2
0
0
1
0
3
2
3
0
1
1
2
0
2
3
0
2
3
1
0
3
0
1
3
2
3
2
2
1
1
0
1
2
2
1
1
1
3
1
2
2
1
0
3
1
2
1
0
3
2
0
1
2
2
3
0
3
3
0
1
2
3
1
0
3
2
2
0
3
1
2
0
1
0
2
3
3
3
1
1
1
1
2
2
1
2
3
2
0
3
0
1
1
4 743604070103328947
2
0
2
3
3
1
1
3
0
3
0
0
2
0
1
0
0
2
3
2
1
0
2
2
2
0
1
3
0
2
1
1
2
2
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 968750000000000000
? 984375000000000000
? 992187500000000000
? 996093750000000000
? 99...

result:

ok ok  Ok, Accepted!

Test #4:

score: 0

Accepted

time: 58ms

memory: 3796kb

input:

100
4 147666650676818621
0
1
3
2
0
2
0
2
1
1
1
3
2
0
1
1
0
3
1
3
3
1
2
2
2
3
3
2
2
3
0
1
1
1
3
2
1
1
1
2
0
2
3
3
0
3
0
1
1
0
1
1
1
2
1
3
0
1
3
1
2
3
1
0
2
1
1
3
3
3
2
1
3
2
1
3
3
3
1
1
3
1
2
0
1
3
1
3
1
1
0
2
1
3 706760201708868499
0
2
2
2
0
3
0
3
2
3
0
0
2
0
2
0
0
3
0
2
3
0
3
3
2
3
3
3
0
2
2
3
3
3
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 250000000000000000
? 375000000000000000
? 437500000000000000
? 468750000000000000
? 484375000000000000
? 476562500000000000
? 472656250000000000
? 47...

result:

ok ok  Ok, Accepted!

Test #5:

score: 0

Accepted

time: 71ms

memory: 3804kb

input:

100
3 863388859085152073
3
2
0
3
0
3
2
2
2
0
3
3
3
2
3
2
0
3
0
0
3
3
2
2
3
3
3
3
2
2
0
2
2
0
3
3
3
0
0
3
0
3
3
3
3
3
0
2
0
3
3
0
0
2
2
0
0
3
2
3
3
0
0
2
2
0
2
3
2
0
0
3
0
2
0
2
0
0
0
0
2
2
2
3
3
0
0
0
0
0
2
2
2
2
0
3
3
1
1
4 568485237988395059
2
0
2
2
0
2
0
0
2
3
3
1
1
3
2
2
0
2
2
2
3
0
3
0
0
3
3
3
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 968750000000000000
? 984375000000000000
? 992187500000000000
?...

result:

ok ok  Ok, Accepted!

Test #6:

score: 0

Accepted

time: 60ms

memory: 3764kb

input:

100
4 164933399261330929
1
0
1
2
3
3
1
0
3
3
2
1
3
0
1
3
1
1
2
2
1
2
2
1
0
2
0
0
3
2
2
3
3
3
0
0
2
1
2
3
2
3
1
1
3
0
3
0
0
0
2
3
3
2
1
3
0
0
0
3
2
2
3
1
3
3
0
0
3
0
1
2
3
1
0
3
2
2
2
1
3
1
0
3
2
0
3
2
1
3
0
0
1
3 891313378078419553
0
0
0
2
2
0
3
3
3
0
3
0
0
0
2
3
0
0
3
3
3
3
3
3
0
2
3
3
2
2
0
2
0
3
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 625000000000000000
? 562500000000000000
? 593750000000000000
? 578125000000000000
? 570312500000000000
? 566406250000000000
? 56...

result:

ok ok  Ok, Accepted!

Test #7:

score: 0

Accepted

time: 87ms

memory: 3808kb

input:

100
3 538006843598842063
3
2
0
3
2
2
3
3
0
3
2
3
0
3
2
2
3
0
2
2
2
2
3
3
2
3
3
0
2
2
3
3
3
2
3
3
2
0
2
0
3
3
0
2
3
3
0
3
0
3
3
2
3
2
2
0
3
2
0
3
3
2
3
3
2
3
0
0
2
2
3
2
2
3
2
3
2
0
2
3
0
0
0
2
0
3
3
3
2
3
2
3
2
3
0
0
1
1
1
4 549284943163075843
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 968750000000000000
? 984375000000000000
? 992187500000000000
?...

result:

ok ok  Ok, Accepted!

Test #8:

score: 0

Accepted

time: 35ms

memory: 3808kb

input:

100
4 665159744525127307
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
0
0
0
2
0
0
3
0
1
0
2
2
1
3
3
1
1
1
3
3
2
2
0
2
2
3
1
2
3
1
1
3
2
0
2
3
0
1
3
2
0
3
3
2
2
0
1
3
1
3
3
1
1
1
3
3
0
0
0
1
3
3
1
3 916444470470253863
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1000000000000000000
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 906250000000000000
? 890625000000000000
? 882812500000000000
? 8...

result:

ok ok  Ok, Accepted!

Test #9:

score: 0

Accepted

time: 59ms

memory: 3792kb

input:

100
3 487940875095685871
3
0
0
0
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
0
3
2
2
0
3
0
0
3
0
2
2
3
3
0
2
0
3
2
0
3
3
0
3
2
3
2
3
3
0
0
3
3
0
2
2
2
0
2
2
2
3
0
3
2
2
2
0
2
0
3
3
2
0
3
0
0
2
1
3
1
4 370306040205397949
1
2
2
1
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 968750000000000000
? 984375000000000000
? 992187500000000000
?...

result:

ok ok  Ok, Accepted!

Test #10:

score: 0

Accepted

time: 44ms

memory: 3856kb

input:

100
4 889428325406206057
0
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
3
3
2
1
1
0
0
0
2
1
2
2
3
2
1
1
3
1
0
1
3
2
2
1
2
1
0
3
1
1
1
2
1
1
2
3
3
1
2
1
2
0
0
2
0
1
3
3
2
1
2
1
3
0
0
1
2
1
1
3
1
1
3 225456159430798763
3
0
0
0
0
0
2
2
0
2
2
2
2
2
2
2
0
2
3
2
0
0
0
2
0
2
2
2
2
3
0
0
2
0
0
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 812500000000000000
? 781250000000000000
? 765625000000000000
? 773437500000000000
? 769531250000000000
? 77...

result:

ok ok  Ok, Accepted!

Test #11:

score: 0

Accepted

time: 56ms

memory: 3756kb

input:

100
3 496633816626479111
2
2
2
0
0
0
2
0
0
2
0
2
2
2
0
0
0
0
2
0
0
2
2
2
0
2
0
2
0
2
0
0
2
0
2
0
2
0
3
1
1
0
0
3
3
2
1
0
0
0
0
0
0
3
3
0
0
1
0
0
0
0
2
1
1
0
2
1
0
1
3
0
2
2
0
1
1
2
0
2
0
0
1
2
0
0
1
2
2
0
0
2
2
2
2
2
0
0
1
4 125690197446535321
1
0
1
2
1
0
0
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 625000000000000000
? 562500000000000000
? 531250000000000000
? 515625000000000000
? 523437500000000000
?...

result:

ok ok  Ok, Accepted!

Test #12:

score: 0

Accepted

time: 64ms

memory: 3708kb

input:

100
3 656547332672301971
3
3
0
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
0
0
2
2
1
0
2
0
0
2
2
0
0
1
1
1
2
0
0
2
2
1
1
2
2
2
1
2
1
2
2
1
0
1
2
0
0
1
1
1
1
1
2
0
0
1
2
0
1
2
1
1
2
1
1
1
0
0
2
0
0
1
3 605541250900799743
0
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 250000000000000000
? 125000000000000000
? 62500000000000000
? 31250000000000000
? 15625000000000000
? 7812500000000000
? 3906...

result:

ok ok  Ok, Accepted!

Test #13:

score: 0

Accepted

time: 83ms

memory: 3780kb

input:

100
4 989173108175529157
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
0
2
0
2
0
0
0
2
0
0
0
0
0
2
2
2
0
0
0
0
0
2
2
2
2
2
0
0
2
0
2
2
0
2
2
0
2
0
0
0
2
0
2
2
2
0
2
2
2
0
2
2
0
2
0
0
2
1
2
2
1
4 638816668137932387
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 250000000000000000
? 375000000000000000
? 312500000000000000
? 343750000000000000
? 328125000000000000
? 320312500000000000
? 316406250000000000
? 31...

result:

ok ok  Ok, Accepted!

Test #14:

score: 0

Accepted

time: 70ms

memory: 3644kb

input:

100
3 385464428245055857
2
0
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
0
3
3
0
2
3
2
2
1
1
2
2
2
3
2
0
0
1
3
2
2
0
0
3
1
0
0
0
0
2
2
2
0
3
2
3
2
3
2
0
0
3
3
3
0
2
2
0
3
2
0
0
1
2
2
3
1
1
3
2
0
1
4 119725295734086751
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 906250000000000000
? 921875000000000000
? 929687500000000000
?...

result:

ok ok  Ok, Accepted!

Test #15:

score: 0

Accepted

time: 90ms

memory: 3640kb

input:

100
4 800170129874524841
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
0
2
2
2
0
0
0
0
0
0
2
0
2
2
2
0
2
0
2
0
2
2
0
2
0
2
2
2
2
0
0
0
2
2
0
0
2
0
2
2
0
2
0
0
0
0
2
0
0
2
0
2
2
2
0
2
0
1
1
3 506818010300568433
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 812500000000000000
? 843750000000000000
? 859375000000000000
? 867187500000000000
? 863281250000000000
? 86...

result:

ok ok  Ok, Accepted!

Test #16:

score: 0

Accepted

time: 82ms

memory: 3760kb

input:

100
3 9960255883813919
2
2
3
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
0
3
3
3
2
1
3
2
1
2
0
0
2
0
2
2
3
0
2
2
3
0
1
0
2
2
1
3
0
2
1
1
3
3
1
2
0
1
2
2
2
2
3
0
0
0
2
2
0
2
2
2
1
0
1
0
1
0
1
0
2
3
0
1
4 9978988463072513
0
1
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
0
3
1
3
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 812500000000000000
? 843750000000000000
? 859375000000000000
? 851562500000000000
?...

result:

ok ok  Ok, Accepted!

Test #17:

score: 0

Accepted

time: 80ms

memory: 3776kb

input:

100
4 9999187615847257
1
2
1
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
0
2
0
1
2
1
0
0
1
2
3
0
2
1
1
1
1
3
3
1
1
1
1
0
0
1
3
3
2
2
3
1
2
2
0
1
1
2
3
2
3
3
1
0
0
0
1
2
0
1
3
1
0
1
2
0
2
1
1
3
1
2
3
1
0
3
1
4 9971575805712097
0
2
2
2
0
2
0
0
2
2
2
2
2
0
0
2
2
2
2
2
2
2
2
2
1
0
2
0
0
1
1
3
1
2
1
0
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 625000000000000000
? 687500000000000000
? 656250000000000000
? 640625000000000000
? 648437500000000000
? 652343750000000000
? 65...

result:

ok ok  Ok, Accepted!

Test #18:

score: 0

Accepted

time: 58ms

memory: 3812kb

input:

100
3 9969673006738409
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
0
0
0
0
0
2
0
0
2
0
0
0
0
2
2
0
0
0
2
2
2
2
2
2
2
2
0
0
0
0
2
2
2
2
0
0
2
0
0
0
2
2
2
2
0
2
0
0
0
2
2
2
2
2
2
2
2
2
0
1
1
4 9964246081551361
1
2
2
2
1
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
0
2
0
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 250000000000000000
? 125000000000000000
? 62500000000000000
? 31250000000000000
? 15625000000000000
? 23437500000000000
? 195...

result:

ok ok  Ok, Accepted!

Test #19:

score: 0

Accepted

time: 82ms

memory: 3760kb

input:

100
4 9969128201318179
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
3
0
2
0
3
0
1
2
1
3
0
2
0
1
0
1
2
2
2
0
1
0
0
0
2
3
2
2
0
2
0
1
2
3
3
2
1
3
2
2
0
0
0
3
2
3
0
2
1
3
2
3
1
3
0
2
1
2
3
0
0
3
2
2
3
1
3 9993961495429033
0
2
0
2
0
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1000000000000000000
? 500000000000000000
? 250000000000000000
? 375000000000000000
? 312500000000000000
? 281250000000000000
? 265625000000000000
? 273437500000000000
? 2...

result:

ok ok  Ok, Accepted!

Test #20:

score: 0

Accepted

time: 44ms

memory: 3848kb

input:

100
3 9982837953857471
2
2
2
0
0
2
0
2
2
0
2
2
0
2
2
3
0
0
2
2
2
2
2
0
0
3
0
0
0
0
2
2
2
2
2
0
0
0
3
3
0
3
0
3
2
2
3
0
2
0
2
2
3
2
3
0
0
3
2
0
0
3
0
3
3
3
3
3
2
3
2
0
3
3
3
3
3
0
0
0
0
0
3
3
2
2
2
3
0
2
0
3
0
3
2
3
0
0
1
3 9972148169782157
2
2
0
0
0
0
3
0
2
0
0
0
3
0
2
0
3
2
2
0
2
2
2
2
2
0
2
2
0
0
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 968750000000000000
? 984375000000000000
? 992187500000000000
?...

result:

ok ok  Ok, Accepted!

Test #21:

score: 0

Accepted

time: 100ms

memory: 3784kb

input:

100
3 9977254467714467
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
2
1
4 9980246790405299
2
3
2
2
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
3
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 968750000000000000
? 984375000000000000
? 992187500000000000
?...

result:

ok ok  Ok, Accepted!

Test #22:

score: 0

Accepted

time: 81ms

memory: 3684kb

input:

100
3 9971217343085497
0
2
3
3
2
3
3
3
0
2
0
3
2
3
2
3
3
2
2
3
3
2
3
2
2
3
2
3
3
3
3
3
2
3
0
3
2
3
2
0
2
2
3
3
0
0
0
2
0
2
2
0
0
0
2
0
0
2
0
3
2
3
0
3
3
0
3
2
3
2
2
3
3
2
2
3
2
3
3
0
3
2
0
0
3
2
3
3
2
0
0
0
3
0
0
2
0
0
1
3 9956757902033689
2
2
0
2
0
2
2
2
2
0
0
2
2
0
2
2
2
0
2
2
2
2
2
2
2
2
2
2
2
2
...

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 968750000000000000
? 984375000000000000
? 992187500000000000
?...

result:

ok ok  Ok, Accepted!

Test #23:

score: 0

Accepted

time: 14ms

memory: 3796kb

input:

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1000000000000000000
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 906250000000000000
? 921875000000000000
? 914062500000000000
? 9...

result:

ok ok  Ok, Accepted!

Test #24:

score: 0

Accepted

time: 48ms

memory: 3716kb

input:

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 968750000000000000
? 953125000000000000
? 960937500000000000
?...

result:

ok ok  Ok, Accepted!

Test #25:

score: 0

Accepted

time: 53ms

memory: 3712kb

input:

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 968750000000000000
? 984375000000000000
? 992187500000000000
?...

result:

ok ok  Ok, Accepted!

Test #26:

score: 0

Accepted

time: 36ms

memory: 3792kb

input:

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 750000000000000000
? 875000000000000000
? 937500000000000000
? 968750000000000000
? 984375000000000000
? 992187500000000000
? 996093750000000000
? 99...

result:

ok ok  Ok, Accepted!

Test #27:

score: 0

Accepted

time: 45ms

memory: 3764kb

input:

output:

? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 500000000000000000
? 250000000000000000
? 125000000000000000
? 62500000000000000
? 31250000000000000
? 15625000000000000
? 7812500000000000
? 3906...

result:

ok ok  Ok, Accepted!