import algorithm import deques import options import sequtils import sets import std/heapqueue import std/math import std/tables import strformat import strutils #{.checks: off.} {.warning[UnusedImport]: off.} {.hint[XDeclaredButNotUsed]: off.} const letter: string = "abcdefghijklmnopqrstuvwxyz" const Letter: string = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" const MAX_INT: int = high(int) const MIN_INT: int = low(int) const MOD998244353 = 998_244_353 const MOD1000000007 = 1_000_000_007 const DXDY4: seq[tuple[x, y: int]] = @[(0, 1), (1, 0), (0, -1), (-1, 0)] const DXDY8: seq[tuple[x, y: int]] = @[(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, -1), (-1, 1)] 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(' '): return c proc nextString(): string = var get = false result = "" while true: var c = getchar() if int(c) > int(' '): get = true result.add(c) else: if get: break get = false proc nextStrings(n: int): seq[string] = for _ in 0.. 0: var i = start while i <= stop: yield i i+=step else: var i = start while i >= stop: yield i i+=step func `+`(a, b: bool): bool = a or b func `*`(a, b: bool): bool = a and b func `+`(a: var bool, b: bool): bool = a = a or b func `*`(a: var bool, b: bool): bool = a = a and b func `|`(a, b: bool): bool = a or b proc `|=`(a: var bool, b: bool) = a = a or b func `|`(c1, c2: int): int = c1 or c2 func `&`(a, b: bool): bool = a and b 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 func ceil[T: SomeInteger](b, a: T): T = (a+b-1) div a func all(a: openArray[bool]): bool = result = true for x in a: result &= x func any(a: openArray[bool]): bool = result = false for x in a: result |= x # 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..