import sys input = lambda: sys.stdin.readline().rstrip() # sys.setrecursionlimit(10**7) # sys.set_int_max_str_digits(10**6) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') def mp():return map(int,input().split()) def lmp():return list(map(int,input().split())) def lm1(LIST): return list(map(lambda x:x-1, LIST)) def mps(A):return [tuple(map(int, input().split())) for _ in range(A)] def stoi(LIST):return list(map(int,LIST)) def itos(LIST):return list(map(str,LIST)) def atoi(LIST): return [ord(i)-ord("a") for i in LIST] def Atoi(LIST): return [ord(i)-ord("A") for i in LIST] def LT(LIST,N): return LIST[bisect.bisect_left(LIST,N)-1] def LE(LIST,N): return LIST[bisect.bisect_right(LIST,N)-1] def GT(LIST,N): return LIST[bisect.bisect_right(LIST,N)] def GE(LIST,N): return LIST[bisect.bisect_left(LIST,N)] def bitA(X,A):return X & 1<