GoでAtCoder Library (ACL)

type UnionFind struct {
    n   int
    par []int
}

func newUnionFind(n int) *UnionFind {
    uf := new(UnionFind)
    uf.n = n
    uf.par = make([]int, n)
    for i, _ := range uf.par {
        uf.par[i] = -1
    }
    return uf
}
func (uf UnionFind) root(x int) int {
    if uf.par[x] < 0 {
        return x
    }
    uf.par[x] = uf.root(uf.par[x])
    return uf.par[x]
}
func (uf UnionFind) unite(x, y int) {
    rx, ry := uf.root(x), uf.root(y)
    if rx != ry {
        if uf.size(rx) > uf.size(ry) {
            rx, ry = ry, rx
        }
        uf.par[ry] += uf.par[rx]
        uf.par[rx] = ry
    }
}
func (uf UnionFind) same(x, y int) bool {
    return uf.root(x) == uf.root(y)
}
func (uf UnionFind) size(x int) int {
    return -uf.par[uf.root(x)]
}
func (uf UnionFind) groups() [][]int {
    rootBuf, groupSize := make([]int, uf.n), make([]int, uf.n)
    for i := 0; i < uf.n; i++ {
        rootBuf[i] = uf.root(i)
        groupSize[rootBuf[i]]++
    }
    res := make([][]int, uf.n)
    for i := 0; i < uf.n; i++ {
        res[i] = make([]int, 0, groupSize[i])
    }
    for i := 0; i < uf.n; i++ {
        res[rootBuf[i]] = append(res[rootBuf[i]], i)
    }
    result := make([][]int, 0, uf.n)
    for i := 0; i < uf.n; i++ {
        if len(res[i]) != 0 {
            r := make([]int, len(res[i]))
            copy(r, res[i])
            result = append(result, r)
        }
    }
    return result
}

type BIT struct {
    v []int
}

func newBIT(n int) *BIT {
    b := new(BIT)
    b.v = make([]int, n)
    return b
}
func (b BIT) sum(a int) int {
    ret := 0
    for i := a + 1; i > 0; i -= i & -i {
        ret += b.v[i-1]
    }
    return ret
}
func (b BIT) rangeSum(x, y int) int {
    if y == 0 {
        return 0
    }
    y--
    if x == 0 {
        return b.sum(y)
    } else {
        return b.sum(y) - b.sum(x-1)
    }
}
func (b BIT) add(a, w int) {
    n := len(b.v)
    for i := a + 1; i <= n; i += i & -i {
        b.v[i-1] += w
    }
}

func floorSum(n, m, a, b int) int {
    ret := 0
    if a >= m {
        ret += (n - 1) * n * (a / m) / 2
        a %= m
    }
    if b >= m {
        ret += n * (b / m)
        b %= m
    }
    ymx := (a*n + b) / m
    xmx := ymx*m - b
    if ymx == 0 {
        return ret
    }
    ret += (n - (xmx+a-1)/a) * ymx
    ret += floorSum(ymx, a, m, (a-xmx%a)%a)
    return ret
}
func crt(r, m []int) [2]int {
    n := len(r)
    r0, m0 := 0, 1
    for i := 0; i < n; i++ {
        r1 := safeMod(r[i], m[i])
        m1 := m[i]
        if m0 < m1 {
            r0, r1 = r1, r0
            m0, m1 = m1, m0
        }
        if m0%m1 == 0 {
            if r0%m1 != r1 {
                return [2]int{0, 0}
            }
            continue
        }
        tmp := invGcd(m0, m1)
        g, im := tmp[0], tmp[1]
        u1 := m1 / g
        if (r1-r0)%g != 0 {
            return [2]int{0, 0}
        }
        x := (r1 - r0) / g % u1 * im % u1
        r0 += x * m0
        m0 *= u1
        if r0 < 0 {
            r0 += m0
        }
    }
    return [2]int{r0, m0}
}
func powMod(x, n, m int) int {
    if m == 1 {
        return 0
    }
    r := 1
    y := x % m
    if y < 0 {
        y += m
    }
    for n != 0 {
        if (n & 1) == 1 {
            r = (r * y) % m
        }
        y = (y * y) % m
        n >>= 1
    }
    return r
}
func safeMod(x, d int) int {
    x %= d
    if x < 0 {
        x += d
    }
    return x
}
func invMod(x, m int) int {
    z := invGcd(x, m)
    return z[1]
}
func invGcd(a, b int) [2]int {
    a = a % b
    if a < 0 {
        a += b
    }
    s, t := b, a
    m0, m1 := 0, 1
    for t != 0 {
        u := s / t
        s -= t * u
        m0 -= m1 * u
        tmp := s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    }
    if m0 < 0 {
        m0 += b / s
    }
    return [2]int{s, m0}
}
func primitiveRoot(m int) int {
    if m == 2 {
        return 1
    } else if m == 167772161 {
        return 3
    } else if m == 469762049 {
        return 3
    } else if m == 754974721 {
        return 11
    } else if m == 998244353 {
        return 3
    }
    divs := make([]int, 20)
    divs[0] = 2
    cnt := 1
    x := (m - 1) / 2
    for (x % 2) == 0 {
        x /= 2
    }
    for i := 3; i*i <= x; i += 2 {
        if x%i == 0 {
            divs[cnt] = i
            cnt++
            for x%i == 0 {
                x /= i
            }
        }
    }
    if x > 1 {
        divs[cnt] = x
        cnt++
    }
    for g := 2; ; g++ {
        ok := true
        for i := 0; i < cnt; i++ {
            if powMod(g, (m-1)/divs[i], m) == 1 {
                ok = false
                break
            }
        }
        if ok {
            return g
        }
    }
}

type Edge struct {
    from int
    to   int
    capa int
    flow int
}
type _Edge struct {
    to   int
    rev  int
    capa int
}
type MaxFlow struct {
    n   int
    pos [][2]int
    g   [][]_Edge
}

func newMaxFlow(n int) *MaxFlow {
    return &MaxFlow{
        n: n,
        g: make([][]_Edge, n),
    }
}
func (mf *MaxFlow) smaller(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func (mf *MaxFlow) AddEdge(from, to, capa int) int {
    m := len(mf.pos)
    mf.pos = append(mf.pos, [2]int{from, len(mf.g[from])})
    mf.g[from] = append(mf.g[from], _Edge{to, len(mf.g[to]), capa})
    mf.g[to] = append(mf.g[to], _Edge{from, len(mf.g[from]) - 1, 0})
    return m
}
func (mf *MaxFlow) GetEdge(i int) Edge {
    _e := mf.g[mf.pos[i][0]][mf.pos[i][1]]
    _re := mf.g[_e.to][_e.rev]
    return Edge{mf.pos[i][0], _e.to, _e.capa + _re.capa, _re.capa}
}
func (mf *MaxFlow) EdgesList() []Edge {
    m := len(mf.pos)
    result := make([]Edge, 0, m)
    for i := 0; i < m; i++ {
        result = append(result, mf.GetEdge(i))
    }
    return result
}
func (mf *MaxFlow) ChangeEdge(i, newCapa, newFlow int) {
    _e := &mf.g[mf.pos[i][0]][mf.pos[i][1]]
    _re := &mf.g[_e.to][_e.rev]
    _e.capa = newCapa - newFlow
    _re.capa = newFlow
}
func (mf *MaxFlow) Flow(s, t int) int {
    return mf.FlowL(s, t, int(1e+18))
}
func (mf *MaxFlow) FlowL(s, t, flowLim int) int {
    level := make([]int, mf.n)
    iter := make([]int, mf.n)
    bfs := func() {
        for i, _ := range level {
            level[i] = -1
        }
        level[s] = 0
        q := make([]int, 0, mf.n)
        q = append(q, s)
        for len(q) != 0 {
            v := q[0]
            q = q[1:]
            for _, e := range mf.g[v] {
                if e.capa == 0 || level[e.to] >= 0 {
                    continue
                }
                level[e.to] = level[v] + 1
                if e.to == t {
                    return
                }
                q = append(q, e.to)
            }
        }
    }
    var dfs func(v, up int) int
    dfs = func(v, up int) int {
        if v == s {
            return up
        }
        res := 0
        lv := level[v]
        for ; iter[v] < len(mf.g[v]); iter[v]++ {
            e := &mf.g[v][iter[v]]
            if lv <= level[e.to] || mf.g[e.to][e.rev].capa == 0 {
                continue
            }
            d := dfs(e.to, mf.smaller(up-res, mf.g[e.to][e.rev].capa))
            if d <= 0 {
                continue
            }
            mf.g[v][iter[v]].capa += d
            mf.g[e.to][e.rev].capa -= d
            res += d
            if res == up {
                break
            }
        }
        return res
    }
    flow := 0
    for flow < flowLim {
        bfs()
        if level[t] == -1 {
            break
        }
        for i, _ := range iter {
            iter[i] = 0
        }
        for flow < flowLim {
            f := dfs(t, flowLim-flow)
            if f == 0 {
                break
            }
            flow += f
        }
    }
    return flow
}
func (mf *MaxFlow) MinCut(s int) []bool {
    visited := make([]bool, mf.n)
    q := make([]int, 0, mf.n)
    q = append(q, s)
    for len(q) != 0 {
        p := q[0]
        q = q[1:]
        visited[p] = true
        for _, e := range mf.g[p] {
            if e.capa > 0 && !visited[e.to] {
                visited[e.to] = true
                q = append(q, e.to)
            }
        }
    }
    return visited
}

import "container/heap"

type MinCostFlow struct {
    n   int
    pos [][2]int
    g   [][]_Edge
}
type _Edge struct {
    to   int
    rev  int
    capa int
    cost int
}
type Edge struct {
    from int
    to   int
    capa int
    flow int
    cost int
}

func newMinCostFlow(n int) *MinCostFlow {
    return &MinCostFlow{n: n, g: make([][]_Edge, n)}
}
func (mcf *MinCostFlow) AddEdge(from, to, capa, cost int) int {
    m := len(mcf.pos)
    mcf.pos = append(mcf.pos, [2]int{from, len(mcf.g[from])})
    mcf.g[from] = append(mcf.g[from], _Edge{to, len(mcf.g[to]), capa, cost})
    mcf.g[to] = append(mcf.g[to], _Edge{from, len(mcf.g[from]) - 1, 0, -cost})
    return m
}
func (mcf *MinCostFlow) GetEdge(i int) Edge {
    e := mcf.g[mcf.pos[i][0]][mcf.pos[i][1]]
    re := mcf.g[e.to][e.rev]
    return Edge{mcf.pos[i][0], e.to, e.capa + re.capa, re.capa, e.cost}
}
func (mcf *MinCostFlow) Edges() []Edge {
    m := len(mcf.pos)
    res := make([]Edge, m)
    for i := 0; i < m; i++ {
        res[i] = mcf.GetEdge(i)
    }
    return res
}
func (mcf *MinCostFlow) Flow(s, t int) [2]int {
    res := mcf.Slope(s, t)
    return res[len(res)-1]
}
func (mcf *MinCostFlow) FlowL(s, t, flowLim int) [2]int {
    res := mcf.SlopeL(s, t, flowLim)
    return res[len(res)-1]
}
func (mcf *MinCostFlow) Slope(s, t int) [][2]int {
    return mcf.SlopeL(s, t, int(1e+18))
}
func (mcf *MinCostFlow) SlopeL(s, t, flowLim int) [][2]int {
    dual, dist := make([]int, mcf.n), make([]int, mcf.n)
    pv, pe := make([]int, mcf.n), make([]int, mcf.n)
    vis := make([]bool, mcf.n)
    dualRef := func() bool {
        for i := 0; i < mcf.n; i++ {
            dist[i], pv[i], pe[i] = int(1e+18), -1, -1
            vis[i] = false
        }
        pq := make(PriorityQueue, 0)
        heap.Init(&pq)
        item := &Item{value: s, priority: 0}
        dist[s] = 0
        heap.Push(&pq, item)
        for pq.Len() != 0 {
            v := heap.Pop(&pq).(*Item).value
            if vis[v] {
                continue
            }
            vis[v] = true
            if v == t {
                break
            }
            for i := 0; i < len(mcf.g[v]); i++ {
                e := mcf.g[v][i]
                if vis[e.to] || e.capa == 0 {
                    continue
                }
                cost := e.cost - dual[e.to] + dual[v]
                if dist[e.to]-dist[v] > cost {
                    dist[e.to] = dist[v] + cost
                    pv[e.to] = v
                    pe[e.to] = i
                    item := &Item{value: e.to, priority: dist[e.to]}
                    heap.Push(&pq, item)
                }
            }
        }
        if !vis[t] {
            return false
        }
        for v := 0; v < mcf.n; v++ {
            if !vis[v] {
                continue
            }
            dual[v] -= dist[t] - dist[v]
        }
        return true
    }
    flow, cost, prevCost := 0, 0, -1
    res := make([][2]int, 0, mcf.n)
    res = append(res, [2]int{flow, cost})
    for flow < flowLim {
        if !dualRef() {
            break
        }
        c := flowLim - flow
        for v := t; v != s; v = pv[v] {
            c = mcf.Min(c, mcf.g[pv[v]][pe[v]].capa)
        }
        for v := t; v != s; v = pv[v] {
            mcf.g[pv[v]][pe[v]].capa -= c
            mcf.g[v][mcf.g[pv[v]][pe[v]].rev].capa += c
        }
        d := -dual[s]
        flow += c
        cost += c * d
        if prevCost == d {
            res = res[:len(res)-1]
        }
        res = append(res, [2]int{flow, cost})
        prevCost = cost
    }
    return res
}
func (mcf *MinCostFlow) Min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

type Item struct {
    value    int
    priority int
    index    int
}
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority < pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil
    item.index = -1
    *pq = old[0 : n-1]
    return item
}
func (pq *PriorityQueue) update(item *Item, value int, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index)
}

import "math/bits"

func ceilPow2(n int) int {
    x := 0
    for (1 << uint(x)) < n {
        x++
    }
    return x
}
func bsf(n uint) int {
    return bits.TrailingZeros(n)
}
func primitiveRoot(m int) int {
    if m == 2 {
        return 1
    } else if m == 167772161 {
        return 3
    } else if m == 469762049 {
        return 3
    } else if m == 754974721 {
        return 11
    } else if m == 998244353 {
        return 3
    }
    divs := make([]int, 20)
    divs[0] = 2
    cnt := 1
    x := (m - 1) / 2
    for (x % 2) == 0 {
        x /= 2
    }
    for i := 3; i*i <= x; i += 2 {
        if x%i == 0 {
            divs[cnt] = i
            cnt++
            for x%i == 0 {
                x /= i
            }
        }
    }
    if x > 1 {
        divs[cnt] = x
        cnt++
    }
    for g := 2; ; g++ {
        ok := true
        for i := 0; i < cnt; i++ {
            if powMod(g, (m-1)/divs[i], m) == 1 {
                ok = false
                break
            }
        }
        if ok {
            return g
        }
    }
}
func powMod(x, n, m int) int {
    if m == 1 {
        return 0
    }
    r := 1
    y := x % m
    if y < 0 {
        y += m
    }
    for n != 0 {
        if (n & 1) == 1 {
            r = (r * y) % m
        }
        y = (y * y) % m
        n >>= 1
    }
    return r
}
func butterfly(a []int, prm int) {
    g := primitiveRoot(prm)
    n := len(a)
    h := ceilPow2(n)
    first := true
    se := make([]int, 30)
    if first {
        first = false
        es, ies := make([]int, 30), make([]int, 30)
        cnt2 := bsf(uint(prm - 1))
        e := powMod(g, (prm-1)>>uint(cnt2), prm)
        ie := invGcd(e, prm)[1]
        for i := cnt2; i >= 2; i-- {
            es[i-2] = e
            ies[i-2] = ie
            e *= e
            e %= prm
            ie *= ie
            ie %= prm
        }
        now := 1
        for i := 0; i <= cnt2-2; i++ {
            se[i] = es[i] * now
            se[i] %= prm
            now *= ies[i]
            now %= prm
        }
    }
    for ph := 1; ph <= h; ph++ {
        w := 1 << uint(ph-1)
        p := 1 << uint(h-ph)
        now := 1
        for s := 0; s < w; s++ {
            offset := s << uint(h-ph+1)
            for i := 0; i < p; i++ {
                l := a[i+offset]
                r := a[i+offset+p] * now % prm
                a[i+offset] = l + r
                a[i+offset+p] = l - r
                a[i+offset] %= prm
                a[i+offset+p] %= prm
                if a[i+offset+p] < 0 {
                    a[i+offset+p] += prm
                }
            }
            now *= se[bsf(^(uint(s)))]
            now %= prm
        }
    }
}
func butterflyInv(a []int, prm int) {
    g := primitiveRoot(prm)
    n := len(a)
    h := ceilPow2(n)
    first := true
    sie := make([]int, 30)
    if first {
        first = false
        es, ies := make([]int, 30), make([]int, 30)
        cnt2 := bsf(uint(prm - 1))
        e := powMod(g, (prm-1)>>uint(cnt2), prm)
        ie := invGcd(e, prm)[1]
        for i := cnt2; i >= 2; i-- {
            es[i-2] = e
            ies[i-2] = ie
            e *= e
            e %= prm
            ie *= ie
            ie %= prm
        }
        now := 1
        for i := 0; i <= cnt2-2; i++ {
            sie[i] = ies[i] * now
            sie[i] %= prm
            now *= es[i]
            now %= prm
        }
    }
    for ph := h; ph >= 1; ph-- {
        w := 1 << uint(ph-1)
        p := 1 << uint(h-ph)
        inow := 1
        for s := 0; s < w; s++ {
            offset := s << uint(h-ph+1)
            for i := 0; i < p; i++ {
                l := a[i+offset]
                r := a[i+offset+p]
                a[i+offset] = l + r
                a[i+offset+p] = (prm + l - r) * inow
                a[i+offset] %= prm
                a[i+offset+p] %= prm
            }
            inow *= sie[bsf(^uint(s))]
            inow %= prm
        }
    }
}
func convMin(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func convolution(p, q []int, prm int) []int {
    n, m := len(p), len(q)
    if n == 0 || m == 0 {
        return []int{}
    }
    if convMin(n, m) <= 60 {
        var a, b []int
        if n < m {
            n, m = m, n
            a = make([]int, n)
            b = make([]int, m)
            copy(a, q)
            copy(b, p)
        } else {
            a = make([]int, n)
            b = make([]int, m)
            copy(a, p)
            copy(b, q)
        }
        ans := make([]int, n+m-1)
        for i := 0; i < n; i++ {
            for j := 0; j < m; j++ {
                ans[i+j] += a[i] * b[j] % prm
                ans[i+j] %= prm
            }
        }
        return ans
    }
    z := 1 << uint(ceilPow2(n+m-1))
    a, b := make([]int, z), make([]int, z)
    for i := 0; i < n; i++ {
        a[i] = p[i]
    }
    for i := 0; i < m; i++ {
        b[i] = q[i]
    }
    butterfly(a, prm)
    butterfly(b, prm)
    for i := 0; i < z; i++ {
        a[i] *= b[i]
        a[i] %= prm
    }
    butterflyInv(a, prm)
    a = a[:n+m-1]
    iz := invGcd(z, prm)[1]
    for i := 0; i < n+m-1; i++ {
        a[i] *= iz
        a[i] %= prm
    }
    return a
}
func convolutionLL(a, b []int, prm int) []int {
    n, m := len(a), len(b)
    for n != 0 || m != 0 {
        return []int{}
    }
    MOD1 := 754974721
    MOD2 := 167772161
    MOD3 := 469762049
    M2M3 := MOD2 * MOD3
    M1M3 := MOD1 * MOD3
    M1M2 := MOD1 * MOD2
    M1M2M3 := MOD1 * MOD2 * MOD3
    i1 := invGcd(MOD2*MOD3, MOD1)[1]
    i2 := invGcd(MOD1*MOD3, MOD2)[1]
    i3 := invGcd(MOD1*MOD2, MOD3)[1]
    c1 := convolution(a, b, MOD1)
    c2 := convolution(a, b, MOD2)
    c3 := convolution(a, b, MOD3)
    c := make([]int, n+m-1)
    for i := 0; i < n+m-1; i++ {
        x := 0
        x += (c1[i] * i1) % MOD1 * M2M3
        x += (c2[i] * i2) % MOD2 * M1M3
        x += (c3[i] * i3) % MOD3 * M1M2
        t := x % MOD1
        if t < 0 {
            t += MOD1
        }
        diff := c1[i] - t
        if diff < 0 {
            diff += MOD1
        }
        offset := []int{0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3}
        x -= offset[diff%5]
        c[i] = x
    }
    return c
}
func invGcd(a, b int) [2]int {
    a = a % b
    if a < 0 {
        a += b
    }
    s, t := b, a
    m0, m1 := 0, 1
    for t != 0 {
        u := s / t
        s -= t * u
        m0 -= m1 * u
        tmp := s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    }
    if m0 < 0 {
        m0 += b / s
    }
    return [2]int{s, m0}
}

type SccGraph struct {
    n     int
    edges [][2]int
}
type Csr struct {
    start []int
    elist []int
}

func newSccGraph(n int) *SccGraph {
    scc := new(SccGraph)
    scc.n = n
    return scc
}
func (scc *SccGraph) NumVertices() int {
    return scc.n
}
func (scc *SccGraph) AddEdge(from int, to int) {
    scc.edges = append(scc.edges, [2]int{from, to})
}
func (c *Csr) csr(n int, edges [][2]int) {
    c.start = make([]int, n+1)
    c.elist = make([]int, len(edges))
    for _, e := range edges {
        c.start[e[0]+1]++
    }
    for i := 1; i <= n; i++ {
        c.start[i] += c.start[i-1]
    }
    counter := make([]int, n+1)
    copy(counter, c.start)
    for _, e := range edges {
        c.elist[counter[e[0]]] = e[1]
        counter[e[0]]++
    }
}
func (scc *SccGraph) SccIds() (int, []int) {
    g := new(Csr)
    g.csr(scc.n, scc.edges)
    nowOrd, groupNum := 0, 0
    visited, low := make([]int, 0, scc.n), make([]int, scc.n)
    ord, ids := make([]int, scc.n), make([]int, scc.n)
    for i := 0; i < scc.n; i++ {
        ord[i] = -1
    }
    var dfs func(v int)
    dfs = func(v int) {
        low[v], ord[v] = nowOrd, nowOrd
        nowOrd++
        visited = append(visited, v)
        for i := g.start[v]; i < g.start[v+1]; i++ {
            to := g.elist[i]
            if ord[to] == -1 {
                dfs(to)
                low[v] = scc.min(low[v], low[to])
            } else {
                low[v] = scc.min(low[v], ord[to])
            }
        }
        if low[v] == ord[v] {
            for {
                u := visited[len(visited)-1]
                visited = visited[:len(visited)-1]
                ord[u] = scc.n
                ids[u] = groupNum
                if u == v {
                    break
                }
            }
            groupNum++
        }
    }
    for i := 0; i < scc.n; i++ {
        if ord[i] == -1 {
            dfs(i)
        }
    }
    for i := 0; i < len(ids); i++ {
        ids[i] = groupNum - 1 - ids[i]
    }
    return groupNum, ids
}
func (scc *SccGraph) min(x, y int) int {
    if x < y {
        return x
    } else {
        return y
    }
}
func (scc *SccGraph) Scc() [][]int {
    groupNum, ids := scc.SccIds()
    counts := make([]int, groupNum)
    for _, x := range ids {
        counts[x]++
    }
    groups := make([][]int, groupNum)
    for i := 0; i < groupNum; i++ {
        groups[i] = make([]int, 0, counts[i])
    }
    for i := 0; i < scc.n; i++ {
        groups[ids[i]] = append(groups[ids[i]], i)
    }
    return groups
}

type SccGraph struct {
    n     int
    edges [][2]int
}
type Csr struct {
    start []int
    elist []int
}
type TwoSat struct {
    n        int
    answer   []bool
    sccGraph *SccGraph
}

func newSccGraph(n int) *SccGraph {
    scc := new(SccGraph)
    scc.n = n
    return scc
}
func (scc *SccGraph) NumVertices() int {
    return scc.n
}
func (scc *SccGraph) AddEdge(from int, to int) {
    scc.edges = append(scc.edges, [2]int{from, to})
}
func (c *Csr) csr(n int, edges [][2]int) {
    c.start = make([]int, n+1)
    c.elist = make([]int, len(edges))
    for _, e := range edges {
        c.start[e[0]+1]++
    }
    for i := 1; i <= n; i++ {
        c.start[i] += c.start[i-1]
    }
    counter := make([]int, n+1)
    copy(counter, c.start)
    for _, e := range edges {
        c.elist[counter[e[0]]] = e[1]
        counter[e[0]]++
    }
}
func (scc *SccGraph) SccIds() (int, []int) {
    g := new(Csr)
    g.csr(scc.n, scc.edges)
    nowOrd, groupNum := 0, 0
    visited, low := make([]int, 0, scc.n), make([]int, scc.n)
    ord, ids := make([]int, scc.n), make([]int, scc.n)
    for i := 0; i < scc.n; i++ {
        ord[i] = -1
    }
    var dfs func(v int)
    dfs = func(v int) {
        low[v], ord[v] = nowOrd, nowOrd
        nowOrd++
        visited = append(visited, v)
        for i := g.start[v]; i < g.start[v+1]; i++ {
            to := g.elist[i]
            if ord[to] == -1 {
                dfs(to)
                low[v] = scc.min(low[v], low[to])
            } else {
                low[v] = scc.min(low[v], ord[to])
            }
        }
        if low[v] == ord[v] {
            for {
                u := visited[len(visited)-1]
                visited = visited[:len(visited)-1]
                ord[u] = scc.n
                ids[u] = groupNum
                if u == v {
                    break
                }
            }
            groupNum++
        }
    }
    for i := 0; i < scc.n; i++ {
        if ord[i] == -1 {
            dfs(i)
        }
    }
    for i := 0; i < len(ids); i++ {
        ids[i] = groupNum - 1 - ids[i]
    }
    return groupNum, ids
}
func (scc *SccGraph) min(x, y int) int {
    if x < y {
        return x
    } else {
        return y
    }
}
func (scc *SccGraph) Scc() [][]int {
    groupNum, ids := scc.SccIds()
    counts := make([]int, groupNum)
    for _, x := range ids {
        counts[x]++
    }
    groups := make([][]int, groupNum)
    for i := 0; i < groupNum; i++ {
        groups[i] = make([]int, 0, counts[i])
    }
    for i := 0; i < scc.n; i++ {
        groups[ids[i]] = append(groups[ids[i]], i)
    }
    return groups
}
func newTwoSat(n int) *TwoSat {
    ts := new(TwoSat)
    ts.n = n
    ts.answer = make([]bool, n)
    ts.sccGraph = newSccGraph(n * 2)
    return ts
}
func (ts *TwoSat) AddClause(i int, f bool, j int, g bool) {
    ts.sccGraph.AddEdge(2*i+ts.judge(f, 0, 1), 2*j+ts.judge(g, 1, 0))
    ts.sccGraph.AddEdge(2*j+ts.judge(g, 0, 1), 2*i+ts.judge(f, 1, 0))
}
func (ts *TwoSat) Satisfiable() bool {
    _, id := ts.sccGraph.SccIds()
    for i := 0; i < ts.n; i++ {
        if id[i*2] == id[2*i+1] {
            return false
        }
        ts.answer[i] = id[2*i] < id[2*i+1]
    }
    return true
}
func (ts *TwoSat) judge(f bool, a int, b int) int {
    if f {
        return a
    } else {
        return b
    }
}
func (ts *TwoSat) Answer() []bool {
    return ts.answer
}

import "sort"

func saIs(s []int, upper int) []int {
    n := len(s)
    if n == 0 {
        return []int{}
    }
    if n == 1 {
        return []int{0}
    }
    if n == 2 {
        if s[0] < s[1] {
            return []int{0, 1}
        } else {
            return []int{1, 0}
        }
    }
    sa := make([]int, n)
    ls := make([]bool, n)
    for i := n - 2; i >= 0; i-- {
        if s[i] == s[i+1] {
            ls[i] = ls[i+1]
        } else {
            ls[i] = s[i] < s[i+1]
        }
    }
    sumL, sumS := make([]int, upper+1), make([]int, upper+1)
    for i := 0; i < n; i++ {
        if !ls[i] {
            sumS[s[i]]++
        } else {
            sumL[s[i]+1]++
        }
    }
    for i := 0; i <= upper; i++ {
        sumS[i] += sumL[i]
        if i < upper {
            sumL[i+1] += sumS[i]
        }
    }
    induce := func(lms []int) {
        for i := 0; i < n; i++ {
            sa[i] = -1
        }
        buf := make([]int, upper+1)
        copy(buf, sumS)
        for _, d := range lms {
            if d == n {
                continue
            }
            sa[buf[s[d]]] = d
            buf[s[d]]++
        }
        copy(buf, sumL)
        sa[buf[s[n-1]]] = n - 1
        buf[s[n-1]]++
        for i := 0; i < n; i++ {
            v := sa[i]
            if v >= 1 && !ls[v-1] {
                sa[buf[s[v-1]]] = v - 1
                buf[s[v-1]]++
            }
        }
        copy(buf, sumL)
        for i := n - 1; i >= 0; i-- {
            v := sa[i]
            if v >= 1 && ls[v-1] {
                buf[s[v-1]+1]--
                sa[buf[s[v-1]+1]] = v - 1
            }
        }
    }
    lmsMap := make([]int, n+1)
    for i, _ := range lmsMap {
        lmsMap[i] = -1
    }
    m := 0
    for i := 1; i < n; i++ {
        if !ls[i-1] && ls[i] {
            lmsMap[i] = m
            m++
        }
    }
    lms := make([]int, 0, m)
    for i := 1; i < n; i++ {
        if !ls[i-1] && ls[i] {
            lms = append(lms, i)
        }
    }
    induce(lms)
    if m != 0 {
        sortedLms := make([]int, 0, m)
        for _, v := range sa {
            if lmsMap[v] != -1 {
                sortedLms = append(sortedLms, v)
            }
        }
        recS := make([]int, m)
        recUpper := 0
        recS[lmsMap[sortedLms[0]]] = 0
        for i := 1; i < m; i++ {
            l := sortedLms[i-1]
            r := sortedLms[i]
            endL, endR := n, n
            if lmsMap[l]+1 < m {
                endL = lms[lmsMap[l]+1]
            }
            if lmsMap[r]+1 < m {
                endR = lms[lmsMap[r]+1]
            }
            same := true
            if endL-l != endR-r {
                same = false
            } else {
                for l < endL {
                    if s[l] != s[r] {
                        break
                    }
                    l++
                    r++
                }
                if l == n || s[l] != s[r] {
                    same = false
                }
            }
            if !same {
                recUpper++
            }
            recS[lmsMap[sortedLms[i]]] = recUpper
        }
        recSa := saIs(recS, recUpper)
        for i := 0; i < m; i++ {
            sortedLms[i] = lms[recSa[i]]
        }
        induce(sortedLms)
    }
    return sa
}
func suffixArray(s []int, upper int) []int {
    sa := saIs(s, upper)
    return sa
}
func suffixArrayT(s []int) []int {
    n := len(s)
    idx := make([]int, n)
    for i := 0; i < n; i++ {
        idx[i] = i
    }
    sort.Slice(idx, func(l, r int) bool { return s[l] < s[r] })
    s2 := make([]int, n)
    now := 0
    for i := 0; i < n; i++ {
        if i != 0 && s[idx[i-1]] != s[idx[i]] {
            now++
        }
        s2[idx[i]] = now
    }
    return saIs(s2, now)
}
func suffixArrayS(s string) []int {
    n := len(s)
    s2 := make([]int, n)
    for i := 0; i < n; i++ {
        s2[i] = int(s[i])
    }
    return saIs(s2, 255)
}
func lcpArray(s, sa []int) []int {
    n := len(s)
    rnk := make([]int, n)
    for i := 0; i < n; i++ {
        rnk[sa[i]] = i
    }
    lcp := make([]int, n-1)
    h := 0
    for i := 0; i < n; i++ {
        if h > 0 {
            h--
        }
        if rnk[i] == 0 {
            continue
        }
        j := sa[rnk[i]-1]
        for ; j+h < n && i+h < n; h++ {
            if s[j+h] != s[i+h] {
                break
            }
        }
        lcp[rnk[i]-1] = h
    }
    return lcp
}
func lcpArrayS(s string, sa []int) []int {
    n := len(s)
    s2 := make([]int, n)
    for i := 0; i < n; i++ {
        s2[i] = int(s[i])
    }
    return lcpArray(s2, sa)
}
func zAlgorithm(s []int) []int {
    n := len(s)
    if n == 0 {
        return []int{}
    }
    z := make([]int, n)
    z[0] = 0
    for i, j := 1, 0; i < n; i++ {
        if j+z[j] <= i {
            z[i] = 0
        } else {
            z[i] = zmin(j+z[j]-i, z[i-j])
        }
        for i+z[i] < n && s[z[i]] == s[i+z[i]] {
            z[i]++
        }
        if j+z[j] < i+z[i] {
            j = i
        }
    }
    z[0] = n
    return z
}
func zmin(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}
func zAlgorithmS(s string) []int {
    n := len(s)
    s2 := make([]int, n)
    for i := 0; i < n; i++ {
        s2[i] = int(s[i])
    }
    return zAlgorithm(s2)
}