from math import ceil




def       __lowerCAmelCase      (						A_   : int						,	A_   : Dict					)    ->  Tuple:
  __UpperCAmelCase						    =       list(range(0						,	A_					)					)

  __UpperCAmelCase						    =       [item for sublist in list(device_map.values()					) for item in sublist]

  # Duplicate check
  __UpperCAmelCase						    =       []
  for i in device_map_blocks:
    if device_map_blocks.count(A_					) > 1 and i not in duplicate_blocks:
      duplicate_blocks.append(A_					)
    # Missing blocks
  __UpperCAmelCase						    =       [i for i in blocks if i not in device_map_blocks]
  __UpperCAmelCase						    =       [i for i in device_map_blocks if i not in blocks]

  if len(A_					) != 0:
    raise ValueError(
        "Duplicate attention blocks specified in device_map. Attention blocks must be specified to one device."
        " These attention blocks were specified more than once: " + str(A_					)					)
  if len(A_					) != 0:
    raise ValueError(
        "There are attention blocks for this model that are not specified in the device_map. Add these attention "
        "blocks to a device on the device_map: " + str(A_					)					)
  if len(A_					) != 0:
    raise ValueError(
        "The device_map contains more attention blocks than this model has. Remove these from the device_map:"
        + str(A_					)					)





def       __lowerCAmelCase      (						A_   : Tuple						,	A_   : Optional[Any]					)    ->  int:
  __UpperCAmelCase						    =       list(range(A_					)					)
  __UpperCAmelCase						    =       int(ceil(n_layers / len(A_					)					)					)
  __UpperCAmelCase						    =       [layers[i : i + n_blocks] for i in range(0						,	A_						,	A_					)]

  return dict(zip(A_						,	A_					)					)




def       __lowerCAmelCase      (						A_   : str					)    ->  Any:
  if not head:
    return True
  # split the list to two parts
  __UpperCAmelCase    ,		__UpperCAmelCase						    =       head.next, head
  while fast and fast.next:
    __UpperCAmelCase						    =       fast.next.next
    __UpperCAmelCase						    =       slow.next
  __UpperCAmelCase						    =       slow.next
  __UpperCAmelCase						    =       None  # Don't forget here! But forget still works!
  # reverse the second part
  __UpperCAmelCase						    =       None
  while second:
    __UpperCAmelCase						    =       second.next
    __UpperCAmelCase						    =       node
    __UpperCAmelCase						    =       second
    __UpperCAmelCase						    =       nxt
  # compare two parts
  # second part has the same or one less node
  while node:
    if node.val != head.val:
      return False
    __UpperCAmelCase						    =       node.next
    __UpperCAmelCase						    =       head.next
  return True




def       __lowerCAmelCase      (						A_   : Optional[Any]					)    ->  Optional[Any]:
  if not head or not head.next:
    return True

  # 1. Get the midpoint (slow)
  __UpperCAmelCase						    =       __UpperCAmelCase						    =       __UpperCAmelCase						    =       head
  while fast and fast.next:
    __UpperCAmelCase    ,		__UpperCAmelCase						    =       fast.next.next, slow.next

  # 2. Push the second half into the stack
  __UpperCAmelCase						    =       [slow.val]
  while slow.next:
    __UpperCAmelCase						    =       slow.next
    stack.append(slow.val					)

  # 3. Comparison
  while stack:
    if stack.pop() != cur.val:
      return False
    __UpperCAmelCase						    =       cur.next

  return True





def       __lowerCAmelCase      (						A_   : int					)    ->  Optional[int]:
  if not head or not head.next:
    return True
  __UpperCAmelCase						    =       {}
  __UpperCAmelCase						    =       0
  while head:
    if head.val in d:
      d[head.val].append(A_					)
    else:
      __UpperCAmelCase						    =       [pos]
    __UpperCAmelCase						    =       head.next
    pos += 1
  __UpperCAmelCase						    =       pos - 1
  __UpperCAmelCase						    =       0
  for v in d.values():
    if len(A_					) % 2 != 0:
      middle += 1
    else:
      __UpperCAmelCase						    =       0
      for i in range(0						,	len(A_					)					):
        if v[i] + v[len(A_					) - 1 - step] != checksum:
          return False
        step += 1
    if middle > 1:
      return False
  return True



