\(\lbrack L,R\rbrack\) で \(L\) 以上 \(R\) 以下の整数全体を表すこととします。

\(\displaystyle\omega=(\omega _ 1,\omega _ 2,\ldots,\omega _ M)\in\Omega=\prod _ {i=1} ^ M\lbrack L _ i,R _ i\rbrack\) を \(i\) 回目 \((1\le i\le M)\) の操作が \(\omega _ i\) である一連の操作に対応させます（どの \(\omega\) も等しい確率で起こります）。 標本空間を \(\Omega\) とする確率変数 \(X _ {i,j}\ (0\le i\le M,1\le j\le N)\) を \(i\) 回目の操作の直後に \(j\) 番目の皿に入っている石の個数として定めます（\(i=0\) のとき、\(X _ {i,j}=A _ j\) とします）。

求めたいものは操作が終わったあと各皿に入っている石の個数の期待値 \(E\lbrack X _ {M,j}\rbrack\ (1\le j\le N)\) です。

\(1\le i\le M\) に対して、\(X _ {i,j}\) は

• \(j\notin\lbrack L _ i,R _i\rbrack\) のとき \(X _ {i,j}=X _ {i-1,j}\)
• \(j\in\lbrack L _ i,R _ i\rbrack\) かつ \(\omega _ i\ne j\) のとき \(X _ {i,j}=0\)
• \(j\in\lbrack L _ i,R _ i\rbrack\) かつ \(\omega _ i=j\) のとき \(\displaystyle X _ {i,j}=\sum _ {k=L _ i} ^ {R _ i}X _ {i - 1,k}\)

です。 ここから \(X _ {i.j}\) の期待値について考えると、

• \(j\notin\lbrack L _ i,R _i\rbrack\) のとき \(E\lbrack X _ {i,j}\rbrack=E\lbrack X _ {i-1,j}\rbrack\)
• \(j\in\lbrack L _ i,R _i\rbrack\) のとき \(\displaystyle E\lbrack X _ {i,j}\rbrack=\dfrac1{R _ i-L _ i+1}E\left\lbrack\sum _ {k=L _ i} ^ {R _ i}X _ {i-1,k}\right\rbrack=\dfrac1{R _ i-L _ i+1}\sum _ {k=L _ i} ^ {R _ i}E\lbrack X _ {i-1,k}\rbrack\)（期待値の線形性より）

となります。

よって、\(E\lbrack X _ {i,j}\rbrack\ (1\le j\le N)\) を区間和・区間代入を処理する遅延セグメント木で管理し、インラインで更新を行うことでこの問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <optional>
#include <atcoder/lazysegtree>
#include <atcoder/modint>

int main() {
    using namespace std;
    using modint = atcoder::static_modint<998244353>;
    // (区間の長さ, 区間の総和) を管理する遅延セグメント木
    using segtree = atcoder::lazy_segtree<
        pair<unsigned, modint>,
        [](const auto& lhs, const auto& rhs){return make_pair(lhs.first + rhs.first, lhs.second + rhs.second);},
        []{return pair<unsigned, modint>{};},
        optional<modint>,
        [](const auto& a, const auto& b){return a ? make_pair(b.first, b.first * *a) : b;},
        [](const auto& a, const auto& b){return a ? a : b;},
        []{return nullopt;}
    >;

    unsigned N, M;
    cin >> N >> M;
    segtree expected_value(N);
    for (unsigned i{}, A; i < N; ++i) {
        cin >> A;
        expected_value.set(i, {1, A});
    }
    for (unsigned i{}, L, R; i < M; ++i) {
        cin >> L >> R;
        --L; // 0-indexed 半開区間にする
        const auto sum{expected_value.prod(L, R).second}; // 区間の総和を求めて
        expected_value.apply(L, R, sum / (R - L)); // 全体に代入
    }

    for (unsigned i{}; i < N; ++i)
        cout << expected_value.get(i).second.val() << " ";
    cout << endl;
    return 0;
}