


'''simple docstring'''






import torch
from torch import nn






class   __snake_case			(  nn.Module):







    """simple docstring"""



    def __init__(  self       :    List[str]       ,		lowerCamelCase       :    int       ,		lowerCamelCase       :    Dict       ,		lowerCamelCase       :    Dict       ,		lowerCamelCase       :    List[str]       ,		lowerCamelCase       :    int=1       ,		lowerCamelCase       :    Optional[int]=False						)  ->    Optional[int]:
      super().__init__()

      lowerCAmelCase_     : List[str]     =  n_token
      lowerCAmelCase_     : Optional[int]     =  d_embed
      lowerCAmelCase_     : str     =  d_proj

      lowerCAmelCase_     : Union[str, Any]     =  cutoffs + [n_token]
      lowerCAmelCase_     : List[Any]     =  [0] + self.cutoffs
      lowerCAmelCase_     : int     =  div_val

      lowerCAmelCase_     : str     =  self.cutoffs[0]
      lowerCAmelCase_     : List[str]     =  len(self.cutoffs						) - 1
      lowerCAmelCase_     : int     =  self.shortlist_size + self.n_clusters

      if self.n_clusters > 0:
        lowerCAmelCase_     : Dict     =  nn.Parameter(torch.zeros(self.n_clusters       ,		self.d_embed						)						)
        lowerCAmelCase_     : Optional[Any]     =  nn.Parameter(torch.zeros(self.n_clusters						)						)

      lowerCAmelCase_     : List[str]     =  nn.ModuleList()
      lowerCAmelCase_     : int     =  nn.ParameterList()

      if div_val == 1:
        for i in range(len(self.cutoffs						)						):
          if d_proj != d_embed:
            self.out_projs.append(nn.Parameter(torch.FloatTensor(lowerCamelCase       ,		lowerCamelCase						)						)						)
          else:
            self.out_projs.append(lowerCamelCase						)

        self.out_layers.append(nn.Linear(lowerCamelCase       ,		lowerCamelCase						)						)
      else:
        for i in range(len(self.cutoffs						)						):
          lowerCAmelCase_,				lowerCAmelCase_     : List[str]     =  self.cutoff_ends[i], self.cutoff_ends[i + 1]
          lowerCAmelCase_     : Dict     =  d_embed // (div_val**i)

          self.out_projs.append(nn.Parameter(torch.FloatTensor(lowerCamelCase       ,		lowerCamelCase						)						)						)

          self.out_layers.append(nn.Linear(lowerCamelCase       ,		r_idx - l_idx						)						)

      lowerCAmelCase_     : Tuple     =  keep_order

    def __lowercase  (  self       :    Any       ,		lowerCamelCase       :    List[Any]       ,		lowerCamelCase       :    Tuple       ,		lowerCamelCase       :    Optional[Any]       ,		lowerCamelCase       :    Optional[Any]						)  ->    Union[str, Any]:
      if proj is None:
        lowerCAmelCase_     : List[Any]     =  nn.functional.linear(lowerCamelCase       ,		lowerCamelCase       ,		bias=lowerCamelCase						)
      else:
        # if CUDA_MAJOR <= 9 and CUDA_MINOR <= 1:
        lowerCAmelCase_     : int     =  nn.functional.linear(lowerCamelCase       ,		proj.t().contiguous()						)
        lowerCAmelCase_     : Any     =  nn.functional.linear(lowerCamelCase       ,		lowerCamelCase       ,		bias=lowerCamelCase						)
        # else:
        #     logit = torch.einsum('bd,de,ev->bv', (hidden, proj, weight.t()))
        #     if bias is not None:
        #         logit = logit + bias

      return logit

    def __lowercase  (  self       :    Any       ,		lowerCamelCase       :    Tuple       ,		lowerCamelCase       :    List[str]=None       ,		lowerCamelCase       :    Optional[Any]=False						)  ->    Union[str, Any]:

      if labels is not None:
        # Shift so that tokens < n predict n
        lowerCAmelCase_     : str     =  hidden[..., :-1, :].contiguous()
        lowerCAmelCase_     : Any     =  labels[..., 1:].contiguous()
        lowerCAmelCase_     : Dict     =  hidden.view(-1       ,		hidden.size(-1						)						)
        lowerCAmelCase_     : Tuple     =  labels.view(-1						)
        if hidden.size(0						) != labels.size(0						):
          raise RuntimeError("""Input and labels should have the same size in the batch dimension."""						)
      else:
        lowerCAmelCase_     : Union[str, Any]     =  hidden.view(-1       ,		hidden.size(-1						)						)

      if self.n_clusters == 0:
        lowerCAmelCase_     : Tuple     =  self._compute_logit(lowerCamelCase       ,		self.out_layers[0].weight       ,		self.out_layers[0].bias       ,		self.out_projs[0]						)
        if labels is not None:
          lowerCAmelCase_     : Any     =  labels != -1_00
          lowerCAmelCase_     : int     =  torch.zeros_like(lowerCamelCase       ,		dtype=hidden.dtype       ,		device=hidden.device						)
          lowerCAmelCase_     : Optional[Any]     =  (
              -nn.functional.log_softmax(lowerCamelCase       ,		dim=-1						)[mask].gather(1       ,		labels[mask].unsqueeze(1						)						).squeeze(1						)
          )
        else:
          lowerCAmelCase_     : Union[str, Any]     =  nn.functional.log_softmax(lowerCamelCase       ,		dim=-1						)
      else:
        # construct weights and biases
        lowerCAmelCase_,				lowerCAmelCase_     : Any     =  [], []
        for i in range(len(self.cutoffs						)						):
          if self.div_val == 1:
            lowerCAmelCase_,				lowerCAmelCase_     : Optional[int]     =  self.cutoff_ends[i], self.cutoff_ends[i + 1]
            lowerCAmelCase_     : int     =  self.out_layers[0].weight[l_idx:r_idx]
            lowerCAmelCase_     : Tuple     =  self.out_layers[0].bias[l_idx:r_idx]
          else:
            lowerCAmelCase_     : Union[str, Any]     =  self.out_layers[i].weight
            lowerCAmelCase_     : Union[str, Any]     =  self.out_layers[i].bias

          if i == 0:
            lowerCAmelCase_     : Optional[Any]     =  torch.cat([weight_i, self.cluster_weight]       ,		dim=0						)
            lowerCAmelCase_     : List[Any]     =  torch.cat([bias_i, self.cluster_bias]       ,		dim=0						)

          weights.append(lowerCamelCase						)
          biases.append(lowerCamelCase						)

        lowerCAmelCase_,				lowerCAmelCase_,				lowerCAmelCase_     : Dict     =  weights[0], biases[0], self.out_projs[0]

        lowerCAmelCase_     : Optional[int]     =  self._compute_logit(lowerCamelCase       ,		lowerCamelCase       ,		lowerCamelCase       ,		lowerCamelCase						)
        lowerCAmelCase_     : Optional[int]     =  nn.functional.log_softmax(lowerCamelCase       ,		dim=1						)

        if labels is None:
          lowerCAmelCase_     : Dict     =  hidden.new_empty((head_logit.size(0						), self.n_token)						)
        else:
          lowerCAmelCase_     : Optional[int]     =  torch.zeros_like(lowerCamelCase       ,		dtype=hidden.dtype       ,		device=hidden.device						)

        lowerCAmelCase_     : int     =  0
        lowerCAmelCase_     : Union[str, Any]     =  [0] + self.cutoffs
        for i in range(len(lowerCamelCase						) - 1						):
          lowerCAmelCase_,				lowerCAmelCase_     : List[str]     =  cutoff_values[i], cutoff_values[i + 1]

          if labels is not None:
            lowerCAmelCase_     : Union[str, Any]     =  (labels >= l_idx) & (labels < r_idx)
            lowerCAmelCase_     : Union[str, Any]     =  mask_i.nonzero().squeeze()

            if indices_i.numel() == 0:
              continue

            lowerCAmelCase_     : Dict     =  labels.index_select(0       ,		lowerCamelCase						) - l_idx
            lowerCAmelCase_     : str     =  head_logprob.index_select(0       ,		lowerCamelCase						)
            lowerCAmelCase_     : str     =  hidden.index_select(0       ,		lowerCamelCase						)
          else:
            lowerCAmelCase_     : Dict     =  hidden

          if i == 0:
            if labels is not None:
              lowerCAmelCase_     : int     =  head_logprob_i.gather(1       ,		target_i[:, None]						).squeeze(1						)
            else:
              lowerCAmelCase_     : Optional[int]     =  head_logprob[:, : self.cutoffs[0]]
          else:
            lowerCAmelCase_,				lowerCAmelCase_,				lowerCAmelCase_     : List[Any]     =  weights[i], biases[i], self.out_projs[i]

            lowerCAmelCase_     : List[Any]     =  self._compute_logit(lowerCamelCase       ,		lowerCamelCase       ,		lowerCamelCase       ,		lowerCamelCase						)
            lowerCAmelCase_     : Tuple     =  nn.functional.log_softmax(lowerCamelCase       ,		dim=1						)
            lowerCAmelCase_     : Any     =  self.cutoffs[0] + i - 1  # No probability for the head cluster
            if labels is not None:
              lowerCAmelCase_     : Optional[int]     =  head_logprob_i[:, cluster_prob_idx] + tail_logprob_i.gather(
                  1       ,		target_i[:, None]						).squeeze(1						)
            else:
              lowerCAmelCase_     : Dict     =  head_logprob[:, cluster_prob_idx, None] + tail_logprob_i
              lowerCAmelCase_     : Union[str, Any]     =  logprob_i

          if labels is not None:
            if (hasattr(self       ,		"""keep_order"""						) and self.keep_order) or keep_order:
              out.index_copy_(0       ,		lowerCamelCase       ,		-logprob_i						)
            else:
              out[offset : offset + logprob_i.size(0						)].copy_(-logprob_i						)
            offset += logprob_i.size(0						)

      return out





    def __lowercase  (  self       :    Optional[Any]       ,		lowerCamelCase       :    Dict						)  ->    Union[str, Any]:
      if self.n_clusters == 0:
        lowerCAmelCase_     : int     =  self._compute_logit(lowerCamelCase       ,		self.out_layers[0].weight       ,		self.out_layers[0].bias       ,		self.out_projs[0]						)
        return nn.functional.log_softmax(lowerCamelCase       ,		dim=-1						)
      else:
        # construct weights and biases
        lowerCAmelCase_,				lowerCAmelCase_     : Optional[int]     =  [], []
        for i in range(len(self.cutoffs						)						):
          if self.div_val == 1:
            lowerCAmelCase_,				lowerCAmelCase_     : Dict     =  self.cutoff_ends[i], self.cutoff_ends[i + 1]
            lowerCAmelCase_     : Optional[int]     =  self.out_layers[0].weight[l_idx:r_idx]
            lowerCAmelCase_     : str     =  self.out_layers[0].bias[l_idx:r_idx]
          else:
            lowerCAmelCase_     : List[str]     =  self.out_layers[i].weight
            lowerCAmelCase_     : List[Any]     =  self.out_layers[i].bias

          if i == 0:
            lowerCAmelCase_     : str     =  torch.cat([weight_i, self.cluster_weight]       ,		dim=0						)
            lowerCAmelCase_     : Union[str, Any]     =  torch.cat([bias_i, self.cluster_bias]       ,		dim=0						)

          weights.append(lowerCamelCase						)
          biases.append(lowerCamelCase						)

        lowerCAmelCase_,				lowerCAmelCase_,				lowerCAmelCase_     : int     =  weights[0], biases[0], self.out_projs[0]
        lowerCAmelCase_     : List[Any]     =  self._compute_logit(lowerCamelCase       ,		lowerCamelCase       ,		lowerCamelCase       ,		lowerCamelCase						)

        lowerCAmelCase_     : Tuple     =  hidden.new_empty((head_logit.size(0						), self.n_token)						)
        lowerCAmelCase_     : Union[str, Any]     =  nn.functional.log_softmax(lowerCamelCase       ,		dim=1						)

        lowerCAmelCase_     : List[Any]     =  [0] + self.cutoffs
        for i in range(len(lowerCamelCase						) - 1						):
          lowerCAmelCase_,				lowerCAmelCase_     : int     =  cutoff_values[i], cutoff_values[i + 1]

          if i == 0:
            lowerCAmelCase_     : List[Any]     =  head_logprob[:, : self.cutoffs[0]]
          else:
            lowerCAmelCase_,				lowerCAmelCase_,				lowerCAmelCase_     : Tuple     =  weights[i], biases[i], self.out_projs[i]

            lowerCAmelCase_     : Optional[int]     =  self._compute_logit(lowerCamelCase       ,		lowerCamelCase       ,		lowerCamelCase       ,		lowerCamelCase						)
            lowerCAmelCase_     : List[Any]     =  nn.functional.log_softmax(lowerCamelCase       ,		dim=1						)

            lowerCAmelCase_     : Optional[int]     =  head_logprob[:, -i] + tail_logprob_i
            lowerCAmelCase_     : Tuple     =  logprob_i

        return out







'''simple docstring'''






from __future__ import annotations







def 							UpperCamelCase_     (       A__   :  list				,       A__   :  int				,       A__   :  int				,       A__   :  int   ):
  '''simple docstring'''





  lowerCAmelCase_     : int     =  []
  lowerCAmelCase_,				lowerCAmelCase_     : Any     =  input_list[low:mid], input_list[mid : high + 1]
  while left and right:
    result.append((left if left[0] <= right[0] else right).pop(0   )   )
  lowerCAmelCase_     : Dict     =  result + left + right
  return input_list







def 							UpperCamelCase_     (       A__   :  list   ):
  '''simple docstring'''





  if len(A__   ) <= 1:
    return input_list
  lowerCAmelCase_     : str     =  list(A__   )

  # iteration for two-way merging
  lowerCAmelCase_     : Dict     =  2
  while p <= len(A__   ):
    # getting low, high and middle value for merge-sort of single list
    for i in range(0				,       len(A__   )				,       A__   ):
      lowerCAmelCase_     : Tuple     =  i
      lowerCAmelCase_     : List[str]     =  i + p - 1
      lowerCAmelCase_     : Optional[Any]     =  (low + high + 1) // 2
      lowerCAmelCase_     : List[str]     =  merge(A__				,       A__				,       A__				,       A__   )
    # final merge of last two parts
    if p * 2 >= len(A__   ):
      lowerCAmelCase_     : Union[str, Any]     =  i
      lowerCAmelCase_     : Dict     =  merge(A__				,       0				,       A__				,       len(A__   ) - 1   )
      break
    p *= 2

  return input_list


if __name__ == "__main__":
  __A   :    int											= input("Enter numbers separated by a comma:\n").strip()
  if user_input == "":
    __A   :    str											= []
  else:
    __A   :    Optional[Any]											= [int(item.strip()) for item in user_input.split(",")]
  print(iter_merge_sort(unsorted))



