Twenty-two
给定长度为 n 的序列 a1,a2,…,an。有两类操作:
- 给定 c,对所有 1≤i≤n,令 ai←min(ai,c)。
- 给定 l,r,c,对所有 l≤i≤r,令 ai←max(ai,c)。
一共有 m 个第 1 类操作和 k 个第 2 类操作。每个操作都要恰好执行一次,但可以任意安排执行顺序,共有 (m+k)! 种操作排列。不同的操作排列可能得到相同的最终序列。
求可能得到的不同最终序列的数量,对 998244353 取模。
输入格式
第一行包含三个整数 n,m,k(1≤n,m,k≤150),分别表示序列长度、第 1 类操作数和第 2 类操作数。
第二行包含 n 个整数 a1,a2,…,an(1≤ai≤n),表示初始序列。
第三行包含 m 个整数(每个都在 [1,n] 内),依次给出每个第 1 类操作的参数 c。
接下来 k 行,每行包含三个整数 l,r,c(1≤l≤r≤n,1≤c≤n),描述一个第 2 类操作。
输出格式
输出一行一个整数,表示不同最终序列数量对 998244353 取模的结果。
样例
5 2 2
4 1 3 5 2
2 4
1 3 3
2 5 5
6