题目描述

小 $\alpha$ 给了你一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$。小 $\alpha$ 有若干个操作，操作分为两类：

1. 给定 $c$，令

   $$a_i \leftarrow \min(a_i,c)$$

   对每个 $1\le i\le n$ 执行。

2. 给定 $l,r,c$，令

   $$a_i \leftarrow \max(a_i,c)$$

   对每个 $l\le i\le r$ 执行。

设第一种操作共有 $m$ 个，第二种操作共有 $k$ 个。共有 $(m+k)!$ 种不同的操作顺序。对每种顺序，将这些操作依次作用到初始序列 $a_1,a_2,\ldots,a_n$ 后，都能得到一个最终序列。

请问可能得到多少种不同的最终序列。答案对 $998244353$ 取模。

输入格式

第一行三个正整数 $n,m,k$，表示序列长度、第一种操作的个数和第二种操作的个数。

第二行 $n$ 个整数，表示初始序列 $a_1,a_2,\ldots,a_n$。

第三行 $m$ 个整数，表示所有第一种操作的参数 $c$。

接下来 $k$ 行，每行三个整数 $l,r,c$，表示一个第二种操作。

输出格式

输出一行一个正整数，表示最终序列个数对 $998244353$ 取模后的结果。

样例 0

输入

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

输出

6

数据范围与提示

对于所有数据，保证 $1\le n,m,k\le 150$。