This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub hitonanode/cplib-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite" #include "../../modint.hpp" #include "../../segmenttree/point-update-range-get_nonrecursive.hpp" #include "../heavy_light_decomposition.hpp" #include <iostream> #include <vector> using namespace std; using mint = ModInt<998244353>; using P = pair<mint, mint>; struct PointSetRangeComposite : public NonrecursiveSegmentTree<P, P, bool> { using SegTree = NonrecursiveSegmentTree<P, P, bool>; P merge_data(const P &vl, const P &vr) override { return make_pair(vl.first * vr.first, vr.first * vl.second + vr.second); }; P data2ret(const P &v, const bool &q) override { return v; } P merge_ret(const P &vl, const P &vr) override { return merge_data(vl, vr); }; PointSetRangeComposite(const std::vector<P> &seq, P zero) : SegTree::NonrecursiveSegmentTree() { SegTree::initialize(seq, zero); }; }; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N, Q; cin >> N >> Q; vector<P> V(N); for (auto &x : V) cin >> x.first >> x.second; HeavyLightDecomposition hld(N); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; hld.add_edge(u, v); } hld.build(); vector<P> stinit = hld.segtree_rearrange(V); PointSetRangeComposite segtree(stinit, P{1, 0}); reverse(stinit.begin(), stinit.end()); PointSetRangeComposite segtreeinv(stinit, P{1, 0}); while (Q--) { int q, u, v, x; cin >> q >> u >> v >> x; if (q == 0) { segtree.update(hld.aligned_id[u], P{v, x}); segtreeinv.update(N - 1 - hld.aligned_id[u], P{v, x}); } else { mint ret = x; hld.for_each_vertex_noncommutative( u, v, [&](int l, int r) -> void { assert(0 <= l and l <= r and r < N); P tmp = segtreeinv.get(N - 1 - r, N - 1 - l + 1); ret = tmp.first * ret + tmp.second; }, [&](int l, int r) -> void { assert(0 <= l and l <= r and r < N); P tmp = segtree.get(l, r + 1); ret = tmp.first * ret + tmp.second; }); cout << ret << '\n'; } } }
#line 1 "tree/test/vertex-set-path-composite.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/vertex_set_path_composite" #line 2 "modint.hpp" #include <cassert> #include <iostream> #include <set> #include <vector> template <int md> struct ModInt { using lint = long long; constexpr static int mod() { return md; } static int get_primitive_root() { static int primitive_root = 0; if (!primitive_root) { primitive_root = [&]() { std::set<int> fac; int v = md - 1; for (lint i = 2; i * i <= v; i++) while (v % i == 0) fac.insert(i), v /= i; if (v > 1) fac.insert(v); for (int g = 1; g < md; g++) { bool ok = true; for (auto i : fac) if (ModInt(g).pow((md - 1) / i) == 1) { ok = false; break; } if (ok) return g; } return -1; }(); } return primitive_root; } int val_; int val() const noexcept { return val_; } constexpr ModInt() : val_(0) {} constexpr ModInt &_setval(lint v) { return val_ = (v >= md ? v - md : v), *this; } constexpr ModInt(lint v) { _setval(v % md + md); } constexpr explicit operator bool() const { return val_ != 0; } constexpr ModInt operator+(const ModInt &x) const { return ModInt()._setval((lint)val_ + x.val_); } constexpr ModInt operator-(const ModInt &x) const { return ModInt()._setval((lint)val_ - x.val_ + md); } constexpr ModInt operator*(const ModInt &x) const { return ModInt()._setval((lint)val_ * x.val_ % md); } constexpr ModInt operator/(const ModInt &x) const { return ModInt()._setval((lint)val_ * x.inv().val() % md); } constexpr ModInt operator-() const { return ModInt()._setval(md - val_); } constexpr ModInt &operator+=(const ModInt &x) { return *this = *this + x; } constexpr ModInt &operator-=(const ModInt &x) { return *this = *this - x; } constexpr ModInt &operator*=(const ModInt &x) { return *this = *this * x; } constexpr ModInt &operator/=(const ModInt &x) { return *this = *this / x; } friend constexpr ModInt operator+(lint a, const ModInt &x) { return ModInt(a) + x; } friend constexpr ModInt operator-(lint a, const ModInt &x) { return ModInt(a) - x; } friend constexpr ModInt operator*(lint a, const ModInt &x) { return ModInt(a) * x; } friend constexpr ModInt operator/(lint a, const ModInt &x) { return ModInt(a) / x; } constexpr bool operator==(const ModInt &x) const { return val_ == x.val_; } constexpr bool operator!=(const ModInt &x) const { return val_ != x.val_; } constexpr bool operator<(const ModInt &x) const { return val_ < x.val_; } // To use std::map<ModInt, T> friend std::istream &operator>>(std::istream &is, ModInt &x) { lint t; return is >> t, x = ModInt(t), is; } constexpr friend std::ostream &operator<<(std::ostream &os, const ModInt &x) { return os << x.val_; } constexpr ModInt pow(lint n) const { ModInt ans = 1, tmp = *this; while (n) { if (n & 1) ans *= tmp; tmp *= tmp, n >>= 1; } return ans; } static constexpr int cache_limit = std::min(md, 1 << 21); static std::vector<ModInt> facs, facinvs, invs; constexpr static void _precalculation(int N) { const int l0 = facs.size(); if (N > md) N = md; if (N <= l0) return; facs.resize(N), facinvs.resize(N), invs.resize(N); for (int i = l0; i < N; i++) facs[i] = facs[i - 1] * i; facinvs[N - 1] = facs.back().pow(md - 2); for (int i = N - 2; i >= l0; i--) facinvs[i] = facinvs[i + 1] * (i + 1); for (int i = N - 1; i >= l0; i--) invs[i] = facinvs[i] * facs[i - 1]; } constexpr ModInt inv() const { if (this->val_ < cache_limit) { if (facs.empty()) facs = {1}, facinvs = {1}, invs = {0}; while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2); return invs[this->val_]; } else { return this->pow(md - 2); } } constexpr ModInt fac() const { while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2); return facs[this->val_]; } constexpr ModInt facinv() const { while (this->val_ >= int(facs.size())) _precalculation(facs.size() * 2); return facinvs[this->val_]; } constexpr ModInt doublefac() const { lint k = (this->val_ + 1) / 2; return (this->val_ & 1) ? ModInt(k * 2).fac() / (ModInt(2).pow(k) * ModInt(k).fac()) : ModInt(k).fac() * ModInt(2).pow(k); } constexpr ModInt nCr(int r) const { if (r < 0 or this->val_ < r) return ModInt(0); return this->fac() * (*this - r).facinv() * ModInt(r).facinv(); } constexpr ModInt nPr(int r) const { if (r < 0 or this->val_ < r) return ModInt(0); return this->fac() * (*this - r).facinv(); } static ModInt binom(int n, int r) { static long long bruteforce_times = 0; if (r < 0 or n < r) return ModInt(0); if (n <= bruteforce_times or n < (int)facs.size()) return ModInt(n).nCr(r); r = std::min(r, n - r); ModInt ret = ModInt(r).facinv(); for (int i = 0; i < r; ++i) ret *= n - i; bruteforce_times += r; return ret; } // Multinomial coefficient, (k_1 + k_2 + ... + k_m)! / (k_1! k_2! ... k_m!) // Complexity: O(sum(ks)) template <class Vec> static ModInt multinomial(const Vec &ks) { ModInt ret{1}; int sum = 0; for (int k : ks) { assert(k >= 0); ret *= ModInt(k).facinv(), sum += k; } return ret * ModInt(sum).fac(); } // Catalan number, C_n = binom(2n, n) / (n + 1) // C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, ... // https://oeis.org/A000108 // Complexity: O(n) static ModInt catalan(int n) { if (n < 0) return ModInt(0); return ModInt(n * 2).fac() * ModInt(n + 1).facinv() * ModInt(n).facinv(); } ModInt sqrt() const { if (val_ == 0) return 0; if (md == 2) return val_; if (pow((md - 1) / 2) != 1) return 0; ModInt b = 1; while (b.pow((md - 1) / 2) == 1) b += 1; int e = 0, m = md - 1; while (m % 2 == 0) m >>= 1, e++; ModInt x = pow((m - 1) / 2), y = (*this) * x * x; x *= (*this); ModInt z = b.pow(m); while (y != 1) { int j = 0; ModInt t = y; while (t != 1) j++, t *= t; z = z.pow(1LL << (e - j - 1)); x *= z, z *= z, y *= z; e = j; } return ModInt(std::min(x.val_, md - x.val_)); } }; template <int md> std::vector<ModInt<md>> ModInt<md>::facs = {1}; template <int md> std::vector<ModInt<md>> ModInt<md>::facinvs = {1}; template <int md> std::vector<ModInt<md>> ModInt<md>::invs = {0}; using ModInt998244353 = ModInt<998244353>; // using mint = ModInt<998244353>; // using mint = ModInt<1000000007>; #line 2 "segmenttree/point-update-range-get_nonrecursive.hpp" #include <algorithm> #line 4 "segmenttree/point-update-range-get_nonrecursive.hpp" #include <functional> #line 6 "segmenttree/point-update-range-get_nonrecursive.hpp" #include <stack> #line 8 "segmenttree/point-update-range-get_nonrecursive.hpp" // CUT begin // Nonrecursive Segment Tree (point-update, range-get) // - Conditions for operations: // - merge_data: [TDATA, TDATA] -> TDATA, e(x, y) == e(y, x) // - data2ret: [TDATA, TQUERY] -> TRET // - merge_ret: [TRET, TRET] -> TRET, g(defaultRET, x) == x, g(x, y) = g(y, x) // - commutability f(e(x, y), q) == g(f(x, q), f(y, q)) template <typename TDATA, typename TRET, typename TQUERY> struct NonrecursiveSegmentTree { int N; TRET defaultRET; virtual TDATA merge_data(const TDATA &, const TDATA &) = 0; virtual TRET data2ret(const TDATA &, const TQUERY &) = 0; virtual TRET merge_ret(const TRET &, const TRET &) = 0; std::vector<TDATA> data; inline TDATA &at(int i) { return data[i]; } inline void _merge(int i) { at(i) = merge_data(at(i << 1), at((i << 1) + 1)); } void initialize(const std::vector<TDATA> &seq, TRET RET_ZERO) { N = seq.size(); defaultRET = RET_ZERO; data = seq; data.insert(data.end(), seq.begin(), seq.end()); for (int i = N - 1; i; i--) _merge(i); } NonrecursiveSegmentTree() = default; void update(int pos, const TDATA &x) { assert(pos >= 0 and pos < N); at(pos + N) = x; for (int i = pos + N; i > 1;) i >>= 1, _merge(i); } // [l, r), 0-indexed TRET get(int l, int r, TQUERY query = NULL) { assert(l >= 0 and r <= N); TRET retl = defaultRET, retr = defaultRET; l += N, r += N; while (l < r) { if (l & 1) retl = merge_ret(retl, data2ret(data[l++], query)); if (r & 1) retr = merge_ret(data2ret(data[--r], query), retr); l >>= 1, r >>= 1; } return merge_ret(retl, retr); } // Calculate smallest r that satisfies condition(g(f(x_l, q), ..., f(x_{r - 1}, q)) == true // Assumption: Monotonicity of g(x_l, ..., x_r) about r (l: fixed) // Complexity: O(log N) int binary_search(int l, std::function<bool(TRET)> condition, TQUERY query = NULL) { std::stack<int> rs; l += N; int r = N * 2; TRET retl = defaultRET; if (condition(retl)) return l - N; while (l < r) { if (l & 1) { TRET ret_tmp = merge_ret(retl, data2ret(data[l], query)); if (condition(ret_tmp)) { while (l * 2 < N * 2) { ret_tmp = merge_ret(retl, data2ret(data[l * 2], query)); if (condition(ret_tmp)) l *= 2; else retl = ret_tmp, l = l * 2 + 1; } return l - N; } l++; retl = ret_tmp; } if (r & 1) rs.push(--r); l >>= 1, r >>= 1; } while (!rs.empty()) { l = rs.top(); rs.pop(); TRET ret_tmp = merge_ret(retl, data2ret(data[l], query)); if (condition(ret_tmp)) { while (l * 2 < N * 2) { ret_tmp = merge_ret(retl, data2ret(data[l * 2], query)); if (condition(ret_tmp)) l *= 2; else retl = ret_tmp, l = l * 2 + 1; } return l - N; } retl = ret_tmp; } return N; } template <typename T1, typename T2, typename T3> friend std::ostream &operator<<(std::ostream &os, NonrecursiveSegmentTree<T1, T2, T3> s) { os << "[SegmentTree (len: " << s.N << ')'; for (int i = 0; i < s.N; i++) os << s.at(i + s.N) << ','; os << "]"; return os; } }; // Range Minimum Query // - get: return min(x_l, ..., x_{r - 1}) template <typename T> struct RangeMinimumQuery : public NonrecursiveSegmentTree<T, T, bool> { using SegTree = NonrecursiveSegmentTree<T, T, bool>; T merge_data(const T &vl, const T &vr) override { return std::min(vl, vr); }; T data2ret(const T &v, const bool &q) override { return v; } T merge_ret(const T &vl, const T &vr) override { return std::min(vl, vr); }; RangeMinimumQuery(const std::vector<T> &seq, T defaultmin) : SegTree::NonrecursiveSegmentTree() { SegTree::initialize(seq, defaultmin); }; }; // Range Maximum Query // - get: return max(x_l, ..., x_{r - 1}) template <typename T> struct RangeMaximumQuery : public NonrecursiveSegmentTree<T, T, bool> { using SegTree = NonrecursiveSegmentTree<T, T, bool>; T merge_data(const T &vl, const T &vr) override { return std::max(vl, vr); }; T data2ret(const T &v, const bool &q) override { return v; } T merge_ret(const T &vl, const T &vr) override { return std::max(vl, vr); }; RangeMaximumQuery(const std::vector<T> &seq, T defaultmax) : SegTree::NonrecursiveSegmentTree() { SegTree::initialize(seq, defaultmax); }; }; template <typename T> struct PointUpdateRangeSum : public NonrecursiveSegmentTree<T, T, bool> { using SegTree = NonrecursiveSegmentTree<T, T, bool>; T merge_data(const T &vl, const T &vr) override { return vl + vr; }; T data2ret(const T &v, const bool &q) override { return v; } T merge_ret(const T &vl, const T &vr) override { return vl + vr; }; PointUpdateRangeSum(const std::vector<T> &seq, T zero) : SegTree::NonrecursiveSegmentTree() { SegTree::initialize(seq, zero); }; }; // Range Counting less than q Query // - get: return (#{i | l <= i < r, x_i < q}, total sum of them). template <typename T> struct CountAndSumLessThan : public NonrecursiveSegmentTree<std::vector<std::pair<T, T>>, std::pair<int, T>, T> { using TDATA = std::vector<std::pair<T, T>>; using TRET = std::pair<int, T>; using TQUERY = T; TDATA merge_data(const TDATA &vl, const TDATA &vr) override { TDATA ret = vl; ret.insert(ret.end(), vr.begin(), vr.end()); std::sort(ret.begin(), ret.end()); if (ret.size()) { ret[0].second = ret[0].first; for (size_t i = 1; i < ret.size(); i++) ret[i].second = ret[i - 1].second + ret[i].first; } return ret; } TRET data2ret(const TDATA &vec, const TQUERY &q) override { int i = std::lower_bound(vec.begin(), vec.end(), std::make_pair(q, q)) - vec.begin(); if (!i) return std::make_pair(0, 0); else return std::make_pair(i, vec[i - 1].second); } TRET merge_ret(const TRET &l, const TRET &r) override { return std::make_pair(l.first + r.first, l.second + r.second); } using SegTree = NonrecursiveSegmentTree<TDATA, TRET, TQUERY>; CountAndSumLessThan(const std::vector<T> &seq) : SegTree::NonrecursiveSegmentTree() { std::vector<TDATA> init; for (auto x : seq) init.emplace_back(TDATA{std::pair<T, T>(x, x)}); SegTree::initialize(init, TRET(0, 0)); } }; #line 5 "tree/heavy_light_decomposition.hpp" #include <queue> #line 7 "tree/heavy_light_decomposition.hpp" #include <utility> #line 9 "tree/heavy_light_decomposition.hpp" // Heavy-Light Decomposition of trees // Based on http://beet-aizu.hatenablog.com/entry/2017/12/12/235950 struct HeavyLightDecomposition { int V; int k; int nb_heavy_path; std::vector<std::vector<int>> e; std::vector<int> par; // par[i] = parent of vertex i (Default: -1) std::vector<int> depth; // depth[i] = distance between root and vertex i std::vector<int> subtree_sz; // subtree_sz[i] = size of subtree whose root is i std::vector<int> heavy_child; // heavy_child[i] = child of vertex i on heavy path (Default: -1) std::vector<int> tree_id; // tree_id[i] = id of tree vertex i belongs to std::vector<int> aligned_id, aligned_id_inv; // aligned_id[i] = aligned id for vertex i (consecutive on heavy edges) std::vector<int> head; // head[i] = id of vertex on heavy path of vertex i, nearest to root std::vector<int> head_ids; // consist of head vertex id's std::vector<int> heavy_path_id; // heavy_path_id[i] = heavy_path_id for vertex [i] HeavyLightDecomposition(int sz = 0) : V(sz), k(0), nb_heavy_path(0), e(sz), par(sz), depth(sz), subtree_sz(sz), heavy_child(sz), tree_id(sz, -1), aligned_id(sz), aligned_id_inv(sz), head(sz), heavy_path_id(sz, -1) {} void add_edge(int u, int v) { e[u].emplace_back(v); e[v].emplace_back(u); } void _build_dfs(int root) { std::stack<std::pair<int, int>> st; par[root] = -1; depth[root] = 0; st.emplace(root, 0); while (!st.empty()) { int now = st.top().first; int &i = st.top().second; if (i < (int)e[now].size()) { int nxt = e[now][i++]; if (nxt == par[now]) continue; par[nxt] = now; depth[nxt] = depth[now] + 1; st.emplace(nxt, 0); } else { st.pop(); int max_sub_sz = 0; subtree_sz[now] = 1; heavy_child[now] = -1; for (auto nxt : e[now]) { if (nxt == par[now]) continue; subtree_sz[now] += subtree_sz[nxt]; if (max_sub_sz < subtree_sz[nxt]) max_sub_sz = subtree_sz[nxt], heavy_child[now] = nxt; } } } } void _build_bfs(int root, int tree_id_now) { std::queue<int> q({root}); while (!q.empty()) { int h = q.front(); q.pop(); head_ids.emplace_back(h); for (int now = h; now != -1; now = heavy_child[now]) { tree_id[now] = tree_id_now; aligned_id[now] = k++; aligned_id_inv[aligned_id[now]] = now; heavy_path_id[now] = nb_heavy_path; head[now] = h; for (int nxt : e[now]) if (nxt != par[now] and nxt != heavy_child[now]) q.push(nxt); } nb_heavy_path++; } } void build(std::vector<int> roots = {0}) { int tree_id_now = 0; for (auto r : roots) _build_dfs(r), _build_bfs(r, tree_id_now++); } template <class T> std::vector<T> segtree_rearrange(const std::vector<T> &data) const { assert(int(data.size()) == V); std::vector<T> ret; ret.reserve(V); for (int i = 0; i < V; i++) ret.emplace_back(data[aligned_id_inv[i]]); return ret; } // query for vertices on path [u, v] (INCLUSIVE) void for_each_vertex(int u, int v, const std::function<void(int ancestor, int descendant)> &f) const { while (true) { if (aligned_id[u] > aligned_id[v]) std::swap(u, v); f(std::max(aligned_id[head[v]], aligned_id[u]), aligned_id[v]); if (head[u] == head[v]) break; v = par[head[v]]; } } void for_each_vertex_noncommutative( int from, int to, const std::function<void(int ancestor, int descendant)> &fup, const std::function<void(int ancestor, int descendant)> &fdown) const { int u = from, v = to; const int lca = lowest_common_ancestor(u, v), dlca = depth[lca]; while (u >= 0 and depth[u] > dlca) { const int p = (depth[head[u]] > dlca ? head[u] : lca); fup(aligned_id[p] + (p == lca), aligned_id[u]), u = par[p]; } static std::vector<std::pair<int, int>> lrs; int sz = 0; while (v >= 0 and depth[v] >= dlca) { const int p = (depth[head[v]] >= dlca ? head[v] : lca); if (int(lrs.size()) == sz) lrs.emplace_back(0, 0); lrs.at(sz++) = {p, v}, v = par.at(p); } while (sz--) fdown(aligned_id[lrs.at(sz).first], aligned_id[lrs.at(sz).second]); } // query for edges on path [u, v] void for_each_edge(int u, int v, const std::function<void(int, int)> &f) const { while (true) { if (aligned_id[u] > aligned_id[v]) std::swap(u, v); if (head[u] != head[v]) { f(aligned_id[head[v]], aligned_id[v]); v = par[head[v]]; } else { if (u != v) f(aligned_id[u] + 1, aligned_id[v]); break; } } } // lowest_common_ancestor: O(log V) int lowest_common_ancestor(int u, int v) const { assert(tree_id[u] == tree_id[v] and tree_id[u] >= 0); while (true) { if (aligned_id[u] > aligned_id[v]) std::swap(u, v); if (head[u] == head[v]) return u; v = par[head[v]]; } } int distance(int u, int v) const { assert(tree_id[u] == tree_id[v] and tree_id[u] >= 0); return depth[u] + depth[v] - 2 * depth[lowest_common_ancestor(u, v)]; } // Level ancestor, O(log V) // if k-th parent is out of range, return -1 int kth_parent(int v, int k) const { if (k < 0) return -1; while (v >= 0) { int h = head.at(v), len = depth.at(v) - depth.at(h); if (k <= len) return aligned_id_inv.at(aligned_id.at(v) - k); k -= len + 1, v = par.at(h); } return -1; } // Jump on tree, O(log V) int s_to_t_by_k_steps(int s, int t, int k) const { if (k < 0) return -1; if (k == 0) return s; int lca = lowest_common_ancestor(s, t); if (k <= depth.at(s) - depth.at(lca)) return kth_parent(s, k); return kth_parent(t, depth.at(s) + depth.at(t) - depth.at(lca) * 2 - k); } }; #line 7 "tree/test/vertex-set-path-composite.test.cpp" using namespace std; using mint = ModInt<998244353>; using P = pair<mint, mint>; struct PointSetRangeComposite : public NonrecursiveSegmentTree<P, P, bool> { using SegTree = NonrecursiveSegmentTree<P, P, bool>; P merge_data(const P &vl, const P &vr) override { return make_pair(vl.first * vr.first, vr.first * vl.second + vr.second); }; P data2ret(const P &v, const bool &q) override { return v; } P merge_ret(const P &vl, const P &vr) override { return merge_data(vl, vr); }; PointSetRangeComposite(const std::vector<P> &seq, P zero) : SegTree::NonrecursiveSegmentTree() { SegTree::initialize(seq, zero); }; }; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N, Q; cin >> N >> Q; vector<P> V(N); for (auto &x : V) cin >> x.first >> x.second; HeavyLightDecomposition hld(N); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; hld.add_edge(u, v); } hld.build(); vector<P> stinit = hld.segtree_rearrange(V); PointSetRangeComposite segtree(stinit, P{1, 0}); reverse(stinit.begin(), stinit.end()); PointSetRangeComposite segtreeinv(stinit, P{1, 0}); while (Q--) { int q, u, v, x; cin >> q >> u >> v >> x; if (q == 0) { segtree.update(hld.aligned_id[u], P{v, x}); segtreeinv.update(N - 1 - hld.aligned_id[u], P{v, x}); } else { mint ret = x; hld.for_each_vertex_noncommutative( u, v, [&](int l, int r) -> void { assert(0 <= l and l <= r and r < N); P tmp = segtreeinv.get(N - 1 - r, N - 1 - l + 1); ret = tmp.first * ret + tmp.second; }, [&](int l, int r) -> void { assert(0 <= l and l <= r and r < N); P tmp = segtree.get(l, r + 1); ret = tmp.first * ret + tmp.second; }); cout << ret << '\n'; } } }