구간 병렬 유니온 파인드

$N$개의 정점과 $0$개의 간선을 가진 무방향 그래프 $G$와 정수 수열 $x_0, \ldots, x_{N-1}$이 있다. 다음 형식의 쿼리 $Q$개를 처리한다:

• $k$ $a$ $b$: 각 $i=0,1,\ldots,k-1$에 대해 $G$에 간선 $(a + i, b + i)$을 추가한다.

각 쿼리를 처리한 후, 아래에서 정의하는 $X$을 $998244353$로 나눈 나머지를 출력한다:

• 각 $0\leq i,j \leq N-1$에 대해, 정점 $i$과 $j$가 $G$에서 같은 연결 요소에 속하면 $\mathrm{same}(i,j)$을 $1$로 정의하고, 그렇지 않으면 $0$으로 정의한다.
• $X = \sum_{0\leq i<j\leq N-1}\mathrm{same}(i,j)x_ix_j$을 정의한다.

제한 조건

• $1 \leq N \leq 500000$
• $1 \leq Q \leq 500000$
• $0 \leq x_i < 998244353$
• $0 \leq k\leq N$
• $0 \leq a,b \leq N-k$

$N$ $Q$
$x_0$ $\cdots$ $x_{N-1}$
$k$ $a$ $b$
$\vdots$
$k$ $a$ $b$

각 쿼리를 처리한 후, 아래에서 정의하는 $X$을 $998244353$로 나눈 나머지를 출력한다: