結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
 kkishi
|
| 提出日時 | 2022-03-31 07:18:45 |
| 言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,317 ms / 10,000 ms |
| コード長 | 24,857 bytes |
| コンパイル時間 | 4,963 ms |
| コンパイル使用メモリ | 170,492 KB |
| 実行使用メモリ | 32,532 KB |
| 最終ジャッジ日時 | 2024-04-27 22:08:22 |
| 合計ジャッジ時間 | 9,270 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,317 ms
32,424 KB |
| testcase_01 | AC | 844 ms
32,488 KB |
| testcase_02 | AC | 1,224 ms
32,532 KB |
ソースコード
#include <bits/stdc++.h>
#ifndef ATCODER_LAZYSEGTREE_HPP
#define ATCODER_LAZYSEGTREE_HPP 1
#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
#endif // ATCODER_INTERNAL_BITOP_HPP
namespace atcoder {
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
public:
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
} // namespace atcoder
#endif // ATCODER_LAZYSEGTREE_HPP
namespace update_min {
using S = int64_t;
S op(S a, S b) { return std::min(a, b); }
S e() { return std::numeric_limits<S>::max(); }
using F = std::optional<int64_t>;
S mapping(F f, S x) { return f ? *f : x; }
F composition(F f, F g) { return f ? f : g; }
F id() { return std::nullopt; }
using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
} // namespace update_min
namespace add_min {
using S = int64_t;
S op(S a, S b) { return std::min(a, b); }
S e() { return std::numeric_limits<S>::max(); }
using F = int64_t;
S mapping(F f, S x) { return f + x; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }
using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
} // namespace add_min
namespace update_sum {
struct S {
int64_t val;
int64_t len;
};
S op(S a, S b) { return {a.val + b.val, a.len + b.len}; }
S e() { return {0, 0}; }
using F = std::optional<int64_t>;
S mapping(F f, S x) {
if (f) x.val = *f * x.len;
return x;
}
F composition(F f, F g) { return f ? f : g; }
F id() { return std::nullopt; }
class segtree
: public atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> {
public:
segtree() : lazy_segtree() {}
explicit segtree(int n) : lazy_segtree(std::vector<S>(n, {0, 1})) {}
explicit segtree(const std::vector<int64_t>& v) : lazy_segtree(itos(v)) {}
private:
static std::vector<S> itos(const std::vector<int64_t>& v) {
std::vector<S> w(v.size());
for (size_t i = 0; i < v.size(); ++i) {
w[i] = {v[i], 1};
}
return w;
}
};
} // namespace update_sum
namespace add_sum {
struct S {
int64_t val;
int64_t len;
};
S op(S a, S b) { return {a.val + b.val, a.len + b.len}; }
S e() { return {0, 0}; }
using F = int64_t;
S mapping(F f, S x) { return {x.val + f * x.len, x.len}; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }
class segtree
: public atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> {
public:
segtree() : lazy_segtree() {}
explicit segtree(int n) : lazy_segtree(std::vector<S>(n, {0, 1})) {}
explicit segtree(const std::vector<int64_t>& v) : lazy_segtree(itos(v)) {}
private:
static std::vector<S> itos(const std::vector<int64_t>& v) {
std::vector<S> w(v.size());
for (size_t i = 0; i < v.size(); ++i) {
w[i] = {v[i], 1};
}
return w;
}
};
} // namespace add_sum
template <typename T>
class SegmentTree {
public:
using Operation = std::function<T(T, T)>;
SegmentTree(int size, Operation operation, T identity = T())
: operation_(operation), identity_(identity) {
int two = 1;
while (two < size) {
two <<= 1;
}
v_.resize(two * 2 - 1, identity_);
}
void Set(int i, T v) {
int index = Leaf(i);
while (true) {
v_[index] = v;
if (index == 0) break;
v = operation_(v, v_[index + (IsRight(index) ? -1 : 1)]);
index = Parent(index);
}
}
T Get(int i) const { return Aggregate(i, i + 1); }
T Aggregate(int begin, int end) const {
int l = Leaf(begin), r = Leaf(end);
T v = identity_;
while (l < r) {
if (IsRight(l)) {
v = operation_(v, v_[l]);
++l;
}
l = Parent(l);
if (IsRight(r)) {
v = operation_(v, v_[r - 1]);
}
r = Parent(r);
}
return v;
}
private:
int Leaf(int i) const { return i + (v_.size() >> 1); }
bool IsRight(int i) const { return !(i & 1); }
int Parent(int i) const { return (i - 1) >> 1; }
const Operation operation_;
const T identity_;
std::vector<T> v_;
};
template <typename T>
class AddSegmentTree : public SegmentTree<T> {
public:
AddSegmentTree(int n) : SegmentTree<T>(n, [](T a, T b) { return a + b; }) {}
};
#ifndef GRAPH_H_
#define GRAPH_H_
template <typename T>
class Graph {
public:
struct Edge {
int from, to;
T weight;
};
Graph(int n) : edges_(n) {}
void AddEdge(int from, int to, T weight = T()) {
edges_[from].push_back({from, to, weight});
}
const std::vector<Edge> &Edges(int from) const { return edges_[from]; }
std::vector<Edge> &MutableEdges(int from) { return edges_[from]; }
int NumVertices() const { return edges_.size(); }
bool IsTree() const {
std::vector<bool> visited(NumVertices());
auto rec = [&](auto rec, int node, int parent) -> bool {
if (visited[node]) return false;
visited[node] = true;
for (const Edge &e : Edges(node)) {
if (e.to != parent && !rec(rec, e.to, node)) {
return false;
}
}
return true;
};
return rec(rec, 0, -1);
}
private:
std::vector<std::vector<Edge>> edges_;
};
#endif
template <typename T>
class HeavyLightDecomposition {
public:
HeavyLightDecomposition(const Graph<T>& g, int root = 0) : g_(g) {
#ifdef DEBUG
assert(g.IsTree());
#endif
int n = g.NumVertices();
attr_.resize(n);
Dfs1(root, -1, 0);
int index = 0;
Dfs2(root, -1, root, index);
}
std::vector<std::pair<int32_t, int32_t>> Query(
int u, int v, bool include_lca = false) const {
std::vector<std::pair<int32_t, int32_t>> ret;
while (Begin(u) != Begin(v)) {
if (Depth(Begin(u)) < Depth(Begin(v))) std::swap(u, v);
ret.emplace_back(Index(Begin(u)), Index(u) + 1);
u = Parent(Begin(u));
}
u = Index(u), v = Index(v);
if (u > v) std::swap(u, v);
ret.emplace_back(u + (include_lca ? 0 : 1), v + 1);
return ret;
}
int LCA(int u, int v) const {
while (Begin(u) != Begin(v)) {
if (Depth(Begin(u)) < Depth(Begin(v))) std::swap(u, v);
u = Parent(Begin(u));
}
return Depth(u) < Depth(v) ? u : v;
}
int32_t Index(int node) const { return attr_[node].index; }
int32_t Parent(int node) const { return attr_[node].parent; }
private:
void Dfs1(int node, int parent, int depth) {
Attr& a = attr_[node];
a.depth = depth;
a.parent = parent;
a.size = 1;
a.heavy = -1;
for (const auto& e : g_.Edges(node)) {
if (e.to == parent) continue;
Dfs1(e.to, node, depth + 1);
a.size += Size(e.to);
if (a.heavy == -1 || Size(a.heavy) < Size(e.to)) {
a.heavy = e.to;
}
}
}
void Dfs2(int node, int parent, int begin, int& index) {
Attr& a = attr_[node];
a.index = index++;
a.begin = begin;
if (a.heavy == -1) return;
Dfs2(a.heavy, node, begin, index);
for (const auto& e : g_.Edges(node)) {
if (e.to == parent || e.to == a.heavy) continue;
Dfs2(e.to, node, e.to, index);
}
}
int32_t Begin(int node) const { return attr_[node].begin; }
int32_t Depth(int node) const { return attr_[node].depth; }
int32_t Heavy(int node) const { return attr_[node].heavy; }
int32_t Size(int node) const { return attr_[node].size; }
const Graph<T>& g_;
struct Attr {
int32_t begin;
int32_t depth;
int32_t heavy;
int32_t index;
int32_t parent;
int32_t size;
};
std::vector<Attr> attr_;
};
#ifndef MODINT_H_
#define MODINT_H_
namespace {
using i32 = int32_t;
using i64 = int64_t;
} // namespace
#define BIN_OPS(F) F(+) F(-) F(*) F(/)
#define CMP_OPS(F) F(!=) F(<) F(<=) F(==) F(>) F(>=)
template <i32 Mod = 1000000007>
class ModInt {
public:
ModInt() : n_(0) {}
ModInt(i64 n) : n_(n % Mod) {
if (n_ < 0) {
// In C++, (-n)%m == -(n%m).
n_ += Mod;
}
}
ModInt& operator+=(const ModInt& m) {
n_ += m.n_;
if (n_ >= Mod) {
n_ -= Mod;
}
return *this;
}
ModInt& operator++() { return (*this) += 1; }
ModInt& operator-=(const ModInt& m) {
n_ -= m.n_;
if (n_ < 0) {
n_ += Mod;
}
return *this;
}
ModInt& operator--() { return (*this) -= 1; }
ModInt& operator*=(const ModInt& m) {
n_ = i64(n_) * m.n_ % Mod;
return *this;
}
ModInt& operator/=(const ModInt& m) {
*this *= m.Inv();
return *this;
}
#define DEFINE(op) \
ModInt operator op(const ModInt& m) const { return ModInt(*this) op## = m; }
BIN_OPS(DEFINE)
#undef DEFINE
#define DEFINE(op) \
bool operator op(const ModInt& m) const { return n_ op m.n_; }
CMP_OPS(DEFINE)
#undef DEFINE
ModInt operator-() const { return ModInt(-n_); }
ModInt Pow(i64 n) const {
if (n < 0) {
return Inv().Pow(-n);
}
// a * b ^ n = answer.
ModInt a = 1, b = *this;
while (n != 0) {
if (n & 1) {
a *= b;
}
n /= 2;
b *= b;
}
return a;
}
ModInt Inv() const {
#if DEBUG
assert(n_ != 0);
#endif
if (n_ > kMaxCacheSize) {
// Compute the inverse based on Fermat's little theorem. Note that this
// only works when n_ and Mod are relatively prime. The theorem says that
// n_^(Mod-1) = 1 (mod Mod). So we can compute n_^(Mod-2).
return Pow(Mod - 2);
}
for (i64 i = inv_.size(); i <= n_; ++i) {
inv_.push_back(i <= 1 ? i : (Mod / i * -inv_[Mod % i]));
}
return inv_[n_];
}
i64 value() const { return n_; }
static ModInt Fact(i64 n) {
#if DEBUG
assert(0 <= n && n <= kMaxCacheSize);
#endif
for (i64 i = fact_.size(); i <= n; ++i) {
fact_.push_back(i == 0 ? 1 : fact_.back() * i);
}
return fact_[n];
}
static ModInt InvFact(i64 n) {
#if DEBUG
assert(0 <= n && n <= kMaxCacheSize);
#endif
for (i64 i = inv_fact_.size(); i <= n; ++i) {
inv_fact_.push_back(i == 0 ? 1 : inv_fact_.back() / i);
}
return inv_fact_[n];
}
static ModInt Comb(i64 n, i64 k) {
if (!Valid(n, k)) return 0;
return Perm(n, k) * InvFact(k);
}
static ModInt CombSlow(i64 n, i64 k) {
if (!Valid(n, k)) return 0;
return PermSlow(n, k) * InvFact(k);
}
static ModInt Perm(i64 n, i64 k) {
if (!Valid(n, k)) return 0;
#if DEBUG
assert(n <= kMaxCacheSize &&
"n is too large. If k is small, consider using PermSlow.");
#endif
return Fact(n) * InvFact(n - k);
}
static ModInt PermSlow(i64 n, i64 k) {
if (!Valid(n, k)) return 0;
ModInt p = 1;
for (i64 i = 0; i < k; ++i) {
p *= (n - i);
}
return p;
}
private:
static bool Valid(i64 n, i64 k) { return 0 <= n && 0 <= k && k <= n; }
i32 n_;
inline static std::vector<ModInt> fact_;
inline static std::vector<ModInt> inv_fact_;
inline static std::vector<ModInt> inv_;
static const i64 kMaxCacheSize = 10000000;
};
#define DEFINE(op) \
template <i32 Mod, typename T> \
ModInt<Mod> operator op(const T& t, const ModInt<Mod>& m) { \
return ModInt<Mod>(t) op m; \
}
BIN_OPS(DEFINE)
CMP_OPS(DEFINE)
#undef DEFINE
template <i32 Mod>
std::ostream& operator<<(std::ostream& out, const ModInt<Mod>& m) {
out << m.value();
return out;
}
#endif
#include <boost/hana/functional/fix.hpp>
template <typename T, typename = void>
struct is_dereferenceable : std::false_type {};
template <typename T>
struct is_dereferenceable<T, std::void_t<decltype(*std::declval<T>())>>
: std::true_type {};
template <typename T, typename = void>
struct is_iterable : std::false_type {};
template <typename T>
struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>())),
decltype(std::end(std::declval<T>()))>>
: std::true_type {};
template <typename T, typename = void>
struct is_applicable : std::false_type {};
template <typename T>
struct is_applicable<T, std::void_t<decltype(std::tuple_size<T>::value)>>
: std::true_type {};
template <typename T, typename... Ts>
void debug(const T& value, const Ts&... args);
template <typename T>
void debug(const T& v) {
if constexpr (is_dereferenceable<T>::value) {
std::cerr << "{";
if (v) {
debug(*v);
} else {
std::cerr << "nil";
}
std::cerr << "}";
} else if constexpr (is_iterable<T>::value &&
!std::is_same<T, std::string>::value) {
std::cerr << "{";
for (auto it = std::begin(v); it != std::end(v); ++it) {
if (it != std::begin(v)) std::cerr << ", ";
debug(*it);
}
std::cerr << "}";
} else if constexpr (is_applicable<T>::value) {
std::cerr << "{";
std::apply([](const auto&... args) { debug(args...); }, v);
std::cerr << "}";
} else {
std::cerr << v;
}
}
template <typename T, typename... Ts>
void debug(const T& value, const Ts&... args) {
debug(value);
std::cerr << ", ";
debug(args...);
}
#if DEBUG
#define dbg(...) \
do { \
cerr << #__VA_ARGS__ << ": "; \
debug(__VA_ARGS__); \
cerr << " (L" << __LINE__ << ")\n"; \
} while (0)
#else
#define dbg(...)
#endif
void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
std::cin >> value;
read_from_cin(args...);
}
#define rd(type, ...) \
type __VA_ARGS__; \
read_from_cin(__VA_ARGS__);
#define ints(...) rd(int, __VA_ARGS__);
#define strings(...) rd(string, __VA_ARGS__);
// Strings used for yes/no questions. Defined as variables so that it can be
// adjusted for each contest site.
const char *yes_str = "Yes", *no_str = "No";
template <typename T>
void write_to_cout(const T& value) {
if constexpr (std::is_same<T, bool>::value) {
std::cout << (value ? yes_str : no_str);
} else if constexpr (is_iterable<T>::value &&
!std::is_same<T, std::string>::value) {
for (auto it = std::begin(value); it != std::end(value); ++it) {
if (it != std::begin(value)) std::cout << " ";
std::cout << *it;
}
} else {
std::cout << value;
}
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
write_to_cout(value);
std::cout << ' ';
write_to_cout(args...);
}
#define wt(...) \
do { \
write_to_cout(__VA_ARGS__); \
cout << '\n'; \
} while (0)
#define all(x) (x).begin(), (x).end()
#define eb(...) emplace_back(__VA_ARGS__)
#define pb(...) push_back(__VA_ARGS__)
#define dispatch(_1, _2, _3, name, ...) name
#define as_i64(x) \
( \
[] { \
static_assert( \
std::is_integral< \
typename std::remove_reference<decltype(x)>::type>::value, \
"rep macro supports std integral types only"); \
}, \
static_cast<int64_t>(x))
#define rep3(i, a, b) for (int64_t i = as_i64(a); i < as_i64(b); ++i)
#define rep2(i, n) rep3(i, 0, n)
#define rep1(n) rep2(_loop_variable_, n)
#define rep(...) dispatch(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep3(i, a, b) for (int64_t i = as_i64(b) - 1; i >= as_i64(a); --i)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep1(n) rrep2(_loop_variable_, n)
#define rrep(...) dispatch(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define each3(k, v, c) for (auto&& [k, v] : c)
#define each2(e, c) for (auto&& e : c)
#define each(...) dispatch(__VA_ARGS__, each3, each2)(__VA_ARGS__)
template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
for (T& vi : v) is >> vi;
return is;
}
template <typename T, typename U>
std::istream& operator>>(std::istream& is, std::pair<T, U>& p) {
is >> p.first >> p.second;
return is;
}
template <typename T, typename U>
bool chmax(T& a, U b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename T, typename U>
bool chmin(T& a, U b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <typename T, typename U>
auto max(T a, U b) {
return a > b ? a : b;
}
template <typename T, typename U>
auto min(T a, U b) {
return a < b ? a : b;
}
template <typename T>
auto max(const T& v) {
return *std::max_element(v.begin(), v.end());
}
template <typename T>
auto min(const T& v) {
return *std::min_element(v.begin(), v.end());
}
template <typename T>
int64_t sz(const T& v) {
return std::size(v);
}
template <typename T>
int64_t popcount(T i) {
return std::bitset<std::numeric_limits<T>::digits>(i).count();
}
template <typename T>
bool hasbit(T s, int i) {
return std::bitset<std::numeric_limits<T>::digits>(s)[i];
}
template <typename T, typename U>
auto div_floor(T n, U d) {
if (d < 0) {
n = -n;
d = -d;
}
if (n < 0) {
return -((-n + d - 1) / d);
}
return n / d;
};
template <typename T, typename U>
auto div_ceil(T n, U d) {
if (d < 0) {
n = -n;
d = -d;
}
if (n < 0) {
return -(-n / d);
}
return (n + d - 1) / d;
}
template <typename T>
bool even(T x) {
return x % 2 == 0;
}
std::array<std::pair<int64_t, int64_t>, 4> adjacent(int64_t i, int64_t j) {
return {{{i + 1, j}, {i, j + 1}, {i - 1, j}, {i, j - 1}}};
}
bool inside(int64_t i, int64_t j, int64_t I, int64_t J) {
return 0 <= i && i < I && 0 <= j && j < J;
}
template <typename T>
void sort(T& v) {
return std::sort(v.begin(), v.end());
}
template <typename T, typename Compare>
void sort(T& v, Compare comp) {
return std::sort(v.begin(), v.end(), comp);
}
template <typename T>
void reverse(T& v) {
return std::reverse(v.begin(), v.end());
}
template <typename T>
typename T::value_type accumulate(const T& v) {
return std::accumulate(v.begin(), v.end(), typename T::value_type());
}
// big = 2305843009213693951 = 2^61-1 ~= 2.3*10^18
const int64_t big = std::numeric_limits<int64_t>::max() / 4;
using i64 = int64_t;
using i32 = int32_t;
template <typename T>
using low_priority_queue =
std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <typename T>
using V = std::vector<T>;
template <typename T>
using VV = V<V<T>>;
void Main();
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout << std::fixed << std::setprecision(20);
Main();
return 0;
}
const auto& Fix = boost::hana::fix;
using namespace std;
#define int i64
using mint = ModInt<>;
using S = pair<mint, mint>;
S op(S a, S b) { return {a.first + b.first, a.second + b.second}; };
S e() { return {0, 0}; }
using F = mint;
S mapping(F f, S x) { return {x.first + f * x.second, x.second}; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }
using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
void Main() {
ints(n);
V<int> s(n), c(n);
cin >> s >> c;
Graph<int> g(n);
rep(n - 1) {
ints(a, b);
--a, --b;
g.AddEdge(a, b);
g.AddEdge(b, a);
}
HeavyLightDecomposition hld(g);
segtree t(n);
rep(i, n) t.set(hld.Index(i), {s[i], c[i]});
ints(q);
rep(q) {
ints(k);
if (k == 0) {
ints(x, y, z);
--x, --y;
each(l, r, hld.Query(x, y, true)) t.apply(l, r, z);
} else {
ints(x, y);
--x, --y;
mint ans = 0;
each(l, r, hld.Query(x, y, true)) ans += t.prod(l, r).first;
wt(ans);
}
}
}