This is an interactive problem.

You are given a sorted in increasing order singly linked list. You should find the minimum integer in the list which is greater than or equal to x.

More formally, there is a singly liked list built on an array of n elements. Element with index i contains two integers: valuei is the integer value in this element, and nexti that is the index of the next element of the singly linked list (or -1, if the current element is the last). The list is sorted, i.e. if nexti ≠ - 1, then valuenexti > valuei.

You are given the number of elements in the list n, the index of the first element start, and the integer x.

You can make up to 2000 queries of the following two types:

  * ? i (1 ≤ i ≤ n) — ask the values valuei and nexti, 
  * ! ans — give the answer for the problem: the minimum integer, greater than or equal to x, or ! -1, if there are no such integers. Your program should terminate after this query. 



Write a program that solves this problem.

Input

The first line contains three integers n, start, x (1 ≤ n ≤ 50000, 1 ≤ start ≤ n, 0 ≤ x ≤ 109) — the number of elements in the list, the index of the first element and the integer x.

Output

To print the answer for the problem, print ! ans, where ans is the minimum integer in the list greater than or equal to x, or -1, if there is no such integer.

Interaction

To make a query of the first type, print ? i (1 ≤ i ≤ n), where i is the index of element you want to know information about.

After each query of type ? read two integers valuei and nexti (0 ≤ valuei ≤ 109,  - 1 ≤ nexti ≤ n, nexti ≠ 0).

It is guaranteed that if nexti ≠ - 1, then valuenexti > valuei, and that the array values give a valid singly linked list with start being the first element.

Note that you can't ask more than 1999 queries of the type ?.

If nexti = - 1 and valuei = - 1, then it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling exit(0)). You will receive "Wrong Answer", it means that you asked more queries than allowed, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Your solution will get "Idleness Limit Exceeded", if you don't print anything or forget to flush the output, including the final answer.

To flush you can use (just after printing a query and line end):

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



Hacks format

For hacks, use the following format:

In the first line print three integers n, start, x (1 ≤ n ≤ 50000, 1 ≤ start ≤ n, 0 ≤ x ≤ 109).

In the next n lines print the description of the elements of the list: in the i-th line print two integers valuei and nexti (0 ≤ valuei ≤ 109,  - 1 ≤ nexti ≤ n, nexti ≠ 0).

The printed structure should be a valid singly linked list. In particular, it should be possible to reach all elements from start by following links nexti, and the last element end should have -1 in the nextend.

Example

Input

5 3 80
97 -1
58 5
16 2
81 1
79 4


Output

? 1
? 2
? 3
? 4
? 5
! 81

Note

You can read more about singly linked list by the following link: <https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list>

The illustration for the first sample case. Start and finish elements are marked dark. <image>

Difficulty: HARD
Tags: Complete search

Probability
Skill types: Complete search

Starter code:

Solutions:
from random import sample

def R():
	return map(int, input().split())

def ask(i):
	print('?', i, flush=True)
	(v, nxt) = R()
	if v < 0:
		exit()
	return (v, nxt)

def ans(v):
	print('!', v)
	exit()
(n, s, x) = R()
mv = -1
i = s
S = 800
q = range(1, n + 1)
if n > S:
	q = sample(q, S)
	if s not in q:
		q[0] = s
for i in q:
	(v, nxt) = ask(i)
	if v == x or (i == s and v > x):
		ans(v)
	if v < x:
		if nxt < 0:
			ans(-1)
		if v > mv:
			(mv, mnxt) = (v, nxt)
while mv < x and mnxt >= 1:
	(mv, mnxt) = ask(mnxt)
ans(mv if mv >= x else -1)


import random
from sys import stdout
(idx_len, start_idx, x) = (int(x) for x in input().split())
random.seed(153)
requests = list(range(1, idx_len + 1))
random.shuffle(requests)
val_next = [(-1, start_idx)]
for request in requests[:999]:
	print('? {}'.format(request))
	stdout.flush()
	(value, next) = (int(x) for x in input().split())
	val_next.append((value, next))
(closest_value, closest_next) = val_next[0]
for (value, next) in val_next:
	if value < x and value > closest_value:
		closest_value = value
		closest_next = next
while True:
	if closest_next == -1:
		print('! -1')
		exit()
	print('? {}'.format(closest_next))
	stdout.flush()
	(value, next) = (int(x) for x in input().split())
	if value >= x:
		print('! {}'.format(value))
		exit()
	if next == -1:
		print('! -1')
		exit()
	else:
		closest_next = next


from random import sample
SIZE = 950

def R():
	return map(int, input().split())

def ask(i):
	print('?', i, flush=True)
	(v, nxt) = R()
	if v < 0:
		exit()
	return (v, nxt)

def ans(v):
	print('!', v)
	exit()
(n, s, x) = R()
(v, nxt) = ask(s)
if v >= x:
	ans(v)
q = range(1, n + 1)
if n > SIZE:
	q = sample(q, SIZE)
(v, nxt) = max(filter(lambda t: t[0] < x, map(ask, q)), key=lambda t: t[0], default=(v, nxt))
while v < x and nxt >= 1:
	(v, nxt) = ask(nxt)
ans(v if v >= x else -1)


import random
SIZE = 900

def R():
	return map(int, input().split())

def ask(i):
	print('?', i, flush=True)
	(v, nxt) = R()
	if v < 0:
		exit()
	return (v, nxt)
(n, s, x) = R()
q = range(1, n + 1)
if n > SIZE:
	q = random.sample(q, SIZE)
(v, nxt) = max((t for t in map(ask, q) if t[0] < x), default=(-1, s))
while v < x and ~nxt:
	(v, nxt) = ask(nxt)
print('!', v if v >= x else -1)


import random, sys
from datetime import datetime

def main():
	(n, start, x) = map(int, input().split())
	indexes = list(map(lambda x: random.randint(1, n), range(1000)))
	sys.stdout.write('? %d\n' % start)
	sys.stdout.flush()
	(best, bestNext) = map(int, input().split())
	if best >= x:
		sys.stdout.write('! %d\n' % best)
		sys.stdout.flush()
		exit(0)
	for index in indexes:
		sys.stdout.write('? %d\n' % index)
		sys.stdout.flush()
		(value, nextId) = map(int, input().split())
		if value < x and best < value:
			(best, bestNext) = (value, nextId)
	while best < x and bestNext != -1:
		sys.stdout.write('? %d\n' % bestNext)
		sys.stdout.flush()
		(best, bestNext) = map(int, input().split())
	if best < x or best == 2 * 10 ** 9:
		sys.stdout.write('! -1\n')
		sys.stdout.flush()
	else:
		sys.stdout.write('! %d\n' % best)
		sys.stdout.flush()
random.seed(1791791791)
main()


from random import sample
SIZE = 950

def R():
	return map(int, input().split())

def ask(i):
	print('?', i, flush=True)
	(v, nxt) = R()
	if v < 0:
		exit()
	return (v, nxt)
(n, s, x) = R()
(v, nxt) = ask(s)
if v < x:
	q = range(1, n + 1)
	if n > SIZE:
		q = sample(q, SIZE)
	try:
		(v, nxt) = max(filter(lambda t: t[0] < x, map(ask, q)))
	except ValueError:
		pass
	while v < x and nxt >= 1:
		(v, nxt) = ask(nxt)
print('!', v if v >= x else -1)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
(N, X, S) = map(int, input().split())
print('?', X)
(V, ni) = map(int, input().split())
q = {random.randint(1, N) for _ in range(min(N, 999))}
if N > 1000:
	while len(q) < 999:
		q.add(random.randint(1, N))
for i in q:
	print('?', i)
	sys.stdout.flush()
	(a, b) = map(int, input().split())
	if V < a <= S:
		V = a
		ni = b
while V < S and ni > 0:
	print('?', ni)
	sys.stdout.flush()
	(a, b) = map(int, input().split())
	V = a
	ni = b
if V >= S:
	print('!', V)
else:
	print('!', -1)


import sys
import random
(n, start, x) = map(int, input().split())
visited = [False] * (n + 2)
left = 2000
print('? ' + str(start))
left -= 1
sys.stdout.flush()
data = []
(val, nex) = map(int, input().split())
data.append((val, nex))
visited[start] = True
if val >= x:
	print('! ' + str(val))
	sys.stdout.flush()
	sys.exit()
safe = 10 ** 20
for i in range(1000):
	cell = random.randint(1, n)
	if visited[cell]:
		continue
	print('? ' + str(cell))
	left -= 1
	visited[cell] = True
	sys.stdout.flush()
	(val, nex) = map(int, input().split())
	if val > x:
		safe = min(safe, val)
		continue
	if val == x:
		print('! ' + str(x))
		sys.stdout.flush()
		sys.exit()
	if val < x:
		data.append((val, nex))
if len(data) == 0:
	print('! ' + str(safe))
	sys.stdout.flush()
	sys.exit()
data.sort()
currentval = data[-1][0]
currentnext = data[-1][1]
while True:
	if currentnext == -1:
		print('! -1')
		sys.stdout.flush()
		sys.exit()
	if left == 1:
		print('! -1')
		sys.stdout.flush()
		sys.exit()
	print('? ' + str(currentnext))
	left -= 1
	sys.stdout.flush()
	(currentval, currentnext) = map(int, input().split())
	if currentval == -1 and currentnext == -1:
		print('! -1')
		sys.stdout.flush()
		sys.exit()
	if currentval >= x:
		print('! ' + str(currentval))
		sys.stdout.flush()
		sys.exit()


from random import sample
from sys import stdout
read = lambda : map(int, input().split())

def ask(x):
	print('? {}'.format(x))
	stdout.flush()
	return tuple(read())

def answer(x):
	print('! {}'.format(x))
	stdout.flush()
	exit(0)
(n, st, x) = read()
a = [ask(st)]
if a[0][0] >= x:
	answer(a[0][0])
for i in sample(range(1, n + 1), min(n, 999)):
	b = ask(i)
	if b[0] < x:
		a.append(b)
	elif b[0] == x:
		answer(x)
b = max(a)
while True:
	if b[0] >= x:
		answer(b[0])
	if b[1] == -1:
		break
	else:
		b = ask(b[1])
answer(-1)


import random
import sys
(n, start, x) = [int(x) for x in input().split()]
start -= 1

def debug(*args, **kwargs):
	pass
remaining_queries = 2000
perm = list(range(n))
random.shuffle(perm)
debug('random_indices:', perm)
values = [None] * n
nexts = [None] * n
best_i = None

def submit(ans):
	print('!', ans, flush=True)
	exit(0)

def fetch_raw(i):
	print('?', i + 1, flush=True)
	(value, next) = [int(x) for x in input().split()]
	return (value, next - 1)

def fetch(i):
	global remaining_queries
	global values
	global nexts
	global best_i
	if values[i] is None:
		(values[i], nexts[i]) = fetch_raw(i)
		remaining_queries -= 1
		if remaining_queries < 0:
			debug('Too many queries')
	if values[i] == x:
		submit(values[i])
	elif values[i] < x:
		if nexts[i] == -2:
			submit(-1)
		elif best_i is None or values[i] > values[best_i]:
			best_i = i
			debug('best_i+1 =', best_i + 1)
fetch(start)
if values[start] >= x:
	submit(values[start])
rand_reps = 1
lin_reps = 1
rand_i = 0
while True:
	for rand_rep_i in range(rand_reps):
		while rand_i < n and values[perm[rand_i]] is not None:
			rand_i += 1
		if rand_i < n:
			debug('random_choice')
			fetch(perm[rand_i])
		else:
			rand_reps = 0
	for lin_rep_i in range(lin_reps):
		i = best_i
		while values[nexts[i]] is not None:
			debug('sequential_choice')
			fetch(nexts[i])
			if values[nexts[i]] > x:
				submit(values[nexts[i]])
		debug('sequential_choice')
		fetch(nexts[i])
		if values[nexts[i]] > x:
			submit(values[nexts[i]])


from sys import stdin, stdout
import random
(n, start, x) = map(int, stdin.readline().rstrip().split())
if n < 1000:
	choices = random.sample(range(n), n)
else:
	choices = random.sample(range(n), 999)
if start - 1 not in choices:
	choices.append(start - 1)
data = []
for c in choices:
	print('? ' + str(c + 1))
	stdout.flush()
	(value, nxt) = map(int, stdin.readline().rstrip().split())
	data.append((value, nxt))
	if nxt == -1 and value == -1:
		break
data.sort(key=lambda x: x[0])
if data[0][0] >= x:
	print('! ' + str(data[0][0]))
	stdout.flush()
else:
	startAt = len(data) - 1
	for i in range(len(data) - 1):
		if data[i + 1][0] >= x:
			startAt = i
			break
	y = startAt
	value = data[y][0]
	nxt = data[y][1]
	while nxt != -1 and value < x:
		print('? ' + str(nxt))
		stdout.flush()
		(value, nxt) = map(int, stdin.readline().rstrip().split())
		if nxt == -1 and value == -1:
			break
	if value >= x:
		print('! ' + str(value))
		stdout.flush()
	else:
		print('! -1')
		stdout.flush()


from random import sample

def R():
	return map(int, input().split())

def ask(i):
	print('?', i, flush=True)
	(v, nxt) = R()
	if v < 0:
		exit()
	return (v, nxt)

def ans(v):
	print('!', v)
	exit()
(n, s, x) = R()
d = [None] * (n + 1)
f = [False] * (n + 1)
mv = -1
i = s
count = 950
q = range(1, n + 1)
if n > count:
	q = sample(q, count)
	if s not in q:
		q[0] = s
for i in q:
	if not f[i]:
		f[i] = True
		(v, nxt) = ask(i)
		if v == x or (i == s and v > x):
			ans(v)
		if nxt != -1:
			f[nxt] = True
		elif v < x:
			ans(-1)
		if v < x:
			nv = d[nxt]
			if nv is None:
				if v > mv:
					(mv, mnxt) = (v, nxt)
			elif nv > x:
				ans(nv)
		d[i] = v
while mv < x and mnxt >= 1:
	(mv, mnxt) = (d[mnxt], None) if d[mnxt] else ask(mnxt)
ans(mv if mv >= x else -1)


import random
from sys import stdout
(n, start, x) = map(int, input().split())
ans = start
annnsss = -1
z = 0
print('?', start)
stdout.flush()
(anss, b) = map(int, input().split())
if anss >= x:
	print('!', anss)
	stdout.flush()
else:
	i = 0
	while z != 10 and i != 1000:
		i = i + 1
		anns = random.randrange(1, n + 1)
		print('?', anns)
		stdout.flush()
		(annss, b) = map(int, input().split())
		if annss < x and anss < annss:
			ans = anns
			anss = annss
		if annss == x:
			print('!', x)
			stdout.flush()
			z = 10
	if z != 10:
		print('?', ans)
		stdout.flush()
		(anss, b) = map(int, input().split())
		while anss < x and b != -1:
			print('?', b)
			stdout.flush()
			(anss, b) = map(int, input().split())
		if anss < x:
			print('! -1')
			stdout.flush()
		else:
			print('!', anss)
			stdout.flush()


import sys
import random
(n, st, t) = map(int, input().split())
print('?', st)
sys.stdout.flush()
(mn, i1) = map(int, input().split())
if mn >= t:
	print('!', mn)
	sys.stdout.flush()
	exit(0)
ar = list((i for i in range(1, n + 1)))
random.shuffle(ar)
mx = 10 ** 10
for i in range(min(999, len(ar))):
	print('?', ar[i])
	sys.stdout.flush()
	(x, i2) = map(int, input().split())
	if x >= t:
		mx = min(mx, t)
	elif mn < x:
		mn = x
		i1 = i2
for i in range(1000):
	if i1 == -1:
		if mx == 10 ** 10:
			print('!', -1)
			sys.stdout.flush()
			exit(0)
		else:
			print('!', mx)
			sys.stdout.flush()
			exit(0)
	print('?', i1)
	(x, i2) = map(int, input().split())
	if x >= t:
		print('!', x)
		sys.stdout.flush()
		exit(0)
	i1 = i2
if mx == 10 ** 10:
	print('!', -1)
	sys.stdout.flush()
	exit(0)
else:
	print('!', mx)
	sys.stdout.flush()
	exit(0)


import sys
import random
try:
	import frosch
	frosch.hook()
except ImportError:
	pass
ini = lambda : int(sys.stdin.readline())
inl = lambda : [int(x) for x in sys.stdin.readline().split()]
ins = lambda : sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print('\x1b[33m', *a, '\x1b[0m', **dict(file=sys.stderr, **kw))
INFVAL = 10 ** 9 + 5

def solve():
	(n, start, x) = inl()
	d = dict()
	rev = list()
	unknowns = list(range(1, n + 1))
	unknowns.remove(start)
	over_minval = INFVAL
	lastidx = None
	for i in range(1700):
		if not unknowns:
			break
		idx = random.choice(unknowns)
		print(f'? {idx}')
		sys.stdout.flush()
		unknowns.remove(idx)
		(val, nex) = map(int, input().split())
		if nex in unknowns:
			unknowns.remove(nex)
		if val >= x:
			over_minval = min(over_minval, val)
		d[idx] = (val, val, nex)
		rev.append((val, idx, nex))
		if nex == -1:
			lastidx = nex
		elif nex not in d:
			d[nex] = (val + 1, None, None)
	rev.sort()
	head = start
	if rev and x < rev[0][0]:
		over_minval = rev[0][0]
	else:
		for (val, idx, nex) in rev:
			if val >= x:
				over_minval = val
				break
			head = idx

	def query():
		nonlocal head, over_minval
		if head is None or head == lastidx or head == -1:
			return True
		while head in d:
			(_, val, nex) = d[head]
			if nex is None:
				break
			if val is not None and val >= x:
				over_minval = min(over_minval, val)
				return True
			if nex == -1:
				return True
			head = nex
		print(f'? {head}')
		sys.stdout.flush()
		(val, nex) = map(int, input().split())
		d[head] = (val, val, nex)
		if val >= x:
			over_minval = min(over_minval, val)
		head = nex
		return False
	for i in range(299):
		done = query()
		if done:
			break
	if over_minval == INFVAL:
		over_minval = -1
	print(f'! {over_minval}')
solve()


from random import seed, sample
from functools import lru_cache
req_left = 1999

@lru_cache(None)
def ask(x):
	global req_left
	req_left -= 1
	print('?', x, flush=True)
	return tuple(map(int, input().split()))
seed(1337)
(n, start, x) = map(int, input().split())
ch = sample(range(1, n + 1), n // 50 + 1)
if start not in ch:
	ch.append(start)
mv = 0
mc = start
for c in ch:
	(v, n) = ask(c)
	if v < x:
		if v > mv:
			mv = v
			mc = c
	if v == x:
		print('!', v, flush=True)
		exit(0)
nxt = mc
while req_left > 0:
	if nxt == -1:
		break
	(v, nxt) = ask(nxt)
	if v >= x:
		print('!', v, flush=True)
		exit(0)
print('!', -1)


from sys import stdout
import random
(n, start, x) = map(int, input().split())
not_vis = set(range(1, n + 1))
print('? ' + str(start))
stdout.flush()
(val, nxt) = map(int, input().split())
vis = set([start])
while 1:
	if nxt == -1 and val == -1:
		break
	if val >= x:
		print('! ' + str(val))
		stdout.flush()
		break
	if nxt == -1:
		print('! -1')
		break
	print('? ' + str(nxt))
	stdout.flush()
	(v1, n1) = map(int, input().split())
	vis.add(nxt)
	if len(not_vis) > 0:
		rnd = random.sample(not_vis, 1)[0]
		not_vis.remove(rnd)
	else:
		rnd = 1
	print('? ' + str(rnd))
	stdout.flush()
	(v2, n2) = map(int, input().split())
	vis.add(rnd)
	if v2 > v1 and v2 <= x:
		val = v2
		nxt = n2
	else:
		val = v1
		nxt = n1


(n, start, x) = map(int, input().split())
from random import sample
N1 = 1000
d = {}
Q = sample(range(1, n + 1), min(N1, n))
if start not in Q:
	Q[0] = start
for q in Q:
	print('?', q, flush=True)
	(v, n) = map(int, input().split())
	d[q] = (v, n)
L = sorted(((v, q) for (q, (v, n)) in d.items()))
from bisect import bisect
i = bisect(L, (x, 0)) - 1
if i < 0:
	r = L[0][0]
else:
	(v, p) = L[i]
	p = d[p][1]
	while v < x and p != -1:
		print('?', p, flush=True)
		(v, p) = map(int, input().split())
	if v >= x:
		r = v
	else:
		r = -1
print('!', r, flush=True)


from sys import stdout
from random import Random
(n, s, x) = list(map(int, input().split()))
ans = 3 * 10 ** 9
asked = [False for i in range(n + 1)]
cache = [[] for i in range(n + 1)]
max_ask = 1999
t = 1750

def ask(i):
	if asked[i]:
		return cache[i]
	asked[i] = True
	print('?', i)
	stdout.flush()
	res = list(map(int, input().split()))
	cache[i] = res
	return res
f = ask(s)
cs = f[0]
r = Random()
for i in range(t):
	y = r.randint(1, n)
	if not asked[y]:
		q = ask(y)
		if q[0] >= x:
			ans = min(ans, q[0])
		elif cs < q[0] < x:
			s = y
			cs = q[0]
	else:
		i -= 1
for i in range(max_ask - t):
	q = ask(s)
	if q[0] >= x:
		ans = min(ans, q[0])
	s = q[1]
	if s == -1:
		break
if ans == 3 * 10 ** 9:
	print('! -1')
else:
	print('!', ans)


from random import sample
(n, start, x) = map(int, input().split())
f = min(n, 998)

def get(i):
	print('?', i)
	return list(map(int, input().split()))

def answer(a):
	print('!', a)
	exit(0)
arr = []
arr.append(get(start))
if arr[0][0] >= x:
	answer(arr[0][0])
for i in sample(range(1, n + 1), f):
	a = get(i)
	if a[0] < x:
		arr.append(a)
	elif a[0] == x:
		answer(a[0])
u = max(arr)[1]
while u != -1:
	q = get(u)
	if q[0] >= x:
		answer(q[0])
	u = q[1]
answer(-1)


import sys
(n, start, x) = map(int, input().split())
C = min(n, 998)

def get(i):
	sys.stdout.write('? %d\n' % i)
	sys.stdout.flush()
	return list(map(int, sys.stdin.readline().split()))

def answer(a):
	print('! %d' % a)
	exit(0)
m = get(start)[0]
if m >= x:
	answer(m)
from random import sample
queries = [get(i) for i in sample(range(1, n + 1), C)] + [get(start)]
u = max([q for q in queries if q[0] < x])[1]
while u > 0:
	q = get(u)
	if q[0] >= x:
		answer(q[0])
	u = q[1]
answer(-1)


import random
import sys
random.seed(a=5000)
(n, start, x) = map(int, input().split())
visited = [0] * (n + 1)
bestans = 10 ** 10
tmp = 0
bestbefore = start
out = ['?', str(start)]
print(' '.join(out), flush=True)
(value, next) = map(int, input().split())
bestbeforeval = value
if value >= x:
	print(' '.join(['!', str(value)]))
	sys.exit()
tmp = 0
for i in range(1000):
	if tmp == n:
		break
	while True:
		k = random.randint(1, n)
		if visited[k] == 0:
			break
	out = ['?', str(k)]
	print(' '.join(out), flush=True)
	(value, nxt) = map(int, input().split())
	visited[k] = 1
	tmp += 1
	if visited[nxt] == 0:
		visited[nxt] = 1
		tmp += 1
	if value >= x:
		bestans = min(value, bestans)
	elif bestbeforeval < value:
		bestbeforeval = value
		bestbefore = k
curr = bestbefore
while True:
	out = ['?', str(curr)]
	print(' '.join(out), flush=True)
	(value, nxt) = map(int, input().split())
	if nxt == -1:
		if value == -1:
			abdacadabra
			sys.exit()
		elif value >= x:
			out = ['!', str(value)]
			print(' '.join(out))
			sys.exit()
		else:
			print('! -1')
			sys.exit()
	if value >= x:
		out = ['!', str(value)]
		print(' '.join(out))
		sys.exit()
	curr = nxt