





from typing import Any, Dict, List, Optional, Tuple, Union

import torch
from torch import nn
from torch.utils.data import DistributedSampler, RandomSampler

from transformers import PreTrainedModel, Trainer, logging
from transformers.integrations import is_fairscale_available
from transformers.models.fsmt.configuration_fsmt import FSMTConfig
from transformers.optimization import (
    Adafactor,
    AdamW,
    get_constant_schedule,
    get_constant_schedule_with_warmup,
    get_cosine_schedule_with_warmup,
    get_cosine_with_hard_restarts_schedule_with_warmup,
    get_linear_schedule_with_warmup,
    get_polynomial_decay_schedule_with_warmup,
)
from transformers.trainer_pt_utils import get_tpu_sampler
from transformers.training_args import ParallelMode
from transformers.utils import is_torch_tpu_available


if is_fairscale_available():
     from fairscale.optim import OSS


__A             =       logging.get_logger(__name__)

__A             =       {
    "linear": get_linear_schedule_with_warmup,
    "cosine": get_cosine_schedule_with_warmup,
    "cosine_w_restarts": get_cosine_with_hard_restarts_schedule_with_warmup,
    "polynomial": get_polynomial_decay_schedule_with_warmup,
    "constant": get_constant_schedule,
    "constant_w_warmup": get_constant_schedule_with_warmup,
}





class      _SCREAMING_SNAKE_CASE		(			__SCREAMING_SNAKE_CASE					):







 '''simple docstring'''

 def __init__(self       :     Optional[Any] ,				UpperCAmelCase_       :     int=None ,				UpperCAmelCase_       :     str=None ,				*UpperCAmelCase_       :     Optional[Any] ,				**UpperCAmelCase_       :     Optional[Any]) ->List[Any]:



   '''simple docstring'''



   super().__init__(*UpperCAmelCase_ ,				**UpperCAmelCase_)

   if config is None:
     assert isinstance(self.model ,				UpperCAmelCase_), (
         "If no `config` is passed the model to be trained has to be of type `PreTrainedModel`, but is"
         F""" {self.model.__class__}"""
     )
     lowerCamelCase__:   Union[str, Any]    						=self.model.config
   else:
     lowerCamelCase__:   Optional[int]    						=config

   lowerCamelCase__:   Union[str, Any]    						=data_args
   lowerCamelCase__:   List[str]    						=self.config.tgt_vocab_size if isinstance(self.config ,				UpperCAmelCase_) else self.config.vocab_size

   if self.args.label_smoothing != 0 or (self.data_args is not None and self.data_args.ignore_pad_token_for_loss):
     assert self.config.pad_token_id is not None, (
         "Make sure that `config.pad_token_id` is correcly defined when ignoring `pad_token` for loss"
         " calculation or doing label smoothing."
     )

   if self.config.pad_token_id is None and self.config.eos_token_id is not None:
     logger.warning(
         F"""The `config.pad_token_id` is `None`. Using `config.eos_token_id` = {self.config.eos_token_id} for"""
         " padding..")

   if self.args.label_smoothing == 0:
     lowerCamelCase__:   List[Any]    						=torch.nn.CrossEntropyLoss(ignore_index=self.config.pad_token_id)
   else:
     # dynamically import label_smoothed_nll_loss
     from utils import label_smoothed_nll_loss

     lowerCamelCase__:   Any    						=label_smoothed_nll_loss

 def 							SCREAMING_SNAKE_CASE_      (self       :     List[Any] ,				UpperCAmelCase_       :     int) ->List[str]:



   '''simple docstring'''



   if self.optimizer is None:
     lowerCamelCase__:   str    						=["bias", "LayerNorm.weight"]
     lowerCamelCase__:   Tuple    						=[
         {
             "params": [p for n, p in self.model.named_parameters() if not any(nd in n for nd in no_decay)],
             "weight_decay": self.args.weight_decay,
         },
         {
             "params": [p for n, p in self.model.named_parameters() if any(nd in n for nd in no_decay)],
             "weight_decay": 0.0,
         },
     ]
     lowerCamelCase__:   Any    						=Adafactor if self.args.adafactor else AdamW
     if self.args.adafactor:
       lowerCamelCase__:   Optional[int]    						=Adafactor
       lowerCamelCase__:   Tuple    						={"scale_parameter": False, "relative_step": False}
     else:
       lowerCamelCase__:   Dict    						=AdamW
       lowerCamelCase__:   int    						={
           "betas": (self.args.adam_betaa, self.args.adam_betaa),
           "eps": self.args.adam_epsilon,
       }
     lowerCamelCase__:   Union[str, Any]    						=self.args.learning_rate
     if self.sharded_ddp:
       lowerCamelCase__:   int    						=OSS(
           params=UpperCAmelCase_ ,				optim=UpperCAmelCase_ ,				**UpperCAmelCase_ ,				)
     else:
       lowerCamelCase__:   Optional[Any]    						=optimizer_cls(UpperCAmelCase_ ,				**UpperCAmelCase_)

   if self.lr_scheduler is None:
     lowerCamelCase__:   Optional[Any]    						=self._get_lr_scheduler(UpperCAmelCase_)
   else:  # ignoring --lr_scheduler
     logger.warning("scheduler is passed to `Seq2SeqTrainer`, `--lr_scheduler` arg is ignored.")

 def 							SCREAMING_SNAKE_CASE_      (self       :     Dict ,				UpperCAmelCase_       :     Dict) ->int:



   '''simple docstring'''



   lowerCamelCase__:   Union[str, Any]    						=arg_to_scheduler[self.args.lr_scheduler]
   if self.args.lr_scheduler == "constant":
     lowerCamelCase__:   Tuple    						=schedule_func(self.optimizer)
   elif self.args.lr_scheduler == "constant_w_warmup":
     lowerCamelCase__:   Any    						=schedule_func(self.optimizer ,				num_warmup_steps=self.args.warmup_steps)
   else:
     lowerCamelCase__:   Dict    						=schedule_func(
         self.optimizer ,				num_warmup_steps=self.args.warmup_steps ,				num_training_steps=UpperCAmelCase_)
   return scheduler

 def 							SCREAMING_SNAKE_CASE_      (self       :     Dict) ->Optional[torch.utils.data.Sampler]:



   '''simple docstring'''



   if isinstance(self.train_dataset ,				torch.utils.data.IterableDataset):
     return None
   elif is_torch_tpu_available():
     return get_tpu_sampler(self.train_dataset)
   else:
     if self.args.sortish_sampler:
       self.train_dataset.make_sortish_sampler(
           self.args.per_device_train_batch_size ,				distributed=(self.args.parallel_mode == ParallelMode.DISTRIBUTED) ,				)

     return (
         RandomSampler(self.train_dataset)
         if self.args.local_rank == -1
         else DistributedSampler(self.train_dataset)
     )

 def 							SCREAMING_SNAKE_CASE_      (self       :     Optional[Any] ,				UpperCAmelCase_       :     Union[str, Any] ,				UpperCAmelCase_       :     str ,				UpperCAmelCase_       :     Optional[int]) ->List[str]:



   '''simple docstring'''



   if self.args.label_smoothing == 0:
     if self.data_args is not None and self.data_args.ignore_pad_token_for_loss:
       # force training to ignore pad token
       lowerCamelCase__:   Union[str, Any]    						=model(**UpperCAmelCase_ ,				use_cache=UpperCAmelCase_)[0]
       lowerCamelCase__:   List[Any]    						=self.loss_fn(logits.view(-1 ,				logits.shape[-1]) ,				labels.view(-1))
     else:
       # compute usual loss via models
       lowerCamelCase__:   Optional[int]    						=model(**UpperCAmelCase_ ,				labels=UpperCAmelCase_ ,				use_cache=UpperCAmelCase_)[:2]
   else:
     # compute label smoothed loss
     lowerCamelCase__:   Union[str, Any]    						=model(**UpperCAmelCase_ ,				use_cache=UpperCAmelCase_)[0]
     lowerCamelCase__:   Union[str, Any]    						=torch.nn.functional.log_softmax(UpperCAmelCase_ ,				dim=-1)
     lowerCamelCase__:   Optional[Any]    						=self.loss_fn(UpperCAmelCase_ ,				UpperCAmelCase_ ,				self.args.label_smoothing ,				ignore_index=self.config.pad_token_id)
   return loss, logits

 def 							SCREAMING_SNAKE_CASE_      (self       :     Optional[Any] ,				UpperCAmelCase_       :     int ,				UpperCAmelCase_       :     str) ->Tuple:



   '''simple docstring'''



   lowerCamelCase__:   List[str]    						=inputs.pop("labels")
   lowerCamelCase__:   int    						=self._compute_loss(UpperCAmelCase_ ,				UpperCAmelCase_ ,				UpperCAmelCase_)
   return loss

 def 							SCREAMING_SNAKE_CASE_      (self       :     Tuple ,				UpperCAmelCase_       :     nn.Module ,				UpperCAmelCase_       :     Dict[str, Union[torch.Tensor, Any]] ,				UpperCAmelCase_       :     bool ,				UpperCAmelCase_       :     Optional[List[str]] = None ,				) ->Tuple[Optional[float], Optional[torch.Tensor], Optional[torch.Tensor]]:



   '''simple docstring'''



   lowerCamelCase__:   Optional[Any]    						=self._prepare_inputs(UpperCAmelCase_)

   lowerCamelCase__:   str    						={
       "max_length": self.data_args.val_max_target_length
       if self.data_args is not None
       else self.config.max_length,
       "num_beams": self.data_args.eval_beams if self.data_args is not None else self.config.num_beams,
   }

   if self.args.predict_with_generate and not self.args.prediction_loss_only:
     lowerCamelCase__:   Optional[Any]    						=self.model.generate(
         inputs["input_ids"] ,				attention_mask=inputs["attention_mask"] ,				**UpperCAmelCase_ ,				)
     # in case the batch is shorter than max length, the output should be padded
     if generated_tokens.shape[-1] < gen_kwargs["max_length"]:
       lowerCamelCase__:   List[str]    						=self._pad_tensors_to_max_len(UpperCAmelCase_ ,				gen_kwargs["max_length"])

   lowerCamelCase__:   int    						=inputs.pop("labels")
   with torch.no_grad():
     # compute loss on predict data
     lowerCamelCase__:   Optional[Any]    						=self._compute_loss(UpperCAmelCase_ ,				UpperCAmelCase_ ,				UpperCAmelCase_)

   lowerCamelCase__:   Union[str, Any]    						=loss.mean().detach()
   if self.args.prediction_loss_only:
     return (loss, None, None)

   lowerCamelCase__:   List[str]    						=generated_tokens if self.args.predict_with_generate else logits

   if labels.shape[-1] < gen_kwargs["max_length"]:
     lowerCamelCase__:   Any    						=self._pad_tensors_to_max_len(UpperCAmelCase_ ,				gen_kwargs["max_length"])

   return (loss, logits, labels)







 def 							SCREAMING_SNAKE_CASE_      (self       :     Union[str, Any] ,				UpperCAmelCase_       :     List[Any] ,				UpperCAmelCase_       :     Any) ->Dict:



   '''simple docstring'''



   lowerCamelCase__:   Optional[int]    						=self.config.pad_token_id if self.config.pad_token_id is not None else self.config.eos_token_id

   if pad_token_id is None:
     raise ValueError(
         "Make sure that either `config.pad_token_id` or `config.eos_token_id` is defined if tensor has to be"
         F""" padded to `max_length`={max_length}""")

   lowerCamelCase__:   Any    						=pad_token_id * torch.ones(
       (tensor.shape[0], max_length) ,				dtype=tensor.dtype ,				device=tensor.device)
   lowerCamelCase__:   Any    						=tensor
   return padded_tensor








from __future__ import annotations

from collections.abc import Iterable, Iterator
from dataclasses import dataclass

__A             =       (3, 9, -11, 0, 7, 5, 1, -1)
__A             =       (4, 6, 2, 0, 8, 10, 3, -2)



@dataclass
class      _SCREAMING_SNAKE_CASE		:







 '''simple docstring'''
 lowercase_	=    42
 lowercase_	=    42



class      _SCREAMING_SNAKE_CASE		:







 '''simple docstring'''

 def __init__(self       :     Dict ,				UpperCAmelCase_       :     Iterable[int]) ->None:



   '''simple docstring'''



   lowerCamelCase__:   Node | None    						=None
   for i in sorted(UpperCAmelCase_ ,				reverse=UpperCAmelCase_):
     lowerCamelCase__:   Any    						=Node(UpperCAmelCase_ ,				self.head)

 def __iter__(self       :     Optional[int]) ->Iterator[int]:



   '''simple docstring'''



   lowerCamelCase__:   int    						=self.head
   while node:
     yield node.data
     lowerCamelCase__:   List[str]    						=node.next_node

 def __len__(self       :     int) ->int:



   '''simple docstring'''



   return sum(1 for _ in self)







 def __str__(self       :     Union[str, Any]) ->str:



   '''simple docstring'''



   return " -> ".join([str(UpperCAmelCase_) for node in self])





def   lowerCAmelCase_				( __a			,					__a	)  ->	SortedLinkedList:







  """simple docstring"""





  return SortedLinkedList(list(__a	) + list(__a	)	)


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     __A             =       SortedLinkedList
     print(merge_lists(SSL(test_data_odd), SSL(test_data_even)))

