그의 꿈은 C시의 급행열차와 함께 그가 기다리던 역을 굉음을 내며 스쳐 지나갔고, 그만 홀로 남겨졌다.

C시는 $n$개의 역이 있는 새로운 지하철 노선을 개통했습니다. $i$번째 역은 등급 $1 \le a_i \le k$를 가지며, 이는 역의 중요도를 나타냅니다. 일반적으로 역의 등급이 높을수록 더 많은 열차가 그곳에 정차합니다.

C시는 새 지하철 노선에 $m$개의 열차 운행 계통을 개설할 계획입니다. $i$번째 운행 계통은 전환 지점 $p_i$와 두 개의 등급 매개변수 $x_i$와 $y_i$를 가지는데, 이는 해당 계통의 열차가 $1$번 역부터 $p_i$번 역까지는 등급이 $x_i$ 이상인 모든 역에 정차하고, $(p_i + 1)$번 역부터 $n$번 역까지는 등급이 $y_i$ 이상인 모든 역에 정차함을 의미합니다. 더 엄밀하게 말하면, 열차는 다음 조건 중 적어도 하나를 만족하는 모든 역 $j$에 정차합니다:

• $j \le p_i$이고 $a_j \ge x_i$;
• $j > p_i$이고 $a_j \ge y_i$.

몇 가지 예를 살펴봅시다:

• 만약 $x_i = y_i = 1$이면, 열차는 모든 역에 정차합니다. 이러한 종류의 열차 운행 계통은 완행(Local Service)이라고도 불립니다.
• 만약 $x_i = y_i = k$이면, 열차는 등급이 $k$인 역에만 정차합니다. 이러한 종류의 열차 운행 계통은 특급(Limited Express) 또는 기준 열차(Benchmark Train)라고도 불립니다.
• 만약 $x_i = 1, y_i = k$이면, 이 계통은 $1$번과 $p_i$번 사이에서는 완행이고, $(p_i + 1)$번과 $n$번 사이에서는 특급입니다. 이는 도심에서는 모든 역에 정차하고 교외에서는 속도를 높이는 직통 운행(Through Service)일 수 있습니다.

서로 다른 두 역에 모두 정차하는 열차 운행 계통이 적어도 하나 존재하면, 두 역은 직접 도달 가능하다고 합니다. 같은 등급($a_i = a_j$)을 가진 서로 다른 역들의 모든 쌍 $(i, j)$가 직접 도달 가능할 때, 우리는 이 지하철 노선이 효율적이라고 부릅니다.

$p_1, \dots, p_m$과 $x_1, \dots, x_m$이 주어집니다. 지하철 노선이 효율적이 되도록 하는, $1$ 이상 $k$ 이하의 양의 정수로 이루어진 $y_1, \dots, y_m$의 가능한 배치의 수를 계산하세요. 답이 클 수 있으므로 정답을 $998\,244\,353$으로 나눈 나머지를 출력합니다.

입력

첫 번째 줄에는 역의 수, 열차 운행 계통의 수, 역 등급의 상한을 나타내는 세 정수 $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$), $k$ ($1 \le k \le 500$)가 주어집니다. 각 등급을 가진 역이 적어도 하나씩 존재한다는 보장은 없습니다.

두 번째 줄에는 각 역의 등급을 나타내는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$)이 주어집니다.

다음 $m$개의 줄은 열차 운행 계통을 설명합니다. 이 중 $i$번째 줄에는 $i$번째 열차 운행 계통의 두 매개변수를 나타내는 두 정수 $p_i$ ($1 \le p_i < n$)와 $x_i$ ($1 \le x_i \le k$)가 주어집니다.

출력

가능한 배열 $y_1, \dots, y_m$의 개수를 $998\,244\,353$으로 나눈 나머지를 나타내는 정수를 출력합니다.

예제

입력 1

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

출력 1

48

설명

예제 1 설명: 아래는 가능한 배치 중 하나인 $y = [2, 3, 4]$에 대한 그림입니다:

예제 1 그림

• 운행 계통 1: $p_1 = 1, x_1 = 2, y_1 = 2$;
• 운행 계통 2: $p_2 = 2, x_2 = 2, y_2 = 3$;
• 운행 계통 3: $p_3 = 2, x_3 = 3, y_3 = 4$.

입력 2

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

출력 2

80

입력 3

4 2 10
3 7 2 5
1 4
3 3

출력 3

100