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<