class TranspositionTable:
	def __init__(self,capacity=2**20):
		self._capacity=capacity
		self._table=[None]*capacity

	def put(self,key,val):
		self._table[key%self._capacity]=(key,val)

	def get(self,key):
		res=self._table[key%self._capacity]
		if res is None: return None
		elif res[0]==key: return res[1]
		else: return None