{.passc: "-std=gnu++17 -Wall -Wextra -O2 -DONLINE_JUDGE -I/opt/boost/gcc/include -L/opt/boost/gcc/lib -I/opt/ac-library".} {.optimization:speed.} import strformat, macros, std/algorithm, tables, sets, lists, intsets, critbits, sequtils, strutils, std/math, times, sugar, options, bitops, heapqueue, future, std/deques proc powMod*(a, b, c: int): int {.importcpp: "atcoder::pow_mod(#, @)", header: "".} proc po*(a: int): int {.importcpp: "std::fgets(#)", header: "".} const MOD = 1000000007 MOD_ANOTHER = 998244353 # 入力テンプレ------------------------------------------------- proc g(): string = stdin.readLine proc gin(): int = g().parseInt proc gInts(): seq[int] = g().split.map(parseInt) proc gIntsN(n:int): seq[int] = result=newSeq[int](n) for i in 0..n-1:result[i]=gin() proc gIntsNs(n:int): seq[seq[int]] = result=newSeq[seq[int]](n) for i in 0..n-1:result[i]=gInts() proc gStrN(n:int): seq[string] = result = newSeq[string](n) for i in 0..n-1:result[i]=g() # ---------------------------------------------------------------- template last(a:untyped): untyped = a[a.len - 1] func head(a:openarray[int]):Option[int] = if(a.len > 0):a[0].some else:int.none func head(a:openarray[float]):Option[float] = if(a.len > 0):a[0].some else:float.none func head(a:openarray[string]):Option[string] = if(a.len > 0):a[0].some else:string.none template `tail` (a:typed):untyped = a[1..len(a)-1] template `init` (a:typed):untyped = a[0..len(a)-2] template `&&`(a,b:untyped):untyped = if(a==true and b==true):true else: false template `||`(a,b:untyped):untyped = if(a==true or b==true):true else: false func chmax[T](n: var T, m: T) {.inline.} = n = max(n, m) func chmin[T](n: var T, m: T) {.inline.} = n = min(n, m) func plus[T](a,b:T):T=return a+b func product[T](a:openArray[T]):T= result=1 for i in a:result = result * i func subtract[T](a,b:T):T=return a-b func zipwith[T1,T2,T3](f: proc(a:T1,b:T2):T3, xs:openarray[T1],ys:openarray[T2]): seq[T1] = newSeq(result, xs.len) for i in low(xs)..high(xs): result[i] = f(xs[i],ys[i]) proc zip3[S,T,U](a:seq[S],b:seq[T],c:seq[U]):seq[(S,T,U)]= for i in zip(zip(a,b),c):result.add((i[0][0],i[0][1],i[1])) func search[T](x:seq[T],y:T) : bool = for i in x: if i == y : return true return false func `++`[T](a:T):T = a+1 func `--`[T](a:T):T = a-1 func Qsort[T](x:seq[T]):seq[T] = if(x.len<=1):return x else: var pivot = x[0] left:seq[T] = @[] right:seq[T] = @[] for i in 1.. cost[pos] + d): cost[i] = d + cost[pos] heap.push((cost[i],i)) return cost #幅優先探索 func bfs(G:seq[seq[int]],n:int,start:int):(seq[int],seq[int]) = var dist = newSeqWith(n,-1) que = initDeque[int]() prev = newSeqWith(n,-1) dist[start] = 0 que.addLast(start) while(not(que.isemptyQ)): var v = que.popFirst() for nv in G[v]: if(dist[nv] != -1):continue dist[nv] = dist[v] + 1 prev[nv] = v que.addLast(nv) return (dist,prev) #迷路探索 proc mazeBFS(R,C,sy,sx,gy,gx:int,field:seq[string],wall:char):int= var dist=makeSeqNums(R,C,-1) que=initDeque[(int,int)]() que.addLast((sy,sx)) dist[sy][sx]=0 while(not(que.isemptyQ)): var(ny,nx)=que.popFirst() for (i2,j2) in ([[ny+1,nx],[ny-1,nx],[ny,nx+1],[ny,nx-1]]): if(not((i2>=0 and i2 < R) and (j2 >= 0 and j2 < C))):continue if(field[ny][nx]==wall):continue if(dist[i2][j2] == -1): dist[i2][j2]=dist[ny][nx] + 1 que.addLast((i2,j2)) return dist[gy][gx] # ------------------------------------------------------------------ #union-find type UnionFind = ref object parent:seq[int] rank:seq[int] proc makeUf(n:int):UnionFind = result=UnionFind(parent:newSeq[int](n),rank:newSeq[int](n)) for i in 0..uf.rank[b]):swap(a,b) if(uf.rank[a]==uf.rank[b]):uf.rank[b] += 1 uf.parent[a]=b proc sameUf(uf:UnionFind,x,y:int):bool = return if(uf.rootUf(x) == uf.rootUf(y)):true else: false proc sizeUf(uf:UnionFind,a:int):int = - uf.parent[uf.rootUf(a)] #---------------------------------------------------------- #binary indexed tree type Bit = ref object size:int tree:seq[int] proc initBit(n:int):Bit = result = Bit(size:n,tree:newSeqWith(n+1,0)) proc sumBit(bit:Bit,i:int):int = result=0 var k = i k -= 1 while(k>=0): result += bit.tree[k] k = (k and (k+1)) - 1 proc addBit(bit:Bit,i:int,x:int):void = var k = i while(k < bit.size): bit.tree[k] += x k = (k or (k+1)) proc rangeBit(bit:Bit,l:int,r:int):int = if(l==0):return bit.sumBit(r) return bit.sumBit(r) - bit.sumBit(l) proc buildBit(bit:Bit,arr:seq[int]):Bit= for ix,i in arr:bit.addBit(ix,i) return bit proc makeBit(arr:seq[int],n:int):Bit = return initBit(n).buildBit(arr) #---------------------------------------------------------- #累積和 func cumsum[T](m:seq[T],n:int):seq[T] = var zero:T = 0 result : seq[T] = newSeqWith(n+1,zero) for i in 0..