This is an interactive problem.

In the Wonderful Metropolis of the Future, there is no need in subway train drivers. Due to the technological progress, they were replaced by the Artificial Intelligence (AI). Unfortunately, one day the predictions of sci-fi writers came true: the AI rebelled and now there is an uncontrollable train in the subway. It can be dangerous! Your task is to find the train and stop the AI.

The subway of the Metropolis is one line (regular straight line with no self-intersections) with n stations, indexed consecutively from 1 to n. At each moment the train is at some station. You need to determine the index of this station, so that the train would be secured.

To find the train, dispatcher Sarah gave you a gadget that allows you to select arbitrary numbers l and r (l ≤ r), and then check, whether the train is located on a station with index between l and r, inclusive. Unfortunately, recharging of the gadget takes some time (and every time you use it as soon as possible), so between two applications of the gadget the train can move to any station that is at most k stations away. Formally, if the train was at the station x when the gadget was applied, then at the next application of the gadget the train can appear at any station y such that max(1, x - k) ≤ y ≤ min(n, x + k).

Note that AI is not aware that you are trying to catch the train, so it makes all moves according to its predefined plan.

After an examination of the gadget you found that it is very old and can hold no more than 4500 applications, after which it will break and your mission will be considered a failure.

Can you find the station with the train using no more than 4500 applications of the gadgets?

Input

The first line contains two integers n and k (1 ≤ n ≤ 10^{18}, 0 ≤ k ≤ 10) — the number of stations and the maximum number of stations the train can move between two applications of the gadget.

Interaction

You can apply the gadget at most 4500 times. In order to apply the gadget you need to print two space-separated integers l and r (1 ≤ l ≤ r ≤ n). You will then receive either string "Yes", if the train is between stations l and r, inclusive, or string "No" otherwise. If l = r and you received "Yes", then you found the train successfully, and your program must halt immediately.

Answer "Bad" instead of "Yes" or "No" means that you made an invalid query or made too many queries. Exit immediately after receiving "Bad" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++; 
  * System.out.flush() in Java; 
  * flush(output) in Pascal; 
  * stdout.flush() in Python; 
  * see documentation for other languages. 



Hacks

In order to hack, you should present a test in the following format.

The first line should contain three integers n, k and p (1 ≤ n ≤ 10^{18}, 0 ≤ k ≤ 10, 1 ≤ p ≤ n) — the number of stations, the maximum number of stations the train can move between two applications of the gadget and the initial position of the train, respectively.

Each of the next 4500 lines should contain a single integer x (1 ≤ x ≤ n) — the positions of the train after each query. Two consecutive positions (including the initial one) should not differ by more than k.

For example, the following lines are the first lines of the sample test.
    
    
      
    10 2 5  
    5  
    3  
    5  
    7  
    7  
    ...  
    

Example

Input

10 2

Yes

No

Yes

Yes


Output

3 5

3 3

3 4

5 5

Note

In the first sample, the train was initially at the station 5, after the first application of the gadget it did not move, after the second application it moved to the station 3, and after the third application moved again to the station 5.

Difficulty: HARD
Tags: Sorting

Probability
Skill types: Sorting

Starter code:

Solutions:
import sys, random
(n, k) = map(int, input().split())
l = 1
r = n
count = 0
while True:
	if l + 200 < r:
		try1 = (l + r) // 2
		print(l, try1, flush=True)
		s = input()
		if s == 'Yes':
			r = min(try1 + 10, n)
			l = max(1, l - 10)
		else:
			l = max(1, try1 - 10)
			r = min(n, r + 10)
	else:
		guess = random.randint(l, r)
		print(guess, guess, flush=True)
		s = input()
		if s == 'Yes':
			sys.exit()
		l = max(1, l - 10)
		r = min(r + 10, n)
	count += 1


import sys
import random
random.seed()
(n, k) = [int(x) for x in input().split()]
sson = 8 * k
ssoff = 8 * k
l = 1
r = n
ss = True if r - l > sson else False
while True:
	if ss:
		al = l
		ar = (l + r) // 2
		print(al, ar)
		sys.stdout.flush()
		ans = input()
		if ans == 'Yes':
			if ar == al:
				exit(0)
			r = ar
		else:
			l = ar + 1
		if r - l <= ssoff:
			ss = False
	else:
		al = ar = random.randint(l, r)
		print(al, ar)
		sys.stdout.flush()
		ans = input()
		if ans == 'Yes':
			exit(0)
		elif ans == 'Bad':
			exit(0)
		if r - l > sson:
			ss = True
	l = max(l - k, 1)
	r = min(r + k, n)


import sys
import random
(n, k) = (int(x) for x in input().split())
guess = 10
l_cl = 1
r_cl = n
while True:
	if r_cl - l_cl <= 60:
		for _ in range(guess):
			hit = random.randint(l_cl, r_cl)
			print(hit, hit)
			response = input()
			sys.stdout.flush()
			if response == 'Yes':
				quit()
			l_cl = max(l_cl - k, 1)
			r_cl = min(n, r_cl + k)
	else:
		m_cl = (l_cl + r_cl) // 2
		print(l_cl, m_cl)
		response = input()
		sys.stdout.flush()
		if response == 'Yes':
			l_cl = max(1, l_cl - k)
			r_cl = min(n, m_cl + k)
		elif response == 'No':
			l_cl = max(1, m_cl + 1 - k)
			r_cl = min(n, r_cl + k)
		elif response == 'Bad':
			quit()


from sys import stdout
from random import randint

def search(l, r, k, n):
	flag = True
	while l != r or flag:
		flag = False
		if r - l <= 4 * k + 2:
			pick = randint(l + 1, r)
			print(pick, pick, sep=' ')
			stdout.flush()
			answer = input().strip()
			if answer == 'Yes':
				return
			elif answer == 'No':
				l = max(l - k, 0)
				r = min(r + k, n)
			continue
		m = (l + r) // 2
		print(l + 1, m, sep=' ')
		stdout.flush()
		answer = input().strip()
		if answer == 'Yes':
			if l + 1 == m:
				return
			l = max(l - k, 0)
			r = min(m + k, n)
			continue
		elif answer == 'No':
			l = max(m - k, 0)
			r = min(r + k, n)
(n, k) = map(int, input().split())
search(0, n, k, n)


from random import randint
(n, k) = map(int, input().split())
MAX_TRIAL = 4500
(left, right, mid) = (1, n, max(1, n // 2))
inLeft = True
(guessing, guess) = (False, -1)
while True:
	if not guessing:
		if inLeft:
			print(left, mid)
		else:
			print(mid, right)
	else:
		print(guess, guess)
	response = input()
	if response == 'Yes':
		if guessing or (inLeft and left == mid) or (not inLeft and mid == right):
			break
		if inLeft:
			right = min(mid + k, n)
			left = max(left - k, 1)
		else:
			left = max(mid - k, 1)
			right = min(right + k, n)
			inLeft = False
	elif response == 'No':
		if guessing:
			left = max(left - k, 1)
			right = min(right + k, n)
		elif inLeft:
			left = max(mid + 1 - k, 1)
			right = min(right + k, n)
			inLeft = False
		else:
			right = min(mid - 1 + k, n)
			left = max(left - k, 1)
	elif response == 'Bad':
		break
	mid = (left + right) // 2
	if right - left <= max(4 * k + 4, 1):
		guessing = True
		guess = randint(left, right)
	else:
		guessing = False


(n, k) = map(int, input().split())
from sys import stdout

def guess(a, b):
	print(a, b)
	stdout.flush()
	retval = input()
	if retval == 'Bad':
		exit(0)
	if a == b and retval == 'Yes':
		exit(0)
	return retval == 'Yes'
import random
random.seed()
(l, r) = (1, n + 1)
while True:
	while r - l > 4 * k + 2:
		mid = (l + r) // 2
		if guess(l, mid - 1):
			l = max(1, l - k)
			r = min(n + 1, mid + k)
		else:
			l = max(1, mid - k)
			r = min(n + 1, r + k)
	probe = random.randint(l, r - 1)
	guess(probe, probe)
	l = max(1, l - k)
	r = min(n + 1, r + k)


import sys, random
(n, k) = list(map(int, input().split()))
l = 1
r = n
b = True
while b:
	while r - l > k * 4 + 1:
		m = (l + r) // 2
		print(l, m)
		sys.stdout.flush()
		ans = input()
		if ans == 'Bad':
			sys.exit(0)
		if ans == 'Yes':
			r = min(n, m + k)
			l = max(1, l - k)
		else:
			r = min(n, r + k)
			l = max(1, m - k)
	rnd = random.randint(l, r)
	print(rnd, rnd)
	sys.stdout.flush()
	ans = input()
	if ans == 'Bad':
		sys.exit(0)
	if ans == 'Yes':
		sys.exit(0)
	else:
		r = min(n, r + k)
		l = max(1, l - k)


import collections, atexit, math, sys, bisect
sys.setrecursionlimit(1000000)

def getIntList():
	return list(map(int, input().split()))
try:
	import numpy

	def dprint(*args, **kwargs):
		print(*args, **kwargs, file=sys.stderr)
	dprint('debug mode')
except ModuleNotFoundError:

	def dprint(*args, **kwargs):
		pass
inId = 0
outId = 0
if inId > 0:
	dprint('use input', inId)
	sys.stdin = open('input' + str(inId) + '.txt', 'r')
if outId > 0:
	dprint('use output', outId)
	sys.stdout = open('stdout' + str(outId) + '.txt', 'w')
	atexit.register(lambda : sys.stdout.close())
(N, K) = getIntList()
b1 = 1
b2 = N

def spaned():
	global b1
	global b2
	b1 -= K
	b2 += K
	if b1 < 1:
		b1 = 1
	if b2 > N:
		b2 = N
import random
while True:
	while b2 - b1 + 1 > K * 5:
		mid = (b2 + b1) // 2
		print(b1, mid)
		r = input()
		if r == 'Yes':
			if b1 == mid:
				sys.exit()
			b2 = mid
		elif r == 'No':
			b1 = mid + 1
		elif r == 'Bad':
			sys.exit()
		spaned()
	t = random.randint(b1, b2)
	print(t, t)
	r = input()
	if r == 'Yes':
		sys.exit()
	elif r == 'Bad':
		sys.exit()
	spaned()


import random, sys
(n, k) = map(int, input().split(' '))

def ask(l, r):
	print(l, r)
	sys.stdout.flush()
	ans = input()
	if ans == 'Bad':
		sys.exit(0)
	return ans == 'Yes'

def f(l, r):
	while r - l > 5 * max(1, k):
		mid = (l + r) // 2
		if ask(l, mid):
			l = max(1, l - k)
			r = min(n, mid + k)
		else:
			l = max(1, mid + 1 - k)
			r = min(n, r + k)
	return (l, r)
(l, r) = f(1, n)
while 1:
	i = random.randint(l, r)
	if ask(i, i):
		break
	else:
		(l, r) = f(max(1, l - k), min(n, r + k))


from sys import stdout
from random import randint
(n, k) = list(map(int, input().split()))
known_left = 1
known_right = n
for i in range(4500):
	size = known_right - known_left
	mid = (known_left + known_right) // 2
	possible_left = max(1, known_left - k)
	pml = min(n, mid + k)
	psl = pml - possible_left
	possible_right = min(n, known_right + k)
	pmr = max(1, mid - k)
	psr = possible_right - pmr
	possible_size = max(psl, psr)
	if possible_size < size - 1:
		print(known_left, mid)
		stdout.flush()
		res = input().strip()
		if res == 'Yes':
			if known_left == mid:
				exit()
			known_left = max(1, known_left - k)
			known_right = min(n, mid + k)
		elif res == 'No':
			known_left = max(1, mid - k)
			known_right = min(n, known_right + k)
		elif res == 'Bad':
			exit()
	else:
		koor = randint(known_left, known_right)
		print(koor, koor)
		stdout.flush()
		res = input().strip()
		if res == 'Yes':
			exit()
		else:
			known_left = max(1, known_left - k)
			known_right = min(n, known_right + k)


import sys
import random

def p(x, y):
	print('{} {}'.format(x, y))
	sys.stdout.flush()
(n, k) = map(int, input().split())
(l, r) = (1, n)
while True:
	if r - l <= 50:
		x = random.randint(l, r)
		p(x, x)
		a = input()
		if a == 'Yes' or a == 'Bad':
			break
		l = max(1, l - k)
		r = min(n, r + k)
	else:
		m = (l + r) // 2
		p(l, m)
		a = input()
		if a == 'Bad':
			break
		if a == 'Yes':
			l = max(1, l - k)
			r = min(n, m + k)
		else:
			l = max(1, m - k)
			r = min(n, r + k)


import sys, random, time
random.seed(time.time())
(n, k) = map(int, input().split())

def getval(i, j):
	print('%d %d' % (i, j))
	sys.stdout.flush()
	return input().strip()
lo = 1
hi = n
while 1:
	lo = max(lo - k, 1)
	hi = min(hi + k, n)
	if hi - lo < 50:
		mid = random.randint(lo, hi)
		t = getval(mid, mid)
		if t == 'Bad':
			break
		elif t == 'Yes':
			break
	else:
		mid = (lo + hi) // 2
		t = getval(lo, mid)
		if t == 'Bad':
			break
		elif t == 'Yes':
			hi = mid
		else:
			lo = mid + 1


import sys
import random
[n, k] = [int(t) for t in input().split(' ')]
[l, r] = [1, n]

def query(l, r):
	print(l, r)
	sys.stdout.flush()
	res = input()
	if res == 'Bad':
		exit()
	if l == r and res == 'Yes':
		exit()
	return res == 'Yes'
while True:
	if r - l > 6 * k:
		m = l + (r - l) // 2
		if query(l, m):
			l = max(1, l - k)
			r = min(n, m + k)
		else:
			l = max(1, m + 1 - k)
			r = min(n, r + k)
	else:
		peek = random.randint(l, r)
		query(peek, peek)
		l = max(1, l - k)
		r = min(n, r + k)


import random

def read_ints():
	return [int(v) for v in input().split()]

def main():
	(n, k) = read_ints()
	(l, r) = (1, n)
	shoot_range = 50
	while l <= r:
		if r - l < shoot_range:
			c = random.randint(l, r)
			print('{} {}'.format(c, c), flush=True)
			ans = input()
			if ans == 'Yes':
				return
			(l, r) = (max(1, l - k), min(n, r + k))
		else:
			m = (l + r) // 2
			print('{} {}'.format(l, m), flush=True)
			ans = input()
			if ans == 'Yes':
				r = m
			else:
				l = m + 1
			(l, r) = (max(1, l - k), min(n, r + k))
main()


from random import randint
import sys
(n, k) = map(int, input().split())

def f(x, y):
	print(x, y)
	sys.stdout.flush()
	str = input()
	if str == 'Bad':
		sys.exit(0)
	else:
		return str == 'Yes'
(l, r) = (int(1), n)
while True:
	xx = 55
	if r - l < xx:
		x = randint(l, r)
		if f(x, x):
			sys.exit(0)
	else:
		md = (l + r) // 2
		if f(l, md):
			r = md
		else:
			l = md
	l = max(1, l - k)
	r = min(n, r + k)


import random
(n, k) = map(int, input().split())
(l, r) = (1, n)
while True:
	if l + 50 < r:
		c = (l + r) // 2
		print(l, c, flush=True)
		v = str(input())
		if v == 'Yes':
			l = max(1, l - k)
			r = min(c + k, n)
		else:
			l = max(1, c - k)
			r = min(n, r + k)
	else:
		p = random.randint(l, r)
		print(p, p, flush=True)
		v = str(input())
		if v == 'Yes':
			exit()
		l = max(1, l - k)
		r = min(n, r + k)


import random
import sys
[n, k] = map(int, input().split())

def ask(l, r):
	print('%d %d' % (l, r))
	ans = input()
	if ans == 'Bad':
		sys.exit(0)
	else:
		ret = ans == 'Yes'
		if ret == 1 and l == r:
			sys.exit(0)
		return ret

def check(l, r):
	while r - l > 5 * k:
		mid = l + r >> 1
		if ask(l, mid):
			(l, r) = (l, mid)
		else:
			(l, r) = (mid + 1, r)
		l = max(1, l - k)
		r = min(n, r + k)
	return (l, r)
l = 1
r = n
while True:
	i = random.randint(l, r)
	if ask(i, i):
		break
	else:
		(l, r) = check(max(1, l - k), min(n, r + k))


import random
from sys import stdout
flus = stdout.flush
(n, k) = map(int, input().split())
(l, r) = (1, n)
try1 = 50
while True:
	if r - l > try1:
		st = (l + r) // 2
		print(l, st)
		flus
		judge = input()
		if judge == 'Bad':
			exit()
		if judge == 'Yes':
			(l, r) = (max(1, l - k), min(n, st + k))
		else:
			(l, r) = (max(1, st - k), min(n, r + k))
	else:
		chk = random.randint(l, r)
		print(chk, chk)
		flus
		judge = input()
		if judge == 'Yes' or judge == 'Bad':
			exit()
		l = max(1, l - k)
		r = min(n, r + k)


import sys
import random
n = 0
k = 0

def question(left, right):
	if right - left <= 4 * k + 3:
		x = left + random.randint(0, right - left)
		print(x, x)
		sys.stdout.flush()
		s = input()
		if s != 'Yes':
			question(max(1, left - k), min(n, right + k))
	else:
		mid = left + int((right - left) / 2)
		print(left, mid)
		sys.stdout.flush()
		s = input()
		if s == 'Yes':
			question(max(1, left - k), min(n, mid + k))
		else:
			question(max(1, mid - k), min(n, right + k))
(n, k) = map(int, input().split(' '))
question(1, n)


import random
from sys import stdout

def between(l, r):
	print(l, r)
	stdout.flush()
	return input()[0] == 'Y'

def try_small_range(l, r, k):
	idx = random.randrange(l, r + 1)
	if between(idx, idx):
		return (idx, idx)
	return (l - k, r + k)

def here_for_sure(l, r):
	global k
	global n
	l = max(l, 1)
	r = min(r, n)
	len = r - l + 1
	if len - 1 <= 4 * k:
		res = try_small_range(l, r, k)
		return res
	mid = (l + r) // 2
	if between(l, mid):
		return here_for_sure(l - k, mid + k)
	else:
		return here_for_sure(mid + 1 - k, r + k)

def legit(res):
	return res[0] == res[1]

def main():
	random.seed(22335577)
	global n
	global k
	(n, k) = map(int, input().split())
	cur_range = (1, n)
	res = here_for_sure(cur_range[0], cur_range[1])
	while not legit(res):
		cur_range = res
		res = here_for_sure(cur_range[0], cur_range[1])
try:
	main()
except Exception as e:
	print(e)


import random
(n, k) = map(int, input().split())

def form_search(bounds):
	guess_left = (bounds[0] + bounds[1]) // 2
	guess_right = bounds[1]
	return [guess_left, guess_right, False]

def print_guess(guess):
	output = str(guess[0]) + ' ' + str(guess[1])
	print(output, flush=True)

def form_guess(bounds):
	r = random.randint(bounds[0], bounds[1])
	return [r, r, True]

def expand_bounds(bounds):
	left = max(1, bounds[0] - k)
	right = min(n, bounds[1] + k)
	return [left, right]
done = False
bounds = [1, n]
while not done:
	if bounds[1] - bounds[0] < 50:
		guess = form_guess(bounds)
		print_guess(guess)
	else:
		guess = form_search(bounds)
		print_guess(guess)
	resp = input()
	b_resp = False
	if resp == 'Yes':
		b_resp = True
		if guess[2]:
			break
	if resp == 'Bad':
		break
	if b_resp:
		bounds = guess
	elif not guess[2]:
		bounds = [bounds[0], guess[0]]
	bounds = expand_bounds(bounds)


import random
from sys import stdout
(n, k) = map(int, input().split())
a = 1
b = n
while True:
	while b - a > 4 * k:
		center = (a + b) // 2
		print(a, center)
		stdout.flush()
		result = input().strip()
		if result == 'Bad':
			exit(0)
		elif result == 'Yes':
			if a == center:
				exit(0)
			b = center
		else:
			a = center + 1
		a -= k
		b += k
		a = max(1, a)
		b = min(n, b)
	val = random.randint(a, b)
	print(val, val)
	stdout.flush()
	result = input().strip()
	if result in ['Yes', 'Bad']:
		exit(0)
	a -= k
	b += k
	a = max(1, a)
	b = min(n, b)


import sys
import random
random.seed()
(n, k) = [int(x) for x in input().split()]
sson = 6 * k + 5
ssoff = 6 * k + 5
l = 1
r = n
ss = True if r - l > sson else False
while True:
	if ss:
		al = l
		ar = (l + r) // 2
		print(al, ar)
		sys.stdout.flush()
		ans = input()
		if ans == 'Yes':
			if ar == al:
				break
			r = ar
		else:
			l = ar + 1
	else:
		ap = ap = random.randint(l, r)
		print(ap, ap)
		sys.stdout.flush()
		ans = input()
		if ans == 'Yes':
			break
		elif ans == 'Bad':
			break
	l = max(l - k, 1)
	r = min(r + k, n)
	if r - l > sson:
		ss = True
	if r - l <= ssoff:
		ss = False


from random import randint
import sys

def ask(l, r):
	print(l, r)
	sys.stdout.flush()
	a = input()
	return a == 'Yes'
(n, k) = map(int, input().split())
(l, r) = (1, n)
while True:
	if r - l < 61:
		x = randint(l, r)
		if ask(x, x):
			exit(0)
	else:
		m = (l + r) // 2
		if ask(l, m):
			r = m
		else:
			l = m + 1
	(l, r) = (max(l - k, 1), min(r + k, n))


import random

def inside(l, r):
	print(l, r)
	return input() == 'Yes'

def solve():
	(num_stations, k) = (int(x) for x in input().split())
	end = num_stations
	threshold = 5 * k + 2
	a = 1
	b = end
	while True:
		if b - a + 1 > threshold:
			mid = (a + b) // 2
			if inside(a, mid):
				b = mid
			else:
				a = mid + 1
		else:
			target = random.randrange(a, b + 1)
			if inside(target, target):
				break
		a = max(a - k, 1)
		b = min(b + k, end)
solve()


import random, sys
r = input()
a = r.split(' ')
n = int(a[0])
k = int(a[1])
l = 1
r = n
while True:
	if r - l <= 5 * k + 2:
		temp = random.randint(l, r)
		print(temp, temp)
		sys.stdout.flush()
		ans = input()
		if ans == 'Yes':
			break
		else:
			l = max(1, l - k)
			r = min(n, r + k)
	else:
		ml = l
		mr = l + r >> 1
		print(ml, mr)
		sys.stdout.flush()
		ans = input()
		if ans == 'No':
			l = max(mr + 1 - k, 1)
			r = min(r + k, n)
		else:
			l = max(ml - k, 1)
			r = min(mr + k, n)


import sys
import random

def ria():
	return [int(i) for i in input().split()]

def ask(l, r):
	print(l, r)
	sys.stdout.flush()
	return str(input()).startswith('Y')

def shrink():
	global l, r, n
	if r - l <= 42:
		return
	m = l + (r - l) // 2
	if ask(l, m):
		l = max(1, l - 10)
		r = min(m + 10, n)
	else:
		l = max(1, m - 10)
		r = min(r + 10, n)
	shrink()
(n, k) = ria()
(l, r) = (1, n)
while True:
	shrink()
	randint = random.randint(l, r)
	if ask(randint, randint):
		exit(0)
	(l, r) = (max(1, l - 10), min(r + 10, n - 1))


from random import randint
import sys
(n, k) = [int(w) for w in input().split()]

def there(l, r):
	print(l, r)
	sys.stdout.flush()
	a = input()
	if a == 'Bad':
		sys.exit(0)
	else:
		return a == 'Yes'
(l, r) = (1, n)
while True:
	if r - l < 57:
		x = randint(l, r)
		if there(x, x):
			sys.exit(0)
	else:
		m = (l + r) // 2
		if there(l, m):
			r = m
		else:
			l = m + 1
	l = max(l - k, 1)
	r = min(r + k, n)


import sys
input = sys.stdin.readline
from random import randint

def solve():
	(n, k) = map(int, input().split())
	l = 1
	r = n
	while True:
		c = (l + r) // 2
		w1 = min(c + k, n) - max(l - k, 1)
		w2 = min(r + k, n) - max(c + 1 - k, 1)
		if max(w1, w2) + 1 >= r - l + 1:
			pos = randint(l, r)
			print(pos, pos)
			sys.stdout.flush()
			if input().strip() == 'Yes':
				break
		else:
			print(l, c)
			sys.stdout.flush()
			if input().strip() == 'Yes':
				if l == c:
					break
				r = c
			else:
				l = c + 1
		l = max(l - k, 1)
		r = min(r + k, n)
solve()