This is an interactive problem.

Vasya and Petya are going to play the following game: Petya has some positive integer number a. After that Vasya should guess this number using the following questions. He can say a pair of non-negative integer numbers (x, y). Petya will answer him: 

  * "x", if (x mod a) ≥ (y mod a). 
  * "y", if (x mod a) < (y mod a). 



We define (x mod a) as a remainder of division x by a.

Vasya should guess the number a using no more, than 60 questions.

It's guaranteed that Petya has a number, that satisfies the inequality 1 ≤ a ≤ 10^9.

Help Vasya playing this game and write a program, that will guess the number a.

Interaction

Your program should play several games.

Before the start of any game your program should read the string: 

  * "start" (without quotes) — the start of the new game. 
  * "mistake" (without quotes) — in the previous game, you found the wrong answer. Your program should terminate after reading this string and it will get verdict "Wrong answer". 
  * "end" (without quotes) — all games finished. Your program should terminate after reading this string. 



After reading the string "start" (without quotes) the new game starts. 

At the beginning, your program should ask several questions about pairs of non-negative integer numbers (x, y). You can only ask the numbers, that satisfy the inequalities 0 ≤ x, y ≤ 2 ⋅ 10^9. To ask a question print "? x y" (without quotes). As the answer, you should read one symbol: 

  * "x" (without quotes), if (x mod a) ≥ (y mod a). 
  * "y" (without quotes), if (x mod a) < (y mod a). 
  * "e" (without quotes) — you asked more than 60 questions. Your program should terminate after reading this string and it will get verdict "Wrong answer". 



After your program asked several questions your program should print the answer in form "! a" (without quotes). You should print the number a satisfying the inequalities 1 ≤ a ≤ 10^9. It's guaranteed that Petya's number a satisfied this condition. After that, the current game will finish.

We recall that your program can't ask more than 60 questions during one game.

If your program doesn't terminate after reading "mistake" (without quotes), "end" (without quotes) or "e" (without quotes), it can get any verdict, because it will continue reading from closed input. Also, if your program prints answer or question in the incorrect format it can get any verdict, too. Be careful.

Don't forget to flush the output after printing questions and answers.

To flush the output, you can use: 

  * fflush(stdout) in C++. 
  * System.out.flush() in Java. 
  * stdout.flush() in Python. 
  * flush(output) in Pascal. 
  * See the documentation for other languages. 



It's guaranteed that you should play at least 1 and no more than 100 games.

Hacks:

In hacks, you can use only one game. To hack a solution with Petya's number a (1 ≤ a ≤ 10^9) in the first line you should write a single number 1 and in the second line you should write a single number a.

Example

Input


start
x
x
start
x
x
y
start
x
x
y
y
end


Output


? 0 0
? 10 1
! 1
? 0 0
? 3 4
? 2 5
! 2
? 2 4
? 2 5
? 3 10
? 9 1
! 3

Note

In the first test, you should play 3 games with Petya's numbers 1, 2 and 3.

In the first game, Petya will answer "x" (without quotes) to any question, because (x mod 1) = 0 for any integer x. 

In the second game, if you will ask pair (0, 0), the answer will be "x" (without quotes), because (0 mod 2) ≥ (0 mod 2). But if you will ask pair (2, 5), the answer will be "y" (without quotes), because (2 mod 2) < (5 mod 2), because (2 mod 2) = 0 and (5 mod 2) = 1.

Source: codeforces | Difficulty: HARD
Tags: Sorting

Constructive algorithms


Solutions:
import sys

def ask(x, y):
	print('?', x, y)
	return input() == 'y'
while input() == 'start':
	if not ask(0, 1):
		print('! 1')
		continue
	d = 1
	while ask(d, d * 2):
		d *= 2
	r = d
	l = d // 2
	while l + 1 < r:
		m = (l + r) // 2
		if ask(m, m * 2):
			l = m
		else:
			r = m
	print('!', r * 2 if not ask(r * 2 - 1, r * 2) else r * 2 - 1)


import sys

def question(x, y, a):
	if x % a >= y % a:
		return 'x'
	else:
		return 'y'

def real_question(x, y):
	print('? {0} {1}'.format(x, y))
	sys.stdout.flush()
	return input()

class CodeforcesTask1103BSolution:

	def __init__(self):
		self.result = ''

	def read_input(self):
		pass

	def process_task(self):
		while True:
			cmd = input()
			if cmd == 'start':
				q_res = 'y'
				x = 0
				qus = 0
				while q_res != 'x':
					qus += 1
					q_res = real_question(2 ** x, 2 ** (x + 1))
					l = 2 ** x
					r = 2 ** (x + 1)
					x += 1
				if r == 2:
					q_res = real_question(2, 1)
					if q_res == 'x':
						print('! 1')
						sys.stdout.flush()
					else:
						print('! 2')
						sys.stdout.flush()
				else:
					mid = l + (r - l) // 2
					l0 = l
					found = False
					following = False
					r += 2
					while not found:
						qus += 1
						q_res = real_question(l0, mid)
						if q_res == 'y':
							l = mid
							mid += (r - l) // 2
						else:
							r = mid
							mid -= (r - l) // 2
						if r == mid:
							found = True
						elif mid + 1 == r and following > 1:
							found = True
						elif mid + 1 == r:
							following += 1
					print('! {0}'.format(r))
					sys.stdout.flush()
			elif cmd == 'mistake':
				print('error')
				break
			else:
				break

	def get_result(self):
		return self.result
Solution = CodeforcesTask1103BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


from sys import stdout

def ask(x, y):
	print('?', x, y)
	stdout.flush()
	return input() == 'x'

def work():
	if ask(0, 1):
		return 1
	l = 1
	while ask(l * 2, l):
		l *= 2
	r = min(1000000000, l * 2 + 1)
	l += 1
	while r > l:
		mid = (l + r) // 2
		if ask(mid, (mid + 1) // 2):
			l = mid + 1
		else:
			r = mid
	return l
while input() == 'start':
	print('!', work())
	stdout.flush()


from sys import stdout

def ask(x, y):
	print('?', x, y)
	stdout.flush()
	x = input()
	return x == 'x'

def show_res(res):
	print('!', res)
	stdout.flush()

def prepare_game():
	gm = input()
	if gm[0] != 's':
		exit(0)
INF = int(1000000000.0) + 1

def play():
	L = 0
	R = 1
	while R < INF:
		res = ask(L, R)
		if res:
			break
		else:
			L = R
			R *= 2
	st = L
	while R - L > 1:
		m = (R + L) // 2
		if ask(st, m):
			R = m
		else:
			L = m
	show_res(R)
while True:
	prepare_game()
	play()


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[n - 1]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = arr[mid]
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[0]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = arr[mid]
			left = mid + 1
	return res
t = 1
for _ in range(t):
	s = input()
	while s == 'start':
		(l, r) = (0, 0)
		c = 1
		for i in range(31):
			print('?', c // 2, c, flush=True)
			ch = input()
			if ch == 'x':
				(l, r) = (c // 2, c)
				break
			c *= 2
		res = r
		(left, right) = (l + 1, r)
		while left <= right:
			mid = (left + right) // 2
			print('?', l, mid, flush=True)
			ch = input()
			if ch == 'x':
				res = mid
				right = mid - 1
			else:
				left = mid + 1
		print('!', res, flush=True)
		s = input()


a = input()
while a != 'end':
	if a == 'start':
		for i in range(30):
			print('?', 2 ** i, 2 * 2 ** i)
			if input() == 'x':
				break
		bot = 2 ** i
		top = min(2 ** (i + 1), 1000000000)
		if bot == 1:
			print('?', 2, 1)
			if input() == 'x':
				print('!', 1)
			else:
				print('!', 2)
		else:
			bot += 1
			while top != bot:
				mid = (bot + top) // 2
				print('?', 2 * mid, mid)
				if input() == 'x':
					top = mid
				else:
					bot = mid + 1
			print('!', top)
	a = input()