
from __future__ import annotations




def 				__magic_name__				(     __lowerCAmelCase			:		int	,						__lowerCAmelCase			:		int	,						__lowerCAmelCase			:		int							)    ->     tuple[float, float]:
				assert (
				    c % greatest_common_divisor(__lowerCAmelCase	,						__lowerCAmelCase							) == 0
				)  # greatest_common_divisor(a,b) function implemented below
				((__lowerCamelCase)      ,					(__lowerCamelCase)      ,					(__lowerCamelCase))					      =			extended_gcd(__lowerCAmelCase	,						__lowerCAmelCase							)  # extended_gcd(a,b) function implemented below
				__lowerCamelCase					      =			c / d
				return (r * x, r * y)




def 				__magic_name__				(     __lowerCAmelCase			:		int	,						__lowerCAmelCase			:		int	,						__lowerCAmelCase			:		int	,						__lowerCAmelCase			:		int = 2							)    ->     None:
				((__lowerCamelCase)      ,					(__lowerCamelCase))					      =			diophantine(__lowerCAmelCase	,						__lowerCAmelCase	,						__lowerCAmelCase							)  # Initial value
				__lowerCamelCase					      =			greatest_common_divisor(__lowerCAmelCase	,						__lowerCAmelCase							)
				__lowerCamelCase					      =			a // d
				__lowerCamelCase					      =			b // d

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




def 				__magic_name__				(     __lowerCAmelCase			:		int	,						__lowerCAmelCase			:		int							)    ->     int:
				if a < b:
								__lowerCamelCase      ,					__lowerCamelCase					      =			b, a

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

				return b




def 				__magic_name__				(     __lowerCAmelCase			:		int	,						__lowerCAmelCase			:		int							)    ->     tuple[int, int, int]:
				assert a >= 0 and b >= 0

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





def 				__magic_name__				(     __lowerCAmelCase			:		list	,						__lowerCAmelCase			:		int	,						__lowerCAmelCase			:		int	,						__lowerCAmelCase			:		int							)    ->     int:
				__lowerCamelCase					      =			int((lower_bound + upper_bound) // 2							)
				if array[r] == value:
								return r
				if lower_bound >= upper_bound:
								return -1
				if array[r] < value:
								return binary_search(__lowerCAmelCase	,						r + 1	,						__lowerCAmelCase	,						__lowerCAmelCase							)
				else:
								return binary_search(__lowerCAmelCase	,						__lowerCAmelCase	,						r - 1	,						__lowerCAmelCase							)




def 				__magic_name__				(     __lowerCAmelCase			:		int	,						__lowerCAmelCase			:		list							)    ->     list:
				__lowerCamelCase					      =			0
				if matrix[index][0] == value:
								return [index, 0]
				while index < len(__lowerCAmelCase							) and matrix[index][0] < value:
								__lowerCamelCase					      =			binary_search(matrix[index]	,						0	,						len(matrix[index]							) - 1	,						__lowerCAmelCase							)
								if r != -1:
												return [index, r]
								index += 1
				return [-1, -1]


if __name__ == "__main__":
					import doctest

					doctest.testmod()



