結果

問題 No.2295 Union Path Query (Medium)
コンテスト
ユーザー reinsirk
提出日時 2026-11-16 15:03:56
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,212 ms / 4,000 ms
+ 704µs
コード長 33,348 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,568 ms
コンパイル使用メモリ 168,832 KB
実行使用メモリ 225,536 KB
最終ジャッジ日時 2026-11-16 15:04:42
合計ジャッジ時間 41,001 ms
ジャッジサーバーID
(参考情報)
judge3_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#define SKIP_RUNTIME_CHECKS
// Verify: https://yukicoder.me/problems/no/2295
// Submission: https://yukicoder.me/submissions/1199601

// Library: DataStructure/persistent-union-find.cpp
// SPDX-License-Identifier: CC0-1.0
// Original Source: https://nyaannyaan.github.io/library/data-structure/persistent-union-find.hpp.html
// 参考: https://nyaannyaan.github.io/library/data-structure/persistent-array.hpp.html
// ドキュメント: https://github.com/reinsirk/sirkit-cpp-library/blob/main/Document/persistent_union_find.md
//
// API一覧
// [PersistentUnionFind]
// PersistentUnionFind(n=0): n要素の完全永続UF。初期化O(log(n+1))、初期ノード数O(1)。頂点はintの範囲。
// root(i[,version])/leader(i[,version])/find(i[,version]): intの代表頂点、size(i[,version]): 成分サイズ。O(log²(n+1))。
// find_with_size(i[,version]): {代表,負の成分サイズ}。same(a,b[,version])/issame(a,b[,version]): 同一成分か。O(log²(n+1))。
// unite(a,b[,version])/merge(a,b[,version]): 指定版/現在版から結合し新規結合ならtrue。O(log²(n+1))償却時間。
// 結合不要でも指定版が現在版になる。成功1回でO(log(n+1))ノードを追加し全版を保持する。
// Versionは非所有Node*の版ハンドルで、頂点番号ではない。version()で取得して保存し、参照・deleteはしない。
// version(): 現在版のVersion、restore(version): 現在版を選択、size(): 全要素数。O(1)。
// component_count([version]): 成分数、O(n log(n+1))。groups([version]): 成分別頂点昇順一覧、O(n log²(n+1))。
// コピーは保存領域を共有し現在版は独立、移動元は空。ハンドルの寿命はPersistentArrayと同じ。
// arrは互換用公開フィールド。直接更新するとUFの不変条件が壊れるため、操作は上記APIを使う。
//
// [PersistentArray<T,shift>]
// PersistentArray<T,shift=4>(n=0,ID=T{}): [0,n)の初期値ID、O(2^shift + log_(2^shift)(n+1))時間。Tはコピー構築・代入可能。
// PersistentArray(vector,ID): 配列から構築。B=2^shiftとしてO(B+n+(n/B+1)log_B(n+1))時間、O(n+B)領域。
// get(k)/get(version,k): 現在/指定版の値を返す。O(log_(2^shift)(n+1))。
// get_two(a,b)/get_two(version,a,b): 2要素をpair<T,T>で返す。2経路を並行参照、同じ計算量。
// update(k,val)/update(version,k,val): 現在/指定版から分岐して現在版を更新しNode*を返す。
// update_two(a,x,b,y)/update_two(version,a,x,b,y): 2点を同時更新。同じ添字はyを優先しNode*を返す。
// update/update_twoはO(2^shift log_(2^shift)(n+1))償却時間・償却追加領域。size(): 要素数、O(1)。
// restore(version): 現在版を選択。nullptrは全要素IDの版。O(1)。
// rootは現在版の非所有ハンドル。nullptrを指定した版は全要素ID。コピー同士は保存領域を共有し現在版は独立。
// ハンドルは同じ保存領域を所有するインスタンスが残る間有効。移動元は空。全版は最後の所有者と同時に反復解放。
// 別保存領域・寿命切れのハンドルは使用不可。並行更新は外部同期が必要。1<=shift<=8。


// SIRKIT_NAMESPACE_V1: 公開APIはsirkit、既存のgeoはsirkit::geo、内部部品はsirkit::detail。
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <memory>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>


// SIRKIT_NAMESPACE_OPEN_V1
namespace sirkit {
#ifndef SIRKIT_PERSISTENT_ARRAY_DEFINED
#define SIRKIT_PERSISTENT_ARRAY_DEFINED
template<typename T, int shift = 4>
class PersistentArray {
    friend struct PersistentUnionFind;
    static_assert(shift >= 1 && shift <= 8);
    static constexpr std::size_t width = std::size_t{1} << shift;
#if defined(__GNUC__) && !defined(__clang__)
    static constexpr bool compact_nodes = std::is_trivially_copyable_v<T>;
#else
    static constexpr bool compact_nodes = false;
#endif
    struct Storage;
public:
    struct Node {
    private:
        friend class PersistentArray;
        union TrivialContent {
            std::array<Node*, width> children;
            std::array<T, width> values;
            TrivialContent(std::in_place_index_t<0>, std::array<Node*, width> a) : children(a) {}
            TrivialContent(std::in_place_index_t<1>, std::array<T, width> a) : values(a) {}
        };
        using Content = std::conditional_t<compact_nodes, TrivialContent,
                                          std::variant<std::array<Node*, width>, std::array<T, width>>>;
        Content content;
        auto& children() {
            if constexpr (compact_nodes) return content.children;
            else return std::get<0>(content);
        }
        auto& values() {
            if constexpr (compact_nodes) return content.values;
            else return std::get<1>(content);
        }
#ifndef SKIP_RUNTIME_CHECKS
        const Storage* owner;
#endif
        static std::array<T, width> filled(const T& value) {
            return [&value]<std::size_t... I>(std::index_sequence<I...>) {
                return std::array<T, width>{((void)I, value)...};
            }(std::make_index_sequence<width>{});
        }
    public:
        Node(bool leaf, const T& value, const Storage* storage)
            : content(leaf ? decltype(content)(std::in_place_index<1>, filled(value))
                           : decltype(content)(std::in_place_index<0>, std::array<Node*, width>{}))
#ifndef SKIP_RUNTIME_CHECKS
              , owner(storage)
#endif
        { (void)storage; }
        Node(const Node&) = default;
    };
private:
    // 内側vectorの容量内にだけ追加し、全版のNode*を安定させる。
    struct Storage {
        T id;
        std::vector<std::vector<Node>> blocks;
        std::size_t node_count = 0;
        explicit Storage(T value) : id(std::move_if_noexcept(value)) {}
    };
    std::shared_ptr<Storage> storage_;
    std::int64_t size_ = 0;
    int levels_ = 0;
    void check_index(std::int64_t k) const {
#ifndef SKIP_RUNTIME_CHECKS
        if (k < 0 || k >= size_) throw std::out_of_range("PersistentArray: index");
#else
        (void)k;
#endif
    }
    void check_root(Node* n) const {
#ifndef SKIP_RUNTIME_CHECKS
        if (n && n->owner != storage_.get()) throw std::invalid_argument("PersistentArray: foreign version");
#else
        (void)n;
#endif
    }
    Node* allocate(Node* original, bool leaf) {
        if (storage_->node_count == std::numeric_limits<std::size_t>::max())
            throw std::length_error("PersistentArray: node capacity");
        if (storage_->blocks.empty() || storage_->blocks.back().size() == storage_->blocks.back().capacity()) {
            std::vector<Node> block;
            block.reserve(std::min<std::size_t>(512, std::size_t{4} << std::min<std::size_t>(storage_->blocks.size(), 9)));
            storage_->blocks.push_back(std::move(block));
        }
        auto& block = storage_->blocks.back();
        if (original) block.emplace_back(*original);
        else block.emplace_back(leaf, storage_->id, storage_.get());
        ++storage_->node_count;
        return &block.back();
    }
public:
    Node* root = nullptr;
    explicit PersistentArray(std::int64_t n = 0, T id = T{}) {
        if (n < 0) throw std::length_error("PersistentArray: negative size");
        size_ = n;
        std::uint64_t top = n ? static_cast<std::uint64_t>(n - 1) : 0;
        while (top >= width) { ++levels_; top >>= shift; }
        storage_ = std::make_shared<Storage>(std::move_if_noexcept(id)); root = allocate(nullptr, levels_ == 0);
    }
    explicit PersistentArray(const std::vector<T>& values, T id = T{})
        : PersistentArray(vector_size(values), std::move_if_noexcept(id)) {
        // 同じ葉の値は続けて代入し、根から葉までの再走査を減らす。
        for (std::size_t first = 0; first < values.size();) {
            Node* node = root;
            for (int d = levels_; d > 0; --d) {
                auto& next = node->children()[(first >> (d * shift)) & (width - 1)];
                if (!next) next = allocate(nullptr, d == 1);
                node = next;
            }
            const auto count = std::min(width, values.size() - first);
            auto& leaf = node->values();
            for (std::size_t j = 0; j < count; ++j) leaf[j] = values[first + j];
            first += count;
        }
    }
    PersistentArray(const PersistentArray&) = default;
    PersistentArray& operator=(const PersistentArray&) = default;
    PersistentArray(PersistentArray&& other) noexcept
        : storage_(std::move(other.storage_)), size_(std::exchange(other.size_, 0)),
          levels_(std::exchange(other.levels_, 0)), root(std::exchange(other.root, nullptr)) {}
    PersistentArray& operator=(PersistentArray&& other) noexcept {
        if (this != &other) {
            storage_ = std::move(other.storage_); size_ = std::exchange(other.size_, 0);
            levels_ = std::exchange(other.levels_, 0); root = std::exchange(other.root, nullptr);
        }
        return *this;
    }
    void restore(Node* r) { check_root(r); root = r; }
    std::int64_t size() const noexcept { return size_; }
    T get(Node* n, std::int64_t k) const {
        check_index(k); check_root(n); return get_unchecked(n, k);
    }
    T get(std::int64_t k) const { return get(root, k); }
    std::pair<T,T> get_two(Node* base, std::int64_t a, std::int64_t b) const {
        check_index(a); check_index(b); check_root(base);
        return get_two_unchecked(base, a, b);
    }
    std::pair<T,T> get_two(std::int64_t a, std::int64_t b) const { return get_two(root, a, b); }
    Node* update(Node* base, std::int64_t k, const T& value) {
        check_index(k); check_root(base);
        std::array<Node*, 64> path;
        std::array<std::size_t, 64> slots;
        const auto index = static_cast<std::uint64_t>(k);
        Node* n = base;
        for (int d = levels_; d > 0; --d) {
            const auto slot = (index >> (d * shift)) & (width - 1);
            path[d] = n; slots[d] = slot;
            n = n ? n->children()[slot] : nullptr;
        }
        Node* result = allocate(n, true);
        result->values()[index & (width - 1)] = value;
        for (int d = 1; d <= levels_; ++d) {
            Node* parent = allocate(path[d], false);
            parent->children()[slots[d]] = result; result = parent;
        }
        return root = result;
    }
    Node* update(std::int64_t k, const T& value) { return update(root, k, value); }
    Node* update_two(Node* base, std::int64_t a, const T& x, std::int64_t b, const T& y) {
        check_index(a); check_index(b); check_root(base);
        return root = update_two(base, static_cast<std::uint64_t>(a), x,
                                 static_cast<std::uint64_t>(b), y, levels_);
    }
    Node* update_two(std::int64_t a, const T& x, std::int64_t b, const T& y) {
        return update_two(root, a, x, b, y);
    }
private:
    Node* update_one(Node* base, std::uint64_t index, const T& value, int level) {
        Node* result = allocate(base, level == 0);
        Node* current = result;
        for (int d = level; d > 0; --d) {
            auto& child = current->children()[(index >> (d * shift)) & (width - 1)];
            child = allocate(child, d == 1);
            current = child;
        }
        current->values()[index & (width - 1)] = value;
        return result;
    }
    // 共通経路は一度だけ複製する。変更は全て新規ノード内で、rootは呼出元が最後に公開。
    Node* update_two(Node* base, std::uint64_t a, const T& x, std::uint64_t b, const T& y, int level) {
        Node* result = allocate(base, level == 0);
        Node* current = result;
        for (int d = level; d > 0; --d) {
            const auto sa = (a >> (d * shift)) & (width - 1);
            const auto sb = (b >> (d * shift)) & (width - 1);
            auto& children = current->children();
            if (sa != sb) {
                children[sa] = update_one(children[sa], a, x, d - 1);
                children[sb] = update_one(children[sb], b, y, d - 1);
                return result;
            }
            children[sa] = allocate(children[sa], d == 1);
            current = children[sa];
        }
        auto& values = current->values();
        values[a & (width - 1)] = x;
        values[b & (width - 1)] = y;
        return result;
    }
    T get_existing(Node* n, std::int64_t k) const {
        const auto index = static_cast<std::uint64_t>(k);
        for (int d = levels_; d > 0; --d)
            n = n->children()[(index >> (d * shift)) & (width - 1)];
        return n->values()[index & (width - 1)];
    }
    T get_unchecked(Node* n, std::int64_t k) const {
        const auto index = static_cast<std::uint64_t>(k);
        for (int d = levels_; d > 0; --d) {
            if (!n) return storage_->id;
            n = n->children()[(index >> (d * shift)) & (width - 1)];
        }
        return n ? n->values()[index & (width - 1)] : storage_->id;
    }
    // 独立な2本の参照を同じ反復で進める。
    std::pair<T,T> get_two_unchecked(Node* n, std::int64_t a, std::int64_t b) const {
        Node* left = n;
        Node* right = n;
        const auto ia = static_cast<std::uint64_t>(a);
        const auto ib = static_cast<std::uint64_t>(b);
        for (int d = levels_; d > 0; --d) {
            if (left) left = left->children()[(ia >> (d * shift)) & (width - 1)];
            if (right) right = right->children()[(ib >> (d * shift)) & (width - 1)];
        }
        return {left ? left->values()[ia & (width - 1)] : storage_->id,
                right ? right->values()[ib & (width - 1)] : storage_->id};
    }
    // UFの親番号は同じ版で明示更新済みなので、祖先の配列経路は必ず存在する。
    std::pair<T,T> get_two_existing(Node* n, std::int64_t a, std::int64_t b) const {
        Node* left = n; Node* right = n;
        const auto ia = static_cast<std::uint64_t>(a), ib = static_cast<std::uint64_t>(b);
        for (int d = levels_; d > 0; --d) {
            left = left->children()[(ia >> (d * shift)) & (width - 1)];
            right = right->children()[(ib >> (d * shift)) & (width - 1)];
        }
        return {left->values()[ia & (width - 1)], right->values()[ib & (width - 1)]};
    }
    static std::int64_t vector_size(const std::vector<T>& values) {
        if (values.size() > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
            throw std::length_error("PersistentArray: size overflow");
        return static_cast<std::int64_t>(values.size());
    }
};
#endif

#ifndef SIRKIT_PERSISTENT_UNION_FIND_DEFINED
#define SIRKIT_PERSISTENT_UNION_FIND_DEFINED
struct PersistentUnionFind {
    using Node = PersistentArray<int>::Node;
    using Version = Node*;
    PersistentArray<int> arr;
private:
    Version version_ = nullptr;
public:
    explicit PersistentUnionFind(std::size_t n = 0) : arr(checked_size(n), -1), version_(arr.root) {}
    PersistentUnionFind(const PersistentUnionFind&) = default;
    PersistentUnionFind& operator=(const PersistentUnionFind&) = default;
    PersistentUnionFind(PersistentUnionFind&& other) noexcept
        : arr(std::move(other.arr)), version_(std::exchange(other.version_, nullptr)) {}
    PersistentUnionFind& operator=(PersistentUnionFind&& other) noexcept {
        if (this != &other) { arr = std::move(other.arr); version_ = std::exchange(other.version_, nullptr); }
        return *this;
    }
    int size() const noexcept { return static_cast<int>(arr.size()); }
    std::pair<int,int> find_with_size(int i, Version r) const {
        check_version(r); arr.check_index(i);
        int value = arr.get_unchecked(r, i);
        while (value >= 0) { i = value; value = arr.get_existing(r, i); }
        return {i, value};
    }
    std::pair<int,int> find_with_size(int i) const { return find_with_size(i, version_); }
    int find(int i, Version r) const { return find_with_size(i, r).first; }
    int find(int i) const { return find(i, version_); }
    int leader(int i, Version r) const { return find(i, r); }
    int leader(int i) const { return find(i); }
    int root(int i, Version r) const { return find(i, r); }
    int root(int i) const { return find(i); }
    int size(int i, Version r) const { return -find_with_size(i, r).second; }
    int size(int i) const { return size(i, version_); }
    bool same(int i, int j, Version r) const {
        check_version(r); arr.check_index(i); arr.check_index(j);
        if (i == j) return true;
        auto [a, b] = arr.get_two_unchecked(r, i, j);
        // 代表まで上らず、同じ頂点へ到達した時点で連結と分かる。
        while (a >= 0 && b >= 0) {
            i = a; j = b;
            if (i == j) return true;
            const auto values = arr.get_two_existing(r, i, j);
            a = values.first; b = values.second;
        }
        while (a >= 0) { i = a; if (i == j) return true; a = arr.get_existing(r, i); }
        while (b >= 0) { j = b; if (i == j) return true; b = arr.get_existing(r, j); }
        return i == j;
    }
    bool same(int i, int j) const { return same(i, j, version_); }
    bool issame(int i, int j, Version r) const { return same(i, j, r); }
    bool issame(int i, int j) const { return same(i, j); }
    bool unite(int i, int j, Version r) {
        const auto values = find_pair(i, j, r);
        auto [a, sa] = values.first; auto [b, sb] = values.second;
        if (a == b) { version_ = arr.root = r; return false; }
        if (sa > sb) { std::swap(a, b); std::swap(sa, sb); }
        r = arr.update_two(r, static_cast<std::uint64_t>(a), sa + sb,
                           static_cast<std::uint64_t>(b), a, arr.levels_);
        version_ = arr.root = r; return true;
    }
    bool unite(int i, int j) { return unite(i, j, version_); }
    bool merge(int i, int j, Version r) { return unite(i, j, r); }
    bool merge(int i, int j) { return unite(i, j); }
    Version version() const noexcept { return version_; }
    void restore(Version r) { check_version(r); arr.restore(r); version_ = r; }
    int component_count(Version r) const {
        check_version(r);
        int count = 0; for (int i = 0; i < size(); ++i) count += arr.get_unchecked(r, i) < 0; return count;
    }
    int component_count() const { return component_count(version_); }
    std::vector<std::vector<int>> groups(Version r) const {
        check_version(r);
        std::vector<int> leaders(size()), count(size(), 0), slot(size());
        if constexpr (PersistentArray<int>::compact_nodes) {
            for (int i = 0; i < size(); ++i) ++count[leaders[i] = leader_existing_parents(i, r)];
        } else {
            for (int i = 0; i < size(); ++i) ++count[leaders[i] = find(i, r)];
        }
        std::vector<std::vector<int>> result;
        for (int i = 0; i < size(); ++i) if (count[i]) {
            slot[i] = static_cast<int>(result.size()); result.emplace_back(); result.back().reserve(count[i]);
        }
        for (int i = 0; i < size(); ++i) result[slot[leaders[i]]].push_back(i);
        return result;
    }
    std::vector<std::vector<int>> groups() const { return groups(version_); }
private:
    // groupsで版・添字を確かめた後に使う。親の配列経路は同じ版で明示更新済み。
    int leader_existing_parents(int i, Version r) const {
        int value = arr.get_unchecked(r, i);
        while (value >= 0) { i = value; value = arr.get_existing(r, i); }
        return i;
    }
    void check_version(Version r) const {
#ifndef SKIP_RUNTIME_CHECKS
        if (!r && size() != 0) throw std::invalid_argument("PersistentUnionFind: null version");
        arr.check_root(r);
#else
        (void)r;
#endif
    }
    std::pair<std::pair<int,int>, std::pair<int,int>> find_pair(int i, int j, Version r) const {
        check_version(r); arr.check_index(i); arr.check_index(j);
        auto [a, b] = arr.get_two_unchecked(r, i, j);
        while (a >= 0 && b >= 0) {
            i = a; j = b;
            const auto values = arr.get_two_existing(r, i, j);
            a = values.first; b = values.second;
        }
        while (a >= 0) { i = a; a = arr.get_existing(r, i); }
        while (b >= 0) { j = b; b = arr.get_existing(r, j); }
        return {{i, a}, {j, b}};
    }
    static std::int64_t checked_size(std::size_t n) {
        if (n > static_cast<std::size_t>(std::numeric_limits<int>::max()))
            throw std::length_error("PersistentUnionFind: too many vertices");
        return static_cast<std::int64_t>(n);
    }
};
#endif

} // namespace sirkit
// SIRKIT_NAMESPACE_CLOSE_V1
// SIRKIT_NAMESPACE_END_V1


namespace sirkit {}
using namespace sirkit;

// SPDX-License-Identifier: CC0-1.0
// Verify I/O: Verify/current/common/fast_io.hpp
// SPDX-License-Identifier: CC0-1.0
#include <algorithm>
#include <array>
#include <charconv>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <limits>
#include <stdexcept>
#include <string>
#include <string_view>
#include <type_traits>
#include <vector>

#ifndef SIRKIT_VERIFY_FAST_IO_DEFINED
#define SIRKIT_VERIFY_FAST_IO_DEFINED

// VerifyInput(file=stdin): 非所有のFILEから読む。別の入力方式と混用しない。
// >> 整数: 64bit以下の十進整数を読む。検査省略時は値域内の正しい入力を前提とする。
// >> char/string: 空白を飛ばし、1文字/空白までの文字列を読む。
// >> 浮動小数点: 十進文字列を変換する。通常のCロケールで使う。
// bool / !: 直前までの読み取りが成功しているか/失敗したかを返す。
class VerifyInput {
    static constexpr std::size_t buffer_size = 1 << 17;
    std::FILE* file_;
    std::array<unsigned char, buffer_size + 1> buffer_;
    std::size_t position_ = 0, size_ = 0;
    bool good_ = true;

    int peek() {
        if (position_ == size_) {
            size_ = std::fread(buffer_.data(), 1, buffer_size, file_);
            buffer_[size_] = 0; // 補充後の末尾は常に数字でない番兵。
            position_ = 0;
            if (size_ == 0) return EOF;
        }
        return buffer_[position_];
    }

    int skip_space() {
        int c;
        while ((c = peek()) != EOF && c <= ' ') ++position_;
        if (c == EOF) good_ = false;
        return c;
    }

public:
    explicit VerifyInput(std::FILE* file = stdin) : file_(file) {}
    VerifyInput(const VerifyInput&) = delete;
    VerifyInput& operator=(const VerifyInput&) = delete;

    explicit operator bool() const noexcept { return good_; }
    bool operator!() const noexcept { return !good_; }

    template<class T>
        requires (std::is_integral_v<T> && sizeof(T) <= sizeof(std::uint64_t)
                  && !std::is_same_v<T, char>)
    VerifyInput& operator>>(T& result) {
        if (!good_) return *this;
        int c = skip_space();
        if (c == EOF) return *this;
        bool negative = false;
        if (c == '-' || c == '+') {
            negative = c == '-';
            ++position_;
            c = peek();
        }
        if (c == EOF) {
            good_ = false;
            return *this;
        }
#ifndef SKIP_RUNTIME_CHECKS
        if (c < '0' || c > '9') {
            good_ = false;
            return *this;
        }
        // 先頭の0を除けば、20桁以下の末尾直前の値はuint64_tに収まる。
        while (c == '0') {
            ++position_;
            c = peek();
        }
        std::uint64_t previous = 0;
        unsigned last_digit = 0;
        std::size_t digits = 0;
#endif
        std::uint64_t value = 0;
#ifdef SKIP_RUNTIME_CHECKS
        // バッファ末尾の番兵で内側の範囲判定を省き、数字が境界をまたぐときだけ補充する。
        for (;;) {
            const unsigned char* first = buffer_.data() + position_;
            const unsigned char* cursor = first;
            while (static_cast<unsigned>(*cursor - '0') < 10) {
                value = value * 10 + static_cast<unsigned>(*cursor - '0');
                ++cursor;
            }
            position_ += static_cast<std::size_t>(cursor - first);
            if (position_ != size_) break;
            c = peek();
            if (c == EOF) break;
        }
#else
        while (c >= '0' && c <= '9') {
            previous = value;
            last_digit = static_cast<unsigned>(c - '0');
            if (digits <= 20) ++digits;
            value = value * 10 + static_cast<unsigned>(c - '0');
            ++position_;
            c = peek();
        }
#endif
#ifndef SKIP_RUNTIME_CHECKS
        constexpr auto maximum = std::numeric_limits<std::uint64_t>::max();
        if ((c != EOF && c > ' ') || digits > 20
            || (digits == 20 && (previous > maximum / 10
                || (previous == maximum / 10 && last_digit > maximum % 10)))) {
            good_ = false;
            return *this;
        }
        std::uint64_t limit = static_cast<std::uint64_t>(std::numeric_limits<T>::max());
        if constexpr (std::is_signed_v<T>) limit += negative;
        else if (negative && value != 0) good_ = false;
        if (value > limit) good_ = false;
        if (!good_) return *this;
#endif
        if constexpr (std::is_signed_v<T>) {
            constexpr std::uint64_t minimum_magnitude =
                static_cast<std::uint64_t>(std::numeric_limits<T>::max()) + 1;
            // -(最小値)は評価せず、絶対値が最大値+1のときだけ最小値を使う。
            result = negative
                ? (value == minimum_magnitude ? std::numeric_limits<T>::min()
                                  : static_cast<T>(-static_cast<T>(value)))
                : static_cast<T>(value);
        } else result = static_cast<T>(value);
        return *this;
    }

    VerifyInput& operator>>(char& result) {
        if (!good_) return *this;
        const int c = skip_space();
        if (c != EOF) {
            result = static_cast<char>(c);
            ++position_;
        }
        return *this;
    }

    VerifyInput& operator>>(std::string& result) {
        if (!good_) return *this;
        int c = skip_space();
        if (c == EOF) return *this;
        result.clear();
        for (;;) {
            const std::size_t first = position_;
            while (position_ < size_ && buffer_[position_] > ' ') ++position_;
            result.append(reinterpret_cast<const char*>(buffer_.data() + first), position_ - first);
            if (position_ != size_ || peek() == EOF) break;
        }
        return *this;
    }

    template<class T> requires std::is_floating_point_v<T>
    VerifyInput& operator>>(T& result) {
        std::string token;
        *this >> token;
        if (!good_) return *this;
#ifndef SKIP_RUNTIME_CHECKS
        char* end = nullptr;
        const long double value = std::strtold(token.c_str(), &end);
        if (end != token.c_str() + token.size()) good_ = false;
        else result = static_cast<T>(value);
#else
        result = static_cast<T>(std::strtold(token.c_str(), nullptr));
#endif
        return *this;
    }
};

// VerifyOutput(file=stdout): 非所有のFILEへ書く。破棄時にflushし、FILEは閉じない。
// << 整数/char/文字列/浮動小数点: 値を出力する。整数は64bit以下に対応する。
// fixed(digits): 浮動小数点を小数点以下digits桁で出力する(digits>=0)。
// flush(): バッファの内容をFILEへ渡す。bool / !で書き込み失敗を確認できる。
class VerifyOutput {
    static constexpr std::size_t buffer_size = 1 << 17;
    std::FILE* file_;
    std::array<char, buffer_size> buffer_;
    std::size_t size_ = 0;
    int precision_ = 6;
    bool fixed_ = false, good_ = true;

    void write(std::string_view text) {
        while (!text.empty() && good_) {
            if (size_ == buffer_.size()) flush();
            const auto count = std::min(text.size(), buffer_.size() - size_);
            std::memcpy(buffer_.data() + size_, text.data(), count);
            size_ += count;
            text.remove_prefix(count);
        }
    }

public:
    explicit VerifyOutput(std::FILE* file = stdout) : file_(file) {}
    VerifyOutput(const VerifyOutput&) = delete;
    VerifyOutput& operator=(const VerifyOutput&) = delete;
    ~VerifyOutput() { flush(); }

    explicit operator bool() const noexcept { return good_; }
    bool operator!() const noexcept { return !good_; }

    VerifyOutput& fixed(int digits) {
        if (digits < 0) throw std::invalid_argument("negative output precision");
        fixed_ = true;
        precision_ = digits;
        return *this;
    }

    void flush() noexcept {
        std::size_t written = 0;
        while (written < size_ && good_) {
            const auto count = std::fwrite(buffer_.data() + written, 1, size_ - written, file_);
            if (count == 0) good_ = false;
            written += count;
        }
        size_ = 0;
    }

    template<class T>
        requires (std::is_integral_v<T> && sizeof(T) <= sizeof(std::uint64_t)
                  && !std::is_same_v<T, char>)
    VerifyOutput& operator<<(T value) {
        if constexpr (std::is_same_v<T, bool>) return *this << static_cast<char>('0' + value);
        else {
            constexpr std::size_t capacity = std::numeric_limits<std::uint64_t>::digits10 + 3;
            if (buffer_.size() - size_ < capacity) flush();
            if (!good_) return *this;
            const auto end = std::to_chars(buffer_.data() + size_, buffer_.data() + size_ + capacity, value).ptr;
            size_ = static_cast<std::size_t>(end - buffer_.data());
            return *this;
        }
    }

    VerifyOutput& operator<<(char value) {
        if (size_ == buffer_.size()) flush();
        if (good_) buffer_[size_++] = value;
        return *this;
    }

    VerifyOutput& operator<<(std::string_view value) { write(value); return *this; }
    VerifyOutput& operator<<(const std::string& value) { write(value); return *this; }
    VerifyOutput& operator<<(const char* value) { write(value); return *this; }

    template<class T> requires std::is_floating_point_v<T>
    VerifyOutput& operator<<(T value) {
        char local[128];
        const char* format = fixed_ ? "%.*Lf" : "%.*Lg";
        const int count = std::snprintf(local, sizeof(local), format, precision_,
                                        static_cast<long double>(value));
        if (count < 0) good_ = false;
        else if (static_cast<std::size_t>(count) < sizeof(local))
            write(std::string_view(local, static_cast<std::size_t>(count)));
        else {
            std::vector<char> text(static_cast<std::size_t>(count) + 1);
            std::snprintf(text.data(), text.size(), format, precision_, static_cast<long double>(value));
            write(std::string_view(text.data(), static_cast<std::size_t>(count)));
        }
        return *this;
    }
};

inline VerifyInput verify_in;
inline VerifyOutput verify_out;
#endif

#include <cstddef>
#include <cstdint>
#include <vector>

int main() {
    constexpr std::int64_t mod = 998244353;
    int n{}, x{}, q{};
    verify_in >> n >> x >> q;
    PersistentUnionFind uf(n);
    std::vector<PersistentUnionFind::Version> versions{uf.version()};
    std::vector<std::int64_t> weights{0}, component_sum(n);
    versions.reserve(n);
    weights.reserve(n);
    while (q--) {
        int type{};
        verify_in >> type;
        if (type == 1) {
            int v{};
            std::int64_t weight{};
            verify_in >> v >> weight;
            const int left = uf.root(x), right = uf.root(v);
            if (left == right) continue;
            const std::int64_t left_size = uf.size(left), right_size = uf.size(right);
            const auto cross_sum = (weight % mod) * left_size % mod * right_size % mod;
            const auto merged_sum = (component_sum[left] + component_sum[right] + cross_sum) % mod;
            if (uf.unite(x, v)) {
                component_sum[uf.root(x)] = merged_sum;
                versions.push_back(uf.version());
                weights.push_back(weight);
            }
        } else if (type == 2) {
            int u{}, v{};
            verify_in >> u >> v;
            if (!uf.issame(u, v)) {
                verify_out << -1 << '\n';
                continue;
            }
            std::int64_t answer = 0;
            if (u != v) {
                std::size_t low = 0, high = versions.size() - 1;
                while (high - low > 1) {
                    const auto middle = low + (high - low) / 2;
                    if (uf.issame(u, v, versions[middle])) high = middle;
                    else low = middle;
                }
                answer = weights[high];
            }
            verify_out << answer << '\n';
            x = static_cast<int>((static_cast<std::int64_t>(x) + answer) % n);
        } else if (type == 3) {
            int v{};
            verify_in >> v;
            verify_out << component_sum[uf.root(v)] << '\n';
        } else {
            int value{};
            verify_in >> value;
            x = (x + value) % n;
        }
    }
}
0