// [TEMPLATE_BEGIN]
#include <bits/stdc++.h>

#include <cassert>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
#if defined(__unix__) || defined(__APPLE__)
#include <unistd.h>
#endif

std::istream& operator>>(std::istream& is, __int128& x);

namespace input_detail {

#ifdef LOCAL

inline std::size_t& read_count() {
    static std::size_t count = 0;
    return count;
}

inline bool& failed_read() {
    static bool failed = false;
    return failed;
}

inline bool stdin_is_terminal() {
#if defined(__unix__) || defined(__APPLE__)
    return isatty(fileno(stdin));
#else
    return false;
#endif
}

struct EndOfInputChecker {
    ~EndOfInputChecker() {
        if (stdin_is_terminal()) return;
        if (failed_read() || std::cin.bad()) return;

        std::cin >> std::ws;
        std::string token;
        if (std::cin >> token) {
            std::cerr << "[input error] 入力が余っています。\n"
                      << "  すべての読み込みが終わったあとに、まだ入力が残っています。\n"
                      << "  最初に余った値: " << token << '\n'
                      << "  確認ポイント: N と M、H と W、辺数 m、配列長 n などを取り違えていないか見てください。\n";
            std::abort();
        }
    }
};

inline void ensure_end_checker() {
    static EndOfInputChecker checker;
    (void)checker;
}

template <typename T>
inline void read_one(T& x) {
    ensure_end_checker();
    ++read_count();
    if (!(std::cin >> x)) {
        failed_read() = true;
        std::cerr << "[input error] 入力が足りません。\n"
                  << "  " << read_count() << " 個目の値を読もうとしましたが、読み込めませんでした。\n"
                  << "  確認ポイント: N と M、H と W、辺数 m、配列長 n などを取り違えていないか見てください。\n"
                  << "  文字列を数値として読むなど、型が合っていない場合もここで止まります。\n";
        std::abort();
    }
}

#else

template <typename T>
inline void read_one(T& x) {
    std::cin >> x;
}

#endif

template <typename... Ts>
inline void scan_values(Ts&... args) {
    (read_one(args), ...);
}

inline int safe_nonneg_int(int x) {
    assert(x >= 0);
    return x < 0 ? 0 : x;
}

inline bool in_vertex_range(int v, int n) {
    return 0 <= v && v < n;
}

}  // namespace input_detail

// ==================== 単一値・基本入力 ====================

/**
 * @brief 標準入出力の高速化を行う。main関数の最初で呼ぶことを推奨。
 */
inline void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

/**
 * @brief 任意の数の変数を標準入力から読み込む
 * @tparam Ts 引数の型パック
 * @param args 読み込み先の変数
 */
template <typename... Ts>
inline void scan(Ts&... args) {
    input_detail::scan_values(args...);
}

/**
 * @brief 単一の値を標準入力から読み込む
 * @tparam T 読み込む値の型 (デフォルト: long long)
 * @return 読み込んだ値
 */
template <typename T = long long>
inline T read() {
    T x;
    input_detail::read_one(x);
    return x;
}

// ==================== ベクター入力 ====================

/**
 * @brief 入力補助関数の前提
 *
 * - サイズ引数 (n, m, h, w) は 0 以上を想定。
 *   負値は `assert` で検知し、実行継続時は 0 扱い。
 * - グラフの頂点番号は `base` 減算後に `[0, n)` を想定。
 *   範囲外は `assert` で検知し、実行継続時はその辺を無視。
 */

/**
 * @brief 1次元ベクターを標準入力から読み込む（算術型用、offset 付き）
 * @tparam T 要素の型 (デフォルト: long long)
 * @param n 要素数
 * @param offset 読み込み時に引く値 (デフォルト: 0)
 * @return 読み込んだベクター
 */
template <typename T = long long>
    requires std::is_arithmetic_v<T>
inline std::vector<T> read_vec(int n, T offset = 0) {
    const int sz = input_detail::safe_nonneg_int(n);
    std::vector<T> v(sz);
    for (auto& x : v) {
        input_detail::read_one(x);
        x -= offset;
    }
    return v;
}

/**
 * @brief 1次元ベクターを標準入力から読み込む（非算術型用）
 * @tparam T 要素の型
 * @param n 要素数
 * @return 読み込んだベクター
 */
template <typename T>
    requires(!std::is_arithmetic_v<T>)
inline std::vector<T> read_vec(int n) {
    const int sz = input_detail::safe_nonneg_int(n);
    std::vector<T> v(sz);
    for (auto& x : v) {
        input_detail::read_one(x);
    }
    return v;
}

/**
 * @brief 要素数 n と 1次元ベクターをまとめて標準入力から読み込む（算術型用、offset 付き）
 * @tparam T 要素の型 (デフォルト: long long)
 * @param offset 読み込み時に引く値 (デフォルト: 0)
 * @return {要素数, 読み込んだベクター}
 *
 * 使い方:
 *   auto [n, a] = read_vec_with_size<long long>();
 */
template <typename T = long long>
    requires std::is_arithmetic_v<T>
inline std::pair<int, std::vector<T>> read_vec_with_size(T offset = 0) {
    int n;
    input_detail::read_one(n);
    return {n, read_vec<T>(n, offset)};
}

/**
 * @brief 要素数 n と 1次元ベクターをまとめて標準入力から読み込む（非算術型用）
 * @tparam T 要素の型
 * @return {要素数, 読み込んだベクター}
 *
 * 使い方:
 *   auto [n, s] = read_vec_with_size<std::string>();
 */
template <typename T>
    requires(!std::is_arithmetic_v<T>)
inline std::pair<int, std::vector<T>> read_vec_with_size() {
    int n;
    input_detail::read_one(n);
    return {n, read_vec<T>(n)};
}

/**
 * @brief 2次元ベクターを標準入力から読み込む（算術型用、offset 付き）
 * @tparam T 要素の型 (デフォルト: long long)
 * @param h 行数
 * @param w 列数
 * @param offset 読み込み時に引く値 (デフォルト: 0)
 * @return 読み込んだ h×w の2次元ベクター
 */
template <typename T = long long>
    requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_vec2(int h, int w, T offset = 0) {
    const int hh = input_detail::safe_nonneg_int(h);
    const int ww = input_detail::safe_nonneg_int(w);
    std::vector<std::vector<T>> v(hh, std::vector<T>(ww));
    for (auto& row : v) {
        for (auto& x : row) {
            input_detail::read_one(x);
            x -= offset;
        }
    }
    return v;
}

/**
 * @brief 2次元ベクターを標準入力から読み込む（非算術型用）
 * @tparam T 要素の型
 * @param h 行数
 * @param w 列数
 * @return 読み込んだ h×w の2次元ベクター
 */
template <typename T>
    requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_vec2(int h, int w) {
    const int hh = input_detail::safe_nonneg_int(h);
    const int ww = input_detail::safe_nonneg_int(w);
    std::vector<std::vector<T>> v(hh, std::vector<T>(ww));
    for (auto& row : v) {
        for (auto& x : row) {
            input_detail::read_one(x);
        }
    }
    return v;
}

/**
 * @brief 各行の最初に要素数が与えられる可変長2次元ベクターを標準入力から読み込む（算術型用、offset 付き）
 * @tparam T 要素の型 (デフォルト: long long)
 * @param h 行数
 * @param offset 読み込み時に引く値 (デフォルト: 0)
 * @return 読み込んだ可変長の2次元ベクター
 */
template <typename T = long long>
    requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_vec2_var(int h, T offset = 0) {
    const int hh = input_detail::safe_nonneg_int(h);
    std::vector<std::vector<T>> v(hh);
    for (auto& row : v) {
        int m;
        input_detail::read_one(m);
        row = read_vec<T>(m, offset);
    }
    return v;
}

/**
 * @brief 各行の最初に要素数が与えられる可変長2次元ベクターを標準入力から読み込む（非算術型用）
 * @tparam T 要素の型
 * @param h 行数
 * @return 読み込んだ可変長の2次元ベクター
 */
template <typename T>
    requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_vec2_var(int h) {
    const int hh = input_detail::safe_nonneg_int(h);
    std::vector<std::vector<T>> v(hh);
    for (auto& row : v) {
        int m;
        input_detail::read_one(m);
        row = read_vec<T>(m);
    }
    return v;
}

/**
 * @brief 1次元のペアのベクターを標準入力から読み込む
 * @tparam T1 ペアの1つ目の要素の型 (デフォルト: long long)
 * @tparam T2 ペアの2つ目の要素の型 (デフォルト: long long)
 * @param n 要素数
 * @param offset1 1つ目の要素から引く値 (デフォルト: 0)
 * @param offset2 2つ目の要素から引く値 (デフォルト: 0)
 * @return 読み込んだペアのベクター
 */
template <typename T1 = long long, typename T2 = long long>
inline std::vector<std::pair<T1, T2>> read_vec_pair(int n, T1 offset1 = 0, T2 offset2 = 0) {
    const int sz = input_detail::safe_nonneg_int(n);
    std::vector<std::pair<T1, T2>> v(sz);
    for (auto& [x, y] : v) {
        input_detail::scan_values(x, y);
        x -= offset1;
        y -= offset2;
    }
    return v;
}

// ==================== 行列・三角形入力 ====================

/**
 * @brief 上三角行列形式の入力を読み込み、2次元ベクターとして返す（算術型用、offset 付き）
 * @tparam T 要素の型 (デフォルト: long long)
 * @param n 行列のサイズ (n x n)
 * @param symmetric 対称行列にするかどうか (デフォルト: true)
 * @param offset 読み込み時に値から引く量 (デフォルト: 0)
 * @return 読み込んだ 2次元ベクター
 */
template <typename T = long long>
    requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_upper_tri(int n, bool symmetric = true, T offset = 0) {
    const int sz = input_detail::safe_nonneg_int(n);
    std::vector<std::vector<T>> v(sz, std::vector<T>(sz));
    for (int i = 0; i < sz - 1; ++i) {
        for (int j = i + 1; j < sz; ++j) {
            input_detail::read_one(v[i][j]);
            v[i][j] -= offset;
            if (symmetric) v[j][i] = v[i][j];
        }
    }
    return v;
}

/**
 * @brief 上三角行列形式の入力を読み込み、2次元ベクターとして返す（非算術型用）
 * @tparam T 要素の型
 * @param n 行列のサイズ (n x n)
 * @param symmetric 対称行列にするかどうか (デフォルト: true)
 * @return 読み込んだ 2次元ベクター
 */
template <typename T>
    requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_upper_tri(int n, bool symmetric = true) {
    const int sz = input_detail::safe_nonneg_int(n);
    std::vector<std::vector<T>> v(sz, std::vector<T>(sz));
    for (int i = 0; i < sz - 1; ++i) {
        for (int j = i + 1; j < sz; ++j) {
            input_detail::read_one(v[i][j]);
            if (symmetric) v[j][i] = v[i][j];
        }
    }
    return v;
}

/**
 * @brief 下三角行列形式の入力を読み込み、2次元ベクターとして返す（算術型用、offset 付き）
 * @tparam T 要素の型 (デフォルト: long long)
 * @param n 行列のサイズ (n x n)
 * @param symmetric 対称行列にするかどうか (デフォルト: true)
 * @param offset 読み込み時に値から引く量 (デフォルト: 0)
 * @return 読み込んだ 2次元ベクター
 */
template <typename T = long long>
    requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_lower_tri(int n, bool symmetric = true, T offset = 0) {
    const int sz = input_detail::safe_nonneg_int(n);
    std::vector<std::vector<T>> v(sz, std::vector<T>(sz));
    for (int i = 1; i < sz; ++i) {
        for (int j = 0; j < i; ++j) {
            input_detail::read_one(v[i][j]);
            v[i][j] -= offset;
            if (symmetric) v[j][i] = v[i][j];
        }
    }
    return v;
}

/**
 * @brief 下三角行列形式の入力を読み込み、2次元ベクターとして返す（非算術型用）
 * @tparam T 要素の型
 * @param n 行列のサイズ (n x n)
 * @param symmetric 対称行列にするかどうか (デフォルト: true)
 * @return 読み込んだ 2次元ベクター
 */
template <typename T>
    requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_lower_tri(int n, bool symmetric = true) {
    const int sz = input_detail::safe_nonneg_int(n);
    std::vector<std::vector<T>> v(sz, std::vector<T>(sz));
    for (int i = 1; i < sz; ++i) {
        for (int j = 0; j < i; ++j) {
            input_detail::read_one(v[i][j]);
            if (symmetric) v[j][i] = v[i][j];
        }
    }
    return v;
}

// ==================== タプル入力 ====================

namespace detail {

/**
 * @brief タプルの各要素を順番に読み込む（内部実装）
 * @tparam Tuple タプル型
 * @tparam Is インデックスのパック
 * @param t 読み込み先のタプル
 */
template <typename Tuple, std::size_t... Is>
inline void read_tuple_impl(Tuple& t, std::index_sequence<Is...>) {
    input_detail::scan_values(std::get<Is>(t)...);
}

}  // namespace detail

/**
 * @brief 複数の型の値をまとめてタプルとして読み込む
 * @tparam Ts 読み込む型のパック
 * @return 読み込んだ値を格納した std::tuple<Ts...>
 *
 * 使い方:
 *   auto [a, b, c] = read_tuple<int, long long, std::string>();
 */
template <typename... Ts>
inline std::tuple<Ts...> read_tuple() {
    std::tuple<Ts...> t;
    detail::read_tuple_impl(t, std::index_sequence_for<Ts...>{});
    return t;
}

/**
 * @brief n 行分のタプルをベクターとして読み込む
 * @tparam Ts 各行の型のパック
 * @param n 行数
 * @return 読み込んだ std::tuple<Ts...> の std::vector
 *
 * 使い方:
 *   auto v = read_vec_tuple<int, int, long long>(n);
 *   auto [a, b, c] = v[i];
 */
template <typename... Ts>
inline std::vector<std::tuple<Ts...>> read_vec_tuple(int n) {
    const int sz = input_detail::safe_nonneg_int(n);
    std::vector<std::tuple<Ts...>> v(sz);
    for (auto& t : v)
        detail::read_tuple_impl(t, std::index_sequence_for<Ts...>{});
    return v;
}

// ==================== グラフ入力 ====================

/**
 * @brief 無向グラフを辺リストから隣接リスト形式で読み込む
 * @param n 頂点数
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト (vector<vector<int>>)
 *
 * 使い方:
 *   auto g = read_graph(n, m, 1); // 1-indexed 入力
 */
inline std::vector<std::vector<int>> read_graph(int n, int m, int base = 1) {
    const int nn = input_detail::safe_nonneg_int(n);
    const int mm = input_detail::safe_nonneg_int(m);
    std::vector<std::vector<int>> g(nn);
    for (int i = 0; i < mm; i++) {
        int u, v;
        input_detail::scan_values(u, v);
        u -= base;
        v -= base;
        assert(input_detail::in_vertex_range(u, nn) && input_detail::in_vertex_range(v, nn));
        if (!input_detail::in_vertex_range(u, nn) || !input_detail::in_vertex_range(v, nn)) continue;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    return g;
}

/**
 * @brief 有向グラフを辺リストから隣接リスト形式で読み込む
 * @param n 頂点数
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト (vector<vector<int>>)
 *
 * 使い方:
 *   auto g = read_digraph(n, m, 1); // 1-indexed 入力、u -> v の有向辺
 */
inline std::vector<std::vector<int>> read_digraph(int n, int m, int base = 1) {
    const int nn = input_detail::safe_nonneg_int(n);
    const int mm = input_detail::safe_nonneg_int(m);
    std::vector<std::vector<int>> g(nn);
    for (int i = 0; i < mm; i++) {
        int u, v;
        input_detail::scan_values(u, v);
        u -= base;
        v -= base;
        assert(input_detail::in_vertex_range(u, nn) && input_detail::in_vertex_range(v, nn));
        if (!input_detail::in_vertex_range(u, nn) || !input_detail::in_vertex_range(v, nn)) continue;
        g[u].push_back(v);
    }
    return g;
}

/**
 * @brief 木を辺リストから隣接リスト形式で読み込む (n-1 辺)
 * @param n 頂点数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト (vector<vector<int>>)
 *
 * 使い方:
 *   auto g = read_tree(n, 1); // 1-indexed 入力
 */
inline std::vector<std::vector<int>> read_tree(int n, int base = 1) {
    assert(n >= 0);
    if (n <= 0) return {};
    return read_graph(n, n - 1, base);
}

template <typename W>
inline std::vector<std::vector<std::pair<int, W>>> read_weighted_graph(int n, int m, int base = 1);

/**
 * @brief 重み付き木を辺リストから隣接リスト形式で読み込む (n-1 辺)
 * @tparam W 辺の重みの型
 * @param n 頂点数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト。各エントリは {隣接頂点, 重み} のペア
 *
 * 使い方:
 *   auto g = read_weighted_tree<long long>(n, 1);
 */
template <typename W>
inline std::vector<std::vector<std::pair<int, W>>> read_weighted_tree(int n, int base = 1) {
    assert(n >= 0);
    if (n <= 0) return {};
    return read_weighted_graph<W>(n, n - 1, base);
}

/**
 * @brief 重み付き無向グラフを辺リストから隣接リスト形式で読み込む
 * @tparam W 辺の重みの型
 * @param n 頂点数
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト。各エントリは {隣接頂点, 重み} のペア
 *
 * 使い方:
 *   auto g = read_weighted_graph<long long>(n, m, 1);
 *   for (auto [v, w] : g[u]) { ... }
 */
template <typename W>
inline std::vector<std::vector<std::pair<int, W>>> read_weighted_graph(int n, int m, int base) {
    const int nn = input_detail::safe_nonneg_int(n);
    const int mm = input_detail::safe_nonneg_int(m);
    std::vector<std::vector<std::pair<int, W>>> g(nn);
    for (int i = 0; i < mm; i++) {
        int u, v;
        W w;
        input_detail::scan_values(u, v, w);
        u -= base;
        v -= base;
        assert(input_detail::in_vertex_range(u, nn) && input_detail::in_vertex_range(v, nn));
        if (!input_detail::in_vertex_range(u, nn) || !input_detail::in_vertex_range(v, nn)) continue;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    return g;
}

/**
 * @brief 重み付き有向グラフを辺リストから隣接リスト形式で読み込む
 * @tparam W 辺の重みの型
 * @param n 頂点数
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の隣接リスト。各エントリは {隣接頂点, 重み} のペア
 *
 * 使い方:
 *   auto g = read_weighted_digraph<long long>(n, m, 1);
 *   for (auto [v, w] : g[u]) { ... }
 */
template <typename W>
inline std::vector<std::vector<std::pair<int, W>>> read_weighted_digraph(int n, int m, int base = 1) {
    const int nn = input_detail::safe_nonneg_int(n);
    const int mm = input_detail::safe_nonneg_int(m);
    std::vector<std::vector<std::pair<int, W>>> g(nn);
    for (int i = 0; i < mm; i++) {
        int u, v;
        W w;
        input_detail::scan_values(u, v, w);
        u -= base;
        v -= base;
        assert(input_detail::in_vertex_range(u, nn) && input_detail::in_vertex_range(v, nn));
        if (!input_detail::in_vertex_range(u, nn) || !input_detail::in_vertex_range(v, nn)) continue;
        g[u].emplace_back(v, w);
    }
    return g;
}

// ==================== 辺リスト入力 ====================

/**
 * @brief 無向/有向グラフの辺リストを読み込む
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の辺リスト (std::vector<std::pair<int, int>>)
 */
inline std::vector<std::pair<int, int>> read_edges(int m, int base = 1) {
    const int mm = input_detail::safe_nonneg_int(m);
    std::vector<std::pair<int, int>> edges(mm);
    for (int i = 0; i < mm; ++i) {
        int u, v;
        input_detail::scan_values(u, v);
        edges[i] = {u - base, v - base};
    }
    return edges;
}

/**
 * @brief 重み付き無向/有向グラフの辺リストを読み込む
 * @tparam W 辺の重みの型
 * @param m 辺数
 * @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
 * @return 0-indexed の重み付き辺リスト (std::vector<std::tuple<int, int, W>>)
 */
template <typename W>
inline std::vector<std::tuple<int, int, W>> read_weighted_edges(int m, int base = 1) {
    const int mm = input_detail::safe_nonneg_int(m);
    std::vector<std::tuple<int, int, W>> edges(mm);
    for (int i = 0; i < mm; ++i) {
        int u, v;
        W w;
        input_detail::scan_values(u, v, w);
        edges[i] = {u - base, v - base, w};
    }
    return edges;
}
#include <algorithm>
#include <cassert>
#include <concepts>
#include <istream>
#include <numeric>
#include <print>
#include <ranges>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

#define ALL(a) (a).begin(), (a).end()
using lint = long;
using i128 = __int128;

/**
 * @brief i128を標準入力から読み込む
 * @param is 入力ストリーム
 * @param x 読み込み先
 * @return 入力ストリーム
 */
inline std::istream& operator>>(std::istream& is, i128& x) {
    std::string s;
    if (!(is >> s)) return is;

    bool neg = false;
    int i = 0;
    if (!s.empty() && (s[0] == '+' || s[0] == '-')) {
        neg = s[0] == '-';
        i = 1;
    }
    if (i == static_cast<int>(s.size())) {
        is.setstate(std::ios::failbit);
        return is;
    }

    i128 val = 0;
    for (; i < static_cast<int>(s.size()); i++) {
        if (s[i] < '0' || '9' < s[i]) {
            is.setstate(std::ios::failbit);
            return is;
        }
        int d = s[i] - '0';
        val = neg ? val * 10 - d : val * 10 + d;
    }
    x = val;
    return is;
}
/**
 * @brief aをaとbの最小値で更新
 * @param a 更新対象
 * @param b 比較値
 * @return 更新されたらtrue
 */
template <typename T, typename U>
inline bool chmin(T& a, const U& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

/**
 * @brief aをaとbの最大値で更新
 * @param a 更新対象
 * @param b 比較値
 * @return 更新されたらtrue
 */
template <typename T, typename U>
inline bool chmax(T& a, const U& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

/**
 * @brief 整数除算の切り上げ (b>0)
 * @param a 分子
 * @param b 分母
 * @return 切り上げ値
 */
template <std::integral T>
inline T div_ceil(T a, T b) {
    if (a > 0) return a / b + (a % b != 0);
    return a / b;
}

/**
 * @brief 整数除算の切り捨て (b>0)
 * @param a 分子
 * @param b 分母
 * @return 切り捨て値
 */
template <std::integral T>
inline T div_floor(T a, T b) {
    if (a < 0) return a / b - (a % b != 0);
    return a / b;
}

/**
 * @brief 連続整数のvector生成
 * @param n 要素数
 * @param start 開始値(デフォルト0)
 * @return 生成されたvector
 */
template <typename T = int>
inline std::vector<T> iota_vec(int n, T start = 0) {
    std::vector<T> v(n);
    std::iota(v.begin(), v.end(), start);
    return v;
}

/**
 * @brief 非負の剰余を返す (m>0)
 * @param a 元の値
 * @param m 法
 * @return 0以上m未満の剰余
 */
template <std::integral T>
inline T mod(T a, T m) {
    a %= m;
    if (a < 0) a += m;
    return a;
}

/**
 * @brief vectorをソートして重複を削除
 * @param v 対象のvector
 */
template <typename T>
inline void sort_unique(std::vector<T>& v) {
    std::ranges::sort(v);
    v.erase(std::ranges::unique(v).begin(), v.end());
}

/**
 * @brief ソート済みのvectorを返す
 * @param v 対象のvector
 * @return ソート済みのvector
 */
template <typename T>
inline std::vector<T> sorted(std::vector<T> v) {
    std::ranges::sort(v);
    return v;
}

/**
 * @brief 値の昇順に並べた添字列を返す
 * @param v 対象のvector
 * @return v[i]の昇順に並べた添字iの列
 */
template <typename T>
inline std::vector<int> argsort(const std::vector<T>& v) {
    std::vector<int> p(v.size());
    std::iota(p.begin(), p.end(), 0);
    std::ranges::sort(p, {}, [&](int i) { return v[i]; });
    return p;
}

/**
 * @brief 最大値をとる添字を返す
 * @param v 対象のvector（非空）
 * @return 最大値をとる最初の添字
 */
template <typename T>
inline int max_index(const std::vector<T>& v) {
    return std::ranges::max_element(v) - v.begin();
}

/**
 * @brief 最小値をとる添字を返す
 * @param v 対象のvector（非空）
 * @return 最小値をとる最初の添字
 */
template <typename T>
inline int min_index(const std::vector<T>& v) {
    return std::ranges::min_element(v) - v.begin();
}

namespace internal {
/**
 * @brief 多次元のstd::vectorをデフォルト値で生成するヘルパー
 */
template <typename T, typename... Args>
inline auto make_vec_default(int n, Args... args) {
    if constexpr (sizeof...(args) == 0) {
        return std::vector<T>(n);
    } else {
        return std::vector(n, make_vec_default<T>(args...));
    }
}
}  // namespace internal

/**
 * @brief 多次元のstd::vectorを初期値付きで生成する
 * @param n サイズ
 * @param init 初期値
 * @return 1次元のstd::vector
 */
template <typename T>
inline std::vector<T> make_vec(int n, const T& init) {
    return std::vector<T>(n, init);
}

/**
 * @brief 多次元のstd::vectorを初期値付きで生成する（再帰・推論）
 * @param n 最初の次元のサイズ
 * @param args 残りの次元のサイズ、および最終的な初期値
 * @return 多次元のstd::vector
 */
template <typename... Args>
inline auto make_vec(int n, Args... args) {
    return std::vector(n, make_vec(args...));
}

/**
 * @brief 多次元のstd::vectorをデフォルト値で生成する
 * @tparam T 要素の型
 * @param args 次元のサイズ列
 * @return 多次元のstd::vector
 */
template <typename T, typename... Args>
inline auto make_vec(Args... args) {
    return internal::make_vec_default<T>(args...);
}

/**
 * @brief 同じサイズの複数の多次元のstd::vectorを生成する
 * @tparam Ts 各vectorの要素型
 * @param args 次元のサイズ列
 * @return 生成された各テーブルを格納したstd::tuple
 */
template <typename... Ts, typename... Args>
inline auto make_vecs(Args... args) {
    return std::make_tuple(internal::make_vec_default<Ts>(args...)...);
}

/**
 * @brief vectorを2回反復連結
 * @param v 元のvector
 * @return 2倍長のvector
 */
template <typename T>
inline std::vector<T> doubled_vec(const std::vector<T>& v) {
    std::vector<T> res;
    res.reserve(v.size() * 2);
    res.insert(res.end(), v.begin(), v.end());
    res.insert(res.end(), v.begin(), v.end());
    return res;
}

/**
 * @brief 区間[l1,r1)と[l2,r2)の共通長
 * @param l1 区間1左端
 * @param r1 区間1右端
 * @param l2 区間2左端
 * @param r2 区間2右端
 * @return 共通部分の長さ(ない場合は0)
 */
template <typename T>
inline T overlap_length(T l1, T r1, T l2, T r2) {
    return std::max(static_cast<T>(0), std::min(r1, r2) - std::max(l1, l2));
}

/**
 * @brief 文字列をランレングス圧縮する
 * @param s 対象文字列
 * @return {文字, 連続個数} の列
 */
inline std::vector<std::pair<char, int>> run_length_encode(const std::string& s) {
    std::vector<std::pair<char, int>> res;
    for (char c : s) {
        if (res.empty() || res.back().first != c) {
            res.emplace_back(c, 1);
        } else {
            res.back().second++;
        }
    }
    return res;
}

/**
 * @brief ランレングス圧縮された文字列を復元する
 * @param rle {文字, 連続個数} の列
 * @return 復元後の文字列
 */
inline std::string run_length_decode(const std::vector<std::pair<char, int>>& rle) {
    std::string res;
    for (const auto& [c, cnt] : rle) {
        res.append(cnt, c);
    }
    return res;
}

/**
 * @brief [0, n] の範囲の全区間 [l, r) を列挙する
 *
 * 0 <= l < r <= n を満たす全ての区間を {l, r} のペアとして順次生成します。
 * C++23 の std::views::join を利用しており、一時的な vector を作成しません。
 *
 * 使用例:
 * for (auto [l, r] : enumerate_intervals(n)) {
 *     // 区間 [l, r) に対する処理
 * }
 *
 * @param n 範囲の上限（要素数）
 * @return 各区間 {l, r} を生成する View
 */
template <std::integral T>
inline auto enumerate_intervals(T n) {
    return std::views::iota(T(0), n) | std::views::transform([n](T l) {
               return std::views::iota(l + 1, n + 1) |
                      std::views::transform([l](T r) { return std::pair<T, T>{l, r}; });
           }) |
           std::views::join;
}

/**
 * @brief h × w グリッド内の全矩形 [y1, y2) × [x1, x2) を列挙する
 *
 * 0 <= y1 < y2 <= h, 0 <= x1 < x2 <= w を満たす全ての矩形を
 * {y1, x1, y2, x2} の tuple として順次生成します。
 *
 * 使用例:
 * for (auto [y1, x1, y2, x2] : enumerate_all_rectangles(h, w)) {
 *     // 矩形 [y1, y2) × [x1, x2) に対する処理
 * }
 *
 * @param h グリッドの高さ
 * @param w グリッドの幅
 * @return 各矩形 {y1, x1, y2, x2} を生成する View
 */
template <std::integral T>
inline auto enumerate_all_rectangles(T h, T w) {
    return enumerate_intervals(h) | std::views::transform([w](auto y_range) {
               auto [y1, y2] = y_range;
               return enumerate_intervals(w) | std::views::transform([y1, y2](auto x_range) {
                          auto [x1, x2] = x_range;
                          return std::tuple<T, T, T, T>{y1, x1, y2, x2};
                      });
           }) |
           std::views::join;
}

/**
 * @brief h × w グリッド内の固定サイズ矩形を列挙する
 *
 * rect_h × rect_w の各矩形を、左上座標の昇順に
 * {y1, x1, y2, x2} の tuple として順次生成します。
 * rect_h, rect_w は 0 も許容します。
 *
 * 使用例:
 * for (auto [y1, x1, y2, x2] : enumerate_fixed_rectangles(h, w, rect_h, rect_w)) {
 *     // 矩形 [y1, y2) × [x1, x2) に対する処理
 * }
 *
 * @param h グリッドの高さ
 * @param w グリッドの幅
 * @param rect_h 矩形の高さ
 * @param rect_w 矩形の幅
 * @return 各矩形 {y1, x1, y2, x2} を生成する View
 */
template <std::integral T>
inline auto enumerate_fixed_rectangles(T h, T w, T rect_h, T rect_w) {
    assert(T(0) <= rect_h && rect_h <= h && T(0) <= rect_w && rect_w <= w);
    return std::views::iota(T(0), h - rect_h + 1) | std::views::transform([w, rect_h, rect_w](T y1) {
               return std::views::iota(T(0), w - rect_w + 1) |
                      std::views::transform([y1, rect_h, rect_w](T x1) {
                          return std::tuple<T, T, T, T>{y1, x1, y1 + rect_h, x1 + rect_w};
                      });
           }) |
           std::views::join;
}

/**
 * @brief "Yes"/"No"を出力
 * @param b trueでYes, falseでNo
 */
inline void Yes(bool b = true) {
    std::println("{}", (b ? "Yes" : "No"));
}

/**
 * @brief "No"を出力
 */
inline void No() {
    std::println("No");
}

#ifdef LOCAL
#include <utility/debug.hpp>
#else
#define debug(...)
#endif

using namespace std;
namespace rv = std::views;  // NOLINT

// [TEMPLATE_END]

void solve() {
    // Write your code here
    string S;
    scan(S);
    bool ok = true;
    ok &= !S.contains("SKG");
    debug(ok);
    if (!ok) {
        No();
    } else {
        Yes();
        for (auto& c : S) {
            if (c == '.') c = 'G';
        }
        for (auto&& [a, b, c] : S | rv::adjacent<3>) {
            if (a == 'S' && b == 'K' && c == 'G') {
                c = 'K';
            }
        }
        println("{}", S);
    }
}

int main() {
    fast_io();
    solve();
}