白树台学园 (hard version)

题号：NC282546
时间限制：C/C++/Rust/Pascal 8秒，其他语言16秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

本题与 easy version 的区别在于本题每个点的随机区间是给定的，并且有多组针对颜色区间的询问，相对的数据范围也有区别。

题目背景

在一阵诡异的紧张静谧中，她扬起冰雨般的笑容，视线从宫里学长移向路易学长。

「你以为我是大将？真可惜呢。大将的头带，藏在一个绝对安全的家伙头上，也就是——这条。」
会长解开宫里学长的白色头带，翻过来亮出绣好的「将」字。路易学长表情黯然，其他人根本不了解现在是什么状况。
「你懂吧？宫里刚才变成红队的人，然后被白队的圣桥桐香抢走头带，而且他的头带上绣着『将』字。换句话说……」
「红队的大将被淘汰了。」

「——我们赢了。」

题目描述

并非有题目背景。

简要题意

现在给你一个长度为 $n$ 的序列，每个点有一个区间 $[L_i,R_i]$ 表示这个点的颜色在这个里面随机选取。

同时有 $q$ 次操作，每次操作有两种形式，要么是在序列末尾加入一个在区间 $[lt,rt]$ 内随机的数，要么是给定一个颜色区间 $[lt,rt]$ ，表示你需要求出如果只承认颜色区间 $[lt,rt]$ 中的颜色有效，在全局随机一个下标区间的期望颜色数量，对 $998244353$ 取模。
强制在线，具体来讲，你输入的是 $lt'$ 和 $rt'$ ，假设上一次询问的答案为 $lstans$ （不存在则设为 $0$ ），则真正的 $lt=(lt'\ xor\ lstans)\ mod\ m+1,rt=(rt'\ xor\ lstans)\ mod\ m+1$ ，如果 $lt>rt$ ，则交换 $lt,rt$ 。

数据范围

$1\leqslant n,m,q\leqslant 5\times10^5,1\leqslant lt,rt\leqslant m$ 。

$lt',rt'$ 为 long long 范围内的非负整数。

输入描述:

第一行，三个整数 ，分别表示序列长度，值域范围，以及询问次数。
接下来  行，每行两个整数 ，表示第  个点的随机范围。
接下来  行，每行三个整数 ，若 ，则表示在序列末尾加一个数，若 ，则表示询问期望颜色数量，具体可参照题目描述。。

输出描述:

对于每个  操作，输出一行一个整数，表示答案对  取模后的结果。

示例1

输入

复制

输出

复制

465847366
2
532396989

示例2

输入

复制

10 10 20
3 4
2 2
3 3
1 2
1 2
1 6
4 10
4 5
3 4
3 3
1 1432355238 1188125139
2 1495854081 1287747189
1 1031813651 659014611
2 176453019 311972948
1 595152290 1350063891
2 1548786293 657174385
2 537116146 2045708487
2 1181196917 772022214
1 2090978521 1234214707
2 1643803091 1394578160
2 684444582 1196029970
2 1972191771 24965845
1 483722735 474504488
1 795695683 329012153
1 2145759574 1576608400
2 655450311 1424468515
1 553675150 1610608220
2 1325697365 293123810
1 412428424 540843749
2 1807006585 1759479551

输出

复制