CF1327F.AND Segments

You are given three integers $n$, $k$, $m$ and $m$ conditions $(l_1, r_1, x_1), (l_2, r_2, x_2), \dots, (l_m, r_m, x_m)$.

Calculate the number of distinct arrays $a$, consisting of $n$ integers such that:

• $0 \le a_i \lt 2^k$ for each $1 \le i \le n$;
• bitwise AND of numbers $a[l_i] \& a[l_i + 1] \& \dots \& a[r_i] = x_i$ for each $1 \le i \le m$.

Two arrays $a$ and $b$ are considered different if there exists such a position $i$ that $a_i \neq b_i$.

The number can be pretty large so print it modulo $998244353$.

给你三个整数 $n$、$k$、$m$，以及 $m$ 个条件 $(l_1, r_1, x_1), (l_2, r_2, x_2), \dots, (l_m, r_m, x_m)$。

请计算满足以下条件的、由 $n$ 个整数组成的不同数组 $a$ 的个数：

• 对每个 $1 \le i \le n$，均有 $0 \le a_i \lt 2^k$；
• 对每个 $1 \le i \le m$，子数组 $a[l_i] \& a[l_i + 1] \& \dots \& a[r_i]$ 的按位与结果等于 $x_i$。

若存在某个位置 $i$ 使得 $a_i \neq b_i$，则称两个数组 $a$ 和 $b$ 不同。

答案可能非常大，请对 $998244353$ 取模后输出。

The first line contains three integers $n$, $k$ and $m$ ($1 \le n \le 5 \cdot 10^5$, $1 \le k \le 30$, $0 \le m \le 5 \cdot 10^5$) — the length of the array $a$, the value such that all numbers in $a$ should be smaller than $2^k$ and the number of conditions, respectively.

Each of the next $m$ lines contains the description of a condition $l_i$, $r_i$ and $x_i$ ($1 \le l_i \le r_i \le n$, $0 \le x_i \lt 2^k$) — the borders of the condition segment and the required bitwise AND value on it.

第一行包含三个整数 $n$、$k$ 和 $m$（$1 \le n \le 5 \cdot 10^5$，$1 \le k \le 30$，$0 \le m \le 5 \cdot 10^5$），分别表示数组 $a$ 的长度、要求数组 $a$ 中所有数均小于 $2^k$ 的参数 $k$，以及约束条件的个数。

接下来的 $m$ 行每行描述一个约束条件，包含 $l_i$、$r_i$ 和 $x_i$（$1 \le l_i \le r_i \le n$，$0 \le x_i \lt 2^k$），分别表示该约束条件对应区间的左右端点以及该区间上所有元素按位与（bitwise AND）运算结果的要求值。

Print a single integer — the number of distinct arrays $a$ that satisfy all the above conditions modulo $998244353$.

输出一个整数——满足上述所有条件的不同数组 $a$ 的个数对 $998244353$ 取模的结果。

You can recall what is a bitwise AND operation here.

In the first example, the answer is the following arrays: $[3, 3, 7, 6]$, $[3, 7, 7, 6]$ and $[7, 3, 7, 6]$.

你可以在这里回顾什么是按位与（bitwise AND）运算：链接。

在第一个例子中，答案是以下数组：$[3, 3, 7, 6]$、$[3, 7, 7, 6]$ 和 $[7, 3, 7, 6]$。