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 < 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$.

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 < 2^k$) — the borders of the condition segment and the required bitwise AND value on it.

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