テンプレ import bisect , copy , heapq , math , sys from collections import * from functools import lru_cache from itertools import accumulate , combinations , permutations , product def input (): return sys . stdin . readline ()[: - 1 ] def ruiseki ( lst ): return [ 0 ] + list ( accumulate ( lst )) def celi ( a , b ): return - ( - a // b ) sys . setrecursionlimit ( 5000000 ) mod = pow ( 10