For a dictionary $M$ that stores elements formed by a pair of a string key and an integer value, perform a sequence of the following operations. Note that each key in $M$ must be unique.

* insert($key$, $x$): Insert an element formed by a pair of $key$ and $x$ to $M$. If there is an element with $key$, replace the corresponding value with $x$.
* get($key$): Print the value with the specified $key$.

Constraints

* $1 \leq q \leq 200,000$
* $1 \leq x \leq 1,000,000,000$
* $1 \leq $ length of $key$ $ \leq 20$
* $key$ consits of lower-case letter
* For a get operation, the element with the specified key exists in $M$.

Input

The input is given in the following format.


$q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $key$ $x$


or


1 $key$


where the first digits 0, 1 and 2 represent insert and get operations respectively.

Output

For each get operation, print an integer in a line.

Example

Input

7
0 blue 4
0 red 1
0 white 5
1 red
1 blue
0 black 8
1 black


Output

1
4
8

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from collections import defaultdict

def main():
	q = int(input())
	d = defaultdict(int)
	for _ in range(q):
		para = input().split()
		if para[0] == '0':
			d[para[1]] = int(para[2])
		elif para[0] == '1':
			print(d[para[1]])
main()


class Node:

	def __init__(self, key, value):
		self.value = value
		self.key = key
		self.next = None

class HashMap:

	def __init__(self):
		self.k = 2
		self.size = self.k * self.k - 1
		self.count = 0
		self.nodes = [None] * self.size

	def __getitem__(self, key):
		node = self.nodes[self.hash(key)]
		while node is not None and node.key != key:
			node = node.next
		if node is not None:
			return node.value
		else:
			return None

	def __setitem__(self, key, value):
		i = self.hash(key)
		node = self.nodes[i]
		if node is None:
			self.nodes[i] = Node(key, value)
			self.count += 1
		else:
			while node.next is not None and node.key != key:
				node = node.next
			if node.key == key:
				node.value = value
			else:
				node.next = Node(key, value)
				self.count += 1
		if self.count == self.size:
			self._resize(self.k + 1)

	def __len__(self):
		return self.count

	def hash(self, key):
		return hash(key) % self.size

	def _resize(self, k):
		nodes = self.nodes
		self.size = 2 ** k - 1
		self.k = k
		self.nodes = [None] * self.size
		for node in nodes:
			n = node
			while n is not None:
				self.__setitem__(n.key, n.value)
				n = n.next

def run():
	q = int(input())
	m = HashMap()
	for _ in range(q):
		(command, *args) = input().split()
		if command == '0':
			key = args[0]
			value = int(args[1])
			m[key] = value
		elif command == '1':
			key = args[0]
			print(m[key])
		else:
			raise ValueError('invalid command')
run()


d = {}
q = int(input())
for i in range(q):
	a = list(input().split())
	if a[0] == '0':
		d[a[1]] = int(a[2])
	else:
		print(d[a[1]])


q = int(input())
dict = {}
for i in range(q):
	a = input().split()
	if a[0] == '0':
		dict[a[1]] = a[2]
	elif a[0] == '1':
		print(dict[a[1]])


q = int(input())
M = {}
for i in range(q):
	query = input().split()
	if query[0] == '0':
		M[query[1]] = query[2]
	else:
		print(M[query[1]])


dict = {}
q = int(input())
for i in range(q):
	(query, *val) = input().split(' ')
	if query == '0':
		dict[val[0]] = int(val[1])
	else:
		print(dict.get(val[0]))


import bisect
keys = []
q = int(input())
d = {}

def find(x):
	index = bisect.bisect_left(keys, x)
	if index == len(keys):
		return -1
	if keys[index] == x:
		return index
	else:
		return -1
for _ in range(q):
	query = input().split(' ')
	if query[0] == '0':
		if find(query[1]) != -1:
			pass
		else:
			bisect.insort_left(keys, query[1])
		d[query[1]] = query[2]
	elif query[0] == '1':
		if find(query[1]) != -1:
			print(d[query[1]])
		else:
			print(0)


def resolve():
	import sys
	input = sys.stdin.readline
	n = int(input())
	ans = dict()
	for _ in range(n):
		(q, key, *x) = input().split()
		if q == '0':
			ans[key] = x[0]
		else:
			print(ans[key])
resolve()


def main():
	q = int(input())
	d = {}
	for i in range(q):
		query = input()
		cmd = int(query[0])
		if cmd == 0:
			(_, k, v) = query.split(' ')
			v = int(v)
			d[k] = v
		elif cmd == 1:
			(_, k) = query.split(' ')
			v = d.get(k, None)
			if v:
				print(v)
main()


n = int(input())
d = {}
for i in range(n):
	cmd = input().split()
	if cmd[0] == '0':
		d[cmd[1]] = cmd[2]
	elif cmd[0] == '1':
		print(d[cmd[1]])


dic = {}
for i in range(int(input())):
	query = input().split()
	if query[0] == '0':
		dic[query[1]] = query[2]
	else:
		print(dic[query[1]])


D = {}
q = int(input())
for i in range(q):
	L = input().split()
	if L[0] == '0':
		(key, x) = (L[1], L[2])
		D[key] = x
	else:
		key = L[1]
		print(D[key])


import sys
n = int(input())
dic = {}
for i in range(n):
	(a, b, *c) = sys.stdin.readline().split()
	if a == '0':
		dic[b] = int(c[0])
	else:
		print(dic[b])


d = {}
for _ in range(int(input())):
	(op, key, x) = (input().split() + [''])[:3]
	if op == '0':
		d[key] = x
	else:
		print(d[key])


dict = {}
q = int(input())
for i in range(q):
	a = list(input().split())
	if a[0] == '0':
		dict[a[1]] = int(a[2])
	else:
		print(dict[a[1]])


dict = {}
q = int(input())
for i in range(q):
	a = list(input().split())
	if a[0] == '0':
		dict[a[1]] = int(a[2])
	else:
		print(dict[a[1]])


n = int(input())
dic = {}
for i in range(n):
	(q, *args) = map(str, input().split())
	key = args[0]
	val = args[0]
	if q == '0':
		val = int(args[1])
		dic[key] = val
	elif q == '1':
		print(dic[key])


n = int(input())
d = dict()
for i in range(n):
	q = input().split()
	if q[0] == '0':
		d[q[1]] = int(q[2])
	elif q[0] == '1':
		print(d[q[1]])


dict = {}
q = int(input())
for i in range(q):
	line = input().split()
	if line[0] == '0':
		dict[line[1]] = int(line[2])
	elif line[0] == '1':
		print(dict[line[1]])


d = dict()
for _ in range(int(input())):
	(op, key, x) = (input() + ' 1').split()[:3]
	if op == '0':
		d[key] = x
	else:
		print(d[key])


dict = {}
q = int(input())
for i in range(q):
	query = list(input().split())
	operation = query[0]
	key = query[1]
	if operation == '0':
		value = int(query[2])
		dict[key] = value
	else:
		print(dict[key])


dic = {}
for i in range(int(input())):
	order = list(input().split())
	if order[0] == '0':
		if order[1] in dic:
			dic[order[1]] = int(order[2])
		else:
			dic[order[1]] = int(order[2])
	else:
		print(dic[order[1]])


from collections import defaultdict
num_query = int(input())
d: defaultdict = defaultdict()
for _ in range(num_query):
	(op, *v) = input().split()
	if '0' == op:
		d[v[0]] = v[1]
	else:
		print(d[v[0]])


import os
import sys

def main():
	q = int(input())
	dictionary = dict()
	for _ in range(q):
		command = list(input().split())
		if int(command[0]) == 0:
			dictionary[command[1]] = int(command[2])
		else:
			print(dictionary[command[1]])
main()


q = int(input())
M = {}
for i in range(q):
	(query, *inp) = input().split()
	key = inp[0]
	if query == '0':
		x = int(inp[1])
		M[key] = x
	else:
		print(M[key])


import sys
d = {}
input()
for q in sys.stdin:
	q = q.split()
	if q[0] == '0':
		d[q[1]] = q[2]
	else:
		print(d[q[1]])


M = {}
q = int(input())
for _ in range(q):
	(command, *list_num) = input().split()
	if command == '0':
		key = list_num[0]
		x = int(list_num[1])
		M[key] = x
	elif command == '1':
		key = list_num[0]
		print(M[key])
	else:
		raise


d = {}
for _ in range(int(input())):
	a = list(input().split())
	if a[0] == '0':
		d[a[1]] = a[2]
	else:
		print(d[a[1]])


n = int(input())
dic = {}
for _ in range(n):
	com = input().split()
	if com[0] == '0':
		dic[com[1]] = com[2]
	else:
		print(dic[com[1]])


dictionary = dict()
for i in range(int(input())):
	query = [i for i in input().split()]
	if query[0] == '0':
		dictionary.update({query[1]: query[2]})
	elif query[0] == '1':
		print(dictionary[query[1]])


dict = {}
q = int(input())
for i in range(q):
	a = list(input().split())
	if a[0] == '0':
		dict[a[1]] = int(a[2])
	else:
		print(dict[a[1]])


import sys
n = int(input())
d = {}
lines = sys.stdin.readlines()
ans = [None] * n
for i in range(n):
	(q, *arg) = lines[i].split()
	if q == '0':
		d[arg[0]] = arg[1]
	elif q == '1':
		ans[i] = d[arg[0]]
[print(x) for x in ans if x is not None]


import bisect
D = []
N = []
count = 0

def insert(D, N, count, key, x):
	y = bisect.bisect_left(D, key)
	if y < count and D[y] == key:
		N[y] = x
	else:
		D.insert(y, key)
		N.insert(y, x)
		count += 1
	return (D, N, count)

def get(D, N, key):
	y = bisect.bisect_left(D, key)
	print(N[y])
q = int(input())
for i in range(q):
	query = list(map(str, input().split()))
	query[0] = int(query[0])
	if query[0] == 0:
		(D, N, count) = insert(D, N, count, query[1], int(query[2]))
	else:
		get(D, N, query[1])


q = int(input())
d = {}
for _ in range(q):
	command = list(map(str, input().split()))
	query = int(command[0])
	key = command[1]
	if query == 0:
		d[key] = int(command[2])
	else:
		print(d[key])


q = int(input())
dct = {}
for _ in range(q):
	cmmd = input().split()
	if cmmd[0] == '0':
		dct[cmmd[1]] = int(cmmd[2])
	else:
		print(dct[cmmd[1]])


readline = open(0).readline
Q = int(readline())
ans = []
M = {}
C = [M.__setitem__, lambda key, push=ans.append: push('%s\n' % M[key])].__getitem__
for q in range(Q):
	(t, *a) = readline().split()
	C(int(t))(*a)
open(1, 'w').writelines(ans)


di = {}
for _ in range(int(input())):
	line = input().split()
	if line[0] == '0':
		di[line[1]] = line[2]
	else:
		print(di[line[1]])


n = int(input())
dic = {}
a = [None] * n
for i in range(n):
	(c, key, val) = (input() + ' 0').split()[:3]
	if c == '0':
		dic[key] = val
	else:
		a[i] = dic[key]
for x in a:
	if x is not None:
		print(x)