We're going to make our own Contacts application! The application must perform two types of operations:

add name, where $name$ is a string denoting a contact name. This must store $name$ as a new contact in the application.  
find partial, where $partial$ is a string denoting a partial name to search the application for. It must count the number of contacts starting with $partial$ and print the count on a new line.

Given $n$ sequential add and find operations, perform each operation in order.

Example 

Operations are requested as follows:

add ed
add eddie
add edward
find ed
add edwina
find edw
find a

Three $\boldsymbol{add}$ operations include the names 'ed', 'eddie', and 'edward'.  Next, $\textbf{find ed}$ matches all $3$ names.  Note that it matches and counts the entire name 'ed'.  Next, add 'edwina' and then find 'edw'.  $2$ names match: 'edward' and 'edwina'.  In the final operation, there are $0$ names that start with 'a'.  Return the array $[3,2,0]$.  

Function Description   

Complete the contacts function below.  

contacts has the following parameters:

string queries[n]: the operations to perform   

Returns  

int[]: the results of each find operation  

Input Format

The first line contains a single integer, $n$, the number of operations to perform (the size of $\textit{queries[]}$). 

Each of the following $n$ lines contains a string, $\textit{queries}[i]$.  

Constraints

$1\leq n\leq10^5$  
$1\leq\textsf{length of}\:\:name\leq21$  
$1\leq\textsf{length of partial}\leq21$  
$name$ and $partial$ contain lowercase English letters only.
The input does not have any duplicate $name$ for the $\boldsymbol{add}$ operation.

Sample Input
STDIN           Function
-----           --------
4               queries[] size n = 4
add hack        queries = ['add hack', 'add hackerrank', 'find hac', 'find hak']
add hackerrank
find hac
find hak

Sample Output
2
0

Explanation

Add a contact named hack.
Add a contact named hackerrank.
Find the number of contact names beginning with hac. Both name start with hac, add $2$ to the return array.
Find the number of contact names beginning with hak. neither name starts with hak, add $0$ to the return array.

Difficulty: MEDIUM
Tags: String algorithms

Starter code:

Solutions:
import sys
import time
import queue

class Node:
	__slots__ = ['is_leaf', 'value', 'left', 'right', 'mid', 'count']

	def __str__(self):
		return 'value: ' + self.value + ', mid: ' + str(self.mid) + ', left: ' + str(self.left) + ', right: ' + str(self.right)

	def __init__(self):
		self.is_leaf = False
		self.value = None
		self.left = None
		self.right = None
		self.mid = None
		self.count = 0

	def insert(self, word):
		if len(word) == 0:
			return
		if self.value is None:
			self.count = self.count + 1
			self.value = word[0]
			if len(word) == 1:
				self.is_leaf = True
			else:
				if self.mid is None:
					self.mid = Node()
				self.mid.insert(word[1:])
		elif self.value == word[0]:
			self.count = self.count + 1
			if self.mid is None:
				self.mid = Node()
			self.mid.insert(word[1:])
		elif self.value > word[0]:
			if self.left is None:
				self.left = Node()
			self.left.insert(word)
		else:
			if self.right is None:
				self.right = Node()
			self.right.insert(word)

	def words(self):
		words = 0
		nodes_to_check = queue.Queue()
		nodes_to_check.put((self, ''))
		while not nodes_to_check.empty():
			node_prefix = nodes_to_check.get()
			curr_node = node_prefix[0]
			curr_prefix = node_prefix[1]
			if curr_node.value is not None:
				curr_prefix = curr_prefix + curr_node.value
			if curr_node.is_leaf:
				words = words + 1
			if curr_node.mid is not None:
				nodes_to_check.put((curr_node.mid, curr_prefix))
			if curr_node.left is not None:
				nodes_to_check.put((curr_node.left, node_prefix[1]))
			if curr_node.right is not None:
				nodes_to_check.put((curr_node.right, node_prefix[1]))
		return words

	def start_with(self, word):
		parent = None
		root = self
		for char in word:
			if root is None:
				parent = None
			else:
				while root is not None and root.value is not None and (char != root.value):
					if char < root.value:
						root = root.left
					else:
						root = root.right
				if root is not None and char == root.value:
					parent = root
					root = root.mid
				else:
					parent = None
		if parent is None:
			return 0
		else:
			return parent.count
tree = Node()
for line in sys.stdin:
	line = line.replace('\n', '')
	if line.startswith('add'):
		word = line[4:]
		tree.insert(word)
	elif line.startswith('find'):
		word = line[5:]
		print(tree.start_with(word))