code: 
  
  
  
  
  '''simple docstring'''
  
  
  
  
  
  from __future__ import annotations
  
  import unittest
  from collections.abc import Iterator
  
  
  
  
  
  
  class 						lowercase     :
  
  
  
  
  
  
        def __init__(self ,  a__ ,  a__					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				str       						= label
           SCREAMING_SNAKE_CASE__			:				Any       						= parent
           SCREAMING_SNAKE_CASE__			:				Node | None       						= None
           SCREAMING_SNAKE_CASE__			:				Node | None       						= None
  
  
  
  
  
  
  class 						lowercase     :
  
  
  
  
  
  
        def __init__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Node | None       						= None
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Union[str, Any]       						= None
  
  
  
  
  
  
        def    A__(self					)       ->   bool:
           return self.root is None
  
  
  
  
  
  
        def    A__(self ,  a__					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Any       						= self._put(self.root ,  a__					)
  
  
  
  
  
  
        def    A__(self ,  a__ ,  a__ ,  a__ = None					)       ->   Node:
           if node is None:
              SCREAMING_SNAKE_CASE__			:				int       						= Node(a__ ,  a__					)
           else:
              if label < node.label:
                 SCREAMING_SNAKE_CASE__			:				Optional[int]       						= self._put(node.left ,  a__ ,  a__					)
              elif label > node.label:
                 SCREAMING_SNAKE_CASE__			:				List[str]       						= self._put(node.right ,  a__ ,  a__					)
              else:
                 SCREAMING_SNAKE_CASE__			:				Optional[int]       						= f"""Node with label {label} already exists"""
                 raise Exception(a__					)
  
           return node
  
  
  
  
  
  
        def    A__(self ,  a__					)       ->   Node:
           return self._search(self.root ,  a__					)
  
  
  
  
  
  
        def    A__(self ,  a__ ,  a__					)       ->   Node:
           if node is None:
              SCREAMING_SNAKE_CASE__			:				Any       						= f"""Node with label {label} does not exist"""
              raise Exception(a__					)
           else:
              if label < node.label:
                 SCREAMING_SNAKE_CASE__			:				Tuple       						= self._search(node.left ,  a__					)
              elif label > node.label:
                 SCREAMING_SNAKE_CASE__			:				Optional[int]       						= self._search(node.right ,  a__					)
  
           return node
  
  
  
  
  
  
        def    A__(self ,  a__					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Optional[int]       						= self.search(a__					)
           if node.right and node.left:
              SCREAMING_SNAKE_CASE__			:				Tuple       						= self._get_lowest_node(node.right					)
              SCREAMING_SNAKE_CASE__			:				Tuple       						= node.left
              SCREAMING_SNAKE_CASE__			:				Any       						= node.right
              SCREAMING_SNAKE_CASE__			:				Optional[Any]       						= lowest_node
              if node.right:
                 SCREAMING_SNAKE_CASE__			:				List[Any]       						= lowest_node
              self._reassign_nodes(a__ ,  a__					)
           elif not node.right and node.left:
              self._reassign_nodes(a__ ,  node.left					)
           elif node.right and not node.left:
              self._reassign_nodes(a__ ,  node.right					)
           else:
              self._reassign_nodes(a__ ,  a__					)
  
  
  
  
  
  
        def    A__(self ,  a__ ,  a__					)       ->   None:
           if new_children:
              SCREAMING_SNAKE_CASE__			:				List[Any]       						= node.parent
  
           if node.parent:
              if node.parent.right == node:
                 SCREAMING_SNAKE_CASE__			:				Optional[int]       						= new_children
              else:
                 SCREAMING_SNAKE_CASE__			:				Dict       						= new_children
           else:
              SCREAMING_SNAKE_CASE__			:				List[str]       						= new_children
  
  
  
  
  
  
        def    A__(self ,  a__					)       ->   Node:
           if node.left:
              SCREAMING_SNAKE_CASE__			:				int       						= self._get_lowest_node(node.left					)
           else:
              SCREAMING_SNAKE_CASE__			:				Tuple       						= node
              self._reassign_nodes(a__ ,  node.right					)
  
           return lowest_node
  
  
  
  
  
  
        def    A__(self ,  a__					)       ->   bool:
           try:
              self.search(a__					)
              return True
           except Exception:
              return False
  
  
  
  
  
  
        def    A__(self					)       ->   int:
           if self.root is None:
              raise Exception('''Binary search tree is empty'''					)
  
           SCREAMING_SNAKE_CASE__			:				List[str]       						= self.root
           while node.right is not None:
              SCREAMING_SNAKE_CASE__			:				Optional[int]       						= node.right
  
           return node.label
  
  
  
  
  
  
        def    A__(self					)       ->   int:
           if self.root is None:
              raise Exception('''Binary search tree is empty'''					)
  
           SCREAMING_SNAKE_CASE__			:				Tuple       						= self.root
           while node.left is not None:
              SCREAMING_SNAKE_CASE__			:				Any       						= node.left
  
           return node.label
  
  
  
  
  
  
        def    A__(self					)       ->   Iterator[Node]:
           return self._inorder_traversal(self.root					)
  
  
  
  
  
  
        def    A__(self ,  a__					)       ->   Iterator[Node]:
           if node is not None:
              yield from self._inorder_traversal(node.left					)
              yield node
              yield from self._inorder_traversal(node.right					)
  
  
  
  
  
  
        def    A__(self					)       ->   Iterator[Node]:
           return self._preorder_traversal(self.root					)
  
  
  
  
  
  
        def    A__(self ,  a__					)       ->   Iterator[Node]:
           if node is not None:
              yield node
              yield from self._preorder_traversal(node.left					)
              yield from self._preorder_traversal(node.right					)
  
  
  
  
  
  
  class 						lowercase     (   unittest.TestCase):
  
  
  
  
  
  
        @staticmethod
        def    A__()       ->   BinarySearchTree:
           SCREAMING_SNAKE_CASE__			:				Dict       						= BinarySearchTree()
           t.put(8					)
           t.put(3					)
           t.put(6					)
           t.put(1					)
           t.put(1_0					)
           t.put(1_4					)
           t.put(1_3					)
           t.put(4					)
           t.put(7					)
           t.put(5					)
  
           return t
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Optional[int]       						= BinarySearchTree()
           assert t.is_empty()
  
           t.put(8					)
           assert t.root is not None
           assert t.root.parent is None
           assert t.root.label == 8
  
           t.put(1_0					)
           assert t.root.right is not None
           assert t.root.right.parent == t.root
           assert t.root.right.label == 1_0
  
           t.put(3					)
           assert t.root.left is not None
           assert t.root.left.parent == t.root
           assert t.root.left.label == 3
  
           t.put(6					)
           assert t.root.left.right is not None
           assert t.root.left.right.parent == t.root.left
           assert t.root.left.right.label == 6
  
           t.put(1					)
           assert t.root.left.left is not None
           assert t.root.left.left.parent == t.root.left
           assert t.root.left.left.label == 1
  
           with self.assertRaises(a__					):  # noqa: B017
              t.put(1					)
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Optional[int]       						= self._get_binary_search_tree()
  
           SCREAMING_SNAKE_CASE__			:				str       						= t.search(6					)
           assert node.label == 6
  
           SCREAMING_SNAKE_CASE__			:				Optional[Any]       						= t.search(1_3					)
           assert node.label == 1_3
  
           with self.assertRaises(a__					):  # noqa: B017
              t.search(2					)
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Tuple       						= self._get_binary_search_tree()
  
           t.remove(1_3					)
           assert t.root is not None
           assert t.root.right is not None
           assert t.root.right.right is not None
           assert t.root.right.right.right is None
           assert t.root.right.right.left is None
  
           t.remove(7					)
           assert t.root.left is not None
           assert t.root.left.right is not None
           assert t.root.left.right.left is not None
           assert t.root.left.right.right is None
           assert t.root.left.right.left.label == 4
  
           t.remove(6					)
           assert t.root.left.left is not None
           assert t.root.left.right.right is not None
           assert t.root.left.left.label == 1
           assert t.root.left.right.label == 4
           assert t.root.left.right.right.label == 5
           assert t.root.left.right.left is None
           assert t.root.left.left.parent == t.root.left
           assert t.root.left.right.parent == t.root.left
  
           t.remove(3					)
           assert t.root is not None
           assert t.root.left.label == 4
           assert t.root.left.right.label == 5
           assert t.root.left.left.label == 1
           assert t.root.left.parent == t.root
           assert t.root.left.left.parent == t.root.left
           assert t.root.left.right.parent == t.root.left
  
           t.remove(4					)
           assert t.root.left is not None
           assert t.root.left.left is not None
           assert t.root.left.label == 5
           assert t.root.left.right is None
           assert t.root.left.left.label == 1
           assert t.root.left.parent == t.root
           assert t.root.left.left.parent == t.root.left
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				int       						= self._get_binary_search_tree()
  
           t.remove(3					)
           assert t.root is not None
           assert t.root.left is not None
           assert t.root.left.left is not None
           assert t.root.left.right is not None
           assert t.root.left.right.left is not None
           assert t.root.left.right.right is not None
           assert t.root.left.label == 4
           assert t.root.left.right.label == 6
           assert t.root.left.left.label == 1
           assert t.root.left.right.right.label == 7
           assert t.root.left.right.left.label == 5
           assert t.root.left.parent == t.root
           assert t.root.left.right.parent == t.root.left
           assert t.root.left.left.parent == t.root.left
           assert t.root.left.right.left.parent == t.root.left.right
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Optional[Any]       						= self._get_binary_search_tree()
           t.empty()
           assert t.root is None
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				str       						= self._get_binary_search_tree()
           assert not t.is_empty()
  
           t.empty()
           assert t.is_empty()
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Dict       						= self._get_binary_search_tree()
  
           assert t.exists(6					)
           assert not t.exists(-1					)
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Tuple       						= self._get_binary_search_tree()
  
           assert t.get_max_label() == 1_4
  
           t.empty()
           with self.assertRaises(a__					):  # noqa: B017
              t.get_max_label()
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Dict       						= self._get_binary_search_tree()
  
           assert t.get_min_label() == 1
  
           t.empty()
           with self.assertRaises(a__					):  # noqa: B017
              t.get_min_label()
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Tuple       						= self._get_binary_search_tree()
  
           SCREAMING_SNAKE_CASE__			:				Any       						= [i.label for i in t.inorder_traversal()]
           assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]
  
  
  
  
  
  
        def    A__(self					)       ->   None:
           SCREAMING_SNAKE_CASE__			:				Dict       						= self._get_binary_search_tree()
  
           SCREAMING_SNAKE_CASE__			:				Optional[int]       						= [i.label for i in t.preorder_traversal()]
           assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]
  
  
  def 				UpperCamelCase	(  ):
  
  
  
  
     '''simple docstring'''
  
     SCREAMING_SNAKE_CASE__			:				List[str]       						= BinarySearchTree()
     t.put(8   )
     t.put(3   )
     t.put(6   )
     t.put(1   )
     t.put(10   )
     t.put(14   )
     t.put(13   )
     t.put(4   )
     t.put(7   )
     t.put(5   )
  
     print(
         '''
              8
             / \\
            3   10
           / \\    \\
          1   6    14
             / \\   /
            4   7 13
             \\
              5
          '''   )
  
     print('''Label 6 exists:'''	,     t.exists(6   )   )
     print('''Label 13 exists:'''	,     t.exists(13   )   )
     print('''Label -1 exists:'''	,     t.exists(-1   )   )
     print('''Label 12 exists:'''	,     t.exists(12   )   )
  
     # Prints all the elements of the list in inorder traversal
     SCREAMING_SNAKE_CASE__			:				int       						= [i.label for i in t.inorder_traversal()]
     print('''Inorder traversal:'''	,     snake_case   )
  
     # Prints all the elements of the list in preorder traversal
     SCREAMING_SNAKE_CASE__			:				List[str]       						= [i.label for i in t.preorder_traversal()]
     print('''Preorder traversal:'''	,     snake_case   )
  
     print('''Max. label:'''	,     t.get_max_label()   )
     print('''Min. label:'''	,     t.get_min_label()   )
  
     # Delete elements
     print('''\nDeleting elements 13, 10, 8, 3, 6, 14'''   )
     print(
         '''
            4
           / \\
          1   7
               \\
                5
          '''   )
     t.remove(13   )
     t.remove(10   )
     t.remove(8   )
     t.remove(3   )
     t.remove(6   )
     t.remove(14   )
  
     # Prints all the elements of the list in inorder traversal after delete
     SCREAMING_SNAKE_CASE__			:				int       						= [i.label for i in t.inorder_traversal()]
     print('''Inorder traversal after delete:'''	,     snake_case   )
  
     # Prints all the elements of the list in preorder traversal after delete
     SCREAMING_SNAKE_CASE__			:				int       						= [i.label for i in t.preorder_traversal()]
     print('''Preorder traversal after delete:'''	,     snake_case   )
  
     print('''Max. label:'''	,     t.get_max_label()   )
     print('''Min. label:'''	,     t.get_min_label()   )
  
  
  if __name__ == "__main__":
         binary_search_tree_example()
  
  
style_context: 
  
  
  
  
  '''simple docstring'''
  
  
  
  
  
  import argparse
  import json
  import re
  import string
  import sys
  from collections import Counter
  
  
  def 				UpperCamelCase	(  snake_case   ):
  
  
  
  
     '''simple docstring'''
  
     def remove_articles(snake_case   ):
        return re.sub(R'''\b(a|an|the)\b'''	,     ''' '''	,     snake_case   )
  
     def white_space_fix(snake_case   ):
        return " ".join(text.split()   )
  
     def remove_punc(snake_case   ):
        SCREAMING_SNAKE_CASE__			:				Optional[int]       						= set(string.punctuation   )
        return "".join(ch for ch in text if ch not in exclude   )
  
     def lower(snake_case   ):
        return text.lower()
  
     return white_space_fix(remove_articles(remove_punc(lower(snake_case   )   )   )   )
  
  
  def 				UpperCamelCase	(  snake_case	,     snake_case   ):
  
  
  
  
     '''simple docstring'''
  
     SCREAMING_SNAKE_CASE__			:				Tuple       						= normalize_answer(snake_case   ).split()
     SCREAMING_SNAKE_CASE__			:				List[Any]       						= normalize_answer(snake_case   ).split()
     SCREAMING_SNAKE_CASE__			:				Dict       						= Counter(snake_case   ) & Counter(snake_case   )
     SCREAMING_SNAKE_CASE__			:				int       						= sum(common.values()   )
     if num_same == 0:
        return 0
     SCREAMING_SNAKE_CASE__			:				Tuple       						= 1.0 * num_same / len(snake_case   )
     SCREAMING_SNAKE_CASE__			:				Tuple       						= 1.0 * num_same / len(snake_case   )
     SCREAMING_SNAKE_CASE__			:				Optional[Any]       						= (2 * precision * recall) / (precision + recall)
     return fa
  
  
  def 				UpperCamelCase	(  snake_case	,     snake_case   ):
  
  
  
  
     '''simple docstring'''
  
     return normalize_answer(snake_case   ) == normalize_answer(snake_case   )
  
  
  def 				UpperCamelCase	(  snake_case	,     snake_case	,     snake_case   ):
  
  
  
  
     '''simple docstring'''
  
     SCREAMING_SNAKE_CASE__			:				Any       						= []
     for ground_truth in ground_truths:
        SCREAMING_SNAKE_CASE__			:				List[Any]       						= metric_fn(snake_case	,     snake_case   )
        scores_for_ground_truths.append(snake_case   )
     return max(snake_case   )
  
  
  def 				UpperCamelCase	(  snake_case	,     snake_case   ):
  
  
  
  
     '''simple docstring'''
  
     SCREAMING_SNAKE_CASE__			:				str       						= 0
     SCREAMING_SNAKE_CASE__			:				Optional[int]       						= []
     for passage in dataset:
        for qa in passage["qas"]:
           total += 1
           if qa["id"] not in predictions:
              SCREAMING_SNAKE_CASE__			:				Any       						= f"""Unanswered question {qa["id"]} will receive score 0."""
              print(snake_case	,     file=sys.stderr   )
              continue
  
           SCREAMING_SNAKE_CASE__			:				Union[str, Any]       						= [x['''text'''] for x in qa['''answers''']]
           SCREAMING_SNAKE_CASE__			:				Optional[int]       						= predictions[qa['''id''']]
  
           SCREAMING_SNAKE_CASE__			:				List[str]       						= metric_max_over_ground_truths(snake_case	,     snake_case	,     snake_case   )
           if int(_exact_match   ) == 1:
              correct_ids.append(qa['''id''']   )
           exact_match += _exact_match
  
           fa += metric_max_over_ground_truths(snake_case	,     snake_case	,     snake_case   )
  
     SCREAMING_SNAKE_CASE__			:				int       						= exact_match / total
     SCREAMING_SNAKE_CASE__			:				Optional[int]       						= fa / total
  
     return {"exact_match": exact_match, "f1": fa}, correct_ids
  
  
  if __name__ == "__main__":
         lowercase__			=	'''1.0'''
         lowercase__			=	argparse.ArgumentParser('''Official evaluation script for ReCoRD v1.0.''')
         parser.add_argument('''data_file''', help='''The dataset file in JSON format.''')
         parser.add_argument('''pred_file''', help='''The model prediction file in JSON format.''')
         parser.add_argument('''--output_correct_ids''', action='''store_true''', help='''Output the correctly answered query IDs.''')
         lowercase__			=	parser.parse_args()
  
         with open(args.data_file) as data_file:
                lowercase__			=	json.load(data_file)
                if dataset_json["version"] != expected_version:
                       print(
                           F"Evaluation expects v-{expected_version}, but got dataset with v-{dataset_json['version']}",
                           file=sys.stderr,
                       )
                lowercase__			=	dataset_json['''data''']
  
         with open(args.pred_file) as pred_file:
                lowercase__			=	json.load(pred_file)
  
         lowercase__	,     lowercase__			=	evaluate(dataset, predictions)
  
         if args.output_correct_ids:
                print(F"Output {len(correct_ids)} correctly answered question IDs.")
                with open('''correct_ids.json''', '''w''') as f:
                       json.dump(correct_ids, f)
  
  