考虑一个长度为 $n$ 的序列，记作 $a_1, a_2, \dots, a_n$。计划进行 $q$ 次操作，每种操作属于以下两种类型之一：

1. 给定 $c$，对于所有 $1 \le i \le n$，令 $a_i \leftarrow \min(a_i, c)$。
2. 给定 $\ell, r$ 和 $c$，对于所有 $\ell \le i \le r$，令 $a_i \leftarrow \max(a_i, c)$。

我们将恰好执行每种操作各一次。然而，操作的顺序可以是任意的：共有 $q!$ 种可能的顺序。对于每种顺序，将这些操作按该顺序应用于初始序列 $a_1, a_2, \dots, a_n$ 将得到一个最终序列。问题是，有多少种不同的最终序列，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含三个整数 $n, m$ 和 $k$：序列的长度、类型 1 操作的数量以及类型 2 操作的数量 ($1 \le n, m, k \le 150$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$：初始序列 ($1 \le a_i \le n$)。

第三行包含 $m$ 个整数：每个类型 1 操作的参数 $c$ ($1 \le c \le n$)。

接下来的 $k$ 行描述类型 2 的操作。每行包含三个整数 $\ell, r$ 和 $c$：操作的参数 ($1 \le \ell \le r \le n; 1 \le c \le n$)。

输出格式

输出一个正整数：不同最终序列的数量，对 $998\,244\,353$ 取模。

样例

样例输入 1

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

样例输出 1

6