






"""simple docstring"""




class  lowercase_     :






      def __init__(     self  ,  a_						)						->Optional[int]:







        '''simple docstring'''


        _a					      =						data
        _a					      =						None
        _a					      =						None






      def __str__(     self						)						->str:







        '''simple docstring'''


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







class  lowercase_     :






      def __init__(     self						)						->List[Any]:







        '''simple docstring'''


        _a					      =						None
        _a					      =						None






      def __iter__(     self						)						->List[str]:







        '''simple docstring'''


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






      def __str__(     self						)						->int:







        '''simple docstring'''


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






      def __len__(     self						)						->List[Any]:







        '''simple docstring'''


        return sum(1 for _ in self						)






      def       lowerCamelCase__     (     self  ,  a_						)						->List[str]:







        '''simple docstring'''


        self.insert_at_nth(0  ,  a_						)






      def       lowerCamelCase__     (     self  ,  a_						)						->List[str]:







        '''simple docstring'''


        self.insert_at_nth(len(self						)  ,  a_						)






      def       lowerCamelCase__     (     self  ,  a_  ,  a_						)						->int:







        '''simple docstring'''


        _a					      =						len(self						)

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






      def       lowerCamelCase__     (     self						)						->Optional[int]:







        '''simple docstring'''


        return self.delete_at_nth(0						)






      def       lowerCamelCase__     (     self						)						->List[Any]:







        '''simple docstring'''


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






      def       lowerCamelCase__     (     self  ,  a_						)						->Optional[Any]:







        '''simple docstring'''


        _a					      =						len(self						)

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






      def       lowerCamelCase__     (     self  ,  a_						)						->str:







        '''simple docstring'''


        _a					      =						self.head

        while current.data != data:  # Find the position to delete
          if current.next:
            _a					      =						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
          _a					      =						current.next  # 1 --> 3
          _a					      =						current.previous  # 1 <--> 3
        return data






      def       lowerCamelCase__     (     self						)						->Optional[int]:







        '''simple docstring'''


        return len(self						) == 0







def 							lowerCAmelCase			(   )							->				None:







  '''simple docstring'''







  _a					      =						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)


