import algorithm import deques import macros import options import posix import sequtils import sets import std/heapqueue import std/math import std/tables import strformat import strutils import sugar # import atcoder/modint # import atcoder/dsu # import atcoder/segtree # import atcoder/scc #{.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 exit() = exitnow(0) proc getchar(): char {.header: "", varargs.} proc scanf(formatstr: cstring){.header: "", varargs.} proc scan[T](): T = when T is int: scanf("%lld", addr result) elif T is float: scanf("%lf", addr result) elif T is int64: scanf("%lld", addr result) elif T is char: while true: var c = getchar() if int(c) > int(' '): return c elif T is 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 else: assert false, "その型引数に対するscanは定義されていません" proc scan[T](n: int): seq[T] = for _ in 0.. int(' '): return c proc nextChars(h, w: int): seq[seq[char]] = result = newSeqWith(h, newSeqWith(w, '.')) for y in 0.. int(' '): get = true result.add(c) else: if get: break get = false proc nextStrings(n: int): seq[string] = for _ in 0.. 0: var a = start while a < stop: yield a a += step else: var a = start while a > stop: yield a a += 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 func `//`(a, b: int64): int64 = 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 func `%`(a, b: int64): int64 = 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 proc split(n: int): seq[int] = var n = n while n > 0: let v = n % 10 result.add(v) n = n div 10 result.reverse() proc join(a: seq[int]): int = for x in a: result = 10 * result + x proc join(a: seq[char]): string = a.join("") func ceil[T: SomeInteger](b, a: T): T = result = b div a if (b > 0 and b mod a != 0): result += 1 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 template ift(cond: untyped, thenExpr: untyped, elseExpr: untyped): untyped = if cond: thenExpr else: elseExpr # 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 proc inc(a: var int64, b: int64) = a += b template rep(idx: untyped, stop: SomeOrdinal, act: untyped): untyped = for idx in 0 ..< stop: act template rrep(idx: untyped, start, stop: SomeOrdinal, act: untyped): untyped = for idx in start ..< stop: act template rep1(idx: untyped, stop: SomeOrdinal, act: untyped): untyped = for idx in 1 .. stop: 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..