QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#222859#5047. PermutationabsintheAC ✓288ms42068kbC++235.6kb2023-10-21 19:17:222023-10-21 19:17:23

Judging History

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

  • [2023-10-21 19:17:23]
  • 评测
  • 测评结果:AC
  • 用时:288ms
  • 内存:42068kb
  • [2023-10-21 19:17:22]
  • 提交

answer

// problem-url: https://qoj.ac/contest/1039/problem/5047

#if not LOCAL
#define NDEBUG 1
#endif
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(auto i = a; i < (b); ++i)
#define down(x, a) for (auto x = a; x--;)
#define all(x) begin(x), end(x)
#define sz(x) int(size(x))
#define let auto const

using ll = long long;
using lint = ll;
using pii = pair<int, int>;
using vi = vector<int>;

let mod=998244353;

// { ==== Begin library /home/user202729/icpc-trd/content/number-theory/ModularArithmetic.h ====
/**
 * Author: user202729
 * Date: 2023-10-09
 * License: CC0
 * Source: folklore
 * Status: not tested very well
 * Description: Operators for modular arithmetic. You need to set {\tt mod} to
 * some number first and then you can use the structure.
 */



// { ==== Begin library euclid.h ====
/**
 * Author: Unknown
 * Date: 2002-09-15
 * Source: predates tinyKACTL
 * Description: Finds two integers $x$ and $y$, such that $ax+by=\gcd(a,b)$. If
 * you just need gcd, use the built in \texttt{\_\_gcd} instead.
 * If $a$ and $b$ are coprime, then $x$ is the inverse of $a \pmod{b}$.
 */



ll euclid(ll a, ll b, ll &x, ll &y) {
	if (!b) return x = 1, y = 0, a;
	ll d = euclid(b, a % b, y, x);
	return y -= a/b * x, d;
}

// } ==== End library euclid.h ====


struct Mod {
	int x;
	Mod(int y=0) : x(y%mod) { if(x<0) x+=mod; }
	static Mod raw(int y){ Mod r; r.x=y; return r; }
	void operator+=(Mod b) { if((x+=b.x)>=mod) x-=mod; }
	void operator-=(Mod b) { if((x-=b.x)<0) x+=mod; }
	Mod operator-() const { return 0-*this; }
	void operator*=(Mod b) { x=int(ll(x) * b.x % mod); }
	explicit operator int() const{return x;}
		
	[[nodiscard]] Mod pow(auto p) const {
		assert(p>=0);
		Mod a=*this;
		Mod ans = 1; for (; p; p >>= 1, a *= a) if (p&1) ans *= a;
		return ans;
	}

	[[nodiscard]] Mod inv() const {
		assert(x!=0);
		return pow(mod-2);
		//ll z, y, g = euclid(mod, x, z, y); assert(g == 1); return int(y);
	}
	void operator/=(Mod b) { *this *= b.inv(); }

#define A(O) [[nodiscard]] friend Mod operator O(Mod a, Mod b) { a O##= b; return a; }
	A(+) A(-) A(*) A(/)
#undef A

#define C(O) [[nodiscard]] bool operator O(Mod b) const { return x O b.x; }
	C(==) C(!=) C(<) C(>) C(<=) C(>=)
#undef C
};

// } ==== End library /home/user202729/icpc-trd/content/number-theory/ModularArithmetic.h ====


// { ==== Begin library YComb ====

template<class T> struct YComb_{
	T f;
	template<class... Args> auto operator()(Args&&... args)const{
		return f(*this, std::forward<Args>(args)...);
	}
};

template<class T> YComb_<T> YComb(T f){ return {std::move(f)}; }

// } ==== End library YComb ====


#define brute 0

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

#if brute
	rep(seed, 831, 1000000007){
		mt19937 engine(seed);
		let n=uniform_int_distribution(2, 9)(engine);
		let c=uniform_int_distribution(2, 10)(engine);
#else
	int t; cin>>t;
	down(_, t){
		int n; cin>>n;
		int c; cin>>c;
#endif
		vector<int> pos(n, -1);
#if LOCAL
		vector<int> permutation(n);
#endif
		rep(i, 0, n){
			int val;

#if brute
			do val=uniform_int_distribution(0, n-1)(engine); while(pos[val]>=0);
#else
			cin>>val; --val;
#endif

			pos[val]=i;
#if LOCAL
			permutation[i]=val;
#endif
		}

		struct Block{
			int rightEnd, leftExtent, leftVal, rightExtent, rightVal;
		};
		map<int, Block> ranges;
		ranges.insert({0, {n, 0, -1, n, -1}});
		vector<int> par(n, -1);
		vector<int> len(n);
		rep(val, 0, n){
			let p=pos[val];
			let iter=--ranges.upper_bound(p);
			auto& [leftEnd, block]=*iter;
			auto& [rightEnd, leftExtent, leftVal, rightExtent, rightVal]=block;
			assert(p<rightEnd);
			assert(leftEnd<=leftExtent);
			assert(leftExtent<=rightExtent);
			assert(rightExtent<=rightEnd);

			int left=p, right=p+1;
			down(_, 2){
				if(leftExtent!=0 and left-leftExtent<c and leftEnd+(leftEnd==0)+c<=rightEnd) left=leftEnd, right=max(right, min(rightEnd, leftExtent+c));
				if(rightExtent!=n and rightExtent-right<c and rightEnd-(rightEnd==n)-c>=leftEnd) right=rightEnd, left=min(left, max(leftEnd, rightExtent-c));
			}
			if(left==leftEnd and right-left>1){
				assert(right>=leftExtent);
				if(leftVal>=0) par[leftVal]=val;
				leftVal=val, leftExtent=right;
				if(right==rightEnd){
					if(rightVal>=0) par[rightVal]=val;
					rightVal=-1, rightExtent=rightEnd;
				}
			}else if(right==rightEnd and right-left>1){
				assert(left<=rightExtent);
				if(rightVal>=0) par[rightVal]=val;
				rightVal=val, rightExtent=left;
				assert(left!=leftEnd);
			}else{
				let oldRightEnd=rightEnd, oldRightExtent=rightExtent, oldRightVal=rightVal;
				rightExtent=rightEnd=p;
				rightVal=-1;
				ranges.insert(iter, {p+1, {oldRightEnd, p+1, -1, oldRightExtent, oldRightVal}});
			}
			len[val]=right-left;
			//assert(cerr<<val<<":"<<left<<' '<<right<<'\n');
		}
		vector<int> used(n);
		Mod answer=1;
		rep(val, 0, n){
			answer*=len[val]-used[val];
			if(par[val]>=0) used[par[val]]+=used[val]+1;
		}

#if LOCAL
		set<vector<int>> reachable;
		YComb([&](auto dfs, vector<int> permutation)->void{
			auto [iterator, inserted]=reachable.insert(permutation);
			if(inserted){
				rep(i, 0, n-c){
					auto iter=min_element(permutation.begin()+i, permutation.begin()+i+c+1);
					if(iter==permutation.begin()+i){
						auto copy=permutation;
						sort(copy.begin()+i+1, copy.begin()+i+c+1);
						do{
							dfs(copy);
						}while(next_permutation(copy.begin()+i+1, copy.begin()+i+c+1));
					}
					if(iter==permutation.begin()+i+c){
						auto copy=permutation;
						sort(copy.begin()+i, copy.begin()+i+c);
						do{
							dfs(copy);
						}while(next_permutation(copy.begin()+i, copy.begin()+i+c));
					}
				}
			}
		})(permutation);
		assert(answer==Mod(sz(reachable)));
#endif

		cout<<int(answer)<<'\n';
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3432kb

input:

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

output:

6
1
4
6
4

result:

ok 5 number(s): "6 1 4 6 4"

Test #2:

score: 0
Accepted
time: 47ms
memory: 3456kb

input:

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

output:

24
6
6
24
1
24
24
6
18
1
24
4
6
6
6
4
1
12
1
6
6
24
18
2
18
4
6
6
18
6
4
1
6
18
1
6
24
18
6
1
12
18
6
4
2
24
12
4
24
4
4
24
6
1
1
1
1
6
1
4
1
18
1
18
4
4
6
24
6
4
6
1
12
1
4
4
6
24
18
6
2
6
1
12
6
24
1
4
6
1
1
6
1
1
24
12
18
1
4
18
1
4
24
6
4
24
6
24
1
1
6
1
18
24
1
4
1
1
2
6
1
6
4
18
1
24
6
6
4
24
...

result:

ok 100000 numbers

Test #3:

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

input:

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

output:

432
5040
2304
24
201600
720
5040
120
1
20160
720
120
1
360
120
120
2160
141120
192
1
480
1
108
24
1
432
25200
1
30240
35280
35280
720
1800
576
1296
120
35280
20160
432
432
8
201600
192
432
141120
201600
2304
720
2880
576
1
120
201600
576
360
241920
40320
24
1
1
1
35280
1
1
1
3600
720
108
720
1
1296
...

result:

ok 10000 numbers

Test #4:

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

input:

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

output:

144
1
5040
1
192
1
2880
322560
24
1
600
2304
1
1
36
1152
1
1
48
1
120
360
141120
1
1800
322560
2304
282240
362880
362880
480
120
120
48
1
24
36
201600
2160
35280
24
40320
25200
1
1
1296
1296
120
480
20160
480
322560
360
25200
141120
1
720
1
1
120
1152
1440
1
1
1
720
720
576
282240
432
1
1
1
40320
32...

result:

ok 10000 numbers

Test #5:

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

input:

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

output:

360
1
2880
720
1
720
600
48
362880
1
322560
120
432
720
1
5040
30240
24
96
48
2160
720
4320
1
1
720
1152
720
20160
2880
72
2160
35280
96
24
20160
282240
201600
1296
360
576
480
362880
120
40320
1
72
144
720
20160
72
20160
1
241920
20160
72
120
120
15120
360
5040
2880
1
2160
288
1
40320
40320
480
480...

result:

ok 10000 numbers

Test #6:

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

input:

1000
50 19
39 46 34 41 7 19 13 2 28 26 40 1 35 42 11 32 50 25 8 45 24 29 22 18 16 6 36 48 31 27 10 12 38 37 17 49 30 33 43 4 23 3 47 15 9 5 21 14 44 20
50 9
39 16 45 12 25 22 24 15 50 41 21 26 6 18 30 20 44 2 13 10 5 37 34 27 36 47 40 17 8 4 48 42 31 38 23 1 32 28 43 19 29 9 33 35 46 14 7 49 11 3
50...

output:

567646151
904915777
822371487
736050414
600774364
361781505
143685687
220211819
987913491
299469816
837902046
783901458
805655665
1
593639731
1
861744461
1
966786798
504900914
283559646
148890368
772701919
614643632
290522794
1
753390358
641491052
816418869
652885152
1
837902046
295294925
379831433
...

result:

ok 1000 numbers

Test #7:

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

input:

1000
50 3
33 2 10 47 39 26 5 1 9 8 42 27 44 30 36 16 18 12 13 35 43 46 4 22 11 19 6 45 7 32 28 3 34 41 31 50 15 21 38 48 17 29 25 37 14 49 20 24 23 40
50 35
40 8 13 43 24 9 27 35 10 25 12 18 30 39 11 16 22 14 21 36 31 46 42 6 26 7 28 19 34 45 33 47 23 2 5 41 20 32 50 48 4 49 44 37 1 38 15 17 29 3
50...

output:

203567069
572108669
340897625
1
538293216
304827285
540519311
732552014
1
324879016
484802068
511305727
370610850
805869924
1
729545036
73799117
993629707
1
738017996
421226657
515245629
190572217
139305703
1
521746461
606263421
749940761
943237576
1
364507838
676326058
641491052
1
741967906
1
72935...

result:

ok 1000 numbers

Test #8:

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

input:

1000
50 19
33 46 22 48 2 50 11 49 29 4 42 32 40 37 35 18 30 23 36 6 7 27 41 3 26 19 25 14 34 1 20 38 44 24 16 10 47 31 8 5 15 21 13 9 28 12 45 43 39 17
50 12
37 12 30 22 44 21 4 10 17 34 45 43 42 29 7 25 5 48 23 20 14 50 40 1 2 11 13 16 28 49 36 38 6 15 18 19 39 3 27 35 32 8 26 9 46 31 24 47 33 41
5...

output:

93147306
121414421
186574145
59230529
1
1
141779823
526366254
380063818
845671530
970497268
978717980
63011703
1
211771833
1
1
1
676358722
612789666
1
657112938
561656917
839427168
20867134
567646151
589124132
593494012
1
856187068
1
706365909
1
920532689
785969121
1
855830729
460982724
316140945
79...

result:

ok 1000 numbers

Test #9:

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

input:

1000
50 35
45 33 24 31 27 36 7 23 42 15 39 22 41 3 37 48 2 49 20 38 26 35 25 9 28 50 30 46 8 43 4 18 44 1 5 12 21 40 17 19 16 14 29 34 47 6 13 10 11 32
50 38
14 11 35 7 50 4 41 24 18 12 27 19 1 5 22 13 28 17 16 8 43 46 32 49 21 36 48 33 9 31 44 23 2 30 37 25 40 45 26 15 3 38 6 20 10 39 34 29 47 42
5...

output:

1
1
918872114
1
799236323
851682606
466205103
672673398
986109411
237676512
215547397
526381028
30282727
380063818
969653692
549781074
499177977
1
676326058
1
23510511
567646151
123436377
660279506
1
1
230736384
1
847479521
428060021
97907900
339471033
1
1
452699684
1
593639731
767250218
1
1
9024167...

result:

ok 1000 numbers

Test #10:

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

input:

1000
50 35
25 41 33 23 24 12 42 46 45 10 7 16 43 26 39 15 35 11 19 5 21 22 40 9 29 31 3 48 34 36 47 1 27 49 4 6 20 37 17 14 8 28 18 50 44 30 38 2 13 32
50 32
9 25 10 48 28 39 18 6 26 47 40 45 44 30 38 13 37 49 31 11 1 36 32 12 33 7 21 24 43 4 34 20 22 41 16 50 42 19 2 29 5 35 14 3 46 15 17 23 8 27
5...

output:

1
1
1
966786798
62574862
914551701
512681272
726296738
736050414
1
748894162
816418869
59230529
254940118
1
1
978717980
918872114
1
380026194
914551701
254940118
1
833898700
937525290
1
966786798
331196124
590178664
516495362
958314234
864016726
561656917
368233794
507510371
1
283559646
951359943
10...

result:

ok 1000 numbers

Test #11:

score: 0
Accepted
time: 52ms
memory: 3464kb

input:

1000
500 494
212 491 495 442 426 314 341 42 22 247 499 277 226 406 497 209 105 302 213 231 246 123 427 74 466 329 423 89 488 118 250 236 286 360 299 463 51 37 91 112 116 184 10 185 359 59 313 124 297 500 139 82 251 249 238 357 293 381 194 120 462 319 97 401 420 181 198 187 321 374 349 68 308 354 13 ...

output:

1
369819598
79440751
826163737
1
203923370
975564702
636233236
22885662
587959123
210504484
62654757
63173954
325826961
613256208
515280304
542268941
566438719
358739333
241420315
1
1
613344817
690090622
209788531
217004985
266176189
1
69092736
801068619
216892151
195641568
1
697748554
743770407
636...

result:

ok 1000 numbers

Test #12:

score: 0
Accepted
time: 47ms
memory: 3516kb

input:

1000
500 34
431 471 482 232 447 126 478 427 405 418 251 333 407 361 476 9 448 48 276 419 373 138 454 273 160 260 296 432 81 347 79 475 340 225 171 239 422 32 286 86 337 8 129 14 257 289 210 164 338 384 256 493 192 5 227 435 39 283 346 98 13 263 443 102 282 204 46 304 127 100 18 119 179 65 52 157 430...

output:

642107110
994913686
569325635
144114861
981797303
373632628
1
237586273
583461679
435954006
339676851
1
1
530491163
682550749
144845479
788210049
655548099
879284515
1
1
891361363
1
1
107793378
348412766
1
748837249
952360967
990814597
862669788
148631681
1
968433321
630405774
967333268
516507942
1
...

result:

ok 1000 numbers

Test #13:

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

input:

1000
500 410
34 378 77 192 408 295 308 484 293 360 73 371 199 262 403 32 263 443 54 266 286 147 152 63 53 254 181 313 94 255 474 131 129 169 10 93 290 498 35 141 58 27 203 372 52 98 315 281 240 347 116 243 303 213 174 419 66 83 301 260 134 464 144 154 238 46 310 305 457 109 410 170 418 400 339 184 2...

output:

158137008
1
901063286
975507056
1
691751126
1
517876374
1
51401571
962058390
761081352
1
441852974
195964339
80956464
888804009
735850380
131009036
137123897
58529921
1
1
1
696027122
127831228
131009036
483551773
395905754
33901266
431858460
221326270
745951239
805669961
738842231
1
1
936241441
8572...

result:

ok 1000 numbers

Test #14:

score: 0
Accepted
time: 49ms
memory: 3828kb

input:

100
5000 1734
3833 3764 1513 214 4943 189 3853 847 1880 2818 4150 4053 2526 1548 3736 3332 2251 4867 1941 3738 2184 2203 4179 4370 3509 3041 4472 1700 2672 70 271 4489 4363 1242 1066 4672 3327 2437 3013 582 4058 1617 296 4081 3174 2004 3847 2856 521 728 3380 2443 2337 4814 1269 3067 1356 450 2044 27...

output:

479539860
425871512
62427483
270105456
105638884
899923270
686908453
1
1
67946905
790358616
1
175157062
342927479
1
565285796
466220125
97218602
250089907
410446930
219040705
1
202216070
134795355
601016622
524256923
438171434
194366854
448499227
566906878
462990841
1
1
148108274
984972809
1
5377379...

result:

ok 100 numbers

Test #15:

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

input:

100
5000 3200
2756 4969 2724 2257 55 682 3774 4488 1664 3504 2146 1293 1494 2321 4829 4912 195 129 2837 981 4058 2561 3898 4402 4687 583 2860 742 4851 1234 1399 94 4929 4754 4784 526 1245 2229 3419 418 2284 4665 3447 3542 2610 4530 2719 4017 3864 1646 4571 609 2743 1195 3429 3803 3657 1431 25 4527 4...

output:

214249578
566341904
727615688
557417352
196515777
1
794847484
1
893958812
1
235155322
489698323
801357509
1
268786735
276045989
982338656
1
1
237198495
362607205
14383965
1
292714629
1
1
1
41233155
370099150
584677323
95102145
868158089
80536996
398874664
806738256
1
424734813
403007112
486376619
80...

result:

ok 100 numbers

Test #16:

score: 0
Accepted
time: 48ms
memory: 3932kb

input:

100
5000 3696
4765 492 1938 4448 4955 4354 2653 3108 429 3573 1 4605 450 745 1331 2010 4805 4784 240 2217 3245 2511 4973 4505 349 676 1100 4666 2992 4565 4359 4364 1492 1821 1583 3301 616 453 404 3228 3033 4229 158 2 4643 4788 3062 1112 4588 4154 3178 252 2394 1776 1659 603 2830 2356 4684 3267 4715 ...

output:

358487115
46468809
818168279
253942066
446600289
932734478
1
849757973
152390032
250656142
261364043
1
590596235
731357994
463879901
23555375
105295172
784500307
1
1
487388538
509410058
369765289
311230044
1
370046396
1
961162350
361771548
1
64559608
1
547217330
912387290
577805767
894965714
7608513...

result:

ok 100 numbers

Test #17:

score: 0
Accepted
time: 64ms
memory: 7156kb

input:

10
50000 13973
28116 20115 14842 25914 33088 48016 44516 10294 38893 32404 15477 46433 30415 39110 38711 7693 16807 27840 37896 6780 26529 26328 13098 30893 9114 8471 24678 4625 3410 23767 13714 19215 14825 44581 24274 41026 46943 17495 46167 15674 41733 32715 17893 38230 15315 7143 31352 10580 1714...

output:

219376429
950414413
259439554
1
432091619
827170450
577732639
1
492759615
432112264

result:

ok 10 numbers

Test #18:

score: 0
Accepted
time: 91ms
memory: 7132kb

input:

10
50000 46561
38607 36595 27424 49109 23749 36970 28764 48667 44258 2238 17040 46146 16961 33110 44984 172 17987 7665 6775 31316 36880 27871 37929 17375 29286 36191 15763 35881 1996 12366 21624 44080 12150 25296 21202 39150 43562 47025 32716 39927 39692 49076 2671 11486 34973 30411 38517 32446 5477...

output:

1
1
213888805
519627215
33908559
87179321
1
879713497
770834248
1

result:

ok 10 numbers

Test #19:

score: 0
Accepted
time: 70ms
memory: 7072kb

input:

10
50000 29151
18804 16899 46085 21814 6177 25319 28174 31655 38144 20538 35901 14711 8235 47805 42389 6862 26576 39525 11848 29774 7666 38553 44735 40440 16317 39720 26471 38589 16735 40375 13645 1730 12141 11223 45658 415 16923 18437 26578 18805 26781 48719 46757 37441 6119 14149 1264 49098 6804 1...

output:

469176520
580780933
395327162
88098357
319297584
1
463874158
149694556
1
279709473

result:

ok 10 numbers

Test #20:

score: 0
Accepted
time: 76ms
memory: 16744kb

input:

1
500000 355636
31569 203534 208969 149505 342282 95144 290926 72091 411541 415394 194287 350109 291286 301084 127622 489830 305454 43222 181117 467057 210253 478042 23795 210198 191482 53399 93752 379652 45342 391043 133048 196260 209448 218978 432432 293537 299428 235675 302186 222711 9092 159152 ...

output:

314349501

result:

ok 1 number(s): "314349501"

Test #21:

score: 0
Accepted
time: 54ms
memory: 14384kb

input:

1
500000 440516
458006 311081 2448 111658 412361 174277 350345 106661 335273 472776 276631 209395 381577 354444 366543 125897 74196 432486 234768 147404 320955 99157 467291 105345 159194 484670 223451 129650 277376 297726 177109 70511 383323 307753 353371 433487 118986 25051 76563 481873 379661 3286...

output:

381158921

result:

ok 1 number(s): "381158921"

Test #22:

score: 0
Accepted
time: 288ms
memory: 42068kb

input:

1
500000 494348
244265 313469 452656 323186 161233 417512 94776 289408 73780 404479 375264 381643 7423 78482 465334 290594 162577 119160 255393 66139 456507 210887 446193 183225 219875 35232 405908 99279 105133 302617 47956 425809 329798 479480 58663 243704 163644 451720 21854 492994 285396 192133 3...

output:

1

result:

ok 1 number(s): "1"

Test #23:

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

input:

10
50000 5
28116 20115 14842 25914 33088 48016 44516 10294 38893 32404 15477 46433 30415 39110 38711 7693 16807 27840 37896 6780 26529 26328 13098 30893 9114 8471 24678 4625 3410 23767 13714 19215 14825 44581 24274 41026 46943 17495 46167 15674 41733 32715 17893 38230 15315 7143 31352 10580 17144 11...

output:

181086825
798604889
555846360
668802434
498622544
470132683
165097647
178312884
526185318
950228960

result:

ok 10 numbers

Test #24:

score: 0
Accepted
time: 74ms
memory: 4604kb

input:

10
50000 5
38607 36595 27424 49109 23749 36970 28764 48667 44258 2238 17040 46146 16961 33110 44984 172 17987 7665 6775 31316 36880 27871 37929 17375 29286 36191 15763 35881 1996 12366 21624 44080 12150 25296 21202 39150 43562 47025 32716 39927 39692 49076 2671 11486 34973 30411 38517 32446 5477 309...

output:

809817194
5578923
91348846
126140301
277574377
574596330
727863755
713228418
163863997
982683616

result:

ok 10 numbers

Test #25:

score: 0
Accepted
time: 77ms
memory: 4728kb

input:

10
50000 5
18804 16899 46085 21814 6177 25319 28174 31655 38144 20538 35901 14711 8235 47805 42389 6862 26576 39525 11848 29774 7666 38553 44735 40440 16317 39720 26471 38589 16735 40375 13645 1730 12141 11223 45658 415 16923 18437 26578 18805 26781 48719 46757 37441 6119 14149 1264 49098 6804 19958...

output:

548916957
608733746
422715411
238579576
170546121
590692354
180768042
256779969
419944807
675410637

result:

ok 10 numbers

Test #26:

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

input:

1
500000 2
31569 203534 208969 149505 342282 95144 290926 72091 411541 415394 194287 350109 291286 301084 127622 489830 305454 43222 181117 467057 210253 478042 23795 210198 191482 53399 93752 379652 45342 391043 133048 196260 209448 218978 432432 293537 299428 235675 302186 222711 9092 159152 44443...

output:

986138496

result:

ok 1 number(s): "986138496"

Test #27:

score: 0
Accepted
time: 146ms
memory: 16780kb

input:

1
500000 2
458006 311081 2448 111658 412361 174277 350345 106661 335273 472776 276631 209395 381577 354444 366543 125897 74196 432486 234768 147404 320955 99157 467291 105345 159194 484670 223451 129650 277376 297726 177109 70511 383323 307753 353371 433487 118986 25051 76563 481873 379661 32869 490...

output:

67175535

result:

ok 1 number(s): "67175535"

Test #28:

score: 0
Accepted
time: 145ms
memory: 16756kb

input:

1
500000 2
244265 313469 452656 323186 161233 417512 94776 289408 73780 404479 375264 381643 7423 78482 465334 290594 162577 119160 255393 66139 456507 210887 446193 183225 219875 35232 405908 99279 105133 302617 47956 425809 329798 479480 58663 243704 163644 451720 21854 492994 285396 192133 351168...

output:

875296862

result:

ok 1 number(s): "875296862"

Test #29:

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

input:

100
5000 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

172998035
667160976
978979749
750604250
542676448
510977092
208663177
802485586
86009966
364307871
312843970
176943556
814240166
480667822
570139782
514011933
636796319
15698584
368805247
874334980
639404714
226350601
130748039
184090963
674535331
342323791
121280211
428081454
246132950
480978319
73...

result:

ok 100 numbers

Test #30:

score: 0
Accepted
time: 55ms
memory: 3688kb

input:

100
5000 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

987173642
100139550
402256208
562913330
281920522
484783967
118787527
196800977
460351261
321393511
605724269
485881785
209602513
89311649
370158306
408135887
231478334
581654726
343783363
843116645
231274388
494104261
756241598
854443084
386136092
28585454
902552878
616251403
12188862
804229537
722...

result:

ok 100 numbers

Test #31:

score: 0
Accepted
time: 51ms
memory: 3648kb

input:

100
5000 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

966059986
659969941
69297367
676916066
822397207
183192627
603828029
545146830
75696702
482906001
726389516
500396570
611439288
356896246
619796723
652747847
964946488
629066080
302351457
489292638
563991698
985628078
878681940
5463772
506947145
751650784
575018414
886036992
168045160
308406113
3458...

result:

ok 100 numbers

Test #32:

score: 0
Accepted
time: 75ms
memory: 4496kb

input:

10
50000 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

905817957
914829965
977989203
783840682
167471797
550374343
919268478
56110205
959507415
63940270

result:

ok 10 numbers

Test #33:

score: 0
Accepted
time: 67ms
memory: 4512kb

input:

10
50000 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

660855961
111548230
449216790
476859772
807124831
179416035
413283522
196117555
197948350
251627758

result:

ok 10 numbers

Test #34:

score: 0
Accepted
time: 67ms
memory: 4488kb

input:

10
50000 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

243705631
759051025
29943545
635763565
817326129
324551942
204288249
79568538
771991981
457797565

result:

ok 10 numbers

Test #35:

score: 0
Accepted
time: 117ms
memory: 17020kb

input:

1
500000 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

683332050

result:

ok 1 number(s): "683332050"

Test #36:

score: 0
Accepted
time: 133ms
memory: 16988kb

input:

1
500000 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

953899657

result:

ok 1 number(s): "953899657"

Test #37:

score: 0
Accepted
time: 130ms
memory: 16964kb

input:

1
500000 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

714078710

result:

ok 1 number(s): "714078710"

Test #38:

score: 0
Accepted
time: 49ms
memory: 3496kb

input:

1000
500 2
6 4 5 9 1 8 11 3 12 7 160 473 380 285 169 174 394 219 403 331 341 361 310 111 383 237 454 231 349 470 317 157 496 124 490 116 338 350 325 149 402 216 195 487 130 478 241 162 434 226 16 13 15 10 18 14 21 23 17 24 405 132 271 229 301 333 144 263 465 193 327 154 182 477 388 374 420 101 291 3...

output:

952446952
704224738
162190868
747859278
750999865
305895617
696132257
362446030
75938424
962687220
687944269
226978099
35749116
360682194
448335326
438282941
877885222
446743929
351952987
926646391
248342488
822573583
95973415
247967381
179478846
421203247
605431279
417008332
158818015
418367788
267...

result:

ok 1000 numbers

Test #39:

score: 0
Accepted
time: 46ms
memory: 3452kb

input:

1000
500 2
6 3 4 2 10 5 9 13 8 14 15 16 11 18 17 7 1 20 19 21 269 434 443 459 306 225 229 288 307 452 278 425 258 294 264 226 409 207 265 179 287 340 327 426 166 485 224 105 122 240 383 143 303 210 161 107 427 453 189 395 466 108 495 482 449 334 234 281 130 171 257 416 328 317 102 272 263 218 253 35...

output:

384389636
20150216
380272289
457561927
663390061
712572868
331169309
72363832
872944329
984701131
891298445
125625563
535862687
185631268
246253633
132897477
671362022
530130061
927029626
521691035
521237817
102209069
824463742
728357645
226720234
709258267
239207902
115905813
619037294
281244903
36...

result:

ok 1000 numbers

Test #40:

score: 0
Accepted
time: 46ms
memory: 3496kb

input:

1000
500 2
2 6 7 3 9 10 5 12 14 11 1 17 16 4 20 15 18 13 8 24 26 25 19 28 29 27 22 23 33 30 36 31 38 37 35 39 21 42 32 41 110 108 484 325 298 427 463 366 119 324 206 307 462 116 198 309 263 113 114 219 264 142 440 188 257 296 204 273 256 489 181 173 185 193 167 493 447 270 251 189 134 169 197 276 27...

output:

764376721
52420637
443763691
555729672
706085643
324333978
519199765
514209812
591613971
112737796
763172714
854556276
420497968
638336874
358918729
883773385
466662306
351448446
808649160
950879602
559456643
637167767
543277469
526414975
928753613
68177113
415059709
463730880
623603741
838167973
40...

result:

ok 1000 numbers

Test #41:

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

input:

100
5000 2
6 7 4 9 5 2 10 13 11 15 4200 1668 1431 4055 1787 4532 4111 1169 2431 4491 2709 4859 1821 3142 2408 1084 4098 4413 3209 4768 3849 3253 4782 2200 2914 3823 3363 2100 2554 3462 4930 1976 1225 2340 4890 2008 3682 4357 2792 4377 16 12 1 8 17 19 3 22 18 23 1448 4438 1079 4558 1309 2665 3476 485...

output:

547464370
424109895
45001915
859961235
253240921
346886706
908038238
930088850
936741112
962453019
887927785
44802613
202143827
433927228
166277322
305573997
521448440
450514563
680864399
882105809
685255210
471784509
141092878
298254702
302241543
604432859
953516663
514978063
314784155
832670768
22...

result:

ok 100 numbers

Test #42:

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

input:

100
5000 2
5 2 8 6 4 10 7 1 13 14 11 16 15 9 20 3 12 22 17 25 3112 4049 2675 4549 4337 3433 4749 3114 4650 4782 1163 3515 4102 3932 4233 1979 1357 3284 2132 3823 4976 4934 4561 4856 2799 2462 3788 4284 3687 1436 2234 3363 1814 2151 3640 4457 3790 4690 1976 1205 1147 2350 3386 4033 2039 2516 1396 309...

output:

180983707
743997620
773608695
850033102
444515473
444428990
824333098
966922163
638769388
582866987
976714803
396303389
930607222
463305864
126201923
730794284
428595895
305999993
337082162
873664862
921319779
681126391
388472416
337680732
448712836
625283697
56109216
426264971
281920475
772700224
7...

result:

ok 100 numbers

Test #43:

score: 0
Accepted
time: 55ms
memory: 3628kb

input:

100
5000 2
3 2 1 5 10 4 8 9 12 15 14 7 11 17 6 13 18 23 22 25 16 19 24 20 27 28 30 26 33 35 36 29 37 38 40 34 41 31 32 39 2502 2678 1716 1664 1654 3610 3504 1890 3225 1383 3969 3401 1679 4619 1050 3053 3231 3927 4116 3127 4464 2602 3907 3444 2163 2810 2264 4650 2691 1311 3257 1888 2085 3995 3896 270...

output:

87151678
509468947
620710195
959989939
623162707
687778679
477095742
581963182
420897501
398087599
792825484
685119730
160398092
528414129
314053761
984012641
960317580
19458880
586072202
124928086
329899081
689067983
784410125
834703441
569463965
229853439
96133298
133613692
849409864
327408837
528...

result:

ok 100 numbers

Test #44:

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

input:

100
5000 2
5 4 7 3 8 1 6 10 9 15 11 16 18 19 2 12 14 17 13 24 26 27 28 23 25 21 30 29 31 34 32 33 20 39 37 36 35 38 40 41 45 44 43 49 47 50 51 48 53 52 46 57 54 42 58 55 59 63 60 22 66 61 67 69 65 68 70 56 62 73 71 76 64 79 75 81 80 83 72 78 86 85 77 89 88 82 90 92 84 95 93 97 87 96 99 94 102 100 91...

output:

226155149
437140457
135938425
960367388
505682295
735669987
948948954
297557758
233918815
484753746
651659982
76980015
491028515
432617199
27075097
731819717
113016431
268455668
301322452
788174932
384553189
130820291
947613256
811287870
285846282
70203404
885582591
578100483
652767699
585181926
345...

result:

ok 100 numbers

Test #45:

score: 0
Accepted
time: 78ms
memory: 4784kb

input:

10
50000 2
3 2 7 4 9 6 10 8 11 5 47014 16173 18894 14834 21138 39955 37340 49140 35960 40493 30467 46471 18654 36592 10100 11586 35855 37042 43697 46003 14761 45643 11600 26370 18035 35281 34999 18230 45891 45054 33503 30224 40326 23752 23284 35528 23110 20391 48554 12483 15 17 1 16 18 21 12 22 23 2...

output:

521841384
46016458
403329086
759824570
87823090
865881782
244229785
5232225
214361865
574488339

result:

ok 10 numbers

Test #46:

score: 0
Accepted
time: 69ms
memory: 4784kb

input:

10
50000 2
5 6 2 7 10 1 11 9 14 13 15 4 3 18 8 12 17 16 23 20 36960 24295 40618 34404 38931 16175 17907 21630 13480 39528 26030 26831 30074 42104 30115 48871 36805 37337 49272 34273 49209 12533 11404 14014 47824 49713 49775 28460 33709 39727 48018 48688 40733 42752 30438 42159 13560 17623 41912 2167...

output:

785637078
876843486
210739043
155929972
73557416
284481246
928357558
561837516
748391649
969705739

result:

ok 10 numbers

Test #47:

score: 0
Accepted
time: 74ms
memory: 4760kb

input:

10
50000 2
4 7 2 5 9 10 8 11 1 6 14 3 15 12 19 20 13 18 16 25 22 17 27 23 29 31 30 21 34 33 26 32 24 38 35 36 39 37 40 28 43295 29540 24585 44629 26406 20799 33611 20095 41779 21345 17212 43610 31656 12391 49127 14843 20727 30508 20655 32863 40547 16979 46525 17364 48237 18885 20237 32654 30171 3810...

output:

97951263
956075729
273425037
132473549
8781204
354301125
840766776
404234489
588157519
524932176

result:

ok 10 numbers

Test #48:

score: 0
Accepted
time: 79ms
memory: 4752kb

input:

10
50000 2
6 1 8 7 5 2 9 3 14 11 10 17 16 18 4 19 22 12 23 24 21 20 15 28 27 26 30 32 25 35 31 29 37 38 40 36 42 43 33 39 46 34 48 41 49 45 52 50 13 51 54 56 57 55 53 44 47 63 62 59 58 61 64 60 65 67 70 72 69 66 74 76 78 75 68 79 81 83 82 85 71 77 84 88 73 86 80 87 91 89 94 96 93 98 97 95 101 99 92 ...

output:

505943100
737780979
767502794
396284653
808745682
801913744
600575027
122455192
452709938
277620141

result:

ok 10 numbers

Test #49:

score: 0
Accepted
time: 77ms
memory: 4768kb

input:

10
50000 2
6 5 3 1 2 9 7 12 4 10 13 16 14 17 11 20 8 18 15 19 24 23 27 28 29 30 32 26 22 35 25 31 33 34 21 39 41 36 40 37 38 43 48 46 44 50 49 52 47 55 45 56 51 58 53 54 62 60 64 42 66 61 65 69 59 71 67 63 74 73 75 76 70 72 57 81 68 83 82 80 79 84 87 78 89 91 88 92 94 86 77 85 95 90 93 97 98 101 96 ...

output:

853138458
155069549
146561775
708727905
6680973
209914545
403405137
15475200
45265080
553106349

result:

ok 10 numbers

Test #50:

score: 0
Accepted
time: 78ms
memory: 4828kb

input:

10
50000 2
6 3 2 7 5 8 12 11 13 9 15 17 4 16 18 21 20 10 22 1 25 19 14 27 30 26 32 24 23 29 36 37 38 28 35 34 39 43 33 41 31 44 40 42 45 50 46 48 54 55 47 51 56 57 60 52 62 61 64 49 53 67 65 69 63 58 68 70 59 75 71 74 66 76 80 79 72 78 83 73 82 85 88 77 87 86 90 84 92 89 81 96 97 91 100 95 102 94 99...

output:

991101486
436342316
433639479
830709197
672145954
857785116
742820865
746471225
927204138
252302753

result:

ok 10 numbers

Test #51:

score: 0
Accepted
time: 114ms
memory: 15456kb

input:

1
500000 2
1 3 348982 178612 212446 411573 212496 289530 108284 114663 7 4 480236 359156 146415 446342 293599 314613 281378 171186 8 6 424143 389824 223756 287724 236239 175827 475836 175942 12 11 454161 184830 205675 422104 323571 394566 222939 249322 2 14 355304 427784 175395 227860 369983 422253 ...

output:

597920511

result:

ok 1 number(s): "597920511"

Test #52:

score: 0
Accepted
time: 119ms
memory: 15748kb

input:

1
500000 2
6 1 5 8 2 11 10 9 4 7 186677 472010 141709 209894 180811 386253 484326 277050 434947 371446 451195 404837 269352 357665 443461 383235 256838 203889 438524 286376 276854 312338 372936 108538 350220 244341 122214 313843 423594 228462 235370 192655 416294 327781 102897 265348 350683 141847 3...

output:

550625977

result:

ok 1 number(s): "550625977"

Test #53:

score: 0
Accepted
time: 129ms
memory: 16260kb

input:

1
500000 2
2 6 8 4 1 11 5 9 14 3 15 7 10 12 19 17 18 22 13 23 392536 311664 470935 338154 106278 127071 328426 109587 100561 490866 118112 220604 472759 459456 355599 305105 454770 342825 285557 378013 433528 281287 493170 437707 398467 196917 380219 466265 277251 453200 409544 450906 343786 196541 ...

output:

100704267

result:

ok 1 number(s): "100704267"

Test #54:

score: 0
Accepted
time: 133ms
memory: 16276kb

input:

1
500000 2
1 4 7 5 2 11 6 10 14 3 8 13 16 18 20 12 15 21 24 23 17 27 26 29 28 19 31 32 33 25 9 22 36 37 40 34 39 42 35 41 407676 380104 111988 120067 157450 418314 433708 342353 448270 278774 421185 497915 334811 455092 126728 354995 214619 232743 271332 429110 436437 191785 131516 339112 461719 154...

output:

389157720

result:

ok 1 number(s): "389157720"

Test #55:

score: 0
Accepted
time: 115ms
memory: 16204kb

input:

1
500000 2
5 3 6 9 1 2 4 8 11 14 13 16 10 15 18 12 17 22 21 23 25 27 26 24 29 7 28 19 32 31 36 34 38 39 30 40 37 20 42 33 41 47 35 48 44 45 43 46 52 49 53 50 58 57 51 55 56 60 62 63 64 54 65 67 69 66 71 73 74 75 72 70 76 68 61 77 59 83 79 80 84 82 81 86 87 90 92 89 93 88 85 91 98 96 78 99 101 94 104...

output:

13723772

result:

ok 1 number(s): "13723772"

Test #56:

score: 0
Accepted
time: 136ms
memory: 16280kb

input:

1
500000 2
2 5 8 9 10 7 3 1 4 13 14 17 6 18 19 21 15 12 11 25 16 27 24 22 23 29 31 32 26 33 36 30 35 38 28 37 41 39 40 44 20 45 34 47 48 43 42 51 46 49 52 53 58 59 54 60 50 63 62 56 66 55 61 57 65 68 72 69 64 74 71 70 78 77 79 75 76 83 82 85 80 84 67 81 87 73 92 88 86 93 89 91 97 96 94 95 98 100 90 ...

output:

16162549

result:

ok 1 number(s): "16162549"

Test #57:

score: 0
Accepted
time: 119ms
memory: 15732kb

input:

1
500000 2
4 1 3 6 8 5 10 13 12 15 7 11 9 16 19 20 22 21 18 24 14 27 25 26 23 17 31 30 2 29 36 32 34 39 40 41 35 43 38 45 44 37 33 48 46 51 50 53 28 49 54 56 42 52 55 47 58 59 63 64 60 61 62 69 67 57 71 66 73 70 76 75 72 78 77 65 81 80 84 68 79 74 88 89 82 90 86 87 91 83 85 94 97 93 98 100 102 96 10...

output:

41958973

result:

ok 1 number(s): "41958973"

Test #58:

score: 0
Accepted
time: 68ms
memory: 4772kb

input:

10
50000 3
6 8 3 10 11 15 13 21831 11469 9165 39140 28917 20351 42585 42661 10973 49541 11291 33934 39884 38174 32695 13839 8702 33489 27235 30662 49949 25433 9970 43526 37374 37751 39212 48447 31521 35457 32362 24360 33412 39350 44186 34652 26228 45578 13037 42127 35663 33376 32154 17 19 22 23 26 2...

output:

170457619
649034589
664282431
851214755
267815576
139761510
359678644
564982530
708147613
465094936

result:

ok 10 numbers

Test #59:

score: 0
Accepted
time: 68ms
memory: 4656kb

input:

10
50000 2
2 7 5 4 13 8 14 10 19 20 24 27 33 26 30 32 42 45 22 44 18185 44567 38051 26452 34193 48394 12754 43174 48589 14319 43992 24007 44976 48536 43093 17335 47923 25595 26346 18408 42029 12559 22297 15526 45647 16571 13807 28155 32056 20868 41980 36218 24245 34001 12847 17330 41138 47683 22416 ...

output:

473802798
668546385
984031669
231959318
574181986
147977518
896988786
773321046
56679363
788671071

result:

ok 10 numbers

Test #60:

score: 0
Accepted
time: 67ms
memory: 4580kb

input:

10
50000 2
6 7 9 4 3 13 12 2 18 14 16 17 22 28 23 30 31 32 20 35 41 48 37 44 51 50 54 57 55 58 61 60 67 66 69 68 65 71 77 74 17469 12055 25481 30510 18881 17635 45343 26418 47486 28123 20423 16169 25748 24360 38384 29721 20788 40533 29856 20195 41272 46079 29743 33690 31300 36911 28896 11613 25331 4...

output:

450065203
966099404
889228348
196226488
548942997
425608307
491705053
377897477
206948246
187124496

result:

ok 10 numbers

Test #61:

score: 0
Accepted
time: 64ms
memory: 4636kb

input:

10
50000 4
7 5 3 9 13 17 8 22 21 29 31 26 35 34 23 41 45 44 43 36 18 49 54 53 57 58 60 63 52 67 71 64 79 51 82 80 87 76 83 85 93 97 91 98 99 104 103 101 108 110 113 100 106 107 117 116 109 121 122 126 132 134 133 131 139 140 141 136 144 143 137 128 142 145 149 148 135 161 164 168 165 169 179 159 181...

output:

341131077
418140694
672220077
34032154
43426887
256578284
984094503
388138521
752907077
264643081

result:

ok 10 numbers

Test #62:

score: 0
Accepted
time: 66ms
memory: 4628kb

input:

10
50000 4
5 1 4 8 15 6 7 18 19 21 20 27 29 23 32 24 34 37 39 31 38 44 35 43 45 48 60 55 62 63 58 53 59 70 64 67 75 77 76 78 68 88 92 81 94 102 97 104 110 108 112 113 106 99 118 121 117 120 123 126 125 129 132 133 124 130 142 144 143 139 145 148 140 146 151 134 157 159 154 164 136 163 166 167 161 17...

output:

245477175
808456306
952576468
659011750
108017960
290885541
550849597
434506685
277319115
901798393

result:

ok 10 numbers

Test #63:

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

input:

10
50000 2
6 1 3 8 5 13 15 16 10 2 20 7 22 31 30 35 32 38 36 27 45 44 46 42 41 50 51 43 47 55 57 59 56 62 63 49 65 64 71 61 60 74 75 79 76 77 83 81 69 78 85 91 89 92 96 97 94 98 102 99 103 108 105 112 111 101 113 116 119 125 122 115 127 130 136 126 123 133 137 147 148 150 141 154 153 145 152 162 139...

output:

401523383
62183858
49638261
508596658
274782193
213036375
931280871
640726484
786871404
865735294

result:

ok 10 numbers

Test #64:

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

input:

1
500000 3
5 2 4 1 12 17 15 193656 240577 243146 211881 324013 199530 448053 463995 457776 412660 471888 85830 254138 379423 372129 478601 189217 99732 194127 199866 464433 475979 416211 184128 244748 482995 218835 156157 413458 238336 479323 241325 99036 191324 476492 162466 192048 287944 123084 21...

output:

612273610

result:

ok 1 number(s): "612273610"

Test #65:

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

input:

1
500000 4
3 2 1 11 13 12 20 16 28 22 21 128249 446685 109476 247595 159900 130555 135137 221521 430336 249952 214627 243692 296232 160184 148602 174550 339672 425619 286917 196357 200674 330267 211979 90377 425778 417097 412168 214342 391758 198590 136080 495770 107687 304289 220876 476049 271449 1...

output:

343831310

result:

ok 1 number(s): "343831310"

Test #66:

score: 0
Accepted
time: 109ms
memory: 13540kb

input:

1
500000 3
6 10 13 16 9 19 18 21 23 22 30 27 29 42 41 49 46 50 58 56 59 43 63 47 66 70 75 78 189083 262666 118978 118280 295968 186739 445916 260706 438907 266141 341545 495891 350495 117144 91968 329819 221993 463231 73879 301969 86989 464487 195344 300789 179294 76026 182128 161985 323210 373973 3...

output:

125491750

result:

ok 1 number(s): "125491750"

Test #67:

score: 0
Accepted
time: 93ms
memory: 13320kb

input:

1
500000 3
3 7 12 11 13 1 15 6 16 17 21 23 27 20 29 24 35 38 39 40 37 41 46 43 52 50 22 49 58 59 54 62 57 64 61 68 69 66 71 74 72 78 73 80 83 85 90 84 91 92 86 101 96 98 100 107 109 108 111 114 115 116 118 122 126 125 128 130 99 136 119 144 138 141 147 148 153 154 158 151 162 149 163 161 169 170 165...

output:

249023973

result:

ok 1 number(s): "249023973"

Test #68:

score: 0
Accepted
time: 98ms
memory: 14340kb

input:

1
500000 2
3 9 8 15 13 6 17 12 24 23 22 1 32 25 29 35 33 36 39 30 42 43 45 47 40 38 41 53 46 44 55 56 62 60 51 66 59 71 74 75 77 79 82 81 69 83 86 88 73 89 92 93 95 91 94 96 97 101 98 106 99 107 111 103 112 120 119 123 117 125 124 126 130 131 133 110 127 136 134 141 145 148 144 147 155 151 158 157 1...

output:

247731847

result:

ok 1 number(s): "247731847"

Test #69:

score: 0
Accepted
time: 83ms
memory: 12528kb

input:

1
500000 4
7 10 8 11 19 21 23 27 28 33 25 36 30 38 40 46 37 49 56 54 55 59 65 57 67 70 76 77 78 80 82 85 81 91 94 98 102 106 104 107 109 97 96 114 117 115 122 125 127 118 129 119 133 135 131 130 137 140 146 136 147 142 149 138 156 154 157 153 160 162 164 169 158 175 170 176 178 174 180 184 187 189 1...

output:

988660401

result:

ok 1 number(s): "988660401"

Test #70:

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

input:

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

output:

1
18
1
12
1
1
12
1
1
1
1
1
18
1
24
1
1
1
24
1
12
1
24
18
1
1
1
1
12
1
1
1
24
1
1
12
1
1
1
1
1
1
24
1
1
18
1
1
1
12
24
1
1
1
24
24
1
1
1
1
1
1
12
1
1
18
24
1
1
24
18
12
1
1
1
12
1
1
18
18
1
12
1
12
18
12
24
1
1
1
1
24
1
24
18
1
1
1
12
1
1
1
18
24
1
1
1
1
1
1
18
18
24
1
1
1
1
1
12
18
18
12
18
1
1
12
2...

result:

ok 100000 numbers

Test #71:

score: 0
Accepted
time: 49ms
memory: 3520kb

input:

100000
5 356508
1 2 3 4 5
5 351279
1 2 3 4 5
5 263195
1 2 3 4 5
5 116927
1 2 3 4 5
5 53092
1 2 3 4 5
5 145017
1 2 3 4 5
5 248835
1 2 3 4 5
5 207354
1 2 3 4 5
5 163352
1 2 3 4 5
5 281720
1 2 3 4 5
5 273055
1 2 3 4 5
5 260600
1 2 3 4 5
5 439126
1 2 3 4 5
5 271091
1 2 3 4 5
5 22989
1 2 3 4 5
5 434909
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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 100000 numbers

Test #72:

score: 0
Accepted
time: 27ms
memory: 3900kb

input:

10
50000 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

19487265
319849169
206352701
244468465
206352701
976077313
244468465
336576864
976908914
244468465

result:

ok 10 numbers

Test #73:

score: 0
Accepted
time: 81ms
memory: 7328kb

input:

10
50000 176032
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

1
1
1
1
1
1
1
887542511
1
1

result:

ok 10 numbers

Test #74:

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

input:

1
500000 6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

222193066

result:

ok 1 number(s): "222193066"

Test #75:

score: 0
Accepted
time: 18ms
memory: 10944kb

input:

1
500000 176481
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

output:

22402577

result:

ok 1 number(s): "22402577"