#P18287. Twenty-two

Twenty-two

Twenty-two

给定长度为 nn 的序列 a1,a2,…,ana_1,a_2,\ldots,a_n。有两类操作:

  1. 给定 cc,对所有 1≤i≤n1\le i\le n,令 ai←min⁡(ai,c)a_i\leftarrow\min(a_i,c)。
  2. 给定 l,r,cl,r,c,对所有 l≤i≤rl\le i\le r,令 ai←max⁡(ai,c)a_i\leftarrow\max(a_i,c)。

一共有 mm 个第 1 类操作和 kk 个第 2 类操作。每个操作都要恰好执行一次,但可以任意安排执行顺序,共有 (m+k)!(m+k)! 种操作排列。不同的操作排列可能得到相同的最终序列。

求可能得到的不同最终序列的数量,对 998244353998244353 取模。

输入格式

第一行包含三个整数 n,m,kn,m,k(1≤n,m,k≤1501\le n,m,k\le150),分别表示序列长度、第 1 类操作数和第 2 类操作数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤n1\le a_i\le n),表示初始序列。

第三行包含 mm 个整数(每个都在 [1,n][1,n] 内),依次给出每个第 1 类操作的参数 cc。

接下来 kk 行,每行包含三个整数 l,r,cl,r,c(1≤l≤r≤n1\le l\le r\le n,1≤c≤n1\le c\le n),描述一个第 2 类操作。

输出格式

输出一行一个整数,表示不同最终序列数量对 998244353998244353 取模的结果。

样例

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