import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
# source: src/cplib/tmpl/sheep.nim
ImportExpand "cplib/tmpl/sheep" <=== "when not declared CPLIB_TMPL_SHEEP:\n    const CPLIB_TMPL_SHEEP* = 1\n    {.warning[UnusedImport]: off.}\n    {.hint[XDeclaredButNotUsed]: off.}\n    import algorithm\n    import sequtils\n    import tables\n    import macros\n    import math\n    import sets\n    import strutils\n    import strformat\n    import sugar\n    import heapqueue\n    import streams\n    import deques\n    import bitops\n    import std/lenientops\n    import options\n    #入力系\n    proc scanf(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n    proc getchar(): char {.importc: \"getchar_unlocked\", header: \"<stdio.h>\", discardable.}\n    proc ii(): int {.inline.} = scanf(\"%lld\\n\", addr result)\n    proc lii(N: int): seq[int] {.inline.} = newSeqWith(N, ii())\n    proc si(): string {.inline.} =\n        result = \"\"\n        var c: char\n        while true:\n            c = getchar()\n            if c == ' ' or c == '\\n' or c == '\\255':\n                break\n            result &= c\n    \n    # 出力系\n    # 1. 実際の処理を行う proc (openArray を受け取る)\n    proc print_internal(prop: tuple[f: File, sepc: string, endc: string, flush: bool], args: openArray[string]) =\n        for i in 0 ..< args.len:\n            prop.f.write(args[i])\n            if i != args.len - 1:\n                prop.f.write(prop.sepc)\n            else:\n                prop.f.write(prop.endc)\n        if prop.flush:\n            prop.f.flushFile()\n\n    # 2. ユーザーが呼び出すためのインターフェース (varargs を受け取る)\n    proc print*(prop: tuple[f: File, sepc: string, endc: string, flush: bool], args: varargs[string, `$`]) =\n        # varargs は内部では openArray として扱えるので、そのまま渡せる\n        print_internal(prop, args)\n\n    proc print*(args: varargs[string, `$`]) =\n        # こちらも内部用の proc を呼ぶ\n        print_internal((f: stdout, sepc: \" \", endc: \"\\n\", flush: false), args)\n    macro getSymbolName(x: typed): string = x.toStrLit\n    macro debug*(args: varargs[untyped]): untyped =\n        when defined(debug):\n            result = newNimNode(nnkStmtList, args)\n            template prop(e: string = \"\"): untyped = (f: stderr, sepc: \"\", endc: e, flush: true)\n            for i, arg in args:\n                if arg.kind == nnkStrLit:\n                    result.add(quote do: print(prop(), \"\\\"\", `arg`, \"\\\"\"))\n                else:\n                    result.add(quote do: print(prop(\": \"), getSymbolName(`arg`)))\n                    result.add(quote do: print(prop(), `arg`))\n                if i != args.len - 1: result.add(quote do: print(prop(), \", \"))\n                else: result.add(quote do: print(prop(), \"\\n\"))\n        else:\n            return (quote do: discard)\n    #chmin,chmax\n    template `max=`(x, y) =\n        let yVal = y # yが計算式の場合に評価を1回にするため\n        if x < yVal:\n            x = yVal\n\n    template `min=`(x, y) =\n        let yVal = y\n        if x > yVal:\n            x = yVal\n    proc chmin[T](x: var T, y: T):bool=\n        if x > y:\n            x = y\n            return true\n        return false\n    proc chmax[T](x: var T, y: T):bool=\n        if x < y:\n            x = y\n            return true\n        return false\n    #bit演算\n    proc `%`*(x: int, y: int): int =\n        result = x mod y\n        if y > 0 and result < 0: result += y\n        if y < 0 and result > 0: result += y\n    proc `//`*(x: int, y: int): int{.inline.} =\n        result = x div y\n        if y > 0 and result * y > x: result -= 1\n        if y < 0 and result * y < x: result -= 1\n    proc `%=`(x: var int, y: int): void = x = x%y\n    proc `//=`(x: var int, y: int): void = x = x//y\n    proc `**`(x: int, y: int): int = x^y\n    proc `**=`(x: var int, y: int): void = x = x^y\n    proc `^`(x: int, y: int): int = x xor y\n    proc `|`(x: int, y: int): int = x or y\n    proc `&`(x: int, y: int): int = x and y\n    proc `>>`(x: int, y: int): int = x shr y\n    proc `<<`(x: int, y: int): int = x shl y\n    proc `~`(x: int): int = not x\n    proc `^=`(x: var int, y: int): void = x = x ^ y\n    proc `&=`(x: var int, y: int): void = x = x & y\n    proc `|=`(x: var int, y: int): void = x = x | y\n    proc `>>=`(x: var int, y: int): void = x = x >> y\n    proc `<<=`(x: var int, y: int): void = x = x << y\n    proc `[]`(x: int, n: int): bool = (x and (1 shl n)) != 0\n    #便利な変換\n    proc `!`(x: char, a = '0'): int = int(x)-int(a)\n    #定数\n    when not declared CPLIB_UTILS_CONSTANTS:\n        const CPLIB_UTILS_CONSTANTS* = 1\n        const INF32*: int32 = 1001000027.int32\n        const INF64*: int = int(3300300300300300491)\n    \n    const INF = INF64\n    #converter\n\n    #range\n    iterator range(start: int, ends: int, step: int): int =\n        var i = start\n        if step < 0:\n            while i > ends:\n                yield i\n                i += step\n        elif step > 0:\n            while i < ends:\n                yield i\n                i += step\n    iterator range(ends: int): int = (for i in 0..<ends: yield i)\n    iterator range(start: int, ends: int): int = (for i in\n            start..<ends: yield i)\n\n    #joinが非stringでめちゃくちゃ遅いやつのパッチ\n    proc join*[T: not string](a: openArray[T], sep: string = \"\"): string = a.mapit($it).join(sep)\n\n    proc dump[T](arr:seq[seq[T]])=\n        for i in 0..<len(arr):\n            echo arr[i]\n\n    proc sum(slice:HSlice[int,int]):int=\n        return (slice.a+slice.b)*len(slice)//2\n    \n    proc `<`[T](l,r:seq[T]):bool=\n        for i in 0..<min(len(l),len(r)):\n            if l[i] > r[i]:\n                return false\n            elif l[i] < r[i]:\n                return true\n        return len(l) < len(r)\n    \n    # Yes/No\n    proc yes*(b: bool = true): void = print(if b: \"Yes\" else: \"No\")\n    proc no*(b: bool = true): void = yes(not b)\n\n    proc takahashi(b:bool = true) : void = print(if b: \"Takahashi\" else: \"Aoki\")\n    proc aoki(b:bool = true) : void = takahashi(not b)\n\n    template dblock(body: untyped) =\n        when defined(debug):\n            block:\n                body\n"
# source: src/cplib/math/divisor.nim
ImportExpand "cplib/math/divisor" <=== "when not declared CPLIB_MATH_DIVISOR:\n    const CPLIB_MATH_DIVISOR* = 1\n    import sequtils\n    import tables\n    import algorithm\n    when not declared CPLIB_MATH_PRIMEFACTOR:\n        const CPLIB_MATH_PRIMEFACTOR* = 1\n        when not declared CPLIB_MATH_INNER_MATH:\n            const CPLIB_MATH_INNER_MATH* = 1\n            proc add*(a, b, m: int): int {.importcpp: \"((__int128)(#) + (__int128)(#)) % (__int128)(#)\", nodecl.}\n            proc mul*(a, b, m: int): int {.importcpp: \"(__int128)(#) * (__int128)(#) % (__int128)(#)\", nodecl.}\n        \n        when not declared CPLIB_MATH_ISPRIME:\n            const CPLIB_MATH_ISPRIME* = 1\n            when not declared CPLIB_MATH_POWMOD:\n                const CPLIB_MATH_POWMOD* = 1\n                proc powmod*(a, n, m: int): int =\n                    assert m != 0\n                    if m == 1:\n                        return 0\n                    var\n                        rev = 1\n                        a = a\n                        n = n\n                    while n > 0:\n                        if n mod 2 != 0: rev = mul(rev, a, m)\n                        if n > 1: a = mul(a, a, m)\n                        n = n shr 1\n                    return rev\n            \n            proc isprime*(N: int): bool =\n                let bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]\n                if N == 2:\n                    return true\n                if N < 2 or (N and 1) == 0:\n                    return false\n                let N1 = N-1\n                var d = N1\n                var s = 0\n                while (d and 1) == 0:\n                    d = d shr 1\n                    s += 1\n                for a in bases:\n                    var t: int\n                    if a mod N == 0:\n                        continue\n                    t = powmod(a, d, N)\n                    if t == 1 or t == N1:\n                        continue\n                    block test:\n                        for _ in 0..<(s-1):\n                            t = powmod(t, 2, N)\n                            if t == N1:\n                                break test\n                        return false\n                return true\n        \n        when not declared CPLIB_STR_RUN_LENGTH_ENCODE_UTILS:\n            const CPLIB_STR_RUN_LENGTH_ENCODE_UTILS* = 1\n            import sequtils\n            proc run_length_encode*[T](a: seq[T]): seq[(T, int)] =\n                for i in 0..<len(a):\n                    if result.len == 0:\n                        result.add((a[i], 1))\n                        continue\n                    if result[^1][0] == a[i]: result[^1][1] += 1\n                    else: result.add((a[i], 1))\n        \n            proc run_length_encode*(s: string): seq[(char, int)] =\n                var a = s.items.toSeq\n                return run_length_encode(a)\n        \n        import random\n        import std/math\n        import algorithm\n        import tables\n    \n        randomize()\n        proc find_factor(n: int): int =\n            if not ((n and 1) != 0): return 2\n            if isprime(n): return n\n            const m = 128\n            while true:\n                var x, ys, q, r, g = 1\n                var rnd, y = rand(0..n-3) + 2\n                proc f(x: int): int = add(mul(x, x, n), rnd, n)\n                while g == 1:\n                    x = y\n                    for i in 0..<r: y = f(y)\n                    for k in countup(0, r-1, m):\n                        ys = y\n                        for _ in 0..<min(m, r-k):\n                            y = f(y)\n                            q = mul(q, abs(x-y), n)\n                        g = gcd(q, n)\n                        if g != 1: break\n                    r = r shl 1\n                if g == n:\n                    g = 1\n                    while g == 1:\n                        ys = f(ys)\n                        g = gcd(n, abs(x - ys))\n                if g < n:\n                    if isprime(g): return g\n                    elif isprime(n div g): return n div g\n                    return find_factor(g)\n    \n        proc primefactor*(n: int, sorted: bool = true): seq[int] =\n            var n = n\n            while n > 1 and not isprime(n):\n                var p = find_factor(n)\n                while n mod p == 0:\n                    result.add(p)\n                    n = n div p\n            if n > 1: result.add(n)\n            if sorted: return result.sorted\n    \n        proc primefactor_table*(n: int): Table[int, int] =\n            for p in primefactor(n):\n                if p in result: result[p] += 1\n                else: result[p] = 1\n    \n        proc primefactor_tuple*(n: int): seq[(int, int)] = primefactor(n, true).run_length_encode\n    \n    proc divisor_naive(x: int, sorted: bool): seq[int] =\n        for i in 1..x:\n            if i*i > x: break\n            if x mod i == 0:\n                result.add(i)\n                if i*i != x:\n                    result.add(x div i)\n        if sorted: result.sort\n\n    proc divisor*(x: int, sorted: bool = true): seq[int] =\n        if x <= 1000_000: return divisor_naive(x, sorted)\n        var factor = primefactor(x).toCountTable.pairs.toSeq\n        var ans = newSeq[int](0)\n        proc dfs(d, x: int) =\n            if d == factor.len:\n                ans.add(x)\n                return\n            var mul = 1\n            for i in 0..factor[d][1]:\n                dfs(d+1, x*mul)\n                if i != factor[d][1]: mul *= factor[d][0]\n        dfs(0, 1)\n        if sorted: ans.sort\n        return ans\n"
# source: src/cplib/graph/functional_graph.nim
ImportExpand "cplib/graph/functional_graph" <=== "when not declared CPLIB_GRAPH_FUNCTIONALGRAPH:\n    const CPLIB_GRAPH_FUNCTIONALGRAPH* = 1\n    import sequtils\n    when not declared CPLIB_GRAPH_GRAPH:\n        const CPLIB_GRAPH_GRAPH* = 1\n    \n        import sequtils\n        import math\n        type DynamicGraph*[T] = ref object of RootObj\n            edges*: seq[seq[(int32, T)]]\n            len*: int\n        type StaticGraph*[T] = ref object of RootObj\n            src*, dst*: seq[int32]\n            cost*: seq[T]\n            elist*: seq[(int32, T)]\n            start*: seq[int32]\n            len*: int\n    \n        type WeightedDirectedGraph*[T] = ref object of DynamicGraph[T]\n        type WeightedUnDirectedGraph*[T] = ref object of DynamicGraph[T]\n        type UnWeightedDirectedGraph* = ref object of DynamicGraph[int]\n        type UnWeightedUnDirectedGraph* = ref object of DynamicGraph[int]\n        type WeightedDirectedStaticGraph*[T] = ref object of StaticGraph[T]\n        type WeightedUnDirectedStaticGraph*[T] = ref object of StaticGraph[T]\n        type UnWeightedDirectedStaticGraph* = ref object of StaticGraph[int]\n        type UnWeightedUnDirectedStaticGraph* = ref object of StaticGraph[int]\n    \n        type GraphTypes*[T] = DynamicGraph[T] or StaticGraph[T]\n        type DirectedGraph* = WeightedDirectedGraph or UnWeightedDirectedGraph or WeightedDirectedStaticGraph or UnWeightedDirectedStaticGraph\n        type UnDirectedGraph* = WeightedUnDirectedGraph or UnWeightedUnDirectedGraph or WeightedUnDirectedStaticGraph or UnWeightedUnDirectedStaticGraph\n        type WeightedGraph*[T] = WeightedDirectedGraph[T] or WeightedUnDirectedGraph[T] or WeightedDirectedStaticGraph[T] or WeightedUnDirectedStaticGraph[T]\n        type UnWeightedGraph* = UnWeightedDirectedGraph or UnWeightedUnDirectedGraph or UnWeightedDirectedStaticGraph or UnWeightedUnDirectedStaticGraph\n        type DynamicGraphTypes* = WeightedDirectedGraph or UnWeightedDirectedGraph or WeightedUnDirectedGraph or UnWeightedUnDirectedGraph\n        type StaticGraphTypes* = WeightedDirectedStaticGraph or UnWeightedDirectedStaticGraph or WeightedUnDirectedStaticGraph or UnWeightedUnDirectedStaticGraph\n    \n        proc add_edge_dynamic_impl*[T](g: DynamicGraph[T], u, v: int, cost: T, directed: bool) =\n            g.edges[u].add((v.int32, cost))\n            if not directed: g.edges[v].add((u.int32, cost))\n    \n        proc initWeightedDirectedGraph*(N: int, edgetype: typedesc = int): WeightedDirectedGraph[edgetype] =\n            result = WeightedDirectedGraph[edgetype](edges: newSeq[seq[(int32, edgetype)]](N), len: N)\n        proc add_edge*[T](g: var WeightedDirectedGraph[T], u, v: int, cost: T) =\n            g.add_edge_dynamic_impl(u, v, cost, true)\n    \n        proc initWeightedUnDirectedGraph*(N: int, edgetype: typedesc = int): WeightedUnDirectedGraph[edgetype] =\n            result = WeightedUnDirectedGraph[edgetype](edges: newSeq[seq[(int32, edgetype)]](N), len: N)\n        proc add_edge*[T](g: var WeightedUnDirectedGraph[T], u, v: int, cost: T) =\n            g.add_edge_dynamic_impl(u, v, cost, false)\n    \n        proc initUnWeightedDirectedGraph*(N: int): UnWeightedDirectedGraph =\n            result = UnWeightedDirectedGraph(edges: newSeq[seq[(int32, int)]](N), len: N)\n        proc add_edge*(g: var UnWeightedDirectedGraph, u, v: int) =\n            g.add_edge_dynamic_impl(u, v, 1, true)\n    \n        proc initUnWeightedUnDirectedGraph*(N: int): UnWeightedUnDirectedGraph =\n            result = UnWeightedUnDirectedGraph(edges: newSeq[seq[(int32, int)]](N), len: N)\n        proc add_edge*(g: var UnWeightedUnDirectedGraph, u, v: int) =\n            g.add_edge_dynamic_impl(u, v, 1, false)\n    \n        proc len*[T](G: WeightedGraph[T]): int = G.len\n        proc len*(G: UnWeightedGraph): int = G.len\n    \n        iterator `[]`*[T](g: WeightedDirectedGraph[T] or WeightedUnDirectedGraph[T], x: int): (int, T) =\n            for e in g.edges[x]: yield (e[0].int, e[1])\n        iterator `[]`*(g: UnWeightedDirectedGraph or UnWeightedUnDirectedGraph, x: int): int =\n            for e in g.edges[x]: yield e[0].int\n    \n        proc add_edge_static_impl*[T](g: StaticGraph[T], u, v: int, cost: T, directed: bool) =\n            g.src.add(u.int32)\n            g.dst.add(v.int32)\n            g.cost.add(cost)\n            if not directed:\n                g.src.add(v.int32)\n                g.dst.add(u.int32)\n                g.cost.add(cost)\n    \n        proc build_impl*[T](g: StaticGraph[T]) =\n            g.start = newSeqWith(g.len + 1, 0.int32)\n            for i in 0..<g.src.len:\n                g.start[g.src[i]] += 1\n            g.start.cumsum\n            g.elist = newSeq[(int32, T)](g.start[^1])\n            for i in countdown(g.src.len - 1, 0):\n                var u = g.src[i]\n                var v = g.dst[i]\n                g.start[u] -= 1\n                g.elist[g.start[u]] = (v, g.cost[i])\n        proc build*(g: StaticGraphTypes) = g.build_impl()\n    \n        proc initWeightedDirectedStaticGraph*(N: int, edgetype: typedesc = int, capacity: int = 0): WeightedDirectedStaticGraph[edgetype] =\n            result = WeightedDirectedStaticGraph[edgetype](\n                src: newSeqOfCap[int32](capacity),\n                dst: newSeqOfCap[int32](capacity),\n                cost: newSeqOfCap[edgetype](capacity),\n                elist: newSeq[(int32, edgetype)](0),\n                start: newSeq[int32](0),\n                len: N\n            )\n        proc add_edge*[T](g: var WeightedDirectedStaticGraph[T], u, v: int, cost: T) =\n            g.add_edge_static_impl(u, v, cost, true)\n    \n        proc initWeightedUnDirectedStaticGraph*(N: int, edgetype: typedesc = int, capacity: int = 0): WeightedUnDirectedStaticGraph[edgetype] =\n            result = WeightedUnDirectedStaticGraph[edgetype](\n                src: newSeqOfCap[int32](capacity*2),\n                dst: newSeqOfCap[int32](capacity*2),\n                cost: newSeqOfCap[edgetype](capacity*2),\n                elist: newSeq[(int32, edgetype)](0),\n                start: newSeq[int32](0),\n                len: N\n            )\n        proc add_edge*[T](g: var WeightedUnDirectedStaticGraph[T], u, v: int, cost: T) =\n            g.add_edge_static_impl(u, v, cost, false)\n    \n        proc initUnWeightedDirectedStaticGraph*(N: int, capacity: int = 0): UnWeightedDirectedStaticGraph =\n            result = UnWeightedDirectedStaticGraph(\n                src: newSeqOfCap[int32](capacity),\n                dst: newSeqOfCap[int32](capacity),\n                cost: newSeqOfCap[int](capacity),\n                elist: newSeq[(int32, int)](0),\n                start: newSeq[int32](0),\n                len: N\n            )\n        proc add_edge*(g: var UnWeightedDirectedStaticGraph, u, v: int) =\n            g.add_edge_static_impl(u, v, 1, true)\n    \n        proc initUnWeightedUnDirectedStaticGraph*(N: int, capacity: int = 0): UnWeightedUnDirectedStaticGraph =\n            result = UnWeightedUnDirectedStaticGraph(\n                src: newSeqOfCap[int32](capacity*2),\n                dst: newSeqOfCap[int32](capacity*2),\n                cost: newSeqOfCap[int](capacity*2),\n                elist: newSeq[(int32, int)](0),\n                start: newSeq[int32](0),\n                len: N\n            )\n        proc add_edge*(g: var UnWeightedUnDirectedStaticGraph, u, v: int) =\n            g.add_edge_static_impl(u, v, 1, false)\n    \n        proc static_graph_initialized_check*[T](g: StaticGraph[T]) = assert g.start.len > 0, \"Static Graph must be initialized before use.\"\n    \n        iterator `[]`*[T](g: WeightedDirectedStaticGraph[T] or WeightedUnDirectedStaticGraph[T], x: int): (int, T) =\n            g.static_graph_initialized_check()\n            for i in g.start[x]..<g.start[x+1]: yield (g.elist[i][0].int, g.elist[i][1])\n        iterator `[]`*(g: UnWeightedDirectedStaticGraph or UnWeightedUnDirectedStaticGraph, x: int): int =\n            g.static_graph_initialized_check()\n            for i in g.start[x]..<g.start[x+1]: yield g.elist[i][0].int\n    \n        iterator to_and_cost*[T](g: DynamicGraph[T], x: int): (int, T) =\n            for e in g.edges[x]: yield (e[0].int, e[1])\n        iterator to_and_cost*[T](g: StaticGraph[T], x: int): (int, T) =\n            g.static_graph_initialized_check()\n            for i in g.start[x]..<g.start[x+1]: yield (g.elist[i][0].int, g.elist[i][1])\n        \n        import tables\n    \n        type UnWeightedUnDirectedTableGraph*[T] = object \n            toi* : Table[T,int]\n            v* : seq[T]\n            graph* : UnWeightedUnDirectedGraph\n    \n        type UnWeightedDirectedTableGraph*[T] = object \n            toi* : Table[T,int]\n            v* : seq[T]\n            graph* : UnWeightedDirectedGraph\n    \n        type WeightedUnDirectedTableGraph*[T,S] = object \n            toi* : Table[T,int]\n            v* : seq[T]\n            graph* : WeightedUnDirectedGraph[S]\n    \n        type WeightedDirectedTableGraph*[T,S] = object \n            toi* : Table[T,int]\n            v* : seq[T]\n            graph* : WeightedDirectedGraph[S]\n    \n        type UnWeightedTableGraph*[T] = UnWeightedUnDirectedTableGraph[T] or UnWeightedDirectedTableGraph[T]\n        type WeightedTableGraph*[T,S] = WeightedUnDirectedTableGraph[T,S] or WeightedDirectedTableGraph[T,S]\n    \n        proc initUnWeightedUnDirectedTableGraph*[T](V:openArray[T]):UnWeightedUnDirectedTableGraph[T]=\n            for i in 0..<len(V):\n                result.toi[V[i]] = i\n            result.graph = initUnWeightedUnDirectedGraph(len(V))\n            result.v = @V\n    \n        proc initUnWeightedDirectedTableGraph*[T](V:openArray[T]):UnWeightedDirectedTableGraph[T]=\n            for i in 0..<len(V):\n                result.toi[V[i]] = i\n            result.graph = initUnWeightedDirectedGraph(len(V))\n            result.v = @V\n    \n        proc initWeightedUnDirectedTableGraph*[T](V:openArray[T],S:typedesc = int):WeightedUnDirectedTableGraph[T,S]=\n            for i in 0..<len(V):\n                result.toi[V[i]] = i\n            result.graph = initWeightedUnDirectedGraph(len(V),S)\n            result.v = @V\n    \n        proc initWeightedDirectedTableGraph*[T](V:openArray[T],S:typedesc = int):WeightedDirectedTableGraph[T,S]=\n            for i in 0..<len(V):\n                result.toi[V[i]] = i\n            result.graph = initWeightedDirectedGraph(len(V),S)\n            result.v = @V\n    \n        proc add_edge*[T](g: var UnWeightedTableGraph[T],u,v:T)=\n            g.graph.add_edge(g.toi[u],g.toi[v])\n    \n        proc add_edge*[T,S](g: var WeightedTableGraph[T,S],u,v:T,cost:S)=\n            g.graph.add_edge(g.toi[u],g.toi[v],cost)\n    \n        iterator `[]`*[T,S](g: WeightedDirectedTableGraph[T,S] or WeightedUnDirectedTableGraph[T,S], x: T): (T, S) = \n            for (x,y) in g.graph[g.toi[x]]:\n                yield (g.v[x],y)\n        iterator `[]`*[T](g: UnWeightedDirectedTableGraph[T] or UnWeightedUnDirectedTableGraph[T], x: T): T = \n            for x in g.graph[g.toi[x]]:\n                yield g.v[x]\n    \n    when not declared CPLIB_TREE_HLD:\n        const CPLIB_TREE_HLD* = 1\n        import sequtils\n        import algorithm\n        import sets\n        # https://atcoder.jp/contests/abc337/submissions/50216964\n        # ↑上記の提出より引用\n        type HeavyLightDecomposition* = ref object \n            N*: int\n            P*, PP*, PD*, D*, I*, rangeL*, rangeR*: seq[int]\n    \n        proc initHldFromParent*(parent: openArray[int], root: int): HeavyLightDecomposition =\n            let n = len(parent)\n            assert 0 <= root and root < n\n            var hld = HeavyLightDecomposition(N:n)\n            hld.P = @parent\n            hld.P[root] = -1\n    \n            # 親から子を列挙するための連結リスト。\n            var head = newSeqWith(n,-1)\n            var next = newSeqWith(n,-1)\n            for v in 0..<n:\n                if v != root:\n                    assert 0 <= hld.P[v] and hld.P[v] < n\n                    next[v] = head[hld.P[v]]\n                    head[hld.P[v]] = v\n    \n            # 親が必ず子より先に現れる順序。\n            hld.I = newSeq[int](n)\n            hld.I[0] = root\n            var iI = 1\n            for i in 0..<n:\n                var v = head[hld.I[i]]\n                while v != -1:\n                    hld.I[iI] = v\n                    iI += 1\n                    v = next[v]\n            assert iI == n\n    \n            var size = newSeqWith(n,1)\n            var heavy = newSeqWith(n,-1)\n            for i in countdown(n-1,1):\n                let v = hld.I[i]\n                let p = hld.P[v]\n                size[p] += size[v]\n                if heavy[p] == -1 or size[heavy[p]] < size[v]:\n                    heavy[p] = v\n    \n            hld.PP = newSeq[int](n)\n            for v in 0..<n:\n                hld.PP[v] = v\n            for v in hld.I:\n                if heavy[v] != -1:\n                    hld.PP[heavy[v]] = v\n    \n            hld.PD = newSeqWith(n,n)\n            hld.PD[root] = 0\n            hld.D = newSeq[int](n)\n            for v in hld.I:\n                if v != root:\n                    hld.PP[v] = hld.PP[hld.PP[v]]\n                    hld.PD[v] = min(hld.PD[hld.PP[v]],hld.PD[hld.P[v]]+1)\n                    hld.D[v] = hld.D[hld.P[v]]+1\n    \n            hld.rangeL = newSeq[int](n)\n            hld.rangeR = newSeq[int](n)\n            for p in hld.I:\n                hld.rangeR[p] = hld.rangeL[p]+size[p]\n                var ir = hld.rangeR[p]\n                var v = head[p]\n                while v != -1:\n                    if v != heavy[p]:\n                        ir -= size[v]\n                        hld.rangeL[v] = ir\n                    v = next[v]\n                if heavy[p] != -1:\n                    hld.rangeL[heavy[p]] = hld.rangeL[p]+1\n    \n            for v in 0..<n:\n                hld.I[hld.rangeL[v]] = v\n            return hld\n    \n        proc initHld*(g: UnDirectedGraph, root: int): HeavyLightDecomposition =\n            var hld = HeavyLightDecomposition()\n            var n: int = g.len\n            hld.N = n\n            hld.P = newSeqWith(n, -1)\n            hld.I = newSeqWith(n, 0)\n            hld.I[0] = root\n            var iI = 1\n            for i in 0..<n:\n                var p = hld.I[i]\n                for (e, _) in g.to_and_cost(p):\n                    if hld.P[p] != e:\n                        hld.I[iI] = e\n                        hld.P[e] = p\n                        iI += 1\n            var Z = newSeqWith(n, 1)\n            var nx = newSeqWith(n, -1)\n            hld.PP = newSeqWith(n, 0)\n            for i in 0..<n:\n                hld.PP[i] = i\n            for i in 1..<n:\n                var p = hld.I[n-i]\n                Z[hld.P[p]] += Z[p]\n                if nx[hld.P[p]] == -1 or Z[nx[hld.P[p]]] < Z[p]:\n                    nx[hld.P[p]] = p\n            for p in hld.I:\n                if nx[p] != -1:\n                    hld.PP[nx[p]] = p\n            hld.PD = newSeqWith(n, n)\n            hld.PD[root] = 0\n            hld.D = newSeqWith(n, 0)\n            for p in hld.I:\n                if p != root:\n                    hld.PP[p] = hld.PP[hld.PP[p]]\n                    hld.PD[p] = min(hld.PD[hld.PP[p]], hld.PD[hld.P[p]]+1)\n                    hld.D[p] = hld.D[hld.P[p]]+1\n            hld.rangeL = newSeqWith(n, 0)\n            hld.rangeR = newSeqWith(n, 0)\n            for p in hld.I:\n                hld.rangeR[p] = hld.rangeL[p] + Z[p]\n                var ir = hld.rangeR[p]\n                for (e, _) in g.to_and_cost(p):\n                    if hld.P[p] != e and e != nx[p]:\n                        ir -= Z[e]\n                        hld.rangeL[e] = ir\n                if nx[p] != -1:\n                    hld.rangeL[nx[p]] = hld.rangeL[p] + 1\n            for i in 0..<n:\n                hld.I[hld.rangeL[i]] = i\n            return hld\n        proc initHld*(g: DirectedGraph, root: int): HeavyLightDecomposition =\n            var n = g.len\n            var gn = initUnWeightedUnDirectedStaticGraph(n)\n            var seen = initHashSet[(int, int)]()\n            for i in 0..<n:\n                for (j, _) in g.to_and_cost(i):\n                    if (i, j) notin seen:\n                        gn.add_edge(i, j)\n                        seen.incl((i, j))\n                        seen.incl((j, i))\n            gn.build\n            return initHld(gn, root)\n        proc initHld*(adj: openArray[seq[int]], root: int): HeavyLightDecomposition =\n            var n = adj.len\n            var gn = initUnWeightedUnDirectedStaticGraph(n)\n            var seen = initHashSet[(int, int)]()\n            for i in 0..<n:\n                for j in adj[i]:\n                    if (i, j) notin seen:\n                        gn.add_edge(i, j)\n                        seen.incl((i, j))\n                        seen.incl((j, i))\n            gn.build\n            return initHld(gn, root)\n        proc numVertices*(hld: HeavyLightDecomposition): int = hld.N\n        proc depth*(hld: HeavyLightDecomposition, p: int): int = hld.D[p]\n        proc toSeq*(hld: HeavyLightDecomposition, vtx: int): int = hld.rangeL[vtx]\n        proc toVtx*(hld: HeavyLightDecomposition, seqidx: int): int = hld.I[seqidx]\n        proc toSeq2In*(hld: HeavyLightDecomposition, vtx: int): int = hld.rangeL[vtx] * 2 - hld.D[vtx]\n        proc toSeq2Out*(hld: HeavyLightDecomposition, vtx: int): int = hld.rangeR[vtx] * 2 - hld.D[vtx] - 1\n        proc parentOf*(hld: HeavyLightDecomposition, v: int): int = hld.P[v]\n        proc heavyRootOf*(hld: HeavyLightDecomposition, v: int): int = hld.PP[v]\n        proc heavyChildOf*(hld: HeavyLightDecomposition, v: int): int =\n            if hld.toSeq(v) == hld.N-1:\n                return -1\n            var cand = hld.toVtx(hld.toSeq(v) + 1)\n            if hld.PP[v] == hld.PP[cand]:\n                return cand\n            -1\n        proc lca*(hld: HeavyLightDecomposition, u: int, v: int): int =\n            var (u, v) = (u, v)\n            if hld.PD[u] < hld.PD[v]:\n                swap(u, v)\n            while hld.PD[u] > hld.PD[v]:\n                u = hld.P[hld.PP[u]]\n            while hld.PP[u] != hld.PP[v]:\n                u = hld.P[hld.PP[u]]\n                v = hld.P[hld.PP[v]]\n            if hld.D[u] > hld.D[v]:\n                return v\n            u\n        proc dist*(hld: HeavyLightDecomposition, u: int, v: int): int =\n            hld.depth(u) + hld.depth(v) - hld.depth(hld.lca(u, v)) * 2\n        proc path*(hld: HeavyLightDecomposition, r: int, c: int, include_root: bool, reverse_path: bool): seq[(int, int)] =\n            var (r, c) = (r, c)\n            var k = hld.PD[c] - hld.PD[r] + 1\n            if k <= 0:\n                return @[]\n            var res = newSeqWith(k, (0, 0))\n            for i in 0..<k-1:\n                res[i] = (hld.rangeL[hld.PP[c]], hld.rangeL[c] + 1)\n                c = hld.P[hld.PP[c]]\n            if hld.PP[r] != hld.PP[c] or hld.D[r] > hld.D[c]:\n                return @[]\n            var root_off = int(not include_root)\n            res[^1] = (hld.rangeL[r]+root_off, hld.rangeL[c]+1)\n            if res[^1][0] == res[^1][1]:\n                discard res.pop()\n                k -= 1\n            if reverse_path:\n                for i in 0..<k:\n                    res[i] = (hld.N - res[i][1], hld.N - res[i][0])\n            else:\n                res.reverse()\n            res\n        proc subtree*(hld: HeavyLightDecomposition, p: int): (int, int) = (hld.rangeL[p], hld.rangeR[p])\n        iterator subtreeV*(hld: HeavyLightDecomposition, p: int):int=\n            for i in hld.rangeL[p]..<hld.rangeR[p]:\n                yield hld.toVtx(i)\n        proc median*(hld: HeavyLightDecomposition, x: int, y: int, z: int): int =\n            hld.lca(x, y) xor hld.lca(y, z) xor hld.lca(x, z)\n        proc la*(hld: HeavyLightDecomposition, starting: int, goal: int, d: int): int =\n            var (u, v, d) = (starting, goal, d)\n            if d < 0:\n                return -1\n            var g = hld.lca(u, v)\n            var dist0 = hld.D[u] - hld.D[g] * 2 + hld.D[v]\n            if dist0 < d:\n                return -1\n            var p = u\n            if hld.D[u] - hld.D[g] < d:\n                p = v\n                d = dist0 - d\n            while hld.D[p] - hld.D[hld.PP[p]] < d:\n                d -= hld.D[p] - hld.D[hld.PP[p]] + 1\n                p = hld.P[hld.PP[p]]\n            hld.I[hld.rangeL[p] - d]\n        iterator children*(hld: HeavyLightDecomposition, v: int): int =\n            var s = hld.rangeL[v] + 1\n            while s < hld.rangeR[v]:\n                var w = hld.toVtx(s)\n                yield w\n                s += hld.rangeR[w] - hld.rangeL[w]\n        \n    \n        proc initAuxiliaryTree*(hld:HeavyLightDecomposition,v:openArray[int]):UnWeightedUnDirectedTableGraph[int]=\n            var v = v.sortedByit(hld.toseq(it))\n            for i in 0..<(len(v)-1):\n                v.add(hld.lca(v[i],v[i+1]))\n            v = v.sortedByIt(hld.toseq(it)).deduplicate(true)\n            var stack :seq[int]\n            result = initUnWeightedUnDirectedTableGraph[int](v)\n            stack.add(v[0])\n            \n            for i in 1..<len(v):\n                while len(stack) > 0 and hld.toSeq2Out(stack[^1]) < hld.toseq2In(v[i]):\n                    discard stack.pop()\n                if len(stack) != 0:\n                    result.add_edge(stack[^1],v[i])\n                stack.add(v[i])\n        \n        proc initAuxiliaryWeightedTree*(hld: HeavyLightDecomposition, v: openArray[int], S: typedesc = int): WeightedUnDirectedTableGraph[int, S] =\n            var v = v.sortedByit(hld.toseq(it))\n            for i in 0..<(len(v)-1):\n                v.add(hld.lca(v[i],v[i+1]))\n            v = v.sortedByIt(hld.toseq(it)).deduplicate(true)\n            var stack :seq[int]\n            result = initWeightedUnDirectedTableGraph(v, S)\n            stack.add(v[0])\n            for i in 1..<len(v):\n                while len(stack) > 0 and hld.toSeq2Out(stack[^1]) < hld.toseq2In(v[i]):\n                    discard stack.pop()\n                if len(stack) != 0:\n                    result.add_edge(stack[^1], v[i], S(hld.depth(v[i]) - hld.depth(stack[^1])))\n                stack.add(v[i])\n    \n    type Functional_Graph* = ref object \n        tree* : HeavyLightDecomposition\n        cycle_number* : seq[int]\n        cycle_idx* : seq[int]\n        roots* : seq[int]\n        cycle* : seq[seq[int]]\n        depth_tin : seq[seq[int]]\n        cycle_depth : seq[seq[seq[int]]]\n        component_size : seq[int]\n\n    proc initFunctionalGraph*(v:openArray[int]):Functional_Graph=\n        let n = len(v)\n        var removed = newSeqOfCap[int](n)\n        var sizes = newseqwith(n,0)\n        var cycle_number = newseqwith(n,-1)\n        var cycle_idx = newseqwith(n,-1)\n        var parent = newSeqWith(n+1,-1)\n        var roots = newseqwith(n,0)\n        var cycle : seq[seq[int]]\n        for i in 0..<n:\n            assert 0 <= v[i] and v[i] < n\n            sizes[v[i]] += 1\n        for i in 0..<n:\n            if sizes[i] == 0:\n                removed.add(i)\n        var removed_idx = 0\n        while removed_idx < len(removed):\n            let i = removed[removed_idx]\n            removed_idx += 1\n            let j = v[i]\n            parent[i] = j\n            sizes[j] -= 1\n            if sizes[j] == 0:\n                removed.add(j)\n\n        var alr = newseqwith(n,false)\n        for i in 0..<n:\n            if sizes[i] != 0 and not alr[i]:\n                let cycle_n = len(cycle)\n                var now = i\n                cycle.add(@[])\n                while not alr[now]:\n                    alr[now] = true\n                    cycle_number[now] = cycle_n\n                    cycle_idx[now] = len(cycle[cycle_n])\n                    roots[now] = now\n                    cycle[cycle_n].add(now)\n                    parent[now] = n\n                    now = v[now]\n        # 削除順の逆から見れば、遷移先のrootは既に決まっている。\n        var i = len(removed)\n        while i > 0:\n            i -= 1\n            let x = removed[i]\n            roots[x] = roots[v[x]]\n\n        result = Functional_Graph(\n            tree:initHldFromParent(parent,n),\n            cycle_number:cycle_number,\n            roots:roots,\n            cycle:cycle,\n            cycle_idx:cycle_idx\n        )\n\n        # depthごとにHLDのEuler Tour上の位置を昇順で持つ。\n        result.depth_tin = newSeq[seq[int]](n)\n        for tin in 0..<result.tree.N:\n            let x = result.tree.toVtx(tin)\n            if x < n:\n                let d = result.tree.depth(x)-1\n                result.depth_tin[d].add(tin)\n\n        # cycleごとに (cycle_idx[root]-depth) mod cycle_size で分類し、\n        # 各列にはdepthを昇順で持つ。\n        result.cycle_depth = newSeq[seq[seq[int]]](len(cycle))\n        result.component_size = newSeq[int](len(cycle))\n        for cid in 0..<len(cycle):\n            result.cycle_depth[cid] = newSeq[seq[int]](len(cycle[cid]))\n        for d in 0..<len(result.depth_tin):\n            for tin in result.depth_tin[d]:\n                let v = result.tree.toVtx(tin)\n                let root = roots[v]\n                let cid = cycle_number[root]\n                let csiz = len(cycle[cid])\n                let residue = (cycle_idx[root]-(d mod csiz)+csiz) mod csiz\n                result.cycle_depth[cid][residue].add(d)\n                result.component_size[cid] += 1\n\n    proc initFunctionalGraph*(graph:UnWeightedDirectedGraph):Functional_Graph=\n        var v = newSeq[int](len(graph))\n        for i in 0..<len(graph):\n            for j in graph[i]:\n                v[i] = j\n        return initFunctionalGraph(v)\n\n    proc incycle*(namori:Functional_Graph,x:int):bool=\n        return namori.cycle_number[x] != -1\n\n    proc movekth*(functional_graph:Functional_Graph,x,cnt:int):int=\n        #xからcnt回動いたらどこに行くか\n        if functional_graph.tree.depth(x)-1 >= cnt:\n            return functional_graph.tree.la(x,len(functional_graph.cycle_number),cnt)\n        else:\n            var root = functional_graph.roots[x]\n            var cnt = cnt-(functional_graph.tree.depth(x)-1)\n            return functional_graph.cycle[functional_graph.cycle_number[root]][(functional_graph.cycle_idx[root]+cnt) mod len(functional_graph.cycle[functional_graph.cycle_number[root]])]\n\n    proc cyclesize*(functional_graph:Functional_Graph,x:int):int=\n        var root = functional_graph.roots[x]\n        return functional_graph.cycle[functional_graph.cycle_number[root]].len()\n\n    proc canmove_size*(functional_graph:Functional_Graph,x:int):int=\n        return functional_graph.tree.depth(x)-1+functional_graph.cyclesize(x)\n\n    proc reachable_to_size*(functional_graph:Functional_Graph,x:int):int=\n        if functional_graph.incycle(x):\n            return functional_graph.component_size[functional_graph.cycle_number[x]]\n        let (l,r) = functional_graph.tree.subtree(x)\n        return r-l\n\n    proc depth*(functional_graph:Functional_Graph,x:int):int=\n        return functional_graph.tree.depth(x)-1\n\n    proc dist*(functional_graph:Functional_Graph,u,v:int):int=\n        if functional_graph.cycle_number[functional_graph.roots[u]] != functional_graph.cycle_number[functional_graph.roots[v]]:\n            return -1\n        var lca = functional_graph.tree.lca(u,v)\n        if lca == v:\n            return functional_graph.tree.depth(u)-functional_graph.tree.depth(v)\n        if lca == len(functional_graph.cycle_number):\n            if functional_graph.incycle(v):\n                var x = functional_graph.cycle_idx[functional_graph.roots[u]]\n                var y = functional_graph.cycle_idx[v]\n                if x < y:\n                    return y-x+functional_graph.depth(u)\n                else:\n                    return y+len(functional_graph.cycle[functional_graph.cycle_number[v]])-x+functional_graph.depth(u)\n        return -1\n\n    proc get_cycle*(functional_graph:Functional_Graph,x:int):seq[int]=\n        var root = functional_graph.roots[x]\n        return functional_graph.cycle[functional_graph.cycle_number[root]]\n\n    proc root*(functional_graph:Functional_Graph,x:int):int=\n        return functional_graph.roots[x]\n\n    proc compressed_forest*(functional_graph:Functional_Graph):(UnWeightedUnDirectedGraph,seq[int],seq[int])=\n        let n = len(functional_graph.cycle_number)\n        var compressed = newSeqWith(n,-1)\n        var roots = newSeq[int](len(functional_graph.cycle))\n        var compressed_n = 0\n\n        for cid,cycle in functional_graph.cycle:\n            roots[cid] = compressed_n\n            for v in cycle:\n                compressed[v] = compressed_n\n            compressed_n += 1\n\n        for v in 0..<n:\n            if compressed[v] == -1:\n                compressed[v] = compressed_n\n                compressed_n += 1\n\n        var forest = initUnWeightedUnDirectedGraph(compressed_n)\n        for v in 0..<n:\n            if not functional_graph.incycle(v):\n                forest.add_edge(compressed[v],compressed[functional_graph.tree.P[v]])\n\n        return (forest,compressed,roots)\n\n    proc walk*(functional_graph:Functional_Graph,x,k:int):seq[int]=\n        let n = len(functional_graph.cycle_number)\n        assert 0 <= x and x < n\n        assert 0 <= k and k < high(int)\n        result = newSeq[int](k+1)\n        var now = x\n        for i in 0..k:\n            result[i] = now\n            if i < k:\n                if functional_graph.incycle(now):\n                    let cid = functional_graph.cycle_number[now]\n                    let next_idx = (functional_graph.cycle_idx[now]+1) mod len(functional_graph.cycle[cid])\n                    now = functional_graph.cycle[cid][next_idx]\n                else:\n                    now = functional_graph.tree.P[now]\n\n    import algorithm\n\n    proc count_kth*(functional_graph:Functional_Graph,x,k:int):int=\n        assert 0 <= x and x < len(functional_graph.cycle_number)\n        assert k >= 0\n        if not functional_graph.incycle(x):\n            let d = functional_graph.depth(x)\n            if k > functional_graph.depth_tin.high-d:\n                return 0\n            let (l,r) = functional_graph.tree.subtree(x)\n            let tins = functional_graph.depth_tin[d+k]\n            return tins.lowerBound(r)-tins.lowerBound(l)\n\n        let cid = functional_graph.cycle_number[x]\n        let csiz = len(functional_graph.cycle[cid])\n        let residue = (functional_graph.cycle_idx[x]-(k mod csiz)+csiz) mod csiz\n        return functional_graph.cycle_depth[cid][residue].upperBound(k)\n"


var md = 100003

var memo = newseqwith(100003,-1)

proc f(x:int):int=
    if memo[x] != -1:
        return memo[x]
    var res = 0
    for y in divisor(x):
        res += y
    memo[x] = res%md
    return res%md


var N,K = ii()

var tmp = newseqwith(md,-1)



for i in range(md):
    tmp[i] = f(i)


var G = initFunctionalGraph(tmp)

if K == 1:
    echo N
    quit()
else:
    echo G.movekth(f(N),K-2)