




from functools import lru_cache



@lru_cache
def   lowerCAmelCase						(						_lowerCAmelCase							:				int		):




 """simple docstring"""







 if not isinstance(_lowerCAmelCase  ,							_lowerCAmelCase		):
  raise TypeError("k must be an integer."		)
 if k < 0:
  raise ValueError("k integer must be greater or equal to zero."		)
 if k == 0:
  return 0
 elif k == 1:
  return 1
 else:
  return fibonacci(k - 1		) + fibonacci(k - 2		)



def   lowerCAmelCase						(						_lowerCAmelCase							:				list  ,							_lowerCAmelCase							:				int		):




 """simple docstring"""







 UpperCAmelCase__								=  len(_lowerCAmelCase		)
 # Find m such that F_m >= n where F_i is the i_th fibonacci number.
 UpperCAmelCase__								=  0
 while True:
  if fibonacci(_lowerCAmelCase		) >= len_list:
   UpperCAmelCase__								=  i
   break
  i += 1
 UpperCAmelCase__								=  0
 while fibb_k > 0:
  UpperCAmelCase__								=  min(
      offset + fibonacci(fibb_k - 1		)  ,							len_list - 1		)  # Prevent out of range
  UpperCAmelCase__								=  arr[index_k]
  if item_k_1 == val:
   return index_k
  elif val < item_k_1:
   fibb_k -= 1
  elif val > item_k_1:
   offset += fibonacci(fibb_k - 1		)
   fibb_k -= 2
 else:
  return -1


if __name__ == "__main__":
  import doctest

  doctest.testmod()











from __future__ import annotations



def   lowerCAmelCase						(						_lowerCAmelCase							:				int  ,							_lowerCAmelCase							:				int  ,							_lowerCAmelCase							:				int		):




 """simple docstring"""







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



def   lowerCAmelCase						(						_lowerCAmelCase							:				int  ,							_lowerCAmelCase							:				int  ,							_lowerCAmelCase							:				int  ,							_lowerCAmelCase							:				int = 2		):




 """simple docstring"""







 ((UpperCAmelCase__)	,	(UpperCAmelCase__))								=  diophantine(_lowerCAmelCase  ,							_lowerCAmelCase  ,							_lowerCAmelCase		)  # Initial value
 UpperCAmelCase__								=  greatest_common_divisor(_lowerCAmelCase  ,							_lowerCAmelCase		)
 UpperCAmelCase__								=  a // d
 UpperCAmelCase__								=  b // d

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



def   lowerCAmelCase						(						_lowerCAmelCase							:				int  ,							_lowerCAmelCase							:				int		):




 """simple docstring"""







 if a < b:
  UpperCAmelCase__	,	UpperCAmelCase__								=  b, a

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

 return b



def   lowerCAmelCase						(						_lowerCAmelCase							:				int  ,							_lowerCAmelCase							:				int		):




 """simple docstring"""







 assert a >= 0 and b >= 0

 if b == 0:
  UpperCAmelCase__	,	UpperCAmelCase__	,	UpperCAmelCase__								=  a, 1, 0
 else:
  ((UpperCAmelCase__)	,	(UpperCAmelCase__)	,	(UpperCAmelCase__))								=  extended_gcd(_lowerCAmelCase  ,							a % b		)
  UpperCAmelCase__								=  q
  UpperCAmelCase__								=  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)





