Background

Welcome to the Planetarium.

Here, there is beautiful infinite radiance that never disappears at any time.

The sky full of stars is waiting for everyone to come.

Problem Description

To study the stars in the Planetarium, Mengmei used a giant projector—Yena—to arrange the stars into a sequence, and then built a segment tree on this star sequence.

This is a segment tree that maintains interval sums. The weight of each node is the sum of the weights of all stars in the interval corresponding to that node. Sometimes Mengmei starts a journey in the starry sky from the root node of this segment tree. When she is about to enter a child node, suppose the sums of weights of the intervals corresponding to the left and right subtrees are $sum_l$ and $sum_r$, and the weight of the current node is $sum_{cur}$. Mengmei will enter the left subtree with probability $\frac{sum_l}{sum_{cur}}$, otherwise she enters the right subtree.

During the journey, Mengmei adds up the weights of the nodes she passes through. Now she wants you to design an algorithm to compute the expected value of this accumulated weight.

Of course, if the stars never change, Mengmei would find it very boring. So she will issue some commands. Each command is: for the stars with indices in $[l,r]$, increase their weights by $v$. However, since all the staff in the museum have left, no one taught Mengmei how to maintain lazy tags on the segment tree, so each of her commands will update all segment tree nodes in real time.

To avoid differences in segment tree implementations, here is part of the code Mengmei uses to maintain this problem:

const int N = 100010, MOD = 998244353;
int a[N], sum[N << 2];
#define lson (o << 1)
#define rson (o << 1 | 1)
void pushup(int o) {
	sum[o] = (sum[lson] + sum[rson]) % MOD;
}
void build(int o, int l, int r) {
	if (l == r) {
		sum[o] = a[l];
	} else {
		int mid = (l + r) >> 1;
		build(lson, l, mid);
		build(rson, mid + 1, r);
		pushup(o);
	}
}
void change(int o, int l, int r, int q, int v) {
	if (l == r) {
		sum[o] = (sum[o] + v) % MOD;
		return;
	}
	int mid = (l + r) >> 1;
	if (q <= mid) change(lson, l, mid, q, v);
	else change(rson, mid + 1, r, q, v);
	pushup(o);
}
void add_to_interval(int l, int r, int v) {
	for (int i = l; i <= r; i ++) {
		change(1, 1, n, i, v);
	}
}

Here, the array a represents the weight of each star, the array sum represents the weight of each segment tree node, and the function add_to_interval represents one operation.

Input Format

The first line contains two integers $n,m$, representing the sequence length and the number of operations.

The second line contains $n$ integers, representing this sequence.

Next, there are $m$ lines, each being one of the following:

$1 \ l \ r \ v$, meaning that all nodes in the interval $[l,r]$ are increased by $v$;

$2$, meaning one query.

Output Format

For each operation $2$, output one answer. Let the answer in lowest terms be $\frac{p}{q}$ (it is guaranteed that $q$ is not a multiple of $998244353$), then output $p\cdot q^{-1}\mod 998244353$.

4 3
1 2 3 4
2
1 1 3 1
2

399297760
844668322

Hint

For $30\%$ of the testdata, it is guaranteed that $1 \leq n,m\leq 100$.

For another $20\%$ of the testdata, all operations of type 1 satisfy $l=r$.

For $100\%$ of the testdata, it is guaranteed that $1\leq n,m \leq 10^5,1 \leq a_i,v \leq 10^9,1\le l\le r\le n$.

The sample answers are actually $\frac{94}{5}$ and $\frac{303}{13}$.

Translated by ChatGPT 5