

import enum
import shutil
import sys


a_     ,	a_						     =    shutil.get_terminal_size()

a_						     =    {'UP': 'A', 'DOWN': 'B', 'RIGHT': 'C', 'LEFT': 'D'}






class _UpperCamelCase							(							enum.Enum   ):
			'''simple docstring'''







			lowerCamelCase__           =0
			lowerCamelCase__           =1

def  lowerCamelCase__ (					_a							,			_a=""):
	sys.stdout.write(str(_a) + end)
	sys.stdout.flush()

def  lowerCamelCase__ (					_a							,			_a							,			_a=""):
	forceWrite(f"\u001b[{color}m{content}\u001b[0m"							,			_a)

def  lowerCamelCase__ (					):
	forceWrite("\r")

def  lowerCamelCase__ (					_a							,			_a):
	forceWrite(f"\033[{num_lines}{CURSOR_TO_CHAR[direction.upper()]}")

def  lowerCamelCase__ (					):
	forceWrite(" " * TERMINAL_WIDTH)
	reset_cursor()


def  lowerCamelCase__ (					):
	reset_cursor()
	forceWrite("-" * TERMINAL_WIDTH)



from __future__ import annotations

def  lowerCamelCase__ (					_a							,			_a):
	if b == 0:
		return (1, 0)
	((SCREAMING_SNAKE_CASE)     ,(SCREAMING_SNAKE_CASE))   :      Tuple				     =       extended_euclid(_a							,			a % b)
	SCREAMING_SNAKE_CASE   :      Dict				     =       a // b
	return (y, x - k * y)

def  lowerCamelCase__ (					_a							,			_a							,			_a							,			_a):
	((SCREAMING_SNAKE_CASE)     ,(SCREAMING_SNAKE_CASE))   :      str				     =       extended_euclid(_a							,			_a)
	SCREAMING_SNAKE_CASE   :      str				     =       na * na
	SCREAMING_SNAKE_CASE   :      int				     =       ra * x * na + ra * y * na
	return (n % m + m) % m

def  lowerCamelCase__ (					_a							,			_a):
	((SCREAMING_SNAKE_CASE)     ,(SCREAMING_SNAKE_CASE))   :      List[str]				     =       extended_euclid(_a							,			_a)
	if b < 0:
		SCREAMING_SNAKE_CASE   :      int				     =       (b % n + n) % n
	return b

def  lowerCamelCase__ (					_a							,			_a							,			_a							,			_a):
	SCREAMING_SNAKE_CASE     ,SCREAMING_SNAKE_CASE   :      Dict				     =       invert_modulo(_a							,			_a), invert_modulo(_a							,			_a)
	SCREAMING_SNAKE_CASE   :      Optional[int]				     =       na * na
	SCREAMING_SNAKE_CASE   :      Optional[Any]				     =       ra * x * na + ra * y * na
	return (n % m + m) % m


if __name__ == "__main__":
			from doctest import testmod

			testmod(name='chinese_remainder_theorem', verbose=True)
			testmod(name='chinese_remainder_theorem2', verbose=True)
			testmod(name='invert_modulo', verbose=True)
			testmod(name='extended_euclid', verbose=True)