QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#311414#7795. 茧zyc070419100 ✓381ms24808kbC++147.5kb2024-01-22 12:36:152024-01-22 12:36:15

Judging History

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

  • [2024-01-22 12:36:15]
  • 评测
  • 测评结果:100
  • 用时:381ms
  • 内存:24808kb
  • [2024-01-22 12:36:15]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 3;
const ll MX = (1ll << 60);

inline int read() {
	char ch = getchar(); int x = 0;
	while (!isdigit(ch)) {ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	return x;
}

inline ll Read() {
	char ch = getchar(); ll x = 0;
	while (!isdigit(ch)) {ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	return x;
}

ll mx;
int T, n, k, sum;
vector<ll> vec[N];
bool tag = true;

namespace subtask1 {
	bool check() {return k == 1;}
	
	void solve() {
		ll res;
		for (int qwq = 1; qwq <= T; ++qwq) {
			res = 0;
			for (auto x : vec[qwq]) {
				if (x % 2 == 0) {
					res ^= x;
					if (x % 4) res ^= 1;
				}
				else if ((x + 1) % 4) res ^= 1;
			}
			puts(res ? "Lily" : "Kaguya");
		}
	}
}

namespace subtask2 {
	const int M = (1 << 22) - 1;
	const int W = (1 << 22) + 3;
	
	int a[W];
	
	inline bool check() {return mx <= M;}
	
	inline void solve() {
		a[0] = 0; int lst = 0, x;
		for (int i = 1;; ++i) {
			x = 1;
			for (int j = 1; j <= k; ++j) x *= i;
			for (int j = lst + 1 ; j < x && j <= M; ++j) a[j] = a[j - i];
			if (x <= M) a[lst = x] = i;
			else break;
		}
		for (int i = 1; i <= M; ++i) a[i] ^= a[i - 1];
		int res;
		for (int qwq = 1; qwq <= T; ++qwq) {
			res = 0;
			for (auto x : vec[qwq]) res ^= a[x];
			puts(res ? "Lily" : "Kaguya");
		}
	}
}

namespace subtask3 {
	const int M = (1 << 18) - 1;
	const int W = (1 << 18) + 3;
	
	vector<ll> pw;
	int a[W];
	
	inline bool check() {return tag && mx < (1ll << 32) && sum <= 1000;}
	
	inline int calc(ll x) {
		if (x <= M) return a[x];
		if (x == 2) {
			int pos = sqrt(x); ll y = 1ll * pos * pos;
			if (x == y) return pos;
			else return calc((x - y) % (pos + 1) + y);
		}
		int pos = upper_bound(pw.begin(), pw.end(), x) - pw.begin() - 1;
		ll y = (x - pw[pos]) % (pos + 1) + pw[pos];
		if (y == pw[pos]) return pos;
		return calc(y - pos - 1);
	}
	
	void solve() {
		a[0] = 0; int lst = 0;
		for (int i = 1, x;; ++i) {
			x = 1;
			for (int j = 1; j <= k; ++j) x *= i;
			for (int j = lst + 1 ; j < x && j <= M; ++j) a[j] = a[j - i];
			if (x <= M) a[lst = x] = i;
			else break;
		}
		int res;
		for (int i = 0;; ++i) {
			ll x = 1;
			for (int j = 1; j <= k; ++j) x = min(x * i, mx + 1);
			if (x > mx) break;
			pw.push_back(x);
		}
		for (int qwq = 1; qwq <= T; ++qwq) {
			res = 0;
			for (int i = 1; i < vec[qwq].size(); i += 2) res ^= calc(vec[qwq][i]);
			puts(res ? "Lily" : "Kaguya");
		}
	}
}

namespace subtask4 {
	inline bool check() {return k == 2 && tag;}
	
	int work(int x, int y) {
		if (x & 1) return work(y - x / 2 - 1, y - x / 2 - 1);
		else return y - x / 2;
	}
	
	inline int calc(ll x) {
		int pos = sqrt(x);
		while (1ll * pos * pos > x) pos--;
		while (1ll * (pos + 1) * (pos + 1) <= x) pos++;
		x = (x - 1ll * pos * pos) % (pos + 1);
		return work(x, pos);
	}
	
	void solve() {
		int res = 0;
		for (int qwq = 1; qwq <= T; ++qwq) {
			res = 0;
			for (int i = 1; i < vec[qwq].size(); i += 2) res ^= calc(vec[qwq][i]);
			puts(res ? "Lily" : "Kaguya");
		}
	}
}

namespace subtask5 {
	vector<ll> pw;
	
	inline bool check() {return k == 3 && tag;}
	
	inline int calc(ll x) {
		int pos = upper_bound(pw.begin(), pw.end(), x) - pw.begin() - 1;
		return (x - pw[pos] + pos) % (pos + 1);
	}
	
	void solve() {
		pw.push_back(0);
		for (int i = 1;; ++i) {
			ll x = 1;
			for (int j = 1; j <= k; ++j) {
				if ((mx + 1) / i <= x) x = mx + 1;
				else x *= i;
			}
			if (x > mx) break;
			pw.push_back(x);
		}
		int res = 0;
		for (int qwq = 1; qwq <= T; ++qwq) {
			res = 0;
			for (int i = 1; i < vec[qwq].size(); i += 2) res ^= calc(vec[qwq][i]);
			puts(res ? "Lily" : "Kaguya");
		}
	}
}

namespace subtask6 {
	vector<ll> pw;
	
	inline bool check() {return !(k & 1);}
	int work(int x, int y) {
		if (x & 1) return work(y - x / 2 - 1, y - x / 2 - 1);
		else return y - x / 2;
	}
	inline int get_pos(ll x) {
		if (k == 2) {
			int pos = sqrt(x);
			while (1ll * pos * pos > x) pos--;
			while (1ll * (pos + 1) * (pos + 1) <= x) pos++;
			return pos;
		}else {
			int pos = upper_bound(pw.begin(), pw.end(), x) - pw.begin() - 1;
			return pos;
		}
	}
	inline int sum(int x) {
		if ((x & 3) == 0) return x;
		else if ((x & 3) == 2) return x ^ 1;
		else if ((x & 3) == 1) return 1;
		else return 0;
	}
	inline int calc(int x) {
		if (x <= 0) return 0;
		if (x & 1) return calc(x + 1) ^ ((x + 1) / 2);
		return sum(x / 2) ^ calc(x / 2 - 1);
	}
	
	void solve() {
		if (k > 2) {
			pw.push_back(0);
			for (int i = 1;; ++i) {
				ll x = 1;
				for (int j = 1; j <= k; ++j) {
					if ((mx + 1) / i <= x) x = mx + 1;
					else x *= i;
				}
				if (x > mx) break;
				pw.push_back(x);
			}
		}
		int res;
		for (int qwq = 1; qwq <= T; ++qwq) {
			res = 0;
			for (auto x : vec[qwq]) {
				if (x == 0) continue;
				int pos = get_pos(x);
				res ^= calc(pos - 1);
				ll y = 1ll;
				for (int j = 1; j <= k; ++j) y *= pos;
				ll z = x - y;
				z %= ((pos + 1) << 1);
				x = y + z;
				if (x - y <= pos) res ^= calc(pos + pos) ^ calc(pos + pos - (x - y) - 1);
				else res ^= calc(pos + pos - (x - y - pos)) ^ calc(pos - 1);
			}
			puts(res ? "Lily" : "Kaguya");
		}
	}
}

namespace subtask7 {
	ll pre[(1 << 15) + 3];
	vector<ll> pw;
	
	inline bool check() {return k & 1;}
	inline int get_pos(ll x) {
		int pos = upper_bound(pw.begin(), pw.end(), x) - pw.begin() - 1;
		return pos;
	}
	inline int sum(int x) {
		if ((x & 3) == 0) return x;
		else if ((x & 3) == 2) return x ^ 1;
		else if ((x & 3) == 1) return 1;
		else return 0;
	}
	inline int calc(int x) {
		if (k == 3) {
			int res = sum(x);
			if (((x / 4) & 1) ^ ((x & 3) >= 1)) res ^= 1;
			return res;
		}else {
			return pre[x];
		}
	}
	
	void solve() {
		pw.push_back(0);
		for (int i = 1;; ++i) {
			ll x = 1;
			for (int j = 1; j <= k; ++j) {
				if ((mx + 1) / i <= x) x = mx + 1;
				else x *= i;
			}
			if (x > mx) break;
			pw.push_back(x);
		}
		if (k == 5) {
			for (int i = 1; i < pw.size(); ++i) {
				pre[i] = pre[i - 1] ^ i;
				ll len = pw[i + 1] - pw[i];
				if (((len - 1) / (i + 1)) & 1) pre[i] ^= sum(i);
			}
		}
		
		int res;
		for (int qwq = 1; qwq <= T; ++qwq) {
			res = 0;
			for (auto x : vec[qwq]) {
				if (x == 0) continue;
				int pos = get_pos(x);
				res ^= calc(pos - 1) ^ pos;
				ll y = 1ll;
				for (int j = 1; j <= k; ++j) y *= pos;
				y = x - y;
				if (y) {
					if (((y - 1) / (pos + 1)) & 1) {
						y = (y - 1) % (pos + 1);
						res ^= sum(pos) ^ sum(y);
					}else {
						y = (y - 1) % (pos + 1);
						res ^= sum(y);
					}
				}
			}
			puts(res ? "Lily" : "Kaguya");
		}
	}
}

int main() {
	T = read(); k = read(); ll x;
	for (int i = 1; i <= T; ++i) {
		n = read(); sum += n; tag &= (n % 2 == 0);
		while (n--) x = Read(), vec[i].push_back(x), mx = max(mx, x);
		if (tag) for (int j = 0; j < vec[i].size(); j += 2) tag &= (vec[i][j] + 1 == vec[i][j + 1]);
	}
	
//	subtask7 :: solve(); exit(0);
	
	if (subtask1 :: check()) subtask1 :: solve();
	else if (subtask2 :: check()) subtask2 :: solve();
	else if (subtask3 :: check()) subtask3 :: solve();
	else if (subtask4 :: check()) subtask4 :: solve();
	else if (subtask5 :: check()) subtask5 :: solve();
	else if (subtask6 :: check()) subtask6 :: solve();
	else if (subtask7 :: check()) subtask7 :: solve();
	return 0;
}
/*
1 3
5
7 10 18 3 25 
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 8ms
memory: 10172kb

input:

1136 1
1
113619249930092995
2
457093394163961514 36523281
2
52273 586907144813890981
149
13412372218 128311326 618178541606515600 756479282467845696 276251850291230545 978441742104676009 1035439042005099 1105099328508110145 981121546786695466 97032240925148816 171 149766413231751232 28137602525069 9...

output:

Kaguya
Lily
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Lily
Lily
Lily
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Lily
L...

result:

ok 1136 tokens

Subtask #2:

score: 5
Accepted

Test #2:

score: 5
Accepted
time: 8ms
memory: 23560kb

input:

9868 2
6
45196 27174 14224 5578 40059 47649
8
38740 7 56634 37760 43117 57202 349 102
7
47 498 25922 50544 13 48434 12
11
59314 45 4091 47301 3701 38642 253 11 48627 30158 36
4
1209 43050 22162 22239
12
5 64446 660 18577 46228 48927 6 47617 55178 30917 45801 8
8
60993 148 109 37947 19683 2613 3278 1...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
...

result:

ok 9868 tokens

Test #3:

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

input:

14255 3
2
25431 1431
9
6455 6976 25699 5 64472 6603 40 38 14
16
55580 48907 4456 10524 42216 47 63931 63762 53439 26656 34 44195 2043 8761 27558 36
20
44674 37691 48056 15873 52517 57044 5922 61629 15692 3 62877 10974 6 4507 23119 34595 23 2717 58541 1857
1
45217
8
61934 53794 1102 50 40833 35001 37...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Kagu...

result:

ok 14255 tokens

Test #4:

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

input:

22059 4
3
16 134 1
5
46554 7709 268 4 36331
6
19728 61853 17949 7 4855 38920
2
1 35389
2
15749 41751
5
32063 47259 1078 56138 16362
3
2009 4599 23517
4
33 200 3038 15556
2
1 401
2
3245 65166
3
21532 2478 25347
2
2809 10699
6
25271 2005 43749 9 5 41206
2
30434 87
6
47897 478 1684 174 14290 961
3
3387...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya...

result:

ok 22059 tokens

Test #5:

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

input:

22872 5
5
2 37314 15910 93 7338
5
26212 55591 69 1857 8051
2
31713 2
2
2135 2118
3
13642 2034 59512
1
217
7
55365 2284 1 24506 33610 57519 10075
1
433
3
59 52 1572
7
10554 65 3 7622 24964 11 25621
10
39719 29778 48994 182 42292 48025 4070 59304 58958 4186
2
28524 2
1
27728
8
29032 28789 1 178 766 34...

output:

Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Lily
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Ka...

result:

ok 22872 tokens

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #6:

score: 10
Accepted
time: 8ms
memory: 23540kb

input:

6839 2
17
224984 2 833273 2067770 338355 901894 1679997 133482 3910338 204 66192 1011364 37 128 20 949106 1195015
15
634678 297242 115 1061781 996944 4 427042 1212821 6175 84 289 2568587 5500 1496533 3581457
6
281854 3131119 1496695 10164 133 3317
15
34562 74 3521796 863475 3344736 453013 23 1994270...

output:

Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Lily
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Ka...

result:

ok 6839 tokens

Test #7:

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

input:

10017 3
6
568016 487338 4070627 27 3859427 4384
1
789275
2
167 51
2
11869 1
19
2378345 44494 705262 2061753 3131409 2 2 2332606 1935304 3056056 502475 3876757 332052 3101503 813 1493744 4260 387489 82859
3
205205 16529 4125531
29
40208 1766700 397131 1152394 103926 2 163083 4 3909408 3553066 3998082...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Lily
...

result:

ok 10017 tokens

Test #8:

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

input:

13927 4
7
92 3883763 88110 2 2313854 108102 41129
2
5 25334
8
1528214 1137 2505858 2387 2253451 1563671 2743087 225373
5
1156685 532264 2373059 2126678 3240826
9
111625 2389 247 3992621 4448 128613 2920953 1099070 103458
21
3390 20 19816 24729 3793052 3365319 3712556 2547516 2 1742810 503602 1 94909...

output:

Lily
Kaguya
Lily
Lily
Lily
Kaguya
Kaguya
Lily
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kagu...

result:

ok 13927 tokens

Test #9:

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

input:

18003 5
2
833877 1803069
1
4
1
4446
17
12612 1756224 233 315585 47983 1432 967831 1176615 2465654 53241 188 55972 4793 3896048 3795886 805349 2441141
7
1408978 22493 2312 489 1406745 428988 596505
3
142741 3467 3243
7
903354 3 6253 1616 3836996 340 3949022
1
4087622
9
1 1175749 3811867 419872 415396...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguy...

result:

ok 18003 tokens

Subtask #4:

score: 10
Accepted

Test #10:

score: 10
Accepted
time: 381ms
memory: 9216kb

input:

500 2
2
37980539 37980540
2
193 194
2
643 644
2
3409676912 3409676913
2
537559 537560
2
374273640 374273641
2
7 8
2
3795849784 3795849785
2
79614 79615
2
3438078922 3438078923
2
3757510845 3757510846
2
1 2
2
1824633835 1824633836
2
1 2
2
55 56
2
714486861 714486862
2
2772062264 2772062265
2
14788368...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
...

result:

ok 500 tokens

Test #11:

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

input:

500 3
2
1321906355 1321906356
2
72 73
2
3261 3262
2
3 4
2
233038343 233038344
2
48806099 48806100
2
3093435489 3093435490
2
1 2
2
2529852032 2529852033
2
2448664571 2448664572
2
116570 116571
2
3544932649 3544932650
2
1982289066 1982289067
2
8 9
2
1714949081 1714949082
2
1850902999 1850903000
2
5 6
...

output:

Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Lily
Kaguya
Ka...

result:

ok 500 tokens

Subtask #5:

score: 10
Accepted

Dependency #4:

100%
Accepted

Test #12:

score: 10
Accepted
time: 335ms
memory: 8608kb

input:

25 2
40
32765 32766 3342432694 3342432695 2317586775 2317586776 36296128 36296129 2133632147 2133632148 58935 58936 1544281865 1544281866 1239424 1239425 3030161418 3030161419 2830847513 2830847514 2882661816 2882661817 145 146 3989168095 3989168096 1 2 1412485952 1412485953 10 11 76543 76544 14 15 ...

output:

Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily

result:

ok 25 tokens

Test #13:

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

input:

35 3
32
1585 1586 2824220127 2824220128 182367 182368 95651 95652 3017855765 3017855766 3106581274 3106581275 4175145930 4175145931 2865392917 2865392918 1378354252 1378354253 1 2 1663486 1663487 514671652 514671653 19239538 19239539 1220903525 1220903526 165580067 165580068 2580936259 2580936260
16...

output:

Kaguya
Lily
Lily
Lily
Kaguya
Lily
Lily
Kaguya
Kaguya
Lily
Kaguya
Lily
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily

result:

ok 35 tokens

Test #14:

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

input:

48 4
18
1627586260 1627586261 3764325828 3764325829 170192371 170192372 45382517 45382518 102 103 1403365777 1403365778 2557811780 2557811781 3482286328 3482286329 800725091 800725092
4
1287 1288 99908839 99908840
28
45571035 45571036 79454079 79454080 3135714078 3135714079 447320 447321 45021423 45...

output:

Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Lily
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Lily
Kaguya
Lily
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily...

result:

ok 48 tokens

Test #15:

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

input:

64 5
16
312749448 312749449 127844147 127844148 908 909 1388166519 1388166520 763091843 763091844 31689 31690 3195751097 3195751098 636493 636494
18
3668366738 3668366739 4194828724 4194828725 3454154942 3454154943 2772368000 2772368001 3729985934 3729985935 3522718179 3522718180 2679204187 26792041...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Lily
Lily
Kag...

result:

ok 64 tokens

Subtask #6:

score: 10
Accepted

Test #16:

score: 10
Accepted
time: 8ms
memory: 10180kb

input:

1169 2
98
2052761 2052762 861925831649843897 861925831649843898 1031265876706940814 1031265876706940815 617144630657193626 617144630657193627 72 73 138103 138104 156743812713553 156743812713554 205151719721047118 205151719721047119 1065302803446555430 1065302803446555431 1545284063203 1545284063204 ...

output:

Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Lily
Lily
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Lily
Kaguya
Lily
Lily
Lily
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguy...

result:

ok 1169 tokens

Subtask #7:

score: 10
Accepted

Test #17:

score: 10
Accepted
time: 26ms
memory: 18480kb

input:

1775 3
56
1113086767934729403 1113086767934729404 395289496182979739 395289496182979740 1036610723921853591 1036610723921853592 273906 273907 1081906643487536771 1081906643487536772 442413497681636481 442413497681636482 13354476004 13354476005 477736247131002 477736247131003 6159425067 6159425068 5 ...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya...

result:

ok 1775 tokens

Subtask #8:

score: 10
Accepted

Test #18:

score: 10
Accepted
time: 2ms
memory: 8700kb

input:

47 2
15
226 33559 101516630 2758718 1497465096 143 10221 19229493 2 19317677 2599390763 2043194 462237450 4045936184 209655973
24
1951804242 97 1448079073 419079478 1033169500 1875 2482 2350383606 16 3958107653 2574141589 2934502110 2036 2574986227 1794970348 4009429601 2844472951 155702147 18791465...

output:

Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
K...

result:

ok 47 tokens

Subtask #9:

score: 10
Accepted

Test #19:

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

input:

71 3
20
1902494844 129105842 1836429008 2862717739 3767166853 2686186537 1099034 40 344827 734438640 2231265370 2818449793 114955743 540338925 553099374 9179 2122555208 580 371 1909359957
30
18 2762110981 262509769 2811288568 3618225103 47784509 255418873 4040384827 159350 87784115 1619856413 8813 1...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kag...

result:

ok 71 tokens

Subtask #10:

score: 20
Accepted

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Dependency #7:

100%
Accepted

Dependency #8:

100%
Accepted

Dependency #9:

100%
Accepted

Test #20:

score: 20
Accepted
time: 3ms
memory: 9060kb

input:

1154 1
1
1009014346344200323
131
18594 215077590 727042719455267674 138750 942932193271109771 245305663172709684 170009236000516854 253 470657953795280202 5040950807414 151962329969739264 166619740 316182164577658906 534287180570561646 300290472604123736 789059311357964070 729624426928674252 5749620...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Lily
Kaguya
Kaguya
Lily
Lily
Lily
Kaguya
Kaguya
Kaguya
Lily
Kagu...

result:

ok 1154 tokens

Test #21:

score: 0
Accepted
time: 36ms
memory: 9976kb

input:

2308 2
40
3756353460062 50159562215017064 8177271 7394860535 1116013837541874047 729913293883678135 377625489605 10540910 330744315971420 1472626160 204413336865 34037465770682240 1096201987486951862 1395457 539796 121997358587 307099070449740551 384079286740760339 330434733993460264 647629950522098...

output:

Lily
Kaguya
Kaguya
Lily
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Lily
Lily
Kaguya
Lily
Lily
Kaguya
Lily
Lily
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Lily
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
K...

result:

ok 2308 tokens

Test #22:

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

input:

3498 3
2
744730718447771495 1
40
1537 913635853495520547 123387819752362188 1216 35 76249034629137797 56356173146555751 20018313908 43050 469256949814945769 713125440238497379 369397951410593610 192844159025632498 782022413460584552 331815486727526080 109941434625766410 3200 228 346162210479510953 1...

output:

Kaguya
Lily
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Li...

result:

ok 3498 tokens

Test #23:

score: 0
Accepted
time: 28ms
memory: 8692kb

input:

4881 4
24
413133061115 509053854990047150 24279056137926488 940893960096857756 54548814689 5202592 257891432611570473 401884386470886343 419563816802462834 1137778298587763343 1078968329392034122 1498265464 3191773527189574 199527093915285195 1063275693216 429 816146433444319966 109240407867 5580138...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
L...

result:

ok 4881 tokens

Test #24:

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

input:

6307 5
30
21205 32529499410586 59491750487468 125447624045 330243296028754 186122875620078155 2681228133623078 231118199874385440 832145267 2582081284455427 618524082887586688 523277714022923592 7546881826 546 867437793523349253 59704 52284 876873354240463 5207112987 8880515570787 509732306100431217...

output:

Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Lily
Lily
Kaguya
Kaguya
Kaguya
Kaguya
Lily
Kaguya
Kaguya
Kaguya
Kaguya
...

result:

ok 6307 tokens