Background

___出了一道语法入门题

输入一个整数 \(N\)，输出 \(N\)

Description

他制作了 \(N\) 组数据，第 \(i\) 组数据的输入为 \(a_i\)。

场上有 \(M\) 位在考试的选手，第 \(i\) 个人在看完题后一眼秒出了一个 \(O(n^{b_i})\) 的优秀做法。

___作为监考人员来到考场，他发现有 \(Q\) 个时间依次发生：

• 1 l r k 第 \([l,r]\) 个选手同时想到了一个新做法，复杂度变成了 \(O(n^k)\)，不保证做法比原来优。
• 2 l r ___随机钦定了一个编号在 \([l,r]\) 中的选手，他想知道在 \(N\) 组数据中随机钦定一组给这个选手测试得到的时间消耗的期望是多少。

请注意，我们认为对于输入 \(x\)，一个 \(O(n^y)\) 的算法的时间消耗就是 \(x^y\)。

Input Format

第一行三个正整数 \(N,M,Q\)。

第二行 \(N\) 个正整数表示 \(a_i\)。

第三行 \(M\) 个正整数表示 \(b_i\)。

接下来 \(Q\) 行，每行格式见题面描述。

Output Format

对于每个询问操作，输出一行表示答案对 \(998244353\) 取模后的结果。

Sample 1

Input

6 6 2
1 1 4 5 1 4
1 2 3 4 5 6
1 1 3 1
2 1 3

Output

665496238

explanation

\(\frac{1+1+4+5+1+4}{6}=665496238 \pmod {998244353}\)

Sample 2

Input

8 9 10
2 5 7 8 9 9 5 1
10 9 3 6 8 1 7 3 8
2 2 5
1 2 8 9
2 9 9
2 4 9
2 8 9
1 1 8 9
2 2 8
1 2 8 4
2 3 9
2 1 3

Output

158037188
263238209
891860370
440762635
618287061
821942545
705219604

explanation

500 - Internal Server Error

Limitation

对于所有数据，\(1\leq N,M,Q\leq 10^5\)，对于任意时刻 \(1\leq a_i,b_i\leq 10^5\)。

Subtask 1[5 pts]

不存在操作 \(2\)。

Subtask 2[5 pts]

\(N,M,Q,a_i,b_i\leq 100\)。

Subtask 3[10 pts]

\(N,M,Q,a_i,b_i\leq 1000\)。

Subtask 4[25 pts]

\(N,a_i,b_i\leq 1000\)。

Subtask 5[15 pts]

不存在操作 \(1\)。

Subtask 6[40 pts]

无特殊限制。