
"""simple docstring"""







class      __a      :







       def __init__(       self				,lowerCamelCase_		):



          '''simple docstring'''

          _UpperCAmelCase 						=       data
          _UpperCAmelCase 						=       None
          _UpperCAmelCase 						=       None







       def __str__(       self		):



          '''simple docstring'''

          return f'''{self.data}'''






class      __a      :







       def __init__(       self		):



          '''simple docstring'''

          _UpperCAmelCase 						=       None
          _UpperCAmelCase 						=       None







       def __iter__(       self		):



          '''simple docstring'''

          _UpperCAmelCase 						=       self.head
          while node:
             yield node.data
             _UpperCAmelCase 						=       node.next







       def __str__(       self		):



          '''simple docstring'''

          return "->".join([str(a_		) for item in self]		)







       def __len__(       self		):



          '''simple docstring'''

          return sum(1 for _ in self		)







       def  _snake_case      (       self				,lowerCamelCase_		):



          '''simple docstring'''

          self.insert_at_nth(0				,a_		)







       def  _snake_case      (       self				,lowerCamelCase_		):



          '''simple docstring'''

          self.insert_at_nth(len(self		)				,a_		)







       def  _snake_case      (       self				,lowerCamelCase_				,lowerCamelCase_		):



          '''simple docstring'''

          _UpperCAmelCase 						=       len(self		)

          if not 0 <= index <= length:
             raise IndexError("list index out of range"		)
          _UpperCAmelCase 						=       Node(a_		)
          if self.head is None:
             _UpperCAmelCase 						=       _UpperCAmelCase 						=       new_node
          elif index == 0:
             _UpperCAmelCase 						=       new_node
             _UpperCAmelCase 						=       self.head
             _UpperCAmelCase 						=       new_node
          elif index == length:
             _UpperCAmelCase 						=       new_node
             _UpperCAmelCase 						=       self.tail
             _UpperCAmelCase 						=       new_node
          else:
             _UpperCAmelCase 						=       self.head
             for _ in range(0				,a_		):
                _UpperCAmelCase 						=       temp.next
             _UpperCAmelCase 						=       new_node
             _UpperCAmelCase 						=       temp.previous
             _UpperCAmelCase 						=       temp
             _UpperCAmelCase 						=       new_node







       def  _snake_case      (       self		):



          '''simple docstring'''

          return self.delete_at_nth(0		)







       def  _snake_case      (       self		):



          '''simple docstring'''

          return self.delete_at_nth(len(self		) - 1		)







       def  _snake_case      (       self				,lowerCamelCase_		):



          '''simple docstring'''

          _UpperCAmelCase 						=       len(self		)

          if not 0 <= index <= length - 1:
             raise IndexError("list index out of range"		)
          _UpperCAmelCase 						=       self.head  # default first node
          if length == 1:
             _UpperCAmelCase 						=       _UpperCAmelCase 						=       None
          elif index == 0:
             _UpperCAmelCase 						=       self.head.next
             _UpperCAmelCase 						=       None
          elif index == length - 1:
             _UpperCAmelCase 						=       self.tail
             _UpperCAmelCase 						=       self.tail.previous
             _UpperCAmelCase 						=       None
          else:
             _UpperCAmelCase 						=       self.head
             for _ in range(0				,a_		):
                _UpperCAmelCase 						=       temp.next
             _UpperCAmelCase 						=       temp
             _UpperCAmelCase 						=       temp.previous
             _UpperCAmelCase 						=       temp.next
          return delete_node.data







       def  _snake_case      (       self				,lowerCamelCase_		):



          '''simple docstring'''

          _UpperCAmelCase 						=       self.head

          while current.data != data:  # Find the position to delete
             if current.next:
                _UpperCAmelCase 						=       current.next
             else:  # We have reached the end an no value matches
                raise ValueError("No data matching given value"		)

          if current == self.head:
             self.delete_head()

          elif current == self.tail:
             self.delete_tail()

          else:  # Before: 1 <--> 2(current) <--> 3
             _UpperCAmelCase 						=       current.next  # 1 --> 3
             _UpperCAmelCase 						=       current.previous  # 1 <--> 3
          return data







       def  _snake_case      (       self		):



          '''simple docstring'''

          return len(self		) == 0



def       __UpperCAmelCase		(		)  ->							None:
   _UpperCAmelCase 						=       DoublyLinkedList()
   assert linked_list.is_empty() is True
   assert str(UpperCamelCase_					) == ""

   try:
      linked_list.delete_head()
      raise AssertionError  # This should not happen.
   except IndexError:
      assert True  # This should happen.

   try:
      linked_list.delete_tail()
      raise AssertionError  # This should not happen.
   except IndexError:
      assert True  # This should happen.

   for i in range(10					):
      assert len(UpperCamelCase_					) == i
      linked_list.insert_at_nth(UpperCamelCase_     ,	i + 1					)
   assert str(UpperCamelCase_					) == "->".join(str(UpperCamelCase_					) for i in range(1     ,	11					)					)

   linked_list.insert_at_head(0					)
   linked_list.insert_at_tail(11					)
   assert str(UpperCamelCase_					) == "->".join(str(UpperCamelCase_					) for i in range(0     ,	12					)					)

   assert linked_list.delete_head() == 0
   assert linked_list.delete_at_nth(9					) == 10
   assert linked_list.delete_tail() == 11
   assert len(UpperCamelCase_					) == 9
   assert str(UpperCamelCase_					) == "->".join(str(UpperCamelCase_					) for i in range(1     ,	10					)					)


if __name__ == "__main__":
  from doctest import testmod

  testmod()









"""simple docstring"""




from __future__ import annotations






def 							lowerCAmelCase			(   UpperCamelCase_:				int  ,			UpperCamelCase_:				int  ,			UpperCamelCase_:				int       )							->				tuple[float, float]:







  '''simple docstring'''







  assert (
      c % greatest_common_divisor(UpperCamelCase_  ,			UpperCamelCase_       ) == 0
  )  # greatest_common_divisor(a,b) function implemented below
  ((_a)      ,						(_a)      ,						(_a))					      =						extended_gcd(UpperCamelCase_  ,			UpperCamelCase_       )  # extended_gcd(a,b) function implemented below
  _a					      =						c / d
  return (r * x, r * y)






def 							lowerCAmelCase			(   UpperCamelCase_:				int  ,			UpperCamelCase_:				int  ,			UpperCamelCase_:				int  ,			UpperCamelCase_:				int = 2       )							->				None:







  '''simple docstring'''







  ((_a)      ,						(_a))					      =						diophantine(UpperCamelCase_  ,			UpperCamelCase_  ,			UpperCamelCase_       )  # Initial value
  _a					      =						greatest_common_divisor(UpperCamelCase_  ,			UpperCamelCase_       )
  _a					      =						a // d
  _a					      =						b // d

  for i in range(UpperCamelCase_       ):
    _a					      =						xa + i * q
    _a					      =						ya - i * p
    print(UpperCamelCase_  ,			UpperCamelCase_       )






def 							lowerCAmelCase			(   UpperCamelCase_:				int  ,			UpperCamelCase_:				int       )							->				int:







  '''simple docstring'''







  if a < b:
    _a      ,						_a					      =						b, a

  while a % b != 0:
    _a      ,						_a					      =						b, a % b

  return b






def 							lowerCAmelCase			(   UpperCamelCase_:				int  ,			UpperCamelCase_:				int       )							->				tuple[int, int, int]:







  '''simple docstring'''







  assert a >= 0 and b >= 0

  if b == 0:
    _a      ,						_a      ,						_a					      =						a, 1, 0
  else:
    ((_a)      ,						(_a)      ,						(_a))					      =						extended_gcd(UpperCamelCase_  ,			a % b       )
    _a					      =						q
    _a					      =						p - q * (a // b)

  assert a % d == 0 and b % d == 0
  assert d == a * x + b * y

  return (d, x, y)


if __name__ == "__main__":
     from doctest import testmod

     testmod(name="""diophantine""", verbose=True)
     testmod(name="""diophantine_all_soln""", verbose=True)
     testmod(name="""extended_gcd""", verbose=True)
     testmod(name="""greatest_common_divisor""", verbose=True)


