// >>> TEMPLATES #include using namespace std; using ll = long long; using ld = long double; using i32 = int32_t; using i64 = int64_t; #define int ll #define double ld #define rep(i,n) for (int i = 0; i < (int)(n); i++) #define rep1(i,n) for (int i = 1; i <= (int)(n); i++) #define repR(i,n) for (int i = (int)(n)-1; i >= 0; i--) #define rep1R(i,n) for (int i = (int)(n); i >= 1; i--) #define loop(i,a,B) for (int i = a; i B; i++) #define loopR(i,a,B) for (int i = a; i B; i--) #define all(x) (x).begin(), (x).end() #define allR(x) (x).rbegin(), (x).rend() #define pb push_back #define eb emplace_back #define mp make_pair #define fst first #define snd second auto constexpr INF32 = numeric_limits::max()/2-1; auto constexpr INF64 = numeric_limits::max()/2-1; auto constexpr INF = numeric_limits::max()/2-1; #ifdef LOCAL #include "debug.hpp" #define dump(...) cerr << "[" << setw(3) << __LINE__ << ":" << __FUNCTION__ << "] ", dump_impl(#__VA_ARGS__, __VA_ARGS__) #define say(x) cerr << "[" << __LINE__ << ":" << __FUNCTION__ << "] " << x << endl #define debug if (1) #else #define dump(...) (void)(0) #define say(x) (void)(0) #define debug if (0) #endif template using pque_max = priority_queue; template using pque_min = priority_queue, greater >; template ::value>::type> ostream& operator<<(ostream& os, T const& v) { bool f = true; for (auto const& x : v) os << (f ? "" : " ") << x, f = false; return os; } template ::value>::type> istream& operator>>(istream& is, T &v) { for (auto& x : v) is >> x; return is; } template istream& operator>>(istream& is, pair& p) { return is >> p.first >> p.second; } struct IOSetup { IOSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } iosetup; template struct FixPoint : private F { constexpr FixPoint(F&& f) : F(forward(f)) {} template constexpr auto operator()(T&&... x) const { return F::operator()(*this, forward(x)...); } }; struct MakeFixPoint { template constexpr auto operator|(F&& f) const { return FixPoint(forward(f)); } }; #define MFP MakeFixPoint()| #define def(name, ...) auto name = MFP [&](auto &&name, __VA_ARGS__) template struct vec_impl { using type = vector::type>; template static type make_v(size_t n, U&&... x) { return type(n, vec_impl::make_v(forward(x)...)); } }; template struct vec_impl { using type = T; static type make_v(T const& x = {}) { return x; } }; template using vec = typename vec_impl::type; template auto make_v(Args&&... args) { return vec_impl::make_v(forward(args)...); } template void quit(T const& x) { cout << x << endl; exit(0); } template constexpr bool chmin(T& x, T const& y) { if (x > y) { x = y; return true; } return false; } template constexpr bool chmax(T& x, T const& y) { if (x < y) { x = y; return true; } return false; } template constexpr auto sumof(It b, It e) { return accumulate(b,e,typename iterator_traits::value_type{}); } template int sz(T const& x) { return x.size(); } template int lbd(C const& v, T const& x) { return lower_bound(v.begin(), v.end(), x)-v.begin(); } template int ubd(C const& v, T const& x) { return upper_bound(v.begin(), v.end(), x)-v.begin(); } template int ppt(C const& v, F f) { return partition_point(v.begin(), v.end(), f)-v.begin(); } // <<< // >>> lazy segment tree template struct LazySegtree : Handler { static int32_t btmbit(int64_t x) { return x ? __builtin_ctzll(x) : -1; } // static int32_t btmbit(int32_t x) { return x ? __builtin_ctz(x) : -1; } using Value = typename Handler::Value; using Lazy = typename Handler::Lazy; using Handler::unit_value; // () -> Value using Handler::unit_action; // () -> Lazy using Handler::merge; // (Value,Value) -> Value using Handler::act; // (Lazy,Lazy&,Value&) -> void vector v; vector lz; int n; mutable Lazy tmp; LazySegtree() {} template LazySegtree(T&&... x) { init(forward(x)...); } template ()(0))> void init(int n, F gen) { assert(n >= 0); this->n = n; v.resize(2*n); lz.assign(n, unit_action()); for (int i = 0; i < n; i++) v[n+i] = gen(i); for (int i = n-1; i >= 1; i--) v[i] = merge(v[2*i],v[2*i+1]); } void init(int n) { init(n, [&](int) { return unit_value(); }); } void init(int n, Value const& x) { init(n, [&](int) { return x; }); } void init(vector const& v) { init(v.size(), [&](int i) { return v[i]; }); } int size() const { return n; } void act(Lazy const& x, int i) { act(x, (i < n ? lz[i] : tmp), v[i]); } void flush(int k) { if (n <= k || lz[k] == unit_action()) return; act(lz[k], 2*k); act(lz[k], 2*k+1); lz[k] = unit_action(); } void flush(int l, int r) { for (int p = __lg(l += n), q = __lg(r += n-1); q; --p,--q) { flush(l >> p); flush(r >> q); } } void build(int i) { i += n; i >>= btmbit(i); while (i >>= 1) v[i] = merge(v[2*i],v[2*i+1]); } Value get(int l, int r) { assert(0 <= l); assert(l <= r); assert(r <= n); flush(l,r); Value x = unit_value(), y = unit_value(); for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l&1) x = merge(x,v[l++]); if (r&1) y = merge(v[--r],y); } return merge(x,y); } void apply(int l, int r, Lazy const& x) { assert(0 <= l); assert(l <= r); assert(r <= n); flush(l,r); for (int a = l+n, b = r+n; a < b; a >>= 1, b >>= 1) { if (a&1) act(x, a++); if (b&1) act(x, --b); } build(l); build(r); } Value operator[](int i) const { return get(i); } Value get(int i) const { assert(0 <= i); assert(i < n); Value x = v[i += n]; while (i >>= 1) act(lz[i], tmp, x); return x; } void set(int i, Value const& x) { assert(0 <= i); assert(i < n); for (int p = __lg(i += n); p; --p) flush(i >> p); for (v[i] = x; i >>= 1; ) v[i] = merge(v[2*i],v[2*i+1]); } vector dat() const { vector ret(size()); for (int i = 0; i < size(); i++) ret[i] = get(i); return ret; } }; // <<< struct RangeMinAdd { using Value = int; using Lazy = int; constexpr static Value unit_value() { return INF; } constexpr static Lazy unit_action() { return 0; } constexpr static Value merge(Value x, Value y) { return min(x,y); } static void act(Lazy x, Lazy &y, Value &z) { y += x, z += x; } }; int32_t main() { int n,q; cin >> n >> q; vector a(n); cin >> a; vector> qs; rep (i,q) { char c; int x,y; cin >> c >> x >> y; qs.eb(c,x,y); } reverse(all(qs)); vector b(n); LazySegtree seg(n,0); rep (i,q) { char c; int x,y; tie(c,x,y) = qs[i]; if (c == 'A') { --x; b[x] += y*seg[x]; } if (c == 'B') { --x,--y; seg.apply(x,y+1,+1); } } rep (i,n) b[i] += a[i]*seg[i]; rep (i,n) cout << b[i] << " "; cout << endl; }