#include <cstdio>#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1const int maxn = 30005;long long sum[maxn << 2];long long val[maxn << 2];bool lazy[maxn << 2];int n, m;inline long long ceil(long long x, int y) { if (x % y == 0) return x / y; if (x > 0) return x / y + 1; else return x / y;}inline long long floor(long long x, int y) { if (x % y == 0) return x / y; if (x > 0) return x / y; else return x / y - 1;}void PushUp(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void PushDown(int rt, int len) { if (lazy[rt]) { lazy[rt] = 0; lazy[rt << 1] = lazy[rt << 1 | 1] = 1; val[rt << 1] = val[rt << 1 | 1] = val[rt]; sum[rt << 1] = val[rt]*(len - (len >> 1)); sum[rt << 1 | 1] = val[rt]*(len >> 1); }}void build(int l, int r, int rt) { lazy[rt] = 0; val[rt] = 0; if (l == r) { scanf("%lld", ∑[rt]); return; } int mid = (l + r) >> 1; build(lson); build(rson); PushUp(rt);}void update(int L, int R, long long x, int l, int r, int rt) { if (L <= l && r <= R) { val[rt] = x; sum[rt] = x * (r - l + 1); lazy[rt] = 1; return; } PushDown(rt, r - l + 1); int mid = (l + r) >> 1; if (L <= mid) update(L, R, x, lson); if (mid < R) update(L, R, x, rson); PushUp(rt);}long long query(int L, int R, int l, int r, int rt) { if (L <= l && r <= R) { return sum[rt]; } long long ret = 0; PushDown(rt, r - l + 1); int mid = (l + r) >> 1; if (L <= mid) ret += query(L, R, lson); if (mid < R) ret += query(L, R, rson); return ret;}int main() { while (scanf("%d%d", &n, &m) == 2) { build(1, n, 1); long long ori = query(1, n, 1, n, 1); while (m--) { int l, r; scanf("%d%d", &l, &r); long long cur = query(1, n, 1, n, 1), tmp = query(l, r, 1, n, 1); long long x; if (cur <= ori) x = ceil(tmp, r - l + 1); else x = floor(tmp, r - l + 1); update(l, r, x, 1, n, 1); } for (int i = 1; i < n; i++) printf("%lld ", query(i, i, 1, n, 1)); printf("%lldnn", query(n, n, 1, n, 1)); } return 0;}
