





"""simple docstring"""





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




def 		lowerCAmelCase_     (  lowercase_       :							Tuple		) ->    Tuple:

 '''simple docstring'''






 def remove_articles(lowercase_       :							str		):
  return re.sub(r'''\b(a|an|the)\b'''			,				''' '''			,				lowercase_		)

 def white_space_fix(lowercase_       :							Union[str, Any]		):
  return " ".join(text.split()		)

 def remove_punc(lowercase_       :							Tuple		):
  __SCREAMING_SNAKE_CASE			:      List[Any] 							=	set(string.punctuation		)
  return "".join(ch for ch in text if ch not in exclude		)

 def lower(lowercase_       :							List[str]		):
  return text.lower()

 return white_space_fix(remove_articles(remove_punc(lower(lowercase_		)		)		)		)




def 		lowerCAmelCase_     (  lowercase_       :							List[str]			,				lowercase_       :							Any		) ->    str:

 '''simple docstring'''






 __SCREAMING_SNAKE_CASE			:      Any 							=	normalize_answer(lowercase_		).split()
 __SCREAMING_SNAKE_CASE			:      Any 							=	normalize_answer(lowercase_		).split()
 __SCREAMING_SNAKE_CASE			:      Dict 							=	Counter(lowercase_		) & Counter(lowercase_		)
 __SCREAMING_SNAKE_CASE			:      Tuple 							=	sum(common.values()		)
 if num_same == 0:
  return 0
 __SCREAMING_SNAKE_CASE			:      Dict 							=	1.0 * num_same / len(lowercase_		)
 __SCREAMING_SNAKE_CASE			:      Dict 							=	1.0 * num_same / len(lowercase_		)
 __SCREAMING_SNAKE_CASE			:      int 							=	(2 * precision * recall) / (precision + recall)
 return fa




def 		lowerCAmelCase_     (  lowercase_       :							int			,				lowercase_       :							Tuple		) ->    str:

 '''simple docstring'''






 return normalize_answer(lowercase_		) == normalize_answer(lowercase_		)




def 		lowerCAmelCase_     (  lowercase_       :							List[Any]			,				lowercase_       :							List[str]			,				lowercase_       :							List[str]		) ->    Optional[Any]:

 '''simple docstring'''






 __SCREAMING_SNAKE_CASE			:      int 							=	[]
 for ground_truth in ground_truths:
  __SCREAMING_SNAKE_CASE			:      Optional[Any] 							=	metric_fn(lowercase_			,				lowercase_		)
  scores_for_ground_truths.append(lowercase_		)
 return max(lowercase_		)




def 		lowerCAmelCase_     (  lowercase_       :							int			,				lowercase_       :							int		) ->    str:

 '''simple docstring'''






 __SCREAMING_SNAKE_CASE			:      Optional[int] 							=	0
 for article in dataset:
  for paragraph in article["paragraphs"]:
   for qa in paragraph["qas"]:
    total += 1
    if qa["id"] not in predictions:
     __SCREAMING_SNAKE_CASE			:      Tuple 							=	"""Unanswered question """ + qa["""id"""] + """ will receive score 0."""
     print(lowercase_			,				file=sys.stderr		)
     continue
    __SCREAMING_SNAKE_CASE			:      List[str] 							=	[x["""text"""] for x in qa["""answers"""]]
    __SCREAMING_SNAKE_CASE			:      Union[str, Any] 							=	predictions[qa["""id"""]]
    exact_match += metric_max_over_ground_truths(lowercase_			,				lowercase_			,				lowercase_		)
    fa += metric_max_over_ground_truths(lowercase_			,				lowercase_			,				lowercase_		)

 __SCREAMING_SNAKE_CASE			:      Union[str, Any] 							=	100.0 * exact_match / total
 __SCREAMING_SNAKE_CASE			:      int 							=	100.0 * fa / total

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


if __name__ == "__main__":
    _lowerCamelCase  					=     '''1.1'''
    _lowerCamelCase  					=     argparse.ArgumentParser(description='''Evaluation for SQuAD ''' + expected_version)
    parser.add_argument('''dataset_file''', help='''Dataset file''')
    parser.add_argument('''prediction_file''', help='''Prediction File''')
    _lowerCamelCase  					=     parser.parse_args()
    with open(args.dataset_file) as dataset_file:
        _lowerCamelCase  					=     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,
            )
        _lowerCamelCase  					=     dataset_json['''data''']
    with open(args.prediction_file) as prediction_file:
        _lowerCamelCase  					=     json.load(prediction_file)
    print(json.dumps(evaluate(dataset, predictions)))








"""simple docstring"""





import math





class       snake_case		:

      def __init__(      self       :Optional[Any]						,							_lowerCamelCase       :Dict						):
       __SCREAMING_SNAKE_CASE			:      str 							=	len(_lowerCamelCase						)
       __SCREAMING_SNAKE_CASE			:      Optional[int] 							=	[0] * (
           4 * self.N
       )  # approximate the overall size of segment tree with array N
       self.build(1						,							0						,							self.N - 1						)

      def 						SCREAMING_SNAKE_CASE_      (      self       :Union[str, Any]						,							_lowerCamelCase       :List[str]						):
       return idx * 2

      def 						SCREAMING_SNAKE_CASE_      (      self       :Tuple						,							_lowerCamelCase       :Optional[Any]						):
       return idx * 2 + 1

      def 						SCREAMING_SNAKE_CASE_      (      self       :int						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :Union[str, Any]						,							_lowerCamelCase       :str						):  # noqa: E741
       if l == r:
        __SCREAMING_SNAKE_CASE			:      Union[str, Any] 							=	A[l]
       else:
        __SCREAMING_SNAKE_CASE			:      Dict 							=	(l + r) // 2
        self.build(self.left(_lowerCamelCase						)						,							_lowerCamelCase						,							_lowerCamelCase						)
        self.build(self.right(_lowerCamelCase						)						,							mid + 1						,							_lowerCamelCase						)
        __SCREAMING_SNAKE_CASE			:      List[Any] 							=	max(self.st[self.left(_lowerCamelCase						)]						,							self.st[self.right(_lowerCamelCase						)]						)

      def 						SCREAMING_SNAKE_CASE_      (      self       :Tuple						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :Union[str, Any]						):
       return self.update_recursive(1						,							0						,							self.N - 1						,							a - 1						,							b - 1						,							_lowerCamelCase						)

      def 						SCREAMING_SNAKE_CASE_      (      self       :Optional[int]						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :Any						,							_lowerCamelCase       :Union[str, Any]						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :str						,							_lowerCamelCase       :Optional[Any]						):  # noqa: E741
       if r < a or l > b:
        return True
       if l == r:
        __SCREAMING_SNAKE_CASE			:      Union[str, Any] 							=	val
        return True
       __SCREAMING_SNAKE_CASE			:      List[Any] 							=	(l + r) // 2
       self.update_recursive(self.left(_lowerCamelCase						)						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						)
       self.update_recursive(self.right(_lowerCamelCase						)						,							mid + 1						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						)
       __SCREAMING_SNAKE_CASE			:      Union[str, Any] 							=	max(self.st[self.left(_lowerCamelCase						)]						,							self.st[self.right(_lowerCamelCase						)]						)
       return True

      def 						SCREAMING_SNAKE_CASE_      (      self       :Tuple						,							_lowerCamelCase       :str						,							_lowerCamelCase       :Any						):
       return self.query_recursive(1						,							0						,							self.N - 1						,							a - 1						,							b - 1						)

      def 						SCREAMING_SNAKE_CASE_      (      self       :str						,							_lowerCamelCase       :Dict						,							_lowerCamelCase       :str						,							_lowerCamelCase       :Union[str, Any]						,							_lowerCamelCase       :Optional[Any]						,							_lowerCamelCase       :Any						):  # noqa: E741
       if r < a or l > b:
        return -math.inf
       if l >= a and r <= b:
        return self.st[idx]
       __SCREAMING_SNAKE_CASE			:      List[str] 							=	(l + r) // 2
       __SCREAMING_SNAKE_CASE			:      Any 							=	self.query_recursive(self.left(_lowerCamelCase						)						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						)
       __SCREAMING_SNAKE_CASE			:      Optional[int] 							=	self.query_recursive(self.right(_lowerCamelCase						)						,							mid + 1						,							_lowerCamelCase						,							_lowerCamelCase						,							_lowerCamelCase						)
       return max(_lowerCamelCase						,							_lowerCamelCase						)



      def 						SCREAMING_SNAKE_CASE_      (      self       :Dict						):
       __SCREAMING_SNAKE_CASE			:      str 							=	[]
       for i in range(1						,							N + 1						):
        show_list += [self.query(_lowerCamelCase						,							_lowerCamelCase						)]
       print(_lowerCamelCase						)


if __name__ == "__main__":
    _lowerCamelCase  					=     [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
    _lowerCamelCase  					=     15
    _lowerCamelCase  					=     SegmentTree(A)
    print(segt.query(4, 6))
    print(segt.query(7, 11))
    print(segt.query(7, 12))
    segt.update(1, 3, 1_11)
    print(segt.query(1, 15))
    segt.update(7, 8, 2_35)
    segt.show_data()

