結果

問題 No.1197 モンスターショー
ユーザー 草苺奶昔
提出日時 2023-03-25 15:17:45
言語 Go
(1.23.4)
結果
AC  
実行時間 1,089 ms / 3,000 ms
コード長 18,899 bytes
コンパイル時間 14,624 ms
コンパイル使用メモリ 223,948 KB
実行使用メモリ 47,488 KB
最終ジャッジ日時 2024-09-18 21:49:59
合計ジャッジ時間 37,230 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// !- NewLazyTreeMonoid(tree *Tree, data []E, isVertex bool) *LazyTreeMonoid:
//   需要传入树、节点（或边）的初始值，以及一个布尔值表示给定的值是否是节点的值。
// !- QueryPath(start, target int) E:
//   用于查询两个节点之间路径的值。(取决于isVertex)
// !- UpdatePath(start, target int, lazy Id):
//   用于更新两个节点之间路径的值。(取决于isVertex)
// !- MaxPath(check func(E) bool, start, target int) int:
//   在树上查找最后一个满足条件的节点，使得从 start 到该节点的路径上的值满足某个条件。
//   若不存在这样的节点则返回 -1。
// !- QuerySubtree(root int) E:
//   用于查询以给定节点为根的子树上的所有节点值的代数和。
// !- UpdateSubtree(root int, lazy Id):
//   用于更新以给定节点为根的子树上的所有节点值的代数和。
// !-QueryAll() E:
//   用于查询整棵树上的所有节点值的代数和。
// !- Get(i int) E
// !- Set(i int, x E)
package main
import (
    "bufio"
    "fmt"
    "math/bits"
    "os"
)
func main() {
    // No.1197 モンスターショー
    // 树上移动距离之和
    // 给定一个有 n 个节点的树，每个节点与一条边相连，边长为 1。
    // 一开始，有 k 只史莱姆分别位于不同的节点上。现在，你需要支持以下操作：
    // 1 i d: 将第 i 只史莱姆从其所在节点移到节点 d。
    // 2 e :查询将所有史莱姆移到节点 e 时，史莱姆移动距离之和。
    // 其中，史莱姆从一个节点到另一个节点的移动距离为其走过的边长之和。
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var n, k, q int
    fmt.Fscan(in, &n, &k, &q)
    pos := make([]int, k) // 史莱姆的初始位置
    for i := range pos {
        fmt.Fscan(in, &pos[i])
        pos[i]--
    }
    tree := NewTree(n)
    for i := 0; i < n-1; i++ {
        var u, v int
        fmt.Fscan(in, &u, &v)
        u--
        v--
        tree.AddEdge(u, v, 1)
    }
    tree.Build(0)
    leaves := make([]E, n)
    for i := 0; i < n; i++ {
        leaves[i] = E{size: 1}
    }
    LM := NewLazyTreeMonoid(tree, leaves, true)
    for _, v := range pos {
        LM.UpdatePath(0, v, 1)
    }
    depth := tree.Depth
    depSum := 0
    for _, v := range pos {
        depSum += depth[v]
    }
    for i := 0; i < q; i++ {
        var op int
        fmt.Fscan(in, &op)
        if op == 1 {
            var slime, moveTo int
            fmt.Fscan(in, &slime, &moveTo)
            slime, moveTo = slime-1, moveTo-1
            depSum -= depth[pos[slime]]
            LM.UpdatePath(0, pos[slime], -1)
            pos[slime] = moveTo
            depSum += depth[pos[slime]]
            LM.UpdatePath(0, pos[slime], 1)
        } else {
            var to int
            fmt.Fscan(in, &to)
            to--
            res := depth[to]*k + depSum
            res -= 2 * LM.QueryPath(0, to).sum
            res += 2 * k
            fmt.Fprintln(out, res)
        }
    }
}
const INF = 1e18
type E = struct{ sum, size int }
type Id = int
func e() E                   { return E{0, 0} }
func id() Id                 { return 0 }
func op(e1, e2 E) E          { return E{e1.sum + e2.sum, e1.size + e2.size} }
func mapping(f Id, g E) E    { return E{g.sum + f*g.size, g.size} }
func composition(f, g Id) Id { return f + g }
type LazyTreeMonoid struct {
    tree     *Tree
    n        int
    unit     E
    isVertex bool
    seg      *_LST
}
// !树的路径查询 + 区间修改, 维护的量需要满足幺半群的性质，且必须要满足交换律.
//  data: 顶点的值, 或者边的值.(边的编号为两个定点中较深的那个点的编号)
//  isVertex: data是否为顶点的值以及查询的时候是否是顶点权值.
func NewLazyTreeMonoid(tree *Tree, data []E, isVertex bool) *LazyTreeMonoid {
    n := len(tree.Tree)
    res := &LazyTreeMonoid{tree: tree, n: n, unit: e(), isVertex: isVertex}
    leaves := make([]E, n)
    if isVertex {
        for v := range leaves {
            leaves[tree.LID[v]] = data[v]
        }
    } else {
        for i := range leaves {
            leaves[i] = res.unit
        }
        for e := 0; e < n-1; e++ {
            v := tree.EidtoV(e)
            leaves[tree.LID[v]] = data[e]
        }
    }
    res.seg = _NewLST(leaves, e, id, op, mapping, composition)
    return res
}
// 第i个顶点或者第i条边的值修改为e.
func (tm *LazyTreeMonoid) Set(i int, e E) {
    if !tm.isVertex {
        i = tm.tree.EidtoV(i)
    }
    i = tm.tree.LID[i]
    tm.seg.Set(i, e)
}
func (tm *LazyTreeMonoid) Get(i int) E {
    return tm.seg.Get(tm.tree.LID[i])
}
func (tm *LazyTreeMonoid) UpdatePath(start, target int, lazy Id) {
    path := tm.tree.GetPathDecomposition(start, target, tm.isVertex)
    for _, ab := range path {
        left, right := ab[0], ab[1]
        if left > right {
            left, right = right, left
        }
        tm.seg.Update(left, right+1, lazy)
    }
}
// 查询 start 到 target 的路径上的值.(点权/边权 由 isVertex 决定)
func (tm *LazyTreeMonoid) QueryPath(start, target int) E {
    path := tm.tree.GetPathDecomposition(start, target, tm.isVertex)
    val := tm.unit
    for _, ab := range path {
        a, b := ab[0], ab[1]
        var x E
        if a <= b {
            x = tm.seg.Query(a, b+1)
        } else {
            x = tm.seg.Query(b, a+1)
        }
        val = op(val, x)
    }
    return val
}
// 找到路径上最后一个 x 使得 QueryPath(start,x) 满足check函数.不存在返回-1.
func (tm *LazyTreeMonoid) MaxPath(check func(E) bool, start, target int) int {
    if !tm.isVertex {
        return tm._maxPathEdge(check, start, target)
    }
    if !check(tm.QueryPath(start, start)) {
        return -1
    }
    path := tm.tree.GetPathDecomposition(start, target, tm.isVertex)
    val := tm.unit
    for _, ab := range path {
        a, b := ab[0], ab[1]
        var x E
        if a <= b {
            x = tm.seg.Query(a, b+1)
        } else {
            x = tm.seg.Query(b, a+1)
        }
        if tmp := op(val, x); check(tmp) {
            val = tmp
            start = tm.tree.idToNode[b]
            continue
        }
        checkTmp := func(x E) bool {
            return check(op(val, x))
        }
        if a <= b {
            i := tm.seg.MaxRight(a, checkTmp)
            if i == a {
                return start
            }
            return tm.tree.idToNode[i-1]
        } else {
            i := tm.seg.MinLeft(a+1, checkTmp)
            if i == a+1 {
                return start
            }
            return tm.tree.idToNode[i]
        }
    }
    return target
}
func (tm *LazyTreeMonoid) QuerySubtree(root int) E {
    l, r := tm.tree.LID[root], tm.tree.RID[root]
    offset := 1
    if tm.isVertex {
        offset = 0
    }
    return tm.seg.Query(l+offset, r)
}
func (tm *LazyTreeMonoid) UpdateSubtree(root int, lazy Id) {
    l, r := tm.tree.LID[root], tm.tree.RID[root]
    offset := 1
    if tm.isVertex {
        offset = 0
    }
    tm.seg.Update(l+offset, r, lazy)
}
func (tm *LazyTreeMonoid) QueryAll() E { return tm.seg.QueryAll() }
func (tm *LazyTreeMonoid) _maxPathEdge(check func(E) bool, u, v int) int {
    lca := tm.tree.LCA(u, v)
    path := tm.tree.GetPathDecomposition(u, lca, tm.isVertex)
    val := tm.unit
    // climb
    for _, ab := range path {
        a, b := ab[0], ab[1]
        x := tm.seg.Query(b, a+1)
        if tmp := op(val, x); check(tmp) {
            val = tmp
            u = tm.tree.Parent[tm.tree.idToNode[b]]
            continue
        }
        checkTmp := func(x E) bool {
            return check(op(val, x))
        }
        i := tm.seg.MinLeft(a+1, checkTmp)
        if i == a+1 {
            return u
        }
        return tm.tree.Parent[tm.tree.idToNode[i]]
    }
    // down
    path = tm.tree.GetPathDecomposition(lca, v, tm.isVertex)
    for _, ab := range path {
        a, b := ab[0], ab[1]
        x := tm.seg.Query(a, b+1)
        if tmp := op(val, x); check(tmp) {
            val = tmp
            u = tm.tree.idToNode[b]
            continue
        }
        checkTmp := func(x E) bool {
            return check(op(val, x))
        }
        i := tm.seg.MaxRight(a, checkTmp)
        if i == a {
            return u
        }
        return tm.tree.idToNode[i-1]
    }
    return v
}
type Tree struct {
    Tree                 [][][2]int // (next, weight)
    Edges                [][3]int   // (u, v, w)
    Depth, DepthWeighted []int
    Parent               []int
    LID, RID             []int // 欧拉序[in,out)
    idToNode             []int
    top, heavySon        []int
    timer                int
}
func NewTree(n int) *Tree {
    tree := make([][][2]int, n)
    lid := make([]int, n)
    rid := make([]int, n)
    idToNode := make([]int, n)
    top := make([]int, n)   // 所处轻/重链的顶点（深度最小），轻链的顶点为自身
    depth := make([]int, n) // 深度
    depthWeighted := make([]int, n)
    parent := make([]int, n)   // 父结点
    heavySon := make([]int, n) // 重儿子
    edges := make([][3]int, 0, n-1)
    for i := range parent {
        parent[i] = -1
    }
    return &Tree{
        Tree:          tree,
        Depth:         depth,
        DepthWeighted: depthWeighted,
        Parent:        parent,
        LID:           lid,
        RID:           rid,
        idToNode:      idToNode,
        top:           top,
        heavySon:      heavySon,
        Edges:         edges,
    }
}
// 添加无向边 u-v, 边权为w.
func (tree *Tree) AddEdge(u, v, w int) {
    tree.Tree[u] = append(tree.Tree[u], [2]int{v, w})
    tree.Tree[v] = append(tree.Tree[v], [2]int{u, w})
    tree.Edges = append(tree.Edges, [3]int{u, v, w})
}
// 添加有向边 u->v, 边权为w.
func (tree *Tree) AddDirectedEdge(u, v, w int) {
    tree.Tree[u] = append(tree.Tree[u], [2]int{v, w})
    tree.Edges = append(tree.Edges, [3]int{u, v, w})
}
// root:0-based
//  当root设为-1时，会从0开始遍历未访问过的连通分量
func (tree *Tree) Build(root int) {
    if root != -1 {
        tree.build(root, -1, 0, 0)
        tree.markTop(root, root)
    } else {
        for i := 0; i < len(tree.Tree); i++ {
            if tree.Parent[i] == -1 {
                tree.build(i, -1, 0, 0)
                tree.markTop(i, i)
            }
        }
    }
}
// 返回 root 的欧拉序区间, 左闭右开, 0-indexed.
func (tree *Tree) Id(root int) (int, int) {
    return tree.LID[root], tree.RID[root]
}
// 返回边 u-v 对应的 欧拉序起点编号, 0-indexed.
func (tree *Tree) Eid(u, v int) int {
    if tree.LID[u] > tree.LID[v] {
        return tree.LID[u]
    }
    return tree.LID[v]
}
// 较深的那个点作为边的编号.
func (tree *Tree) EidtoV(eid int) int {
    e := tree.Edges[eid]
    u, v := e[0], e[1]
    if tree.Parent[u] == v {
        return u
    }
    return v
}
func (tree *Tree) LCA(u, v int) int {
    for {
        if tree.LID[u] > tree.LID[v] {
            u, v = v, u
        }
        if tree.top[u] == tree.top[v] {
            return u
        }
        v = tree.Parent[tree.top[v]]
    }
}
func (tree *Tree) Dist(u, v int, weighted bool) int {
    if weighted {
        return tree.DepthWeighted[u] + tree.DepthWeighted[v] - 2*tree.DepthWeighted[tree.LCA(u, v)]
    }
    return tree.Depth[u] + tree.Depth[v] - 2*tree.Depth[tree.LCA(u, v)]
}
// k: 0-based
//  如果不存在第k个祖先，返回-1
func (tree *Tree) KthAncestor(root, k int) int {
    if k > tree.Depth[root] {
        return -1
    }
    for {
        u := tree.top[root]
        if tree.LID[root]-k >= tree.LID[u] {
            return tree.idToNode[tree.LID[root]-k]
        }
        k -= tree.LID[root] - tree.LID[u] + 1
        root = tree.Parent[u]
    }
}
// 从 from 节点跳向 to 节点,跳过 step 个节点(0-indexed)
//  返回跳到的节点,如果不存在这样的节点,返回-1
func (tree *Tree) Jump(from, to, step int) int {
    if step == 1 {
        if from == to {
            return -1
        }
        if tree.IsInSubtree(to, from) {
            return tree.KthAncestor(to, tree.Depth[to]-tree.Depth[from]-1)
        }
        return tree.Parent[from]
    }
    c := tree.LCA(from, to)
    dac := tree.Depth[from] - tree.Depth[c]
    dbc := tree.Depth[to] - tree.Depth[c]
    if step > dac+dbc {
        return -1
    }
    if step <= dac {
        return tree.KthAncestor(from, step)
    }
    return tree.KthAncestor(to, dac+dbc-step)
}
func (tree *Tree) CollectChild(root int) []int {
    res := []int{}
    for _, e := range tree.Tree[root] {
        next := e[0]
        if next != tree.Parent[root] {
            res = append(res, next)
        }
    }
    return res
}
// 返回沿着`路径顺序`的 [起点,终点] 的 欧拉序 `左闭右闭` 数组.
//  !eg:[[2 0] [4 4]] 沿着路径顺序但不一定沿着欧拉序.
func (tree *Tree) GetPathDecomposition(u, v int, vertex bool) [][2]int {
    up, down := [][2]int{}, [][2]int{}
    for {
        if tree.top[u] == tree.top[v] {
            break
        }
        if tree.LID[u] < tree.LID[v] {
            down = append(down, [2]int{tree.LID[tree.top[v]], tree.LID[v]})
            v = tree.Parent[tree.top[v]]
        } else {
            up = append(up, [2]int{tree.LID[u], tree.LID[tree.top[u]]})
            u = tree.Parent[tree.top[u]]
        }
    }
    edgeInt := 1
    if vertex {
        edgeInt = 0
    }
    if tree.LID[u] < tree.LID[v] {
        down = append(down, [2]int{tree.LID[u] + edgeInt, tree.LID[v]})
    } else if tree.LID[v]+edgeInt <= tree.LID[u] {
        up = append(up, [2]int{tree.LID[u], tree.LID[v] + edgeInt})
    }
    for i := 0; i < len(down)/2; i++ {
        down[i], down[len(down)-1-i] = down[len(down)-1-i], down[i]
    }
    return append(up, down...)
}
func (tree *Tree) GetPath(u, v int) []int {
    res := []int{}
    composition := tree.GetPathDecomposition(u, v, true)
    for _, e := range composition {
        a, b := e[0], e[1]
        if a <= b {
            for i := a; i <= b; i++ {
                res = append(res, tree.idToNode[i])
            }
        } else {
            for i := a; i >= b; i-- {
                res = append(res, tree.idToNode[i])
            }
        }
    }
    return res
}
func (tree *Tree) SubtreeSize(u int) int {
    return tree.RID[u] - tree.LID[u]
}
// child 是否在 root 的子树中 (child和root不能相等)
func (tree *Tree) IsInSubtree(child, root int) bool {
    return tree.LID[root] <= tree.LID[child] && tree.LID[child] < tree.RID[root]
}
func (tree *Tree) ELID(u int) int {
    return 2*tree.LID[u] - tree.Depth[u]
}
func (tree *Tree) ERID(u int) int {
    return 2*tree.RID[u] - tree.Depth[u] - 1
}
func (tree *Tree) build(cur, pre, dep, dist int) int {
    subSize, heavySize, heavySon := 1, 0, -1
    for _, e := range tree.Tree[cur] {
        next, weight := e[0], e[1]
        if next != pre {
            nextSize := tree.build(next, cur, dep+1, dist+weight)
            subSize += nextSize
            if nextSize > heavySize {
                heavySize, heavySon = nextSize, next
            }
        }
    }
    tree.Depth[cur] = dep
    tree.DepthWeighted[cur] = dist
    tree.heavySon[cur] = heavySon
    tree.Parent[cur] = pre
    return subSize
}
func (tree *Tree) markTop(cur, top int) {
    tree.top[cur] = top
    tree.LID[cur] = tree.timer
    tree.idToNode[tree.timer] = cur
    tree.timer++
    if tree.heavySon[cur] != -1 {
        tree.markTop(tree.heavySon[cur], top)
        for _, e := range tree.Tree[cur] {
            next := e[0]
            if next != tree.heavySon[cur] && next != tree.Parent[cur] {
                tree.markTop(next, next)
            }
        }
    }
    tree.RID[cur] = tree.timer
}
type _LST struct {
    n    int
    size int
    log  int
    data []E
    lazy []Id
    e           func() E
    id          func() Id
    op          func(E, E) E
    mapping     func(Id, E) E
    composition func(Id, Id) Id
    dataUint    E
    lazyUint    Id
}
func _NewLST(
    leaves []E,
    e func() E, id func() Id, op func(E, E) E,
    mapping func(Id, E) E, composition func(Id, Id) Id,
) *_LST {
    tree := &_LST{
        e: e, id: id, op: op, mapping: mapping, composition: composition,
        dataUint: e(), lazyUint: id(),
    }
    n := len(leaves)
    tree.n = n
    tree.log = int(bits.Len(uint(n - 1)))
    tree.size = 1 << tree.log
    tree.data = make([]E, tree.size<<1)
    tree.lazy = make([]Id, tree.size)
    for i := range tree.data {
        tree.data[i] = tree.dataUint
    }
    for i := range tree.lazy {
        tree.lazy[i] = tree.lazyUint
    }
    for i := 0; i < n; i++ {
        tree.data[tree.size+i] = leaves[i]
    }
    for i := tree.size - 1; i >= 1; i-- {
        tree.pushUp(i)
    }
    return tree
}
// 查询切片[left:right]的值
//   0<=left<=right<=len(tree.data)
func (tree *_LST) Query(left, right int) E {
    if left < 0 {
        left = 0
    }
    if right > tree.n {
        right = tree.n
    }
    if left >= right {
        return tree.dataUint
    }
    left += tree.size
    right += tree.size
    for i := tree.log; i >= 1; i-- {
        if ((left >> i) << i) != left {
            tree.pushDown(left >> i)
        }
        if ((right >> i) << i) != right {
            tree.pushDown((right - 1) >> i)
        }
    }
    sml, smr := tree.dataUint, tree.dataUint
    for left < right {
        if left&1 != 0 {
            sml = tree.op(sml, tree.data[left])
            left++
        }
        if right&1 != 0 {
            right--
            smr = tree.op(tree.data[right], smr)
        }
        left >>= 1
        right >>= 1
    }
    return tree.op(sml, smr)
}
func (tree *_LST) QueryAll() E {
    return tree.data[1]
}
// 更新切片[left:right]的值
//   0<=left<=right<=len(tree.data)
func (tree *_LST) Update(left, right int, f Id) {
    if left < 0 {
        left = 0
    }
    if right > tree.n {
        right = tree.n
    }
    if left >= right {
        return
    }
    left += tree.size
    right += tree.size
    for i := tree.log; i >= 1; i-- {
        if ((left >> i) << i) != left {
            tree.pushDown(left >> i)
        }
        if ((right >> i) << i) != right {
            tree.pushDown((right - 1) >> i)
        }
    }
    l2, r2 := left, right
    for left < right {
        if left&1 != 0 {
            tree.propagate(left, f)
            left++
        }
        if right&1 != 0 {
            right--
            tree.propagate(right, f)
        }
        left >>= 1
        right >>= 1
    }
    left = l2
    right = r2
    for i := 1; i <= tree.log; i++ {
        if ((left >> i) << i) != left {
            tree.pushUp(left >> i)
        }
        if ((right >> i) << i) != right {
            tree.pushUp((right - 1) >> i)
        }
    }
}
// 二分查询最小的 left 使得切片 [left:right] 内的值满足 predicate
func (tree *_LST) MinLeft(right int, predicate func(data E) bool) int {
    if right == 0 {
        return 0
    }
    right += tree.size
    for i := tree.log; i >= 1; i-- {
        tree.pushDown((right - 1) >> i)
    }
    res := tree.dataUint
    for {
        right--
        for right > 1 && right&1 != 0 {
            right >>= 1
        }
        if !predicate(tree.op(tree.data[right], res)) {
            for right < tree.size {
                tree.pushDown(right)
                right = right<<1 | 1
                if predicate(tree.op(tree.data[right], res)) {
                    res = tree.op(tree.data[right], res)
                    right--
                }
            }
            return right + 1 - tree.size
        }
        res = tree.op(tree.data[right], res)
        if (right & -right) == right {
            break
        }
    }
    return 0
}
// 二分查询最大的 right 使得切片 [left:right] 内的值满足 predicate
func (tree *_LST) MaxRight(left int, predicate func(data E) bool) int {
    if left == tree.n {
        return tree.n
    }
    left += tree.size
    for i := tree.log; i >= 1; i-- {
        tree.pushDown(left >> i)
    }
    res := tree.dataUint
    for {
        for left&1 == 0 {
            left >>= 1
        }
        if !predicate(tree.op(res, tree.data[left])) {
            for left < tree.size {
                tree.pushDown(left)
                left <<= 1
                if predicate(tree.op(res, tree.data[left])) {
                    res = tree.op(res, tree.data[left])
                    left++
                }
            }
            return left - tree.size
        }
        res = tree.op(res, tree.data[left])
        left++
        if (left & -left) == left {
            break
        }
    }
    return tree.n
}
// 单点查询(不需要 pushUp/op 操作时使用)
func (tree *_LST) Get(index int) E {
    index += tree.size
    for i := tree.log; i >= 1; i-- {
        tree.pushDown(index >> i)
    }
    return tree.data[index]
}
// 单点赋值
func (tree *_LST) Set(index int, e E) {
    index += tree.size
    for i := tree.log; i >= 1; i-- {
        tree.pushDown(index >> i)
    }
    tree.data[index] = e
    for i := 1; i <= tree.log; i++ {
        tree.pushUp(index >> i)
    }
}
func (tree *_LST) pushUp(root int) {
    tree.data[root] = tree.op(tree.data[root<<1], tree.data[root<<1|1])
}
func (tree *_LST) pushDown(root int) {
    if tree.lazy[root] != tree.lazyUint {
        tree.propagate(root<<1, tree.lazy[root])
        tree.propagate(root<<1|1, tree.lazy[root])
        tree.lazy[root] = tree.lazyUint
    }
}
func (tree *_LST) propagate(root int, f Id) {
    tree.data[root] = tree.mapping(f, tree.data[root])
    // !叶子结点不需要更新lazy
    if root < tree.size {
        tree.lazy[root] = tree.composition(f, tree.lazy[root])
    }
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0