

from __future__ import annotations

__snake_case							:     Tuple 						=	[2, 1, 4, 5, 6, 0, 8, 9, 1, 2, 0, 6, 4, 2, 0, 6, 5, 3, 2, 7]



class    A__:
						"""simple docstring"""






						def __init__(  self       ,     _lowercase  )      ->				None:
									a_		:		int				    =				-1
									a_		:		int				    =				-1
									a_		:		list[int]				    =				[-1] * length
									a_		:		Node | None				    =				None
									a_		:		Node | None				    =				None





						def __repr__(  self  )      ->				str:
									return F'''Node(min_value={self.minn} max_value={self.maxx})'''







def 			_UpperCAmelCase							(		a__):

			'''simple docstring'''



			a_		:		Any				    =				Node(len(a__))
			a_    ,			a_		:		int				    =				min(a__), max(a__)
			# Leaf node case where the node contains only one unique value
			if root.minn == root.maxx:
						return root
			a_		:		List[Any]				    =				(root.minn + root.maxx) // 2

			a_		:		list[int]				    =				[]
			a_		:		list[int]				    =				[]

			for index, num in enumerate(a__):
						if num <= pivot:
									left_arr.append(a__)
						else:
									right_arr.append(a__)
						a_		:		int				    =				len(a__)
			a_		:		Optional[int]				    =				build_tree(a__)
			a_		:		Optional[Any]				    =				build_tree(a__)
			return root


def 			_UpperCAmelCase							(		a__       ,					a__       ,					a__):

			'''simple docstring'''



			if index < 0 or node is None:
						return 0
			# Leaf node cases
			if node.minn == node.maxx:
						return index + 1 if node.minn == num else 0
			a_		:		Union[str, Any]				    =				(node.minn + node.maxx) // 2
			if num <= pivot:
						# go the left subtree and map index to the left subtree
						return rank_till_index(node.left       ,					a__       ,					node.map_left[index] - 1)
			else:
						# go to the right subtree and map index to the right subtree
						return rank_till_index(node.right       ,					a__       ,					index - node.map_left[index])


def 			_UpperCAmelCase							(		a__       ,					a__       ,					a__       ,					a__):

			'''simple docstring'''



			if start > end:
						return 0
			a_		:		int				    =				rank_till_index(a__       ,					a__       ,					a__)
			a_		:		Union[str, Any]				    =				rank_till_index(a__       ,					a__       ,					start - 1)
			return rank_till_end - rank_before_start


def 			_UpperCAmelCase							(		a__       ,					a__       ,					a__       ,					a__):

			'''simple docstring'''



			if index > (end - start) or start > end or node is None:
						return -1
			# Leaf node case
			if node.minn == node.maxx:
						return node.minn
			# Number of elements in the left subtree in interval [start, end]
			a_		:		Optional[Any]				    =				node.map_left[end] - (
			    node.map_left[start - 1] if start else 0
			)
			if num_elements_in_left_tree > index:
						return quantile(
						    node.left       ,					a__       ,					(node.map_left[start - 1] if start else 0)       ,					node.map_left[end] - 1       ,					)
			else:
						return quantile(
						    node.right       ,					index - num_elements_in_left_tree       ,					start - (node.map_left[start - 1] if start else 0)       ,					end - node.map_left[end]       ,					)


def 			_UpperCAmelCase							(		a__       ,					a__       ,					a__       ,					a__       ,					a__):

			'''simple docstring'''



			if (
			    start > end
			    or node is None
			    or start_num > end_num
			    or node.minn > end_num
			    or node.maxx < start_num
			):
						return 0
			if start_num <= node.minn and node.maxx <= end_num:
						return end - start + 1
			a_		:		Optional[int]				    =				range_counting(
			    node.left       ,					(node.map_left[start - 1] if start else 0)       ,					node.map_left[end] - 1       ,					a__       ,					a__       ,					)
			a_		:		str				    =				range_counting(
			    node.right       ,					start - (node.map_left[start - 1] if start else 0)       ,					end - node.map_left[end]       ,					a__       ,					a__       ,					)
			return left + right


if __name__ == "__main__":
	import doctest

	doctest.testmod()





# Copyright (c) 2021-, NVIDIA CORPORATION.  All rights reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

####################################################################################################

#
# Note: If when running this conversion script you're getting an exception:
#     ModuleNotFoundError: No module named 'megatron.model.enums'
# you need to tell python where to find the clone of Megatron-LM, e.g.:
#
# cd /tmp
# git clone https://github.com/NVIDIA/Megatron-LM
# PYTHONPATH=/tmp/Megatron-LM python src/transformers/models/megatron_bert/convert_megatron_bert_checkpoint.py ...
#
# if you already have it cloned elsewhere, simply adjust the path to the existing path
#
# If the training was done using a Megatron-LM fork, e.g.,
# https://github.com/microsoft/Megatron-DeepSpeed/ then chances are that you need to have that one
# in your path, i.e., /path/to/Megatron-DeepSpeed/
#

import argparse
import os
import re
import zipfile

import torch

from transformers import MegatronBertConfig


def 			_UpperCAmelCase							(		a__       ,					a__       ,					a__=0):

			'''simple docstring'''



			if name is None:
						a_		:		str				    =				None
			else:
						a_		:		List[str]				    =				""".""" * max(0       ,					spaces - 2) + """# {:""" + str(5_0 - spaces) + """s}"""
						a_		:		Optional[Any]				    =				fmt.format(a__)

			# Print and recurse (if needed).
			if isinstance(a__       ,					a__):
						if msg is not None:
									print(a__)
						for k in val.keys():
									recursive_print(a__       ,					val[k]       ,					spaces + 2)
			elif isinstance(a__       ,					torch.Tensor):
						print(a__       ,					""":"""       ,					val.size())
			else:
						print(a__       ,					""":"""       ,					a__)


def 			_UpperCAmelCase							(		a__       ,					a__       ,					a__       ,					a__       ,					a__):

			'''simple docstring'''



			a_		:		int				    =				param.size()
			if checkpoint_version == 1.0:
						# version 1.0 stores [num_heads * hidden_size * num_splits, :]
						a_		:		List[Any]				    =				(num_heads, hidden_size, num_splits) + input_shape[1:]
						a_		:		Any				    =				param.view(*a__)
						a_		:		Any				    =				param.transpose(0       ,					2)
						a_		:		Any				    =				param.transpose(1       ,					2).contiguous()
			elif checkpoint_version >= 2.0:
						# other versions store [num_heads * num_splits * hidden_size, :]
						a_		:		Optional[Any]				    =				(num_heads, num_splits, hidden_size) + input_shape[1:]
						a_		:		Any				    =				param.view(*a__)
						a_		:		Optional[Any]				    =				param.transpose(0       ,					1).contiguous()
			a_		:		Union[str, Any]				    =				param.view(*a__)
			return param


def 			_UpperCAmelCase							(		a__       ,					a__       ,					a__):

			'''simple docstring'''



			a_		:		Dict				    =				{}

			# old versions did not store training args
			a_		:		Union[str, Any]				    =				input_state_dict.get("""args"""       ,					a__)
			if ds_args is not None:
						# do not make the user write a config file when the exact dimensions/sizes are already in the checkpoint
						# from pprint import pprint
						# pprint(vars(ds_args))

						a_		:		Optional[Any]				    =				ds_args.tokenizer_type
						a_		:		str				    =				ds_args.padded_vocab_size
						a_		:		Optional[Any]				    =				ds_args.max_position_embeddings
						a_		:		Optional[Any]				    =				ds_args.hidden_size
						a_		:		Optional[Any]				    =				ds_args.num_layers
						a_		:		Optional[int]				    =				ds_args.num_attention_heads
						a_		:		List[Any]				    =				ds_args.ffn_hidden_size if """ffn_hidden_size""" in ds_args else 4 * ds_args.hidden_size
						# pprint(config)

			# The number of heads.
			a_		:		Tuple				    =				config.num_attention_heads
			# The hidden_size per head.
			a_		:		List[str]				    =				config.hidden_size // heads
			# Megatron-LM checkpoint version
			if "checkpoint_version" in input_state_dict.keys():
						a_		:		Optional[Any]				    =				input_state_dict["""checkpoint_version"""]
			else:
						a_		:		Tuple				    =				0.0

			# The model.
			a_		:		Optional[Any]				    =				input_state_dict["""model"""]
			# The language model.
			a_		:		str				    =				model["""language_model"""]
			# The embeddings.
			a_		:		Dict				    =				lm["""embedding"""]

			# The word embeddings.
			a_		:		str				    =				embeddings["""word_embeddings"""]["""weight"""]
			# Truncate the embedding table to vocab_size rows.
			a_		:		Dict				    =				word_embeddings[: config.vocab_size, :]
			# Store the word embeddings.
			a_		:		str				    =				word_embeddings

			# The position embeddings.
			a_		:		Tuple				    =				embeddings["""position_embeddings"""]["""weight"""]
			assert pos_embeddings.size(0) == config.max_position_embeddings and pos_embeddings.size(1) == config.hidden_size
			# Store the position embeddings.
			a_		:		Optional[Any]				    =				pos_embeddings

			# The token-type embeddings.
			a_		:		Tuple				    =				embeddings["""tokentype_embeddings"""]["""weight"""]
			# Store the position embeddings.
			a_		:		List[Any]				    =				tokentype_embeddings

			# The transformer.
			a_		:		List[str]				    =				lm["""transformer"""] if """transformer""" in lm.keys() else lm["""encoder"""]

			# The regex to extract layer names.
			a_		:		str				    =				re.compile(r"""layers\.(\d+)\.([a-z0-9_.]+)\.([a-z]+)""")

			# The simple map of names for "automated" rules.
			a_		:		List[str]				    =				{
			    """attention.dense""": """.attention.output.dense.""",
			    """self_attention.dense""": """.attention.output.dense.""",
			    """mlp.dense_h_to_4h""": """.intermediate.dense.""",
			    """mlp.dense_4h_to_h""": """.output.dense.""",
			}

			# Keep track of the attention/query/value tensor.
			a_		:		Optional[Any]				    =				None

			# Extract the layers.
			for key, val in transformer.items():
						# Match the name.
						a_		:		Optional[Any]				    =				layer_re.match(a__)

						# Stop if that's not a layer
						if m is None:
									break

						# The index of the layer.
						a_		:		Any				    =				int(m.group(1))
						# The name of the operation.
						a_		:		List[Any]				    =				m.group(2)
						# Is it a weight or a bias?
						a_		:		str				    =				m.group(3)

						# The name of the layer.
						a_		:		Optional[Any]				    =				f'''bert.encoder.layer.{layer_idx}'''

						# For layernorm(s), simply store the layer norm.
						if op_name.endswith("""layernorm"""):
									a_		:		Any				    =				"""attention.ln""" if op_name.startswith("""input""") else """ln"""
									a_		:		Union[str, Any]				    =				val

						# Transpose the QKV matrix.
						elif (
						    op_name == "attention.query_key_value" or op_name == "self_attention.query_key_value"
						) and weight_or_bias == "weight":
									# Make sure the QKV pointer is nil.
									assert attention_qkv_weight is None, ""

									a_		:		int				    =				fix_query_key_value_ordering(a__       ,					a__       ,					3       ,					a__       ,					a__)
									# Store the tensor as we need the bias as well to interleave QKV and biases.
									a_		:		Any				    =				out_val

						# Transpose the bias.
						elif (
						    op_name == "attention.query_key_value" or op_name == "self_attention.query_key_value"
						) and weight_or_bias == "bias":
									# Make sure we read the weight tensor.
									assert attention_qkv_weight is not None, ""

									# Split the QKV matrix into Q, K and V. Megatron stores Q,K,V interleaved.
									a_		:		Tuple				    =				attention_qkv_weight[0 * config.hidden_size : 1 * config.hidden_size, :]
									a_		:		Tuple				    =				attention_qkv_weight[1 * config.hidden_size : 2 * config.hidden_size, :]
									a_		:		Optional[Any]				    =				attention_qkv_weight[2 * config.hidden_size : 3 * config.hidden_size, :]

									a_		:		Optional[Any]				    =				fix_query_key_value_ordering(a__       ,					a__       ,					3       ,					a__       ,					a__)
									# Split the bias.
									a_		:		Optional[int]				    =				out_val[0 * config.hidden_size : 1 * config.hidden_size]
									a_		:		int				    =				out_val[1 * config.hidden_size : 2 * config.hidden_size]
									a_		:		Tuple				    =				out_val[2 * config.hidden_size : 3 * config.hidden_size]

									# Store.
									a_		:		List[str]				    =				q
									a_		:		Any				    =				q_bias
									a_		:		int				    =				k
									a_		:		Optional[int]				    =				k_bias
									a_		:		Optional[Any]				    =				v
									a_		:		Dict				    =				v_bias

									# Clear the stored tensor.
									a_		:		Union[str, Any]				    =				None

						# Copy weights and biases as is.
						elif weight_or_bias in ["weight", "bias"]:
									a_		:		Any				    =				megatron_to_transformers[op_name]
									a_		:		List[str]				    =				val

    # The final layernorm.
			a_		:		int				    =				transformer["""final_layernorm.weight"""]
			a_		:		List[Any]				    =				transformer["""final_layernorm.bias"""]

			# The pooler.
			a_		:		List[str]				    =				lm["""pooler"""]

			# Store the matrix and the bias.
			a_		:		List[str]				    =				pooler["""dense.weight"""]
			a_		:		List[Any]				    =				pooler["""dense.bias"""]

			# The LM head from Megatron (for RACE).
			a_		:		Union[str, Any]				    =				model["""lm_head"""]

			# The transform matrix.
			a_		:		int				    =				lm_head["""dense.weight"""]
			a_		:		Union[str, Any]				    =				lm_head["""dense.bias"""]

			# The transform LN.
			a_		:		Any				    =				lm_head["""layernorm.weight"""]
			a_		:		List[str]				    =				lm_head["""layernorm.bias"""]

			# For the decoder, we replicate the weights.
			a_		:		Optional[Any]				    =				word_embeddings
			a_		:		int				    =				lm_head["""bias"""]

			# The classifier from Megatron (for MLNI).
			a_		:		str				    =				model["""binary_head"""]

			# Store the classifier.
			a_		:		int				    =				binary_head["""weight"""]
			a_		:		str				    =				binary_head["""bias"""]

			# It should be done!
			return output_state_dict


def 			_UpperCAmelCase							(		):

			'''simple docstring'''



			a_		:		List[Any]				    =				argparse.ArgumentParser()
			parser.add_argument("""--print-checkpoint-structure"""       ,					action="""store_true""")
			parser.add_argument("""path_to_checkpoint"""       ,					type=a__       ,					help="""Path to the ZIP file containing the checkpoint""")
			parser.add_argument(
			    """--config_file"""       ,					default=""""""       ,					type=a__       ,					help="""An optional config json file describing the pre-trained model."""       ,					)
			a_		:		Union[str, Any]				    =				parser.parse_args()

			# Extract the basename.
			a_		:		Any				    =				os.path.dirname(args.path_to_checkpoint)

			# Load the model.
			# the .zip is very optional, let's keep it for backward compatibility
			print(f'''Extracting PyTorch state dictionary from "{args.path_to_checkpoint}"''')
			if args.path_to_checkpoint.endswith(""".zip"""):
						with zipfile.ZipFile(args.path_to_checkpoint       ,					"""r""") as checkpoint:
									with checkpoint.open("""release/mp_rank_00/model_optim_rng.pt""") as pytorch_dict:
												a_		:		int				    =				torch.load(a__       ,					map_location="""cpu""")
			else:
						a_		:		int				    =				torch.load(args.path_to_checkpoint       ,					map_location="""cpu""")

			if args.config_file == "":
						# Default config of megatron-bert 345m
						a_		:		str				    =				MegatronBertConfig()

						# different megatron-bert-*-345m models have different vocab sizes, so override the default
						# config (which is for megatron-bert-cased-345m) with the actual vocab dimension
						a_		:		int				    =				input_state_dict["""model"""]["""lm_head"""]["""bias"""].numel()
			else:
						a_		:		Optional[int]				    =				MegatronBertConfig.from_json_file(args.config_file)

			# Convert.
			print("""Converting""")
			a_		:		int				    =				convert_megatron_checkpoint(a__       ,					a__       ,					a__)

			# Print the structure of converted state dict.
			if args.print_checkpoint_structure:
						recursive_print(a__       ,					a__)

			# Store the config to file.
			print("""Saving config""")
			config.save_pretrained(a__)

			# Store the state_dict to file.
			a_		:		Dict				    =				os.path.join(a__       ,					"""pytorch_model.bin""")
			print(f'''Saving checkpoint to "{output_checkpoint_file}"''')
			torch.save(a__       ,					a__)


####################################################################################################

if __name__ == "__main__":
	main()

####################################################################################################


