Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian] and [Vietnamese] as well.

OWCA has fallen and now, L.O.V.E.M.U.F.F.I.N are finally free to do whatever they want.

In order to celebrate their victory, the $N$ members of L.O.V.E.M.U.F.F.I.N (numbered $1$ through $N$) want to have some ice-cream. But first, they need to divide the loot they found in OWCA's headquarters. The loot consists of $M$ dollar bills. In the order from member $1$ to member $N$, the members of L.O.V.E.M.U.F.F.I.N start to propose plans to divide the loot, i.e. the number of dollar bills each member should receive (not necessarily the same for everyone). Whenever someone proposes a plan, a vote is held. Let's denote the current number of members of L.O.V.E.M.U.F.F.I.N by $x$. If at least $\lfloor\frac{x}{K}\rfloor + 1$ members vote *for* a plan, this plan is accepted, the loot is distributed accordingly, no other plans are proposed and everyone goes for icecream. Otherwise, the person who proposed the plan is thrown off the roof for wasting the others' time with nonsense and the next person proposes a plan.

As we all know, all members of L.O.V.E.M.U.F.F.I.N are smart evil scientists. Therefore, during each vote and for each member, this member will vote against the currently proposed plan if they are sure that if this plan is rejected, they will gain at least as much loot as if it was accepted. Assume that all scientists act optimally and are aware that everyone else also acts optimally. We consider those who are thrown off the roof to gain exactly $-10^{100}$ dollars in loot, since they will not live to see another day.

Dr. D happens to be the first person to devise a plan. Can Dr. D avoid being thrown off the roof? If so, what is the maximum amount of loot Dr. D can gain? You should find the answers for multiple scenarios; in each scenario, $N$ and $M$ can be different, but $K$ is the same for all scenarios.

------  Input ------
The first line of the input contains two space-separated integers $K$ and $Q$.
Each of the next $Q$ lines contains two space-separated integers $N$ and $M$ describing a scenario.

------  Output ------
For each scenario, print a single line. If Dr. D can avoid being thrown off the roof, this line should contain a single integer - the maximum amount of loot. Otherwise, it should contain the string "Thrown off the roof." (without quotes).

------  Constraints ------
$2 ≤ K ≤ 10^{5}$
$1 ≤ Q ≤ 5 \cdot 10^{5}$
$1 ≤ N ≤ 10^{18}$
$2 ≤ M ≤ 10^{18}$

------  Subtasks ------
Subtask #1 (15 points):
$K = 2$
$N, M ≤ 5,000$
the sum of $N$ over all scenarios does not exceed $5,000$

Subtask #2 (15 points):
$K = 2$
the sum of $N$ over all scenarios does not exceed $5 \cdot 10^{5}$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------ 
2 2
5 5
1 100
----- Sample Output 1 ------ 
2
100

Difficulty: VERY_HARD

Starter code:

Solutions:
from sys import stdin
(k, T) = map(int, stdin.readline().strip().split())
max_possible = 1000000000000000000
if k != 2:
	not_thrown = [0, 1]
else:
	not_thrown = [0]
k_minus_1 = k - 1
num = k // k_minus_1 + 1
while num < max_possible:
	not_thrown.append(num)
	num = k * num // k_minus_1 + 1
not_thrown = set(not_thrown)
for t in range(1, T + 1):
	(n, m) = map(int, stdin.readline().strip().split())
	if n < m * k:
		if k == 2:
			if n == 1:
				print(m)
				continue
			if n == 2:
				print('Thrown off the roof.')
				continue
			if n == 3:
				print(m)
				continue
			remaining = m - (n + 1) // k
			print(remaining)
		else:
			print(m - n // k)
	elif n - m * k in not_thrown:
		print(0)
	else:
		print('Thrown off the roof.')


import sys
input = sys.stdin.readline
l = list(map(int, input().split()))
k = l[0]
q = l[1]
if k != 2:
	dict1 = {}
	dict1[k + 1] = 1
	prev = k + 1
	r = 3000000
	if k <= 1000 or (k > 10000 and k < 50000):
		for i in range(r):
			new = prev * k // (k - 1)
			new += 1
			dict1[new] = 1
			prev = new
			if len(str(new)) >= 19:
				break
	elif k <= 5000:
		for i in range(3 * 10000):
			new = prev * k // (k - 1)
			new += 1
			dict1[new] = 1
			prev = new
			if len(str(new)) >= 19:
				break
	elif k >= 5000 and k <= 10000:
		for i in range(3 * 100000):
			new = prev * k // (k - 1)
			new += 1
			dict1[new] = 1
			prev = new
			if len(str(new)) >= 19:
				break
	else:
		r = 3000000
		for i in range(r):
			new = prev * k // (k - 1)
			new += 1
			dict1[new] = 1
			prev = new
for i in range(q):
	l1 = list(map(int, input().split()))
	n = l1[0]
	m = l1[1]
	extra = 0
	flag = True
	if k == 2:
		if n == 1:
			extra = 0
		elif n == 2:
			flag = False
			extra = m
		elif n == 3:
			extra = 0
		elif n == 4:
			extra = 2
		elif n == 5:
			extra = 3
		elif n % 2 == 0:
			extra = n // 2
		else:
			extra = n // 2 + 1
		lol = m - extra
		if lol >= 0 and flag == True:
			print(lol)
		else:
			new = n + 1 - 2 * m
			while new % 2 == 0 and new > 0:
				new = new // 2
			if new == 1 or new == 0:
				print(0)
			else:
				print('Thrown off the roof.')
	else:
		extra = n // k
		lol = m - extra
		if lol >= 0:
			print(lol)
		elif n > k * m:
			to_check = n - k * m
			if dict1.get(to_check, 0) != 0:
				print(0)
			else:
				print('Thrown off the roof.')
		else:
			print('Thrown off the roof.')


import sys
input = sys.stdin.readline
(k, q) = map(int, input().split())
dict1 = {}
dict1[1] = 1
prev = 1
border = 10 ** 18
while prev < border:
	dict1[prev] = 1
	prev = prev * k // (k - 1) + 1
for i in range(q):
	(n, m) = map(int, input().split())
	check = m * k
	if n == 1:
		print(m)
	elif n == 2 and k == 2:
		print('Thrown off the roof.')
	elif n == 3 and k == 2:
		print(m)
	elif check + 1 == n and k == 2:
		print(0)
	elif check >= n and k == 2:
		if n % 2 == 0:
			print(max(m - n // 2, 0))
		else:
			print(max(m - n // 2 - 1, 0))
	elif check >= n:
		print(m - n // k)
	elif n - check in dict1:
		print(0)
	else:
		print('Thrown off the roof.')


import sys
import math
input = sys.stdin.readline
(k, q) = map(int, input().split())
if k == 2:
	for i in range(q):
		(n, m) = map(int, input().split())
		if n == 1:
			print(m)
		elif n == 2:
			print('Thrown off the roof.')
		elif n == 3:
			print(m)
		elif n == 4:
			ans = m - 2
			if ans >= 0:
				print(ans)
			else:
				print('Thrown off the roof.')
		elif n <= 2 * m + 1:
			if n % 2 == 0:
				print(m - n // 2)
			else:
				print(m - n // 2 - 1)
		elif n - 1 == 2 * m + 1:
			print('Throw off the roof.')
		elif bin(n - 2 * m + 1).count('1') == 1:
			print(0)
		else:
			print('Thrown off the roof.')
else:
	allnum = {k + 1: 0}
	temp = k + 1
	count = 0
	while temp < 10 ** 18:
		new = temp * k // (k - 1) + 1
		allnum[new] = 0
		temp = new
	for i in range(q):
		(n, m) = map(int, input().split())
		if n <= k * m + k - 1:
			if n >= 1 and n <= k - 1:
				print(m)
			else:
				print(m - n // k)
		elif n - 1 == k * m + k - 1:
			print('Thrown off the roof.')
		else:
			num = n - m * k
			if num in allnum:
				print(0)
			else:
				print('Thrown off the roof.')


import bisect
import sys
input = sys.stdin.readline
(K, Q) = list(map(int, input().strip().split(' ')))

def findout(N, M, K):
	if N == 2 and K == 2:
		return 'Thrown off the roof.'
	if N == 3 and K == 2:
		return M
	if N == 1:
		return M
	if N <= M * K:
		if K == 2:
			return M - (N + 1) // K
		return M - N // K
	remind = N - M * K
	if remind in check:
		return 0
	return 'Thrown off the roof.'

def easy_find(N, M, K):
	if N == 2 and K == 2:
		return -1
	if N == 3 and K == 2:
		return M
	if N == 1:
		return M
	if N <= M * K:
		if K == 2:
			return M - (N + 1) // K
		return M - N // K
	return 'bad'
queries = []
ans = [-1] * Q
for _ in range(Q):
	(N, M) = list(map(int, input().strip().split(' ')))
	temp = easy_find(N, M, K)
	if temp != 'bad':
		ans[_] = temp
	else:
		queries += [(N - M * K, _)]
queries = sorted(queries)
if queries:
	MAX = queries[-1][0]
	check = []
	temp = 1
	while True:
		temp = K * temp // (K - 1) + 1
		check += [temp]
		if temp > MAX:
			break
while queries:
	(remind, post) = queries[-1]
	if check == []:
		ans[post] = -1
		queries.pop()
		continue
	while check[-1] > remind:
		check.pop()
	if check == []:
		ans[post] = -1
		queries.pop()
		continue
	if check[-1] == remind:
		ans[post] = 0
		queries.pop()
	else:
		ans[post] = -1
		queries.pop()
for i in range(Q):
	if ans[i] == -1:
		ans[i] = 'Thrown off the roof.'
	else:
		ans[i] = str(ans[i])
sys.stdout.write('\n'.join(ans))