'''simple docstring'''




from __future__ import annotations





def      _UpperCAmelCase    (							_UpperCamelCase    :	int,   _UpperCamelCase    :	int,   _UpperCamelCase    :	int   )	->      tuple[float, float]:
    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      _UpperCAmelCase    (							_UpperCamelCase    :	int,   _UpperCamelCase    :	int,   _UpperCamelCase    :	int,   _UpperCamelCase    :	int = 2   )	->      None:
    ((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      _UpperCAmelCase    (							_UpperCamelCase    :	int,   _UpperCamelCase    :	int   )	->      int:
    if a < b:
        A_   ,A_     =   b, a

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

    return b





def      _UpperCAmelCase    (							_UpperCamelCase    :	int,   _UpperCamelCase    :	int   )	->      tuple[int, int, int]:
    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)














from __future__ import annotations

def    lowerCAmelCase__		(			_a				:	list[int]     ,					_a				:	int			):
		snake_case_       ,				snake_case_ :							Tuple         =				0, len(_a			) - 1
		while start_ind <= end_ind:
				if array[start_ind] == search_item:
						return start_ind
				elif array[end_ind] == search_item:
						return end_ind
				else:
						start_ind += 1
						end_ind -= 1
    # returns -1 if search_item is not found in array
		return -1


if __name__ == "__main__":
							print(double_linear_search(list(range(1_00)), 40))
