QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#378594#8569. Generalized Collatz Conjectureucup-team1004#TL 11458ms809792kbC++143.3kb2024-04-06 13:42:482024-04-06 13:42:49

Judging History

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

  • [2024-04-06 13:42:49]
  • 评测
  • 测评结果:TL
  • 用时:11458ms
  • 内存:809792kb
  • [2024-04-06 13:42:48]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e6+5,M=1e8+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-8;const int INF=1e9+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,m,A[10],lim;const int k=1e8;
int pr[M/10],ph,La[M],flag[M];
ll f[1000],g[1000];int fh,gh;

namespace PR{
	using LL=__int128;
	ll rng(ll n){return (1ll*rnd()<<30^rnd())%n+1;}
	ll mpow(ll x,ll y,ll p){ll ans=1;while(y) y&1&&(ans=(LL)ans*x%p),y>>=1,x=(LL)x*x%p;return ans;}
	int ckp(ll n){
		if(n%2==0||n<3) return n==2;
		int i,t=0;ll y=n-1;while(y%2==0) y>>=1,t++;
		int lim=5;while(lim--){
			ll z=mpow(rng(n-2)+1,y,n);if(z==1) continue;
			for(i=0;i<t;i++) {
				if(z==n-1) break;
				z=(LL)z*z%n;
			}
			if(i==t) return 0;
		}
		return 1;
	}
	ll divide(ll n){
		ll c=rng(n-1);//cerr<<n<<' '<<c<<'\n';
		auto f=[&](ll x){return ((LL)x*x+c)%n;};
		ll l=0,r=f(l);
		int stp=0;ll val=1;
		while(l^r){
			ll vs=(LL)val*abs(l-r)%n;stp++;
			if(vs==0||stp==128){
				ll d=__gcd(val,n);
				if(d>1) return d;
				stp=0;val=abs(l-r);
			}else val=vs;
			l=f(l);r=f(f(r));
		}
		ll d=__gcd(val,n);
		if(d>1) return d;
		return divide(n);
	}
}
ll st[N];int sh;
void calc(ll n){
	if(n==1) return;
	if(n<=k){
		st[++sh]=La[n];calc(n/La[n]);
		return;  
	}
	if(PR::ckp(n)){st[++sh]=n;return;}
	ll p=PR::divide(n);
	calc(p);calc(n/p);
}
void calcs(ll n){
	sh=0;
	if(n<=k){
		while(n^1) st[++sh]=La[n],n/=La[n];
		return;
	}
	for(int i=1;i<=100;i++) while(n%pr[i]==0) st[++sh]=pr[i],n/=pr[i];
	calc(n);
}
void Solve(){
	int i,j;scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++) scanf("%d",&A[i]);
	calcs(n);lim=sh;f[fh=1]=n;
	for(int T=1;T+1<lim;T++){
		sort(f+1,f+fh+1);
		fh=unique(f+1,f+fh+1)-f-1;
		gh=fh;copy(f+1,f+fh+1,g+1);fh=0;
		for(int i=1;i<=gh&&T+1<lim;i++){
			for(int j=1;j<=m;j++)if(g[i]*A[j]+1<1e14){
				calcs(g[i]*A[j]+1);
				lim=min(lim,T+sh);
				if(T+2<lim) f[++fh]=g[i]*A[j]+1;
			}
			calcs(g[i]);
			for(int j=1;j<=sh;j++) if(T+2<lim) f[++fh]=g[i]/st[j];
		}
		/*if(f.size()>30){
			gdb(f.size());
			cerr<<n<<' '<<m<<' ';
			for(int k=1;k<=m;k++) cerr<<A[k]<<' ';cerr<<'\n';
		} */
	}
	printf("%d\n",lim);
}
void init(){
	for(int i=2;i<=k;i++){
		if(!flag[i]) pr[++ph]=i,La[i]=i;
		for(int j=1;j<=ph&&i*pr[j]<=k;j++) {
			flag[i*pr[j]]=1;La[i*pr[j]]=pr[j];
			if(i%pr[j]==0) break;
		}
	}
}
int main(){
	int t=1;init();
	scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}


详细

Test #1:

score: 100
Accepted
time: 841ms
memory: 808496kb

input:

2
84 2 3 6
18588 3 18 25 44

output:

3
4

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 4994ms
memory: 809428kb

input:

262144
1576395 1 37
1190799 2 11 17
520479 1 29
1676079 1 49
1202944 2 41 47
1906335 2 25 47
1862541 1 47
1879366 1 19
1225773 1 17
1819737 1 59
205155 1 53
1498304 1 61
818565 1 43
1482543 2 41 61
228771 1 59
758241 2 11 23
815056 1 59
576153 1 53
458541 1 35
950211 2 5 29
1495625 1 53
1962415 1 59...

output:

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
2
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
...

result:

ok 262144 tokens

Test #3:

score: 0
Accepted
time: 3640ms
memory: 807800kb

input:

262144
1492393 1 27
1517074 1 23
819009 1 35
1064505 1 3
991575 1 49
489969 1 31
1653561 1 59
1673625 1 19
443385 1 53
1789641 1 39
481915 1 5
1751715 2 5 53
602651 1 61
1721685 1 61
1032795 1 41
605493 1 47
1672192 3 16 29 58
325809 1 39
896704 1 17
1688067 1 61
567520 1 31
2082915 1 23
1879551 1 2...

output:

5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
4
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
...

result:

ok 262144 tokens

Test #4:

score: 0
Accepted
time: 2271ms
memory: 809548kb

input:

262144
1078425 3 35 54 59
1954665 4 43 47 51 59
857175 3 27 49 59
1725032 3 28 31 55
1252611 3 17 53 64
1786023 4 17 27 48 51
1895925 3 53 59 64
1801202 3 25 43 64
1299429 4 17 31 47 63
1467315 3 30 41 47
1094205 3 14 19 23
1430433 3 17 50 53
1142019 3 21 23 53
376155 3 23 38 53
858141 4 11 47 56 62...

output:

3
3
4
3
4
3
3
3
3
3
3
3
3
2
3
3
4
3
3
3
3
2
4
3
3
3
3
3
3
4
3
4
3
3
4
3
3
4
3
3
3
3
3
4
4
4
3
4
2
3
4
3
3
4
3
2
4
3
3
3
2
3
3
3
3
4
3
3
4
2
3
4
2
4
2
2
2
3
3
2
3
4
3
3
4
3
4
3
3
4
3
4
3
3
3
3
4
2
3
4
4
3
2
3
3
3
3
3
3
2
3
2
3
4
3
3
4
3
3
4
3
3
3
4
3
3
3
2
4
4
3
3
2
3
4
2
3
2
2
3
2
4
4
3
2
3
3
4
4
3
...

result:

ok 262144 tokens

Test #5:

score: 0
Accepted
time: 1573ms
memory: 808176kb

input:

262144
580864 3 52 61 63
1709461 3 28 42 55
1572864 2 38 39
1632915 2 49 53
1022625 2 29 59
1883136 8 5 11 19 21 27 35 45 55
596835 3 30 49 62
196587 3 21 42 55
1272750 6 21 27 37 41 45 51
1081593 2 32 55
1757775 2 49 63
1811556 7 22 25 28 29 59 60 62
1698435 2 33 49
140625 2 19 50
1732992 2 8 48
12...

output:

2
2
3
4
4
2
3
3
2
3
4
3
3
4
3
2
4
4
4
3
3
3
2
3
3
3
3
2
2
3
3
2
3
3
3
3
3
2
3
3
4
3
2
3
3
2
3
3
3
4
4
2
2
3
3
3
3
3
3
2
3
3
2
4
4
3
3
4
3
3
4
4
2
3
2
2
4
3
3
3
3
3
3
3
2
2
4
3
3
3
3
3
3
4
4
3
4
2
2
3
4
3
3
3
3
3
3
4
2
3
3
2
3
3
2
3
3
3
3
3
3
4
3
2
3
2
3
2
2
3
4
2
3
3
3
3
3
4
4
3
4
3
4
3
3
3
2
4
2
3
...

result:

ok 262144 tokens

Test #6:

score: 0
Accepted
time: 1194ms
memory: 809572kb

input:

262144
2044416 3 5 17 33
1531872 5 21 27 31 51 55
2035886 2 3 37
1032750 6 29 37 41 49 53 57
910224 4 29 45 51 55
730944 3 23 35 45
993408 2 28 43
1606144 2 23 28
1636633 2 13 37
1875968 1 37
1633800 2 33 47
1519616 2 13 59
1609728 3 23 27 41
1792000 8 3 7 25 27 29 49 53 63
844050 1 14
1269504 1 13
...

output:

2
3
3
2
3
3
3
2
2
4
2
3
3
2
3
4
3
2
3
4
3
3
2
4
2
2
3
3
3
3
2
3
3
2
3
3
2
2
2
2
3
3
3
2
3
2
4
2
4
2
4
2
3
3
3
3
4
2
2
3
2
2
2
2
2
2
4
3
2
3
2
2
3
2
3
3
3
3
2
2
3
4
3
2
3
3
4
2
2
3
3
3
2
2
3
4
3
2
2
2
3
2
3
3
3
2
2
3
4
3
3
2
2
3
2
3
4
3
3
3
3
2
3
2
2
2
2
4
2
3
2
2
2
3
2
3
4
3
3
2
3
2
3
3
3
3
3
2
2
3
...

result:

ok 262144 tokens

Test #7:

score: 0
Accepted
time: 1585ms
memory: 808148kb

input:

262144
1081344 8 35 41 43 47 51 57 59 61
2062976 8 33 37 49 51 53 55 57 59
1798304 8 35 39 41 43 51 57 59 61
1341856 8 35 37 41 45 47 51 55 61
817600 8 15 17 21 29 37 41 45 59
1576788 8 33 39 51 53 55 57 59 63
1843875 8 33 39 43 49 53 55 61 63
1647360 8 33 37 41 47 49 57 59 63
546848 8 33 39 45 51 5...

output:

2
2
2
2
2
3
3
2
2
3
2
2
3
3
3
2
2
3
2
2
3
2
2
2
2
2
2
2
2
3
2
2
2
2
3
2
2
2
2
3
2
2
2
2
2
2
2
3
2
2
2
2
2
3
2
2
2
2
2
2
3
2
3
2
3
2
3
2
2
2
3
2
3
3
2
2
3
2
2
2
2
2
2
2
2
3
3
2
2
2
2
2
3
3
3
3
3
3
2
2
2
2
2
3
3
2
3
2
2
2
3
2
2
3
2
2
2
3
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
2
2
3
2
2
2
3
2
2
2
...

result:

ok 262144 tokens

Test #8:

score: 0
Accepted
time: 956ms
memory: 808068kb

input:

262144
74 2 18 57
682 3 20 31 47
1141614 2 11 62
178 2 7 35
940 2 31 58
1280 2 39 53
2097151 2 28 41
225 2 34 42
574 1 29
225 2 3 26
584 3 20 24 41
948 3 28 29 44
386 3 24 45 62
763 2 14 35
2097097 1 35
954 4 9 15 33 53
42 1 5
225 2 4 33
304 5 7 16 34 55 56
2097138 2 13 37
112 2 6 38
89 2 17 36
938 ...

output:

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

result:

ok 262144 tokens

Test #9:

score: 0
Accepted
time: 961ms
memory: 808376kb

input:

262144
873 2 36 51
2097090 6 4 23 26 43 46 54
713 1 51
94 2 40 43
1110 3 6 26 42
188 2 26 36
2097077 3 20 23 35
52 3 12 46 61
56 2 20 63
418 4 33 49 59 61
245 2 38 57
114 2 15 39
171 2 16 26
388 7 41 45 48 55 59 60 62
844 3 26 28 30
644 3 23 25 28
493 2 36 50
62 2 12 21
418 3 2 36 60
697 2 29 57
276...

output:

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

result:

ok 262144 tokens

Test #10:

score: 0
Accepted
time: 953ms
memory: 808128kb

input:

262144
40 2 17 55
692 3 17 52 61
27 2 51 61
119 2 32 50
382 3 50 52 56
530 3 14 46 55
476032 2 21 49
726 2 2 5
1071 2 34 44
159 5 5 31 47 57 61
200 2 47 59
554 2 1 41
209 2 26 40
235 2 29 64
40 2 14 50
1517568 3 27 35 61
124 2 1 62
562 2 5 58
1485912 7 33 39 41 43 45 51 61
888 1 18
774 3 18 39 55
98...

output:

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

result:

ok 262144 tokens

Test #11:

score: 0
Accepted
time: 961ms
memory: 808360kb

input:

262144
450 3 9 26 35
31 2 22 60
85 2 43 55
234 2 12 60
263 2 2 51
21 2 11 37
460 1 8
2097150 2 19 50
1098 1 63
884736 2 21 57
199 2 13 37
1574144 3 22 48 50
1083 2 21 36
2097088 3 6 9 13
2097149 2 11 35
974 3 36 46 49
2097080 3 28 43 48
222 2 39 43
31 3 15 18 56
234 2 50 55
175 2 1 25
482 3 16 37 54...

output:

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

result:

ok 262144 tokens

Test #12:

score: 0
Accepted
time: 992ms
memory: 808952kb

input:

262144
672 2 53 63
1061 3 33 49 57
806208 1 57
170 2 7 28
976896 2 1 19
1723392 1 33
50 2 19 40
57 3 6 31 32
221 2 34 45
221 2 25 45
2097062 3 25 33 58
1757184 2 27 60
60 2 38 46
428032 8 21 23 25 35 45 47 61 63
88 2 34 39
1221120 1 42
183 2 26 52
259 2 23 50
1096 5 7 10 22 38 44
179 2 61 63
76 8 20...

output:

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

result:

ok 262144 tokens

Test #13:

score: 0
Accepted
time: 957ms
memory: 809192kb

input:

262144
1757479 1 37
2044621 8 33 37 41 43 51 57 61 63
1833763 7 33 37 39 43 49 55 57
1335647 1 35
1219433 2 37 45
1852171 7 17 21 39 41 47 49 63
1272281 6 35 47 49 55 59 61
1061129 1 41
1820629 2 43 59
1950323 1 59
580471 1 37
1555907 2 17 55
657707 3 36 41 59
1937917 5 19 31 32 34 51
1397861 3 33 5...

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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 262144 tokens

Test #14:

score: 0
Accepted
time: 956ms
memory: 809792kb

input:

262144
475249 7 37 45 51 53 57 61 63
849074 7 36 38 40 41 46 53 56
1457041 4 23 25 47 49
989474 1 35
75121 1 49
1966457 1 37
729033 4 33 37 41 63
1793533 1 51
1997439 4 33 43 57 59
233986 2 33 43
1658191 6 1 15 21 37 47 51
191206 6 13 41 43 55 59 63
1580539 4 41 42 46 61
881501 1 37
1107065 8 33 43 ...

output:

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
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
...

result:

ok 262144 tokens

Test #15:

score: 0
Accepted
time: 1163ms
memory: 808792kb

input:

262144
1780798 1 49
1789949 8 33 35 39 43 47 53 55 63
2046821 7 17 33 39 45 47 61 63
1223889 5 1 39 43 49 59
1342617 3 33 39 53
1931975 5 39 41 43 59 61
1883454 8 35 38 40 43 45 53 54 56
530049 1 47
2031474 4 35 41 53 57
1915235 1 39
94030 3 47 51 57
985970 3 29 57 63
138515 5 5 19 23 33 45
1879066 ...

output:

2
3
3
3
3
3
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
2
3
3
3
2
2
3
3
3
3
3
3
3
3
3
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
3
3
3
3
3
3
2
3
3
3
2
3
3
2
3
3
3
3
2
3
3
3
3
3
2
3
3
3
3
2
3
3
3
2
3
3
3
3
3
2
3
3
3
3
3
2
3
3
2
3
2
3
3
2
2
3
3
3
3
3
3
2
3
3
3
3
3
3
3
3
3
3
3
2
3
3
3
2
3
3
3
3
2
2
3
3
3
3
3
...

result:

ok 262144 tokens

Test #16:

score: 0
Accepted
time: 1719ms
memory: 808732kb

input:

262144
29272 1 55
1899573 3 36 40 56
1694145 5 46 51 56 57 61
1507390 4 35 47 57 59
1913469 3 57 59 63
1830846 2 41 50
1638766 3 35 43 47
1037738 5 33 41 47 59 63
1635590 7 37 39 43 47 51 53 55
742743 8 37 39 41 47 51 57 59 61
1486070 7 33 35 41 43 47 53 59
1094196 3 41 51 55
900604 3 43 45 49
37847...

output:

3
3
3
3
3
3
3
2
2
3
2
3
3
3
3
4
3
3
3
2
3
2
3
3
2
3
3
3
3
3
3
4
3
4
3
4
4
3
3
2
3
3
2
3
2
2
2
3
3
2
3
2
3
3
2
3
3
3
2
2
3
4
3
3
3
2
3
2
2
2
3
3
3
3
2
3
3
3
2
2
3
4
3
3
4
3
2
3
2
2
3
2
4
2
2
3
2
3
4
3
2
3
3
4
4
2
4
2
4
3
2
3
4
3
2
3
3
2
3
3
4
3
3
4
3
4
3
3
3
3
3
4
3
3
3
2
3
2
2
2
3
2
4
2
3
2
2
3
2
3
...

result:

ok 262144 tokens

Test #17:

score: 0
Accepted
time: 1523ms
memory: 808176kb

input:

262144
1750554 1 45
283311 8 37 41 43 47 51 55 57 59
157339 1 43
1567436 4 41 43 49 59
1529380 1 37
525182 2 33 41
1927140 4 33 44 57 58
1579525 3 45 51 55
1969374 7 33 35 43 45 51 57 63
1726242 3 7 11 27
985308 2 41 61
140568 7 33 35 43 55 57 59 61
1477422 1 33
1484632 7 39 41 45 47 59 61 63
196828...

output:

3
3
4
3
3
3
3
3
2
2
3
2
3
2
3
2
4
2
3
2
3
2
2
2
3
2
3
2
3
3
3
4
4
2
2
2
3
3
3
4
2
2
3
2
3
4
2
3
3
3
2
3
2
2
3
2
3
3
4
3
2
3
3
3
4
3
3
2
3
2
3
3
3
3
4
3
3
3
3
3
2
2
3
3
3
4
2
3
3
3
3
3
3
3
3
2
3
3
3
3
3
3
3
3
2
3
2
3
4
2
2
2
3
3
3
4
3
2
3
3
3
3
3
2
2
3
3
3
2
2
4
2
3
3
3
3
3
3
2
3
3
2
2
2
3
4
4
2
3
2
...

result:

ok 262144 tokens

Test #18:

score: 0
Accepted
time: 991ms
memory: 809336kb

input:

262144
1575517 8 37 43 49 51 55 57 61 63
1409957 8 37 45 53 55 57 59 61 63
1288769 8 37 41 43 47 49 51 57 59
1929607 8 33 35 41 43 55 57 59 63
1896331 8 37 41 47 51 53 57 61 63
473009 8 8 16 21 23 32 45 53 61
287821 8 35 39 43 45 47 49 57 61
732889 8 39 40 51 52 53 55 59 64
1430089 8 35 39 41 45 49 ...

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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
1
1
...

result:

ok 262144 tokens

Test #19:

score: 0
Accepted
time: 994ms
memory: 808352kb

input:

262144
2068397 8 35 41 43 49 51 55 59 61
2007935 8 41 43 45 49 51 53 57 59
1484547 8 33 35 38 43 45 49 52 53
1382969 8 33 35 37 41 45 49 53 59
2002379 8 3 17 19 33 35 47 57 61
2043139 8 17 19 29 33 51 53 55 63
2085239 8 33 35 39 47 55 57 59 61
1781797 8 37 41 43 45 47 53 57 59
1220721 8 33 35 41 45 ...

output:

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
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
...

result:

ok 262144 tokens

Test #20:

score: 0
Accepted
time: 1085ms
memory: 808012kb

input:

262144
1540382 5 8 22 35 38 41
1075954 1 9
315357 1 9
1753332 2 8 35
1740559 2 8 50
1655255 2 36 62
950813 1 21
1362719 1 7
1663869 6 1 6 13 32 61 62
1743262 4 9 24 26 57
1842557 2 7 55
810834 5 14 17 21 52 56
1835988 3 26 27 34
1653549 1 41
642676 2 20 21
944378 4 17 23 34 56
1957034 3 21 54 55
191...

output:

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

result:

ok 262144 tokens

Test #21:

score: 0
Accepted
time: 1025ms
memory: 809608kb

input:

262141
1765576 1 5
995873 2 21 30
894245 4 1 11 23 26
893593 5 3 13 14 27 32
1717612 1 5
413456 2 17 28
295956 3 15 27 32
356817 3 20 22 29
65121 5 11 13 14 15 18
893840 3 5 16 18
203629 2 20 21
928467 3 4 12 15
612032 1 14
1163038 2 10 23
1992866 1 18
255902 3 17 21 29
146825 1 7
531108 3 1 8 22
18...

output:

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

result:

ok 262141 tokens

Test #22:

score: 0
Accepted
time: 1075ms
memory: 808100kb

input:

262142
2037564 4 33 53 54 63
697482 2 41 57
408390 1 34
1199739 5 34 40 46 50 58
938094 3 54 59 62
964319 7 45 50 52 55 56 59 62
214917 1 45
1308020 1 64
283389 1 46
117497 1 35
1034111 2 43 56
1667640 3 37 43 58
555910 6 44 47 48 49 62 63
1657795 1 50
206804 1 33
1788261 6 34 42 52 56 59 60
1057631...

output:

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

result:

ok 262142 tokens

Test #23:

score: 0
Accepted
time: 1206ms
memory: 809192kb

input:

262141
471200 1 53
249329 4 35 41 59 61
450598 1 49
1096921 2 53 59
1421607 1 43
926740 2 33 59
1527280 4 41 47 57 59
344274 5 35 37 43 45 55
47512 2 39 49
36626 5 33 37 39 47 59
1155924 2 51 63
664099 2 35 55
972545 1 45
1416432 5 33 35 37 47 59
165306 3 49 51 61
1091065 1 53
1286366 2 33 59
288469...

output:

3
1
2
2
3
3
3
3
2
2
3
1
4
3
3
2
2
2
2
3
3
3
2
4
3
2
2
1
3
3
2
2
3
3
3
3
3
2
3
3
1
2
4
3
1
2
4
2
3
2
5
3
3
3
3
2
3
3
3
3
4
3
2
3
2
2
3
3
2
3
3
2
1
4
3
2
3
3
3
2
2
3
1
3
2
3
2
2
3
3
3
3
2
2
2
3
3
4
3
3
3
3
2
2
2
3
2
2
2
2
2
3
1
2
2
3
1
1
2
3
3
3
2
2
2
4
4
4
2
3
2
3
3
3
3
2
2
4
2
3
3
3
2
2
2
3
3
3
3
2
...

result:

ok 262141 tokens

Test #24:

score: 0
Accepted
time: 1148ms
memory: 808128kb

input:

262140
1508641 7 28 31 34 36 43 61 62
1759322 7 1 22 34 37 48 57 62
329439 7 2 19 24 26 37 41 51
2082019 8 8 11 16 30 47 51 56 58
824802 7 6 18 24 31 35 38 59
1894470 7 8 15 24 26 31 39 57
787377 7 2 4 5 21 23 52 62
1242303 7 1 4 6 35 47 51 62
2082172 7 4 8 12 14 23 28 34
19868 8 9 23 27 35 36 40 46...

output:

3
2
3
1
2
2
2
2
2
2
2
2
3
1
3
3
2
3
2
2
2
2
3
2
2
1
3
3
1
3
3
3
2
3
2
3
2
2
2
3
2
2
2
2
2
3
2
1
2
2
2
3
1
3
3
3
2
3
2
2
2
2
2
2
2
2
2
2
2
2
2
3
1
1
2
1
3
2
2
3
2
3
1
2
2
2
3
2
2
2
1
2
1
2
2
1
3
1
1
2
3
2
2
3
2
2
1
2
2
2
2
2
2
2
3
3
2
2
3
2
2
3
3
2
2
2
3
2
3
2
3
2
2
2
2
2
2
2
2
2
2
3
2
2
2
2
2
2
2
2
...

result:

ok 262140 tokens

Test #25:

score: 0
Accepted
time: 1032ms
memory: 808092kb

input:

262063
846837 4 20 37 53 55
907056 6 8 26 39 43 49 57
333809 2 29 35
734788 3 11 31 55
433196 4 15 31 58 64
57181 1 51
992982 5 15 20 24 29 61
236676 5 2 10 32 42 49
871320 3 22 48 60
761494 2 15 29
370290 6 5 13 32 40 60 62
897382 2 46 58
1005520 1 5
15551 6 1 7 20 27 46 63
303266 1 8
736582 2 35 4...

output:

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

result:

ok 262063 tokens

Test #26:

score: 0
Accepted
time: 1103ms
memory: 808764kb

input:

262124
1846841 2 28 48
1919199 4 11 20 23 53
1083016 1 36
1155633 2 44 45
1278282 2 9 48
1860121 5 3 37 48 49 56
1886674 1 37
1073824 3 20 35 58
1923778 3 4 34 50
1355623 6 1 39 42 45 51 56
1751908 4 20 23 49 54
1153008 2 10 37
1453477 2 56 61
1721600 3 30 43 62
1666095 1 15
1214047 4 23 31 42 51
19...

output:

2
3
3
3
3
2
3
3
2
1
3
3
1
3
3
1
3
2
3
2
2
1
2
2
3
1
2
3
3
3
2
3
3
2
3
3
3
2
3
3
3
3
3
3
2
4
3
2
2
2
3
3
3
3
2
3
2
2
2
2
2
2
1
2
2
3
3
3
4
1
2
2
3
3
1
2
2
3
3
2
2
2
2
2
2
2
4
3
5
1
1
3
2
3
2
2
3
3
1
2
3
3
4
2
2
2
3
2
2
3
3
3
2
2
2
2
2
2
3
3
3
3
2
3
3
2
3
4
2
3
3
1
2
2
2
2
3
3
3
3
2
2
3
3
3
2
3
3
3
3
...

result:

ok 262124 tokens

Test #27:

score: 0
Accepted
time: 1022ms
memory: 809556kb

input:

262133
1849834 1 6
75455 2 1 41
1323543 1 23
1331735 1 4
1585945 1 3
791053 1 62
1868546 1 63
1467670 2 40 52
244703 1 32
1243005 2 41 51
321897 1 43
915154 1 40
575914 1 49
328420 1 20
1704229 1 4
1246125 1 23
2025723 1 23
2014366 1 57
166168 2 1 17
1735167 1 36
588547 1 23
1375773 1 6
1942224 1 27...

output:

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

result:

ok 262133 tokens

Test #28:

score: 0
Accepted
time: 7090ms
memory: 809264kb

input:

262143
1197576 6 9 38 42 59 62 64
456036 3 28 29 39
429870 2 46 54
1032784 6 27 31 39 40 41 50
1533936 6 11 32 47 49 51 57
1464528 4 7 24 48 59
506175 6 29 31 34 39 45 61
611760 3 26 28 38
1954620 3 16 25 56
2066324 6 13 17 22 28 35 47
846832 6 8 14 20 38 56 64
873639 6 5 11 17 21 46 47
176988 5 15 ...

output:

4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
...

result:

ok 262143 tokens

Test #29:

score: 0
Accepted
time: 11458ms
memory: 809620kb

input:

262143
667032 7 2 27 34 37 41 51 59
1329732 7 12 25 37 38 41 50 51
555148 7 23 43 47 53 54 56 63
577449 7 3 5 41 52 53 55 63
521696 7 14 28 34 35 44 45 48
1830888 7 9 29 30 35 43 58 63
1916352 7 17 23 36 37 43 47 57
871792 7 2 5 25 38 41 57 61
1996544 7 17 19 31 40 47 58 64
1066268 7 4 18 21 35 40 4...

output:

4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
...

result:

ok 262143 tokens

Test #30:

score: -100
Time Limit Exceeded

input:

262143
269240 8 25 29 37 40 43 50 57 64
691540 8 1 23 24 40 47 56 57 59
1779320 8 4 8 27 28 31 41 49 59
1124648 8 1 16 28 31 46 49 59 61
1392024 8 3 14 19 25 26 31 45 47
394821 8 1 3 11 13 23 29 49 50
648464 8 10 29 31 32 43 52 53 59
1361325 8 11 15 43 44 45 53 55 57
332992 8 10 21 28 29 37 45 52 61...

output:

4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
...

result: