"Duel!"

Betting on the lovely princess Claris, the duel between Tokitsukaze and Quailty has started.

There are $n$ cards in a row. Each card has two sides, one of which has color. At first, some of these cards are with color sides facing up and others are with color sides facing down. Then they take turns flipping cards, in which Tokitsukaze moves first. In each move, one should choose exactly $k$ consecutive cards and flip them to the same side, which means to make their color sides all face up or all face down. If all the color sides of these $n$ cards face the same direction after one's move, the one who takes this move will win.

Princess Claris wants to know who will win the game if Tokitsukaze and Quailty are so clever that they won't make mistakes.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$).

The second line contains a single string of length $n$ that only consists of $0$ and $1$, representing the situation of these $n$ cards, where the color side of the $i$-th card faces up if the $i$-th character is $1$, or otherwise, it faces down and the $i$-th character is $0$.


-----Output-----

Print "once again" (without quotes) if the total number of their moves can exceed $10^9$, which is considered a draw.

In other cases, print "tokitsukaze" (without quotes) if Tokitsukaze will win, or "quailty" (without quotes) if Quailty will win.

Note that the output characters are case-sensitive, and any wrong spelling would be rejected.


-----Examples-----
Input
4 2
0101

Output
quailty

Input
6 1
010101

Output
once again

Input
6 5
010101

Output
tokitsukaze

Input
4 1
0011

Output
once again



-----Note-----

In the first example, no matter how Tokitsukaze moves, there would be three cards with color sides facing the same direction after her move, and Quailty can flip the last card to this direction and win.

In the second example, no matter how Tokitsukaze moves, Quailty can choose the same card and flip back to the initial situation, which can allow the game to end in a draw.

In the third example, Tokitsukaze can win by flipping the leftmost five cards up or flipping the rightmost five cards down.

The fourth example can be explained in the same way as the second example does.

Source: codeforces | Difficulty: HARD
Tags: Complete search

Game theory

Greedy algorithms


Solutions:
def win1():
	if n == k or r[k + 1] == n or l[n - k] == 1:
		return True
	for i in range(2, n - k + 1):
		if l[i - 1] == 1 and r[i + k] == n and (a[i - 1] == a[i + k]):
			return True
	return False

def win2():
	if 2 * k < n:
		return False
	for i in range(2, n - k + 1):
		if l[i - 1] != 1 or r[i + k] != n:
			return False
	return True
s = input().split()
(n, k) = (int(s[0]), int(s[1]))
s = input().split()
a = [0]
l = [0 for i in range(n + 1)]
r = [0 for i in range(n + 1)]
for c in s[0]:
	a.append(int(c))
(l[1], r[n]) = (1, n)
for i in range(2, n + 1):
	if a[i - 1] == a[i]:
		l[i] = l[i - 1]
	else:
		l[i] = i
	if a[n - i + 1] == a[n - i + 2]:
		r[n - i + 1] = r[n - i + 2]
	else:
		r[n - i + 1] = n - i + 1
if win1():
	print('tokitsukaze')
elif win2():
	print('quailty')
else:
	print('once again')


import sys
import math
import bisect
from collections import deque
sys.setrecursionlimit(1000000000)

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def finput():
	return float(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())

def modst(a, s):
	res = 1
	while s:
		if s % 2:
			res *= a
		a *= a
		s //= 2
	return res

def main():
	(n, k) = rinput()
	s = input()
	q = -1
	w = -1
	e = -1
	r = -1
	for i in range(n):
		if s[i] == '0':
			if q == -1:
				q = i
			w = i
		else:
			if e == -1:
				e = i
			r = i
	z = w - q
	x = r - e
	if min(z, x) < k:
		return 'tokitsukaze'
	if z > k or x > k:
		return 'once again'
	c = 0
	v = 0
	for i in range(n):
		if s[i] == '0':
			v += 1
			c = 0
		else:
			c += 1
			v = 0
		if c >= k or v >= k:
			return 'once again'
	return 'quailty'
for i in range(1):
	print(main())


from bisect import bisect_left
(n, k) = map(int, input().split())
s = input()
l = len(s)
flag = -1
pos0 = [-1]
pos1 = [-1]
for i in range(l):
	if s[i] == '0':
		pos0.append(i)
	else:
		pos1.append(i)
pos0.append(10 ** 18)
pos1.append(10 ** 18)
d0 = 1 + (pos0[-2] - pos0[1])
d1 = 1 + (pos1[-2] - pos1[1])
if min(d0, d1) <= k:
	flag = 1
else:
	for i in range(n - k + 1):
		l = i
		r = i + k - 1
		tposl = bisect_left(pos1, l)
		tposr = bisect_left(pos1, r)
		if pos1[tposl - 1] == -1:
			tl = -1
		else:
			tl = pos1[tposl - 1]
		if pos1[tposr] == r:
			tr = pos1[tposr + 1]
			if tr == 10 ** 18:
				tr = -1
		else:
			tr = pos1[tposr]
			if tr == 10 ** 18:
				tr = -1
		td1 = 0
		if tl == -1:
			td1 = 1 + (pos1[-2] - tr)
		elif tr == -1:
			td1 = 1 + (tl - pos1[1])
		else:
			td1 = 1 + (pos1[-2] - pos1[1])
		tposl = bisect_left(pos0, l)
		tposr = bisect_left(pos0, r)
		if pos0[tposl - 1] == -1:
			tl = -1
		else:
			tl = pos0[tposl - 1]
		if pos0[tposr] == r:
			tr = pos0[tposr + 1]
			if tr == 10 ** 18:
				tr = -1
		else:
			tr = pos0[tposr]
			if tr == 10 ** 18:
				tr = -1
		if tl == -1:
			td2 = 1 + (pos0[-2] - tr)
		elif tr == -1:
			td2 = 1 + (tl - pos0[1])
		else:
			td2 = 1 + (pos0[-2] - pos0[1])
		td = max(td1, td2)
		if td > k:
			break
	else:
		flag = 0
if flag == 1:
	print('tokitsukaze')
elif flag == 0:
	print('quailty')
elif flag == -1:
	print('once again')


(n, k) = map(int, input().strip().split())
t = input().strip()
l1 = t.rfind('1') - t.find('1') + 1
l2 = t.rfind('0') - t.find('0') + 1
if l1 <= k or l2 <= k:
	print('tokitsukaze')
elif k < n // 2 or l1 > k + 1 or l2 > k + 1:
	print('once again')
else:
	print('quailty')


import sys

def sum_range(l, r):
	if r < l:
		return 0
	if l == 0:
		return sum[r]
	return sum[r] - sum[l - 1]
(n, k) = map(int, input().split())
cards = input()
sum = [0] * n
sum[0] = 1 if cards[0] == '1' else 0
for i in range(1, n):
	sum[i] += sum[i - 1]
	if cards[i] == '1':
		sum[i] += 1
min0 = min1 = n
max0 = max1 = -1
for i in range(0, n):
	if cards[i] == '1':
		min1 = min(min1, i)
		max1 = i
	else:
		min0 = min(min0, i)
		max0 = i
toki = False
qual = True
for i in range(0, n - k + 1):
	if sum_range(0, i - 1) + sum_range(i + k, n - 1) + k == n:
		toki = True
	if sum_range(0, i - 1) + sum_range(i + k, n - 1) + 0 == 0:
		toki = True
	prefix = sum_range(0, i - 1) == 0
	suffix = sum_range(i + k, n - 1) == 0
	if i > 0 and i + k < n and (prefix ^ suffix == 0):
		qual = False
	if i - min0 > k or i - min1 > k or max0 - (i + k - 1) > k or (max1 - (i + k - 1) > k):
		qual = False
if toki == True:
	print('tokitsukaze')
elif qual == True:
	print('quailty')
else:
	print('once again')


(n, k) = map(int, input().split())
a = input()
A = 0
for i in range(n):
	A += int(a[i])
s = 0
c = 0
W = False
L = False
D = False
for i in range(n):
	s += int(a[i])
	if i >= k:
		s -= int(a[i - k])
		c += int(a[i - k])
	if i >= k - 1:
		if s == A:
			W = True
		elif A - s + k == n:
			W = True
		elif c > 0 and A - s - c > 0:
			D = True
		elif c == 0 and i >= k and (i < n - 1) and (c == 0) and (A - s - c == 0):
			D = True
if W:
	print('tokitsukaze')
elif D or k * 2 < n:
	print('once again')
else:
	print('quailty')


(n, k) = map(int, input().split())
s = input()
fir0 = -1
last0 = -1
fir1 = -1
last1 = -1
for i in range(n):
	if s[i] == '0':
		if fir0 == -1:
			fir0 = i
		last0 = i
	else:
		if fir1 == -1:
			fir1 = i
		last1 = i
d0 = last0 - fir0
d1 = last1 - fir1
if min(d0, d1) < k:
	print('tokitsukaze')
elif d0 > k or d1 > k:
	print('once again')
else:
	cnt1 = 0
	cnt0 = 0
	for i in range(n):
		if s[i] == '0':
			cnt0 += 1
			cnt1 = 0
		else:
			cnt1 += 1
			cnt0 = 0
		if cnt1 >= k or cnt0 >= k:
			print('once again')
			exit()
	print('quailty')


import sys
import copy
input = sys.stdin.readline
(n, k) = map(int, input().split())
C = list(input().strip())

def JUDGE(C):
	ANS_one = 0
	ANS_zero = 0
	for c in C:
		if c == '0':
			ANS_zero += 1
		else:
			break
	for c in C[::-1]:
		if c == '0':
			ANS_zero += 1
		else:
			break
	for c in C:
		if c == '1':
			ANS_one += 1
		else:
			break
	for c in C[::-1]:
		if c == '1':
			ANS_one += 1
		else:
			break
	if ANS_zero >= n - k or ANS_one >= n - k:
		return 1
	else:
		return 0
if JUDGE(C) == 1:
	print('tokitsukaze')
	sys.exit()
if k >= n - 1:
	print('quailty')
	sys.exit()
if k < n / 2:
	print('once again')
	sys.exit()
CAN1 = copy.copy(C)
CAN2 = copy.copy(C)
if C[0] == '0':
	for i in range(1, k + 1):
		CAN1[i] = '1'
else:
	for i in range(1, k + 1):
		CAN1[i] = '0'
if C[-1] == '0':
	for i in range(n - 1, n - k - 1, -1):
		CAN2[i] = '1'
else:
	for i in range(n - 2, n - k - 2, -1):
		CAN2[i] = '0'
if JUDGE(CAN1) == 1 and JUDGE(CAN2) == 1:
	print('quailty')
	sys.exit()
else:
	print('once again')
	sys.exit()


(n, k) = map(int, input().split())
s = input()

def func(s):
	num = 1
	num2 = 1
	for i in range(1, n):
		if s[i] != s[i - 1]:
			break
		num += 1
	for i in range(n - 1, 0, -1):
		if s[i] != s[i - 1]:
			break
		num2 += 1
	if k + num >= n or k + num2 >= n:
		return 0
	elif s[-1] == s[0] and k + num + num2 >= n:
		return 0
	else:
		return 1
if func(s) == 0:
	print('tokitsukaze')
else:
	s2 = list(s)
	nums = [0] * 8
	s3 = list(s)
	for i in range(k):
		s3[i] = '1'
	s4 = list(s)
	for i in range(k):
		s4[i] = '0'
	s5 = list(s)
	for i in range(n - 1, n - k - 1, -1):
		s5[i] = '1'
	s6 = list(s)
	for i in range(n - 1, n - k - 1, -1):
		s6[i] = '0'
	s7 = list(s)
	for i in range(1, k + 1):
		s7[i] = '1'
	s8 = list(s)
	for i in range(1, k + 1):
		s8[i] = '0'
	s9 = list(s)
	for i in range(n - 2, n - k - 2, -1):
		s9[i] = '1'
	s10 = list(s)
	for i in range(n - 2, n - k - 2, -1):
		s10[i] = '0'
	nums[0] = func(s3)
	nums[1] = func(s4)
	nums[2] = func(s5)
	nums[3] = func(s6)
	nums[4] = func(s7)
	nums[5] = func(s8)
	nums[6] = func(s9)
	nums[7] = func(s10)
	if sum(nums) != 0:
		print('once again')
	else:
		print('quailty')


from sys import stdin, stdout, exit
(n, k) = map(int, stdin.readline().split())
s = stdin.readline().strip()

def z(winner):
	return 'tokitsukaze' if winner == 0 else 'quailty'
ones = [i for i in range(n) if s[i] == '1']
zeros = [i for i in range(n) if s[i] == '0']
if not ones or not zeros:
	print(z(0))
	exit()
if max(ones) - min(ones) + 1 <= k or max(zeros) - min(zeros) + 1 <= k:
	print(z(0))
	exit()
if max(ones) - min(ones) + 1 >= k + 2 or max(zeros) - min(zeros) + 1 >= k + 2:
	print('once again')
	exit()
if n == 2 * (k + 1):
	print('once again')
	exit()
print(z(1))


n = list(map(int, input().split()))
st = input()
i = 0
mas = []
while i < len(st):
	mas.insert(i, int(st[i]))
	i = i + 1
i = 0
cnt = 0
while i < n[0]:
	if mas[i] == 1:
		cnt = cnt + 1
	i = i + 1
i = 0
cnt2 = 0
while i < n[1]:
	if mas[i] == 1:
		cnt2 = cnt2 + 1
	i = i + 1
ans = 0
mn = cnt2
id = 0
izm = 0
if cnt - cnt2 == n[0] - n[1] or n[0] - cnt - (n[1] - cnt2) == n[0] - n[1]:
	ans = 1
while i < n[0]:
	if mas[i] == 1:
		cnt2 = cnt2 + 1
	if mas[i - n[1]] == 1:
		cnt2 = cnt2 - 1
	if cnt - cnt2 == n[0] - n[1] or n[0] - cnt - (n[1] - cnt2) == n[0] - n[1]:
		ans = 1
	if cnt2 <= mn:
		mn = cnt2
		id = i - n[1]
		izm = 0
	if n[1] - cnt2 <= mn:
		mn = n[1] - cnt2
		id = i - n[1]
		izm = 1
	i = i + 1
if ans == 1:
	print('tokitsukaze')
	exit(0)
i = 0
zer = [1000000, -1]
one = [1000000, -1]
10001
while i < n[0]:
	if mas[i] == 1:
		one[0] = min(one[0], i)
		one[1] = max(one[1], i)
	if mas[i] == 0:
		zer[0] = min(zer[0], i)
		zer[1] = max(zer[1], i)
	i = i + 1
if one[1] - one[0] - 1 >= n[1] or zer[1] - zer[0] - 1 >= n[1]:
	print('once again')
	exit(0)
id2 = id
while id < id2 + n[1]:
	mas[id] = izm
	id = id + 1
i = 0
cnt2 = 0
cnt = 0
while i < n[0]:
	if mas[i] == 1:
		cnt = cnt + 1
	i = i + 1
i = 0
while i < n[1]:
	if mas[i] == 1:
		cnt2 = cnt2 + 1
	i = i + 1
ans = 0
if cnt - cnt2 == n[0] - n[1] or n[0] - cnt - (n[1] - cnt2) == n[0] - n[1]:
	ans = 1
while i < n[0]:
	if mas[i] == 1:
		cnt2 = cnt2 + 1
	if mas[i - n[1]] == 1:
		cnt2 = cnt2 - 1
	if cnt - cnt2 == n[0] - n[1] or n[0] - cnt - (n[1] - cnt2) == n[0] - n[1]:
		ans = 1
	i = i + 1
if ans == 1:
	print('quailty')
else:
	print('once again')


import sys
(n, k) = map(int, input().split())
i = 0
cc = input()
while i < n and cc[i] == cc[0]:
	i += 1
prefix = i
i = 0
while i < n - 1 and cc[-i - 1] == cc[-1]:
	i += 1
suffix = i
if k + prefix >= n or k + suffix >= n or (cc[0] == cc[-1] and k + prefix + suffix >= n):
	print('tokitsukaze')
	sys.exit(0)
cc0 = cc[0:i] + '0' * k + cc[i + k:n]
if k <= prefix or k <= suffix:
	print('once again')
	sys.exit(0)
if cc[0] == cc[-1]:
	print('once again')
	sys.exit(0)
assert cc[0] != cc[-1] and prefix < k and (suffix < k)
if prefix + k + 2 <= n or suffix + k + 2 <= n:
	print('once again')
	sys.exit(0)
i = k
while cc[i] == cc[0]:
	i += 1
	if i + k >= n:
		break
if i + k < n:
	print('once again')
	sys.exit(0)
i = k
while cc[-i - 1] == cc[-1]:
	i += 1
	if i + k >= n:
		break
if i + k < n:
	print('once again')
	sys.exit(0)
print('quailty')


import sys

def Check():
	for j in [0, 1]:
		if R[j][1] + L[j][n] + k >= n:
			return 1
	return 0
(n, k) = [int(i) for i in input().split()]
S = [int(i) for i in input()]
R = [[0] * (n + 2), [0] * (n + 2)]
L = [[0] * (n + 2), [0] * (n + 2)]
for j in [0, 1]:
	L[S[0]][1] = 1
	for i in range(1, n):
		if S[i] == j:
			L[j][i + 1] = L[j][i] + 1
for j in [0, 1]:
	R[S[n - 1]][n] = 1
	for i in range(n - 2, -1, -1):
		if S[i] == j:
			R[j][i + 1] = R[j][i + 2] + 1
if Check():
	print('tokitsukaze')
	sys.exit(0)
for j in [0, 1]:
	for r in range(k, n + 1):
		l = r - k + 1
		t = [R[j][1], L[j][n], R[j ^ 1][1], L[j ^ 1][n]]
		if R[j][1] >= l - 1:
			R[j][1] = r + R[j][r + 1]
		if L[j][n] >= n - r:
			L[j][n] = n - l + 1 + L[j][l - 1]
		if R[j ^ 1][1] > l - 1:
			R[j ^ 1][1] = l - 1
		if L[j ^ 1][n] > n - r:
			L[j ^ 1][n] = n - r
		if not Check():
			print('once again')
			sys.exit(0)
		(R[j][1], L[j][n], R[j ^ 1][1], L[j ^ 1][n]) = t
print('quailty')


from collections import defaultdict
import sys
input = sys.stdin.readline
inf = 100000000000000000
mod = 998244353
(n, m) = map(int, input().split())
S = input().strip()
SUM0 = [0] * (n + 3)
SUM1 = [0] * (n + 3)
for i in range(len(S)):
	SUM1[i + 1] = SUM1[i]
	if S[i] == '1':
		SUM1[i + 1] += 1
	SUM0[i + 1] = SUM0[i]
	if S[i] == '0':
		SUM0[i + 1] += 1
for i in range(1, n + 1):
	if i + m - 1 > n:
		break
	l = i
	r = i + m - 1
	if SUM1[l - 1] == SUM1[n] - SUM1[r] == 0 or SUM0[l - 1] == SUM0[n] - SUM0[r] == 0:
		print('tokitsukaze')
		sys.exit()
if 2 * m < n or m == 1:
	print('once again')
	sys.exit()
flag = 0
for i in range(2, n + 1):
	if i + m - 1 > n - 1:
		break
	l = i
	r = i + m - 1
	if (SUM1[l - 1] == 0 and SUM0[n] - SUM0[r] == 0 or (SUM0[l - 1] == 0 and SUM1[n] - SUM1[r] == 0)) == False:
		flag = 1
if flag == 0:
	print('quailty')
	sys.exit()
print('once again')