"""Original Unicode dictionary trie; prefix path is not terminal membership."""
import json
def valid(s):
 if type(s) is not str or len(s)>16:raise ValueError('literal Unicode string <=16 codepoints')
class Trie:
 def __init__(self):self.nodes=[{'terminal':False,'children':{}}]
 def add(self,word):
  valid(word);i=0
  for c in word:
   if c not in self.nodes[i]['children']:
    self.nodes[i]['children'][c]=len(self.nodes);self.nodes.append({'terminal':False,'children':{}})
   i=self.nodes[i]['children'][c]
  self.nodes[i]['terminal']=True
 def path(self,s):
  valid(s);i=0;trace=[0]
  for c in s:
   if c not in self.nodes[i]['children']:return None,trace
   i=self.nodes[i]['children'][c];trace.append(i)
  return i,trace
 def contains(self,s):
  i,_=self.path(s);return i is not None and self.nodes[i]['terminal']
 def prefix(self,p):
  i,_=self.path(p);out=[]
  def walk(index,text):
   if self.nodes[index]['terminal']:out.append(text)
   for c,j in sorted(self.nodes[index]['children'].items()):walk(j,text+c)
  if i is not None:walk(i,p)
  return out
def demo():
 words=['کار','کاربر','کارگاه','کارت','ی','ي','می\u200cروم','میروم',''];t=Trie()
 for w in words:t.add(w)
 size=len(t.nodes);t.add('کار');assert len(t.nodes)==size
 queries=sorted({w[:i] for w in words for i in range(len(w)+1)}|{'کارب','کتاب','x','می'});rows=[]
 for p in queries:
  index,path=t.path(p);actual=t.prefix(p);expected=sorted(w for w in set(words) if w.startswith(p));assert actual==expected and t.contains(p)==(p in set(words));rows.append({'query':p,'path_indices':path,'path_exists':index is not None,'exact_member':t.contains(p),'prefix_results':actual})
 witness=next(r for r in rows if r['query']=='کارب');assert witness['path_exists'] and not witness['exact_member'] and witness['prefix_results']==['کاربر']
 assert t.contains('') and t.nodes[0]['terminal'] and t.prefix('ی')==['ی'] and t.prefix('ي')==['ي']
 rejected=[]
 for bad in [True,'x'*17,None]:
  try:t.add(bad)
  except ValueError:rejected.append(repr(bad))
  else:raise AssertionError('expected rejection')
 return {'words':words,'node_table':t.nodes,'all_actual_prefix_and_missing_queries':rows,'query_count':len(rows),'nonterminal_path_witness':witness,'duplicate_insert_is_idempotent':True,'empty_word_is_explicit_root_terminal':True,'order':'Python Unicode codepoint lexical order, not Persian dictionary collation','normalization':'none; Persian/Arabic yeh and ZWNJ remain distinct','rejected':rejected,'scope':'fixed authored dictionary prefix retrieval; no failure links/text scanning/semantic autocomplete/product search'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))