SIS Segtree

#include <bits/stdc++.h>
// tiom4eg's precompiler options
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
// Flags
//#define MAXMIN
#define ENDL
#define AVX2
#define PBDS
// IO settings
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0)
// Quick types
#define ll long long
#define ld double
#define ull unsigned long long
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define mi vector <vector <int> >
// Quick functions
#ifdef ENDL
#define endl "\n"
#endif
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define sz(a) a.size()
#define pb push_back
#define mp make_pair
#ifdef MAXMIN
#define min(a, b) ((a < b) ? (a) : (b))
#define max(a, b) ((a > b) ? (a) : (b))
#endif
// Quick fors
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
// Pragmas
#pragma GCC optimize("O3,unroll-loops") // let the chaos begin!
#ifdef AVX2
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
#endif
#pragma GCC comment(linker, "/stack:200000000")
// PBDS
#ifdef PBDS
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>
#define ook order_of_key
#define fbo find_by_order
using namespace __gnu_pbds;
#endif
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
using namespace std;
mt19937 rng(std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
#define int long long
const int INF = 1e9 + 7, R = 1 << 17;

struct segtree {
    struct node { int s, d; };
    vector <node> t;
    void merge(int v) { t[v].s = t[2 * v].s + t[2 * v + 1].s; }
    void tag(int v, int x, int l) { t[v].s = l * x, t[v].d = x; }
    void push(int v, int l) {
        if (t[v].d == -INF) return;
        tag(2 * v, t[v].d, l / 2), tag(2 * v + 1, t[v].d, l / 2);
        t[v].d = -INF;
    }
    void build(vi& a) {
        t.assign(2 * R, {0, -INF});
        FOR(i, 0, sz(a)) t[R + i].s = a[i];
        RFOR(i, R - 1, 1) merge(i);
    }
    void upd(int ql, int qr, int x, int v = 1, int nl = 0, int nr = R) { // set query
        if (qr <= nl || nr <= ql) return;
        if (ql <= nl && nr <= qr) {
            tag(v, x, nr - nl);
            return;
        }
        push(v, nr - nl);
        int nm = (nl + nr) / 2;
        upd(ql, qr, x, v * 2, nl, nm), upd(ql, qr, x, v * 2 + 1, nm, nr);
        merge(v);
    }
    int get(int ql, int qr, int v = 1, int nl = 0, int nr = R) { // sum query
        if (qr <= nl || nr <= ql) return 0;
        if (ql <= nl && nr <= qr) return t[v].s;
        push(v, nr - nl);
        int nm = (nl + nr) / 2;
        return get(ql, qr, v * 2, nl, nm) + get(ql, qr, v * 2 + 1, nm, nr);
    }
} t;

signed main() {
    fastIO;
    int n, m; cin >> n >> m;
    vi a(n); FOR(i, 0, n) cin >> a[i];
    int sum = 0; FOR(i, 0, n) sum += a[i];
    t.build(a);
    FOR(i, 0, m) {
        int l, r; cin >> l >> r, --l;
        int rsum = t.get(l, r);
        ld g = (ld)(rsum) / (r - l);
        int csum = t.get(0, R);
        if (csum <= sum) t.upd(l, r, ceil(g));
        else t.upd(l, r, floor(g));
    }
    FOR(i, 0, n) cout << t.get(i, i + 1) << ' ';
}