This is the easy version of the problem. The only difference is that in this version there are no "remove" queries.

Initially you have a set containing one element — $0$. You need to handle $q$ queries of the following types:

+ $x$ — add the integer $x$ to the set. It is guaranteed that this integer is not contained in the set;

? $k$ — find the $k\text{-mex}$ of the set.

In our problem, we define the $k\text{-mex}$ of a set of integers as the smallest non-negative integer $x$ that is divisible by $k$ and which is not contained in the set.


-----Input-----

The first line contains an integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of queries.

The following $q$ lines describe the queries.

An addition query of integer $x$ is given in the format + $x$ ($1 \leq x \leq 10^{18}$). It is guaranteed that $x$ was not contained in the set.

A search query of $k\text{-mex}$ is given in the format ? $k$ ($1 \leq k \leq 10^{18}$).

It is guaranteed that there will be at least one query of type ?.


-----Output-----

For each query of type ? output a single integer — the $k\text{-mex}$ of the set.


-----Examples-----

Input
15
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
Output
3
6
3
3
10
3
2000000000000000000
Input
6
+ 100
? 100
+ 200
? 100
+ 50
? 50
Output
200
300
150


-----Note-----

In the first example:

After the first and second queries, the set will contain elements $\{0, 1, 2\}$. The smallest non-negative number that is divisible by $1$ and is not contained in the set is $3$.

After the fourth query, the set will contain the elements $\{0, 1, 2, 4\}$. The smallest non-negative number that is divisible by $2$ and is not contained in the set is $6$.

In the second example:

Initially, the set contains only the element $\{0\}$.

After adding an integer $100$ the set contains elements $\{0, 100\}$.

$100\text{-mex}$ of the set is $200$.

After adding an integer $200$ the set contains elements $\{0, 100, 200\}$.

$100\text{-mex}$ of the set is $300$.

After adding an integer $50$ the set contains elements $\{0, 50, 100, 200\}$.

$50\text{-mex}$ of the set is $150$.

Difficulty: MEDIUM
Tags: Number theory

Data structures

Implementation

Complete search
Skill types: Data structures

Complete search

Starter code:

Solutions:
import sys
import math

def solve():
	inp = sys.stdin.readline
	q = int(inp())
	s = {0}
	d = {}
	for i in range(q):
		(t, x) = inp().split()
		if t == '+':
			s.add(int(x))
		elif t == '?':
			x = int(x)
			v = d.get(x, 0)
			while v in s:
				v += x
			d[x] = v
			print(v)
		else:
			raise Exception('wut')

def main():
	solve()
main()


import sys
import math
inp = sys.stdin.readline
n = int(inp())
s = {0}
d = {}
for i in range(n):
	f = inp().split()
	zn = f[0]
	k = int(f[1])
	if zn == '+':
		s.add(k)
	else:
		v = k
		x = d.get(v, 0)
		while x in s:
			x += k
		d[v] = x
		d[x] = x
		print(x)


from math import inf
from collections import Counter
import sys

def main():
	input = sys.stdin.readline
	q = int(input())
	nums = Counter()
	numbers = 0
	multips = dict()
	for _ in range(q):
		(typeOp, num) = input().split()
		if typeOp == '+':
			nums[int(num)] = 1
			numbers += 1
		elif not nums[int(num)]:
			print(num)
		else:
			multi = multips.get(int(num), 2)
			indexes = 0
			while True and indexes <= numbers:
				if not nums[int(num) * multi]:
					multips[int(num)] = multi
					break
				multi += 1
				indexes += 1
			print(multi * int(num))
main()


from cmath import sqrt
from functools import lru_cache
import sys
from math import log2
import bisect
input = sys.stdin.readline
from collections import defaultdict
import time
mod = 10 ** 9 + 7

def ii():
	return int(input())

def lii():
	return list(map(int, input().split()))

def ss():
	return input()

def lss():
	return list(map(str, input().split()))

def yes():
	sys.stdout.write('YES\n')

def no():
	sys.stdout.write('NO\n')
s = set([0])
h = defaultdict(int)
for _ in range(ii()):
	(a, b) = lss()
	b = int(b)
	if a == '?':
		x = b
		if h[b] != 0:
			x = h[b]
		while x in s:
			x += b
		h[b] = x
		print(x)
	else:
		s.add(b)


import sys
input = sys.stdin.readline
s = set()
d = {}
s.add(0)
for _ in range(int(input())):
	(sign, x) = map(str, input().split())
	x = int(x)
	if sign == '+':
		s.add(x)
	else:
		if x not in d:
			d[x] = x
		while d[x] in s:
			d[x] += x
		print(d[x])


import sys
import threading
from functools import lru_cache
from bisect import bisect_left
import math
from collections import defaultdict, deque
from heapq import *

def main():
	t = int(input())
	a = set()
	mapping = defaultdict(int)
	for _ in range(t):
		(op, x) = input().split()
		x = int(x)
		if op == '+':
			a.add(x)
		else:
			current = mapping[x] + 1
			temp = x * current
			current += 1
			while temp in a:
				temp = x * current
				current += 1
			mapping[x] = current - 2
			print(temp)
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


n = int(input())
P = {}
Si = {}
for i in range(n):
	S = input()
	a = S[0]
	x = int(S[1:])
	if a == '+':
		P[x] = True
	else:
		if x in Si:
			a = Si[x]
		else:
			a = x
		while a in P:
			a += x
		Si[x] = a
		print(a)


s = set([0])
ans = {}
q = int(input())

def add(x):
	s.add(x)

def ask(x):
	if ans.get(x) == None:
		ans[x] = x
	while ans[x] in s:
		ans[x] += x
	print(ans[x])
for i in range(q):
	(c, x) = input().split()
	if c == '+':
		add(int(x))
	else:
		ask(int(x))


last = {}
s = set()
q = int(input())
for i in range(q):
	(qt, num) = input().split()
	num = int(num)
	if qt == '+':
		s.add(num)
	else:
		if num in last:
			k = last[num]
		else:
			k = num
		while k in s:
			k += num
		last[num] = k
		print(k)


q = int(input())
ans = {}
a = set()
for _ in range(q):
	(op, x) = input().split()
	x = int(x)
	if op == '+':
		a.add(x)
		continue
	if x not in ans:
		ans[x] = x
	while ans[x] in a:
		ans[x] += x
	print(ans[x])


q = int(input())
s = {0}
mp = dict()
for qq in range(q):
	(ch, x) = input().split()
	x = int(x)
	if ch == '+':
		s.add(x)
	else:
		y = x
		if x in mp:
			y = mp[x]
		while True:
			if y not in s:
				print(y)
				mp[x] = y
				break
			y += x


from collections import defaultdict

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
check = set()
dic = defaultdict(int)
for ii in range(inp()):
	(flag, val) = input().split()
	val = int(val)
	if flag == '+':
		check.add(val)
	else:
		i = dic[val] + 1
		while i * val in check:
			i += 1
		dic[val] = i - 1
		print(i * val)


(map1, map2) = [{}, {}]
for test_cases in range(int(input())):
	(type, val) = list(input().split())
	ans = 0
	val = int(val)
	if type == '+':
		map1[val] = True
	else:
		if val in map2:
			fuck = map2[val]
		else:
			fuck = val
		while fuck in map1:
			fuck = fuck + val
		map2[val] = fuck + 0
		ans = fuck + 0
		print(ans)


q = int(input())
net = set()
seen = dict()
for i in range(q):
	(a, b) = map(str, input().split())
	if a == '+':
		net.add(int(b))
	else:
		start = int(b)
		if start in seen:
			start = seen[start]
		while start in net:
			start += int(b)
		seen[int(b)] = start
		print(start)


(di, ans) = (dict(), dict())
for _ in range(int(input())):
	(chr, val) = map(str, input().split())
	val = int(val)
	if chr == '+':
		di[val] = True
	else:
		if val in ans:
			ref = ans[val]
		else:
			ans[val] = 0
			ref = 0
		while ref + val in di:
			ref += val
		ans[val] = ref
		print(ref + val)


import math
t = int(input())
seen = set()
kmex = {}
for tc in range(1, t + 1):
	s = list(input().split())
	s[1] = int(s[1])
	if s[0] == '+':
		seen.add(s[1])
		continue
	if s[0] == '?':
		k = s[1]
		m = kmex[k] if k in kmex else 1
		while 1:
			if k * m in seen:
				m += 1
			else:
				break
		kmex[k] = m
		print(k * m)


dic = dict()
s = set()
for _ in range(int(input())):
	(op, n) = input().split()
	n = int(n)
	if op == '+':
		s.add(n)
	else:
		m = n
		if m in dic:
			m = dic[n]
		while True:
			if m not in s:
				print(m)
				dic[n] = m
				break
			m = m + n


import math

def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
s = [0]
a = set(s)
d = {}
for _ in range(N()):
	if 'er9fj48gh48gh4' == 14194665565:
		print('Tanmay')
	(q, n) = [x for x in input().split()]
	n = int(n)
	if q == '+':
		a.add(n)
		i = 1
		while i * n in a:
			i += 1
		d[n] = i * n
		continue
	ans = 0
	if n not in a:
		print(n)
		continue
	if d[n] in a:
		aa = d[n]
		while aa in a:
			aa += n
		d[n] = aa
	print(d[n])


x = int(input())
y = set()
q = {}
while x:
	x -= 1
	(op, m) = input().split()
	m = int(m)
	if op == '+':
		y.add(m)
		continue
	f = q.get(m, m)
	while f in y:
		f += m
	q[m] = f
	print(f)


import math
q = int(input())
a = set()
a.add(0)
d = {}
for _ in range(q):
	s = input()
	x = int(s[2:])
	if s[0] == '+':
		a.add(x)
	else:
		k = x
		if x in d:
			k = d[x]
			while k in a:
				k += x
			d[x] = k
		else:
			while k in a:
				k += x
			d[x] = k
		print(k)


(a, b) = (dict(), dict())
for _ in range(int(input())):
	(s, x) = list(input().split())
	x = int(x)
	if s == '+':
		a[x] = True
	else:
		if x in b:
			y = b[x]
		else:
			y = x
		while y in a:
			y += x
		b[x] = y
		print(y)


import math
l = set()
d = {}
t = int(input())
for i in range(t):
	(znak, a) = input().split()
	a = int(a)
	if znak == '+':
		l.add(a)
	else:
		if d.get(a) == None:
			res = a
		else:
			res = d.get(a)
		while res in l:
			res += a
		print(res)
		d[a] = res


T = int(input())
s = {0}
d = {}
for _ in range(T):
	(ch, n) = input().split()
	n = int(n)
	if ch == '+':
		s.add(n)
	elif ch == '?':
		if n not in d:
			d[n] = n
		while d[n] in s:
			d[n] += n
		print(d[n])


s = set()
kmex = dict()
for _ in range(int(input())):
	(a, b) = input().split()
	b = int(b)
	if a == '+':
		s.add(b)
	else:
		b = int(b)
		if b not in kmex:
			kmex[b] = b
		while kmex[b] in s:
			kmex[b] += b
		print(kmex[b])


dic = {}
for jj in range(int(input())):
	(a, b) = input().split()
	k = int(b)
	if a == '+':
		dic[k] = 0
		for i in range(k, 10 ** 37, k):
			if i not in dic:
				dic[k] = i
				break
	elif k not in dic:
		print(k)
	else:
		for i in range(dic[k], 10 ** 37, k):
			if i not in dic:
				dic[k] = i
				print(i)
				break


s = set()
d = {}
s.add(0)
for _ in range(int(input())):
	(sign, x) = map(str, input().split())
	x = int(x)
	if sign == '+':
		s.add(x)
	else:
		if x not in d:
			d[x] = x
		while d[x] in s:
			d[x] += x
		print(d[x])


n = int(input())
HashSet = set()
HashMap = dict()
for i in range(n):
	(operator, num) = map(str, input().split())
	if operator == '+':
		HashSet.add(int(num))
	else:
		num = int(num)
		if num not in HashMap:
			HashMap[num] = num
		while HashMap[num] in HashSet:
			HashMap[num] += num
		print(HashMap[num])


s = set()
d = {}
for _ in range(int(input())):
	(c, a) = input().split()
	a = int(a)
	if c == '+':
		s.add(a)
	else:
		bg = 1
		if a in d.keys():
			bg = d[a]
		for i in range(bg, 100000000):
			if a * i not in s:
				print(a * i)
				d[a] = i
				break


a = int(input())
s = set()
sl = {}
s.add(0)
sp = []
for i in range(a):
	x = input()
	ni = 0
	x1 = ''
	x2 = ''
	for j in x:
		if j != ' ' and x[0] != '?' and (j != x[0]):
			x1 += j
			ni += 1
		elif j != ' ' and x[0] != '+' and (j != x[0]):
			x2 += j
	if ni >= 1:
		x11 = int(x1)
		s.add(x11)
	else:
		x12 = int(x2)
		if x12 in sl:
			na = sl[x12]
		else:
			na = x12
		while na in s:
			na += x12
		sp.append(na)
		sl[x12] = na
for i in sp:
	print(i)