import algorithm import options import sequtils import sets import std/heapqueue import std/math import std/tables import strformat import strutils const letter: string = "abcdefghijklmnopqrstuvwxyz" const Letter: string = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" const MAX_INT: int = high(int) const MIN_INT: int = low(int) proc scanf(formatstr: cstring){.header: "", varargs.} proc getchar(): char {.header: "", varargs.} proc nextInt(): int = scanf("%lld", addr result) proc nextInts(n: int): seq[int] = var res = newSeq[int](n) for i in 0.. int(' '): get = true result.add(c) else: if get: break get = false func toInt(b: bool): int = if b: return 1 else: return 0 func `+`(a: int, b: bool): int = a + (b.toInt) func `+`(a: bool, b: int): int = (a.toInt) + b func `-`(a: int, b: bool): int = a - (b.toInt) func `-`(a: bool, b: int): int = (a.toInt) - b func `*`(a: int, b: bool): int = a * (b.toInt) func `*`(a: bool, b: int): int = (a.toInt) * b proc `|=`(a: var bool, b: bool) = a = a or b func `|`(c1, c2: int): int = c1 or c2 proc `&=`(a: var bool, b: bool) = a = a and b func `&`(c1, c2: int): int = c1 and c2 func `//`(a, b: int): int = a div b proc `//=`(a: var int, b: int) = a = a div b func `%`(a: int, b: Positive): int = result = a mod b if result < 0: result += b proc `%=`(a: var int, b: int) = a = a mod b func `<<`(a: int, s: int): int = a shl s func `>>`(a: int, s: int): int = a shr s proc `>>=`(a: var int, b: int) = a = a shr b proc `[]`(n, i: Natural): int = (n >> i) & 1 # Z/mo Z上のaの逆元 func inv(a, mo: int): int = var r = (mo, a) var x = (0, 1) while r[1] != 0: x = (x[1], (x[0] - (r[0] div r[1]) * x[1]) % mo) r = (r[1], r[0] % r[1]) if r[0] == 1: return x[0] else: return -1 func bitLength(n: Natural): int = result = 0 var num = abs(n) while num > 0: result += 1 num = num shr 1 proc chmax[T](a: var T, vars: varargs[T]): bool {.discardable.} = let target = max(vars) if a < target: a = target return true else: return false proc chmin[T](a: var T, vars: varargs[T]): bool {.discardable.} = let target = min(vars) if a > target: a = target return true else: return false template present(a: typed): bool = a.len != 0 template empty(a: typed): bool = a.len == 0 template rep(idx: untyped, n: SomeOrdinal, act: untyped): untyped = for idx in 0 ..< n: act template loop(body: untyped): untyped = while true: body func Yn(cond: bool, yes: string = "Yes", no: string = "No"): string = if cond: yes else: no func `<`[T](u, v: openArray[T]): bool = assert u.len == v.len for j in 0..