#P17980. Efficient Express

Efficient Express

Efficient Express

题目描述

一条线路有按顺序编号为 1,…,n1,\ldots,n 的车站,第 jj 个车站的等级为 aja_j,等级在 11 到 kk 之间。

共有 mm 种列车服务。第 ii 种服务由三个参数 pi,xi,yip_i,x_i,y_i 决定,停靠的车站恰好是:

  • 1≤j≤pi1\le j\le p_i 且 aj≥xia_j\ge x_i 的车站;
  • pi<j≤np_i<j\le n 且 aj≥yia_j\ge y_i 的车站。

两个不同的车站可以直接到达,当且仅当至少有一种列车服务同时停靠这两个车站。

已知所有 aj,pi,xia_j,p_i,x_i。求有多少个有序数组 (y1,…,ym)(y_1,\ldots,y_m),其中 1≤yi≤k1\le y_i\le k,能使任意两个等级相同的不同车站均可以直接到达。答案对 998244353998244353 取模。

输入格式

第一行三个整数 n,m,kn,m,k。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

接下来 mm 行,第 ii 行两个整数 pi,xip_i,x_i。

输出格式

输出一个整数,表示方案数模 998244353998244353 的结果。

数据范围

2≤n≤10002\le n\le1000,1≤m≤10001\le m\le1000,1≤k≤5001\le k\le500。

1≤aj,xi≤k1\le a_j,x_i\le k,1≤pi<n1\le p_i<n。不保证每个等级都出现在车站中,列车的已知参数允许相同。

样例 1

4 3 4
2 3 3 2
1 2
2 2
2 3
48

样例 2

7 3 5
2 4 3 2 4 2 3
2 2
4 3
5 2
80

样例 3

4 2 10
3 7 2 5
1 4
3 3
100

样例 3 中没有等级相同的不同车站,因此全部 10210^2 种选择均合法。