'''simple docstring'''





from __future__ import annotations

from collections.abc import Iterable
from dataclasses import dataclass
from typing import Any



class   UpperCamelCase					:







    """simple docstring"""





    A     :    List[Any]				=			("_front", "_back", "_len")



    @dataclass
    class   UpperCamelCase					:







        """simple docstring"""





        A     :    Union[str, Any]				=			None
        A     :    Union[str, Any]				=			None
        A     :    Dict				=			None






    class   UpperCamelCase					:







        """simple docstring"""





        A     :    Optional[Any]				=			("_cur",)





        def __init__(					self     :						List[Any]							,							UpperCAmelCase_     :						Deque._Node | None):


             """simple docstring"""







             a					:							Any							= cur





        def __iter__(					self     :						List[Any]):


             """simple docstring"""







             return self







        def    SCREAMING_SNAKE_CASE_     (					self     :						Dict):


             """simple docstring"""







             if self._cur is None:
                  # finished iterating
                  raise StopIteration
             a					:							Tuple							= self._cur.val
             a					:							str							= self._cur.next_node

             return val






    def __init__(					self     :						int							,							UpperCAmelCase_     :						Iterable[Any] | None = None):


         """simple docstring"""







         a					:							Any							= None
         a					:							Any							= None
         a					:							int							= 0

         if iterable is not None:
              # append every value to the deque
              for val in iterable:
                   self.append(UpperCamelCase_)





    def    SCREAMING_SNAKE_CASE_     (					self     :						Optional[Any]							,							UpperCAmelCase_     :						Any):


         """simple docstring"""







         a					:							str							= self._Node(UpperCamelCase_							,							UpperCamelCase_							,							UpperCamelCase_)
         if self.is_empty():
              # front = back
              a					:							Dict							= node
              a					:							Tuple							= 1
         else:
              # connect nodes
              a					:							int							= node
              a					:							Optional[int]							= self._back
              a					:							Union[str, Any]							= node  # assign new back to the new node

              self._len += 1

              # make sure there were no errors
              assert not self.is_empty(), "Error on appending value."





    def    SCREAMING_SNAKE_CASE_     (					self     :						int							,							UpperCAmelCase_     :						Any):


         """simple docstring"""







         a					:							Tuple							= self._Node(UpperCamelCase_							,							UpperCamelCase_							,							UpperCamelCase_)
         if self.is_empty():
              # front = back
              a					:							Tuple							= node
              a					:							List[str]							= 1
         else:
              # connect nodes
              a					:							str							= self._front
              a					:							Dict							= node
              a					:							str							= node  # assign new front to the new node

              self._len += 1

              # make sure there were no errors
              assert not self.is_empty(), "Error on appending value."





    def    SCREAMING_SNAKE_CASE_     (					self     :						List[str]							,							UpperCAmelCase_     :						Iterable[Any]):


         """simple docstring"""







         for val in iterable:
              self.append(UpperCamelCase_)





    def    SCREAMING_SNAKE_CASE_     (					self     :						List[Any]							,							UpperCAmelCase_     :						Iterable[Any]):


         """simple docstring"""







         for val in iterable:
              self.appendleft(UpperCamelCase_)





    def    SCREAMING_SNAKE_CASE_     (					self     :						int):


         """simple docstring"""







         assert not self.is_empty(), "Deque is empty."

         a					:							List[str]							= self._back
         a					:							List[Any]							= self._back.prev_node  # set new back
         # drop the last node - python will deallocate memory automatically
         a					:							int							= None

         self._len -= 1

         return topop.val





    def    SCREAMING_SNAKE_CASE_     (					self     :						Any):


         """simple docstring"""







         assert not self.is_empty(), "Deque is empty."

         a					:							List[Any]							= self._front
         a					:							Optional[int]							= self._front.next_node  # set new front and drop the first node
         a					:							Tuple							= None

         self._len -= 1

         return topop.val





    def    SCREAMING_SNAKE_CASE_     (					self     :						Dict):


         """simple docstring"""







         return self._front is None





    def __len__(					self     :						Optional[int]):


         """simple docstring"""







         return self._len





    def __eq__(					self     :						Tuple							,							UpperCAmelCase_     :						object):


         """simple docstring"""







         if not isinstance(UpperCamelCase_							,							UpperCamelCase_):
              return NotImplemented

         a					:							List[str]							= self._front
         a					:							List[str]							= other._front

         # if the length of the dequeues are not the same, they are not equal
         if len(self) != len(UpperCamelCase_):
              return False

         while me is not None and oth is not None:
              # compare every value
              if me.val != oth.val:
                   return False
              a					:							Optional[Any]							= me.next_node
              a					:							List[str]							= oth.next_node

         return True





    def __iter__(					self     :						Dict):


         """simple docstring"""







         return Deque._Iterator(self._front)







    def __repr__(					self     :						Union[str, Any]):


         """simple docstring"""







         a					:							str							= []
         a					:							Any							= self._front
         while aux is not None:
              # append the values in a list to display
              values_list.append(aux.val)
              a					:							Union[str, Any]							= aux.next_node

         return f"""[{', '.join(repr(UpperCamelCase_) for val in values_list)}]"""


if __name__ == "__main__":
      import doctest

      doctest.testmod()






'''simple docstring'''

from __future__ import annotations

import sys







def     __UpperCamelCase					(				_lowercase       )			->      int:
	if n < 0:
		raise ValueError('Negative arguments are not supported'       )
	return _fib(_lowercase       )[0]







def     __UpperCamelCase					(				_lowercase       )			->      tuple[int, int]:
	if n == 0:  # (F(0), F(1))
		return (0, 1)

	# F(2n) = F(n)[2F(n+1) − F(n)]
	# F(2n+1) = F(n+1)^2+F(n)^2
	_lowercase	,     _lowercase       :							List[str]  	=		_fib(n // 2       )
	_lowercase       :							Dict  	=		a * (b * 2 - a)
	_lowercase       :							Union[str, Any]  	=		a * a + b * b
	return (d, c + d) if n % 2 else (c, d)


if __name__ == "__main__":
		_A					:     Optional[Any]      =int(sys.argv[1])
		print(F'''fibonacci({n}) is {fibonacci(n)}''')
