

"""simple docstring"""






from collections.abc import Sequence
from queue import Queue
class        _lowercase					:







     def __init__(      self ,						UpperCamelCase_ ,						UpperCamelCase_ ,						UpperCamelCase_ ,						UpperCamelCase_=None ,						UpperCamelCase_=None       ):
      __magic_name__     =      start
      __magic_name__     =      end
      __magic_name__     =      val
      __magic_name__     =      (start + end) // 2
      __magic_name__     =      left
      __magic_name__     =      right







     def __repr__(      self       ):
      return f'''SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'''


class        _lowercase					:







     def __init__(      self ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      __magic_name__     =      collection
      __magic_name__     =      function
      if self.collection:
       __magic_name__     =      self._build_tree(0 ,						len(UpperCamelCase_       ) - 1       )







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      self._update_tree(self.root ,						UpperCamelCase_ ,						UpperCamelCase_       )







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      return self._query_range(self.root ,						UpperCamelCase_ ,						UpperCamelCase_       )







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      if start == end:
       return SegmentTreeNode(UpperCamelCase_ ,						UpperCamelCase_ ,						self.collection[start]       )
      __magic_name__     =      (start + end) // 2
      __magic_name__     =      self._build_tree(UpperCamelCase_ ,						UpperCamelCase_       )
      __magic_name__     =      self._build_tree(mid + 1 ,						UpperCamelCase_       )
      return SegmentTreeNode(UpperCamelCase_ ,						UpperCamelCase_ ,						self.fn(left.val ,						right.val       ) ,						UpperCamelCase_ ,						UpperCamelCase_       )







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      if node.start == i and node.end == i:
       __magic_name__     =      val
       return
      if i <= node.mid:
       self._update_tree(node.left ,						UpperCamelCase_ ,						UpperCamelCase_       )
      else:
       self._update_tree(node.right ,						UpperCamelCase_ ,						UpperCamelCase_       )
      __magic_name__     =      self.fn(node.left.val ,						node.right.val       )







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      if node.start == i and node.end == j:
       return node.val

      if i <= node.mid:
       if j <= node.mid:
        # range in left child tree
        return self._query_range(node.left ,						UpperCamelCase_ ,						UpperCamelCase_       )
       else:
        # range in left child tree and right child tree
        return self.fn(
            self._query_range(node.left ,						UpperCamelCase_ ,						node.mid       ) ,						self._query_range(node.right ,						node.mid + 1 ,						UpperCamelCase_       ) ,						)
      else:
       # range in right child tree
       return self._query_range(node.right ,						UpperCamelCase_ ,						UpperCamelCase_       )







     def 	lowerCAmelCase__    (      self       ):
      if self.root is not None:
       __magic_name__     =      Queue()
       queue.put(self.root       )
       while not queue.empty():
        __magic_name__     =      queue.get()
        yield node

        if node.left is not None:
         queue.put(node.left       )

        if node.right is not None:
         queue.put(node.right       )


if __name__ == "__main__":
 import operator

 for fn in [operator.add, max, min]:
  print("*" * 50)
  __lowerCamelCase										=		SegmentTree([2, 1, 5, 3, 4], fn)
  for node in arr.traverse():
   print(node)
  print()

  arr.update(1, 5)
  for node in arr.traverse():
   print(node)
  print()

  print(arr.query_range(3, 4))  # 7
  print(arr.query_range(2, 2))  # 5
  print(arr.query_range(1, 3))  # 13
  print()




"""simple docstring"""






import json
from typing import List, Optional, Tuple

from tokenizers import normalizers

from ...tokenization_utils_fast import PreTrainedTokenizerFast
from ...utils import logging
from .tokenization_bert import BertTokenizer


__lowerCamelCase										=		logging.get_logger(__name__)

__lowerCamelCase										=		{"vocab_file": "vocab.txt", "tokenizer_file": "tokenizer.json"}

__lowerCamelCase										=		{
    "vocab_file": {
        "bert-base-uncased": "https://huggingface.co/bert-base-uncased/resolve/main/vocab.txt",
        "bert-large-uncased": "https://huggingface.co/bert-large-uncased/resolve/main/vocab.txt",
        "bert-base-cased": "https://huggingface.co/bert-base-cased/resolve/main/vocab.txt",
        "bert-large-cased": "https://huggingface.co/bert-large-cased/resolve/main/vocab.txt",
        "bert-base-multilingual-uncased": (
            "https://huggingface.co/bert-base-multilingual-uncased/resolve/main/vocab.txt"
        ),
        "bert-base-multilingual-cased": "https://huggingface.co/bert-base-multilingual-cased/resolve/main/vocab.txt",
        "bert-base-chinese": "https://huggingface.co/bert-base-chinese/resolve/main/vocab.txt",
        "bert-base-german-cased": "https://huggingface.co/bert-base-german-cased/resolve/main/vocab.txt",
        "bert-large-uncased-whole-word-masking": (
            "https://huggingface.co/bert-large-uncased-whole-word-masking/resolve/main/vocab.txt"
        ),
        "bert-large-cased-whole-word-masking": (
            "https://huggingface.co/bert-large-cased-whole-word-masking/resolve/main/vocab.txt"
        ),
        "bert-large-uncased-whole-word-masking-finetuned-squad": (
            "https://huggingface.co/bert-large-uncased-whole-word-masking-finetuned-squad/resolve/main/vocab.txt"
        ),
        "bert-large-cased-whole-word-masking-finetuned-squad": (
            "https://huggingface.co/bert-large-cased-whole-word-masking-finetuned-squad/resolve/main/vocab.txt"
        ),
        "bert-base-cased-finetuned-mrpc": (
            "https://huggingface.co/bert-base-cased-finetuned-mrpc/resolve/main/vocab.txt"
        ),
        "bert-base-german-dbmdz-cased": "https://huggingface.co/bert-base-german-dbmdz-cased/resolve/main/vocab.txt",
        "bert-base-german-dbmdz-uncased": (
            "https://huggingface.co/bert-base-german-dbmdz-uncased/resolve/main/vocab.txt"
        ),
        "TurkuNLP/bert-base-finnish-cased-v1": (
            "https://huggingface.co/TurkuNLP/bert-base-finnish-cased-v1/resolve/main/vocab.txt"
        ),
        "TurkuNLP/bert-base-finnish-uncased-v1": (
            "https://huggingface.co/TurkuNLP/bert-base-finnish-uncased-v1/resolve/main/vocab.txt"
        ),
        "wietsedv/bert-base-dutch-cased": (
            "https://huggingface.co/wietsedv/bert-base-dutch-cased/resolve/main/vocab.txt"
        ),
    },
    "tokenizer_file": {
        "bert-base-uncased": "https://huggingface.co/bert-base-uncased/resolve/main/tokenizer.json",
        "bert-large-uncased": "https://huggingface.co/bert-large-uncased/resolve/main/tokenizer.json",
        "bert-base-cased": "https://huggingface.co/bert-base-cased/resolve/main/tokenizer.json",
        "bert-large-cased": "https://huggingface.co/bert-large-cased/resolve/main/tokenizer.json",
        "bert-base-multilingual-uncased": (
            "https://huggingface.co/bert-base-multilingual-uncased/resolve/main/tokenizer.json"
        ),
        "bert-base-multilingual-cased": (
            "https://huggingface.co/bert-base-multilingual-cased/resolve/main/tokenizer.json"
        ),
        "bert-base-chinese": "https://huggingface.co/bert-base-chinese/resolve/main/tokenizer.json",
        "bert-base-german-cased": "https://huggingface.co/bert-base-german-cased/resolve/main/tokenizer.json",
        "bert-large-uncased-whole-word-masking": (
            "https://huggingface.co/bert-large-uncased-whole-word-masking/resolve/main/tokenizer.json"
        ),
        "bert-large-cased-whole-word-masking": (
            "https://huggingface.co/bert-large-cased-whole-word-masking/resolve/main/tokenizer.json"
        ),
        "bert-large-uncased-whole-word-masking-finetuned-squad": (
            "https://huggingface.co/bert-large-uncased-whole-word-masking-finetuned-squad/resolve/main/tokenizer.json"
        ),
        "bert-large-cased-whole-word-masking-finetuned-squad": (
            "https://huggingface.co/bert-large-cased-whole-word-masking-finetuned-squad/resolve/main/tokenizer.json"
        ),
        "bert-base-cased-finetuned-mrpc": (
            "https://huggingface.co/bert-base-cased-finetuned-mrpc/resolve/main/tokenizer.json"
        ),
        "bert-base-german-dbmdz-cased": (
            "https://huggingface.co/bert-base-german-dbmdz-cased/resolve/main/tokenizer.json"
        ),
        "bert-base-german-dbmdz-uncased": (
            "https://huggingface.co/bert-base-german-dbmdz-uncased/resolve/main/tokenizer.json"
        ),
        "TurkuNLP/bert-base-finnish-cased-v1": (
            "https://huggingface.co/TurkuNLP/bert-base-finnish-cased-v1/resolve/main/tokenizer.json"
        ),
        "TurkuNLP/bert-base-finnish-uncased-v1": (
            "https://huggingface.co/TurkuNLP/bert-base-finnish-uncased-v1/resolve/main/tokenizer.json"
        ),
        "wietsedv/bert-base-dutch-cased": (
            "https://huggingface.co/wietsedv/bert-base-dutch-cased/resolve/main/tokenizer.json"
        ),
    },
}

__lowerCamelCase										=		{
    "bert-base-uncased": 5_12,
    "bert-large-uncased": 5_12,
    "bert-base-cased": 5_12,
    "bert-large-cased": 5_12,
    "bert-base-multilingual-uncased": 5_12,
    "bert-base-multilingual-cased": 5_12,
    "bert-base-chinese": 5_12,
    "bert-base-german-cased": 5_12,
    "bert-large-uncased-whole-word-masking": 5_12,
    "bert-large-cased-whole-word-masking": 5_12,
    "bert-large-uncased-whole-word-masking-finetuned-squad": 5_12,
    "bert-large-cased-whole-word-masking-finetuned-squad": 5_12,
    "bert-base-cased-finetuned-mrpc": 5_12,
    "bert-base-german-dbmdz-cased": 5_12,
    "bert-base-german-dbmdz-uncased": 5_12,
    "TurkuNLP/bert-base-finnish-cased-v1": 5_12,
    "TurkuNLP/bert-base-finnish-uncased-v1": 5_12,
    "wietsedv/bert-base-dutch-cased": 5_12,
}

__lowerCamelCase										=		{
    "bert-base-uncased": {"do_lower_case": True},
    "bert-large-uncased": {"do_lower_case": True},
    "bert-base-cased": {"do_lower_case": False},
    "bert-large-cased": {"do_lower_case": False},
    "bert-base-multilingual-uncased": {"do_lower_case": True},
    "bert-base-multilingual-cased": {"do_lower_case": False},
    "bert-base-chinese": {"do_lower_case": False},
    "bert-base-german-cased": {"do_lower_case": False},
    "bert-large-uncased-whole-word-masking": {"do_lower_case": True},
    "bert-large-cased-whole-word-masking": {"do_lower_case": False},
    "bert-large-uncased-whole-word-masking-finetuned-squad": {"do_lower_case": True},
    "bert-large-cased-whole-word-masking-finetuned-squad": {"do_lower_case": False},
    "bert-base-cased-finetuned-mrpc": {"do_lower_case": False},
    "bert-base-german-dbmdz-cased": {"do_lower_case": False},
    "bert-base-german-dbmdz-uncased": {"do_lower_case": True},
    "TurkuNLP/bert-base-finnish-cased-v1": {"do_lower_case": False},
    "TurkuNLP/bert-base-finnish-uncased-v1": {"do_lower_case": True},
    "wietsedv/bert-base-dutch-cased": {"do_lower_case": False},
}
class        _lowercase					(     __UpperCAmelCase     ):
     _lowerCamelCase     =       VOCAB_FILES_NAMES
     _lowerCamelCase     =       PRETRAINED_VOCAB_FILES_MAP
     _lowerCamelCase     =       PRETRAINED_INIT_CONFIGURATION
     _lowerCamelCase     =       PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
     _lowerCamelCase     =       BertTokenizer







     def __init__(      self ,						UpperCamelCase_=None ,						UpperCamelCase_=None ,						UpperCamelCase_=True ,						UpperCamelCase_="[UNK]" ,						UpperCamelCase_="[SEP]" ,						UpperCamelCase_="[PAD]" ,						UpperCamelCase_="[CLS]" ,						UpperCamelCase_="[MASK]" ,						UpperCamelCase_=True ,						UpperCamelCase_=None ,						**UpperCamelCase_ ,						):
      super().__init__(
          UpperCamelCase_ ,						tokenizer_file=UpperCamelCase_ ,						do_lower_case=UpperCamelCase_ ,						unk_token=UpperCamelCase_ ,						sep_token=UpperCamelCase_ ,						pad_token=UpperCamelCase_ ,						cls_token=UpperCamelCase_ ,						mask_token=UpperCamelCase_ ,						tokenize_chinese_chars=UpperCamelCase_ ,						strip_accents=UpperCamelCase_ ,						**UpperCamelCase_ ,						)

      __magic_name__     =      json.loads(self.backend_tokenizer.normalizer.__getstate__()       )
      if (
          normalizer_state.get('''lowercase''' ,						UpperCamelCase_       ) != do_lower_case
          or normalizer_state.get('''strip_accents''' ,						UpperCamelCase_       ) != strip_accents
          or normalizer_state.get('''handle_chinese_chars''' ,						UpperCamelCase_       ) != tokenize_chinese_chars
      ):
       __magic_name__     =      getattr(UpperCamelCase_ ,						normalizer_state.pop('''type'''       )       )
       __magic_name__     =      do_lower_case
       __magic_name__     =      strip_accents
       __magic_name__     =      tokenize_chinese_chars
       __magic_name__     =      normalizer_class(**UpperCamelCase_       )

      __magic_name__     =      do_lower_case







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_=None       ):
      __magic_name__     =      [self.cls_token_id] + token_ids_a + [self.sep_token_id]

      if token_ids_a:
       output += token_ids_a + [self.sep_token_id]

      return output







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_ = None       ):
      __magic_name__     =      [self.sep_token_id]
      __magic_name__     =      [self.cls_token_id]
      if token_ids_a is None:
       return len(cls + token_ids_a + sep       ) * [0]
      return len(cls + token_ids_a + sep       ) * [0] + len(token_ids_a + sep       ) * [1]







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_ = None       ):
      __magic_name__     =      self._tokenizer.model.save(UpperCamelCase_ ,						name=UpperCamelCase_       )
      return tuple(UpperCamelCase_       )

