





"""simple docstring"""





class 		lowercase :





      def __init__(	self				,						lowercase			)		->					Tuple:
            lowerCAmelCase  						=	val
            # Number of nodes in left subtree
            lowerCAmelCase  						=	0
            lowerCAmelCase  						=	None
            lowerCAmelCase  						=	None
            lowerCAmelCase  						=	None





      def    _snake_case      (	self				,						lowercase			)		->					Tuple:
            assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

            if self.val < other.val:
                  lowerCAmelCase  						=	self.right
                  lowerCAmelCase  						=	None
                  if self.right:
                        lowerCAmelCase  						=	other
                  lowerCAmelCase  						=	other
                  lowerCAmelCase  						=	self.left_tree_size * 2 + 1
                  return self
            else:
                  lowerCAmelCase  						=	other.right
                  lowerCAmelCase  						=	None
                  if other.right:
                        lowerCAmelCase  						=	self
                  lowerCAmelCase  						=	self
                  lowerCAmelCase  						=	other.left_tree_size * 2 + 1
                  return other







class 		lowercase :





      def __init__(	self				,						lowercase=None				,						lowercase=None				,						lowercase=0			)		->					Any:
            lowerCAmelCase  						=	heap_size
            lowerCAmelCase  						=	bottom_root
            lowerCAmelCase  						=	min_node





      def    _snake_case      (	self				,						lowercase			)		->					Dict:

            # Empty heaps corner cases
            if other.size == 0:
                  return None
            if self.size == 0:
                  lowerCAmelCase  						=	other.size
                  lowerCAmelCase  						=	other.bottom_root
                  lowerCAmelCase  						=	other.min_node
                  return None
            # Update size
            lowerCAmelCase  						=	self.size + other.size

            # Update min.node
            if self.min_node.val > other.min_node.val:
                  lowerCAmelCase  						=	other.min_node
            # Merge

            # Order roots by left_subtree_size
            lowerCAmelCase  						=	[]
            lowerCAmelCase						,		lowerCAmelCase  						=	self.bottom_root, other.bottom_root
            while i or j:
                  if i and ((not j) or i.left_tree_size < j.left_tree_size):
                        combined_roots_list.append((i, True)			)
                        lowerCAmelCase  						=	i.parent
                  else:
                        combined_roots_list.append((j, False)			)
                        lowerCAmelCase  						=	j.parent
        # Insert links between them
            for i in range(len(__UpperCamelCase			) - 1			):
                  if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
                        lowerCAmelCase  						=	combined_roots_list[i + 1][0]
                        lowerCAmelCase  						=	combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
            lowerCAmelCase  						=	combined_roots_list[0][0]
            while i.parent:
                  if (
                      (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
                  ) or (
                      i.left_tree_size == i.parent.left_tree_size
                      and i.left_tree_size != i.parent.parent.left_tree_size
                  ):
                        # Neighbouring Nodes
                        lowerCAmelCase  						=	i.left
                        lowerCAmelCase  						=	i.parent.parent

                        # Merging trees
                        lowerCAmelCase  						=	i.merge_trees(i.parent			)

                        # Updating links
                        lowerCAmelCase  						=	previous_node
                        lowerCAmelCase  						=	next_node
                        if previous_node:
                              lowerCAmelCase  						=	i
                        if next_node:
                              lowerCAmelCase  						=	i
                  else:
                        lowerCAmelCase  						=	i.parent
        # Updating self.bottom_root
            while i.left:
                  lowerCAmelCase  						=	i.left
            lowerCAmelCase  						=	i

            # Update other
            lowerCAmelCase  						=	self.size
            lowerCAmelCase  						=	self.bottom_root
            lowerCAmelCase  						=	self.min_node

            # Return the merged heap
            return self





      def    _snake_case      (	self				,						lowercase			)		->					str:
            if self.size == 0:
                  lowerCAmelCase  						=	Node(__UpperCamelCase			)
                  lowerCAmelCase  						=	1
                  lowerCAmelCase  						=	self.bottom_root
            else:
                  # Create new node
                  lowerCAmelCase  						=	Node(__UpperCamelCase			)

                  # Update size
                  self.size += 1

                  # update min_node
                  if val < self.min_node.val:
                        lowerCAmelCase  						=	new_node
                  # Put new_node as a bottom_root in heap
                  lowerCAmelCase  						=	new_node
                  lowerCAmelCase  						=	self.bottom_root
                  lowerCAmelCase  						=	new_node

                  # Consecutively merge roots with same left_tree_size
                  while (
                      self.bottom_root.parent
                      and self.bottom_root.left_tree_size
                      == self.bottom_root.parent.left_tree_size
                  ):
                        # Next node
                        lowerCAmelCase  						=	self.bottom_root.parent.parent

                        # Merge
                        lowerCAmelCase  						=	self.bottom_root.merge_trees(self.bottom_root.parent			)

                        # Update Links
                        lowerCAmelCase  						=	next_node
                        lowerCAmelCase  						=	None
                        if next_node:
                              lowerCAmelCase  						=	self.bottom_root





      def    _snake_case      (	self			)		->					Dict:
            return self.min_node.val





      def    _snake_case      (	self			)		->					Optional[int]:
            return self.size == 0





      def    _snake_case      (	self			)		->					List[str]:
            lowerCAmelCase  						=	self.min_node.val

            # Last element in heap corner case
            if self.size == 1:
                  # Update size
                  lowerCAmelCase  						=	0

                  # Update bottom root
                  lowerCAmelCase  						=	None

                  # Update min_node
                  lowerCAmelCase  						=	None

                  return min_value
            # No right subtree corner case
            # The structure of the tree implies that this should be the bottom root
            # and there is at least one other root
            if self.min_node.right is None:
                  # Update size
                  self.size -= 1

                  # Update bottom root
                  lowerCAmelCase  						=	self.bottom_root.parent
                  lowerCAmelCase  						=	None

                  # Update min_node
                  lowerCAmelCase  						=	self.bottom_root
                  lowerCAmelCase  						=	self.bottom_root.parent
                  while i:
                        if i.val < self.min_node.val:
                              lowerCAmelCase  						=	i
                        lowerCAmelCase  						=	i.parent
                  return min_value
            # General case
            # Find the BinomialHeap of the right subtree of min_node
            lowerCAmelCase  						=	self.min_node.right
            lowerCAmelCase  						=	None
            lowerCAmelCase  						=	bottom_of_new
            lowerCAmelCase  						=	1

            # Size, min_node and bottom_root
            while bottom_of_new.left:
                  lowerCAmelCase  						=	size_of_new * 2 + 1
                  lowerCAmelCase  						=	bottom_of_new.left
                  if bottom_of_new.val < min_of_new.val:
                        lowerCAmelCase  						=	bottom_of_new
        # Corner case of single root on top left path
            if (not self.min_node.left) and (not self.min_node.parent):
                  lowerCAmelCase  						=	size_of_new
                  lowerCAmelCase  						=	bottom_of_new
                  lowerCAmelCase  						=	min_of_new
                  # print("Single root, multiple nodes case")
                  return min_value
            # Remaining cases
            # Construct heap of right subtree
            lowerCAmelCase  						=	BinomialHeap(
                bottom_root=__UpperCamelCase				,						min_node=__UpperCamelCase				,						heap_size=__UpperCamelCase			)

            # Update size
            lowerCAmelCase  						=	self.size - 1 - size_of_new

            # Neighbour nodes
            lowerCAmelCase  						=	self.min_node.left
            lowerCAmelCase  						=	self.min_node.parent

            # Initialize new bottom_root and min_node
            lowerCAmelCase  						=	previous_node or next_node
            lowerCAmelCase  						=	next_node

            # Update links of previous_node and search below for new min_node and
            # bottom_root
            if previous_node:
                  lowerCAmelCase  						=	next_node

                  # Update bottom_root and search for min_node below
                  lowerCAmelCase  						=	previous_node
                  lowerCAmelCase  						=	previous_node
                  while self.bottom_root.left:
                        lowerCAmelCase  						=	self.bottom_root.left
                        if self.bottom_root.val < self.min_node.val:
                              lowerCAmelCase  						=	self.bottom_root
            if next_node:
                  lowerCAmelCase  						=	previous_node

                  # Search for new min_node above min_node
                  lowerCAmelCase  						=	next_node
                  while i:
                        if i.val < self.min_node.val:
                              lowerCAmelCase  						=	i
                        lowerCAmelCase  						=	i.parent
        # Merge heaps
            self.merge_heaps(__UpperCamelCase			)

            return min_value





      def    _snake_case      (	self			)		->					List[str]:
            lowerCAmelCase  						=	self.bottom_root
            while top_root.parent:
                  lowerCAmelCase  						=	top_root.parent
            # preorder
            lowerCAmelCase  						=	[]
            self.__traversal(__UpperCamelCase				,						__UpperCamelCase			)
            return heap_pre_order





      def    _snake_case      (	self				,						lowercase				,						lowercase				,						lowercase=0			)		->					Union[str, Any]:
            if curr_node:
                  preorder.append((curr_node.val, level)			)
                  self.__traversal(curr_node.left				,						__UpperCamelCase				,						level + 1			)
                  self.__traversal(curr_node.right				,						__UpperCamelCase				,						level + 1			)
            else:
                  preorder.append(("""#""", level)			)





      def __str__(	self			)		->					List[Any]:
            if self.is_empty():
                  return ""
            lowerCAmelCase  						=	self.pre_order()

            return "\n".join(("""-""" * level + str(__UpperCamelCase			)) for value, level in preorder_heap			)


# Unit Tests
if __name__ == "__main__":
  import doctest

  doctest.testmod()













"""simple docstring"""





import argparse
import json
import re
import string
import sys
from collections import Counter


def       UpperCAmelCase__							(  SCREAMING_SNAKE_CASE					:						List[Any]      ):







      '''simple docstring'''




      def remove_articles(SCREAMING_SNAKE_CASE					:						int      ):
            return re.sub(R"""\b(a|an|the)\b"""							,						""" """							,						SCREAMING_SNAKE_CASE      )

      def white_space_fix(SCREAMING_SNAKE_CASE					:						int      ):
            return " ".join(text.split()      )

      def remove_punc(SCREAMING_SNAKE_CASE					:						Union[str, Any]      ):
            lowerCAmelCase  						=	set(string.punctuation      )
            return "".join(ch for ch in text if ch not in exclude      )

      def lower(SCREAMING_SNAKE_CASE					:						Optional[Any]      ):
            return text.lower()

      return white_space_fix(remove_articles(remove_punc(lower(SCREAMING_SNAKE_CASE      )      )      )      )


def       UpperCAmelCase__							(  SCREAMING_SNAKE_CASE					:						Union[str, Any]							,						SCREAMING_SNAKE_CASE					:						Optional[int]      ):







      '''simple docstring'''




      lowerCAmelCase  						=	normalize_answer(SCREAMING_SNAKE_CASE      ).split()
      lowerCAmelCase  						=	normalize_answer(SCREAMING_SNAKE_CASE      ).split()
      lowerCAmelCase  						=	Counter(SCREAMING_SNAKE_CASE      ) & Counter(SCREAMING_SNAKE_CASE      )
      lowerCAmelCase  						=	sum(common.values()      )
      if num_same == 0:
            return 0
      lowerCAmelCase  						=	1.0 * num_same / len(SCREAMING_SNAKE_CASE      )
      lowerCAmelCase  						=	1.0 * num_same / len(SCREAMING_SNAKE_CASE      )
      lowerCAmelCase  						=	(2 * precision * recall) / (precision + recall)
      return fa


def       UpperCAmelCase__							(  SCREAMING_SNAKE_CASE					:						Tuple							,						SCREAMING_SNAKE_CASE					:						Tuple      ):







      '''simple docstring'''




      return normalize_answer(SCREAMING_SNAKE_CASE      ) == normalize_answer(SCREAMING_SNAKE_CASE      )


def       UpperCAmelCase__							(  SCREAMING_SNAKE_CASE					:						List[Any]							,						SCREAMING_SNAKE_CASE					:						Any							,						SCREAMING_SNAKE_CASE					:						str      ):







      '''simple docstring'''




      lowerCAmelCase  						=	[]
      for ground_truth in ground_truths:
            lowerCAmelCase  						=	metric_fn(SCREAMING_SNAKE_CASE							,						SCREAMING_SNAKE_CASE      )
            scores_for_ground_truths.append(SCREAMING_SNAKE_CASE      )
      return max(SCREAMING_SNAKE_CASE      )


def       UpperCAmelCase__							(  SCREAMING_SNAKE_CASE					:						Optional[int]							,						SCREAMING_SNAKE_CASE					:						Dict      ):







      '''simple docstring'''




      lowerCAmelCase  						=	lowerCAmelCase  						=	lowerCAmelCase  						=	0
      for article in dataset:
            for paragraph in article["paragraphs"]:
                  for qa in paragraph["qas"]:
                        total += 1
                        if qa["id"] not in predictions:
                              lowerCAmelCase  						=	"""Unanswered question """ + qa["""id"""] + """ will receive score 0."""
                              print(SCREAMING_SNAKE_CASE							,						file=sys.stderr      )
                              continue
                        lowerCAmelCase  						=	[x["""text"""] for x in qa["""answers"""]]
                        lowerCAmelCase  						=	predictions[qa["""id"""]]
                        exact_match += metric_max_over_ground_truths(SCREAMING_SNAKE_CASE							,						SCREAMING_SNAKE_CASE							,						SCREAMING_SNAKE_CASE      )
                        fa += metric_max_over_ground_truths(SCREAMING_SNAKE_CASE							,						SCREAMING_SNAKE_CASE							,						SCREAMING_SNAKE_CASE      )

      lowerCAmelCase  						=	1_00.0 * exact_match / total
      lowerCAmelCase  						=	1_00.0 * fa / total

      return {"exact_match": exact_match, "f1": fa}


if __name__ == "__main__":
       SCREAMING_SNAKE_CASE__ =       "1.1"
       SCREAMING_SNAKE_CASE__ =       argparse.ArgumentParser(description="Evaluation for SQuAD " + expected_version)
       parser.add_argument("dataset_file", help="Dataset file")
       parser.add_argument("prediction_file", help="Prediction File")
       SCREAMING_SNAKE_CASE__ =       parser.parse_args()
       with open(args.dataset_file) as dataset_file:
              SCREAMING_SNAKE_CASE__ =       json.load(dataset_file)
              if dataset_json["version"] != expected_version:
                     print(
                         "Evaluation expects v-" + expected_version + ", but got dataset with v-" + dataset_json["version"],
                         file=sys.stderr,
                     )
              SCREAMING_SNAKE_CASE__ =       dataset_json["data"]
       with open(args.prediction_file) as prediction_file:
              SCREAMING_SNAKE_CASE__ =       json.load(prediction_file)
       print(json.dumps(evaluate(dataset, predictions)))






