题目描述

在这个问题中，由给出 $N$、$M$ 和 $Q$ 三个正整数。现在我们有一个长度为 $N$ 的整数序列：$a_1,\\ldots,a_N$。初始时，$a_i = 0 (1 \\leq i \\leq N)$。还有一个变量 $ans$，初始时为 $0$。现在，你将会获得 $Q$ 个查询，每个查询有以下几种形式：

• Type 1：

  • $t_i (=1)$ $l_i$ $r_i$ $v_i$

  • 对于每个 $j = l_i,\\ldots,r_i$，都有 $a_j := \\min(a_j,v_i)$。

• Type 2：

  • $t_i (=2)$ $l_i$ $r_i$ $v_i$

  • 对于每个 $j = l_i,\\ldots,r_i$，都有 $a_j := \\max(a_j,v_i)$。

• Type 3：

  • $t_i (=3)$ $l_i$ $r_i$

  • 计算 $a_{l_i} + \\ldots + a_{r_i}$ 的结果，并将其加到 $ans$ 中。

请输出最终的 $ans$ 的值。

在每个查询中，保证 $1$ $\\leq$ $l_i$ $\\leq$ $r_i$ $\\leq$ $N$。而在 Type 1 和 Type 2 中，保证 $0$ $\\leq$ $v_i$ $\\leq$ $M-1$。

约束条件

• $1 \\leq N,M,Q \\leq 200000$
• 输入的所有数字均为整数。

输入

输入以以下格式从标准输入给出：

$N$ $M$ $Q$

输出

输出答案。

示例输入 1

1 2 2

示例输出 1

1

有 $25$ 个有效的输入，其中只有一个结果 $ans$ 为正值，如下所示：

$t_1 = 2, l_1 = 1, r_1 = 1, v_1 = 1, t_2 = 3, l_2 = 1, r_2 = 1$

在这种情况下，$ans$ 的值为 $1$，因此答案是 $1$。

示例输入 2

3 1 4

示例输出 2

0

示例输入 3

111 112 113

示例输出 3

451848306