他的夢想，伴隨著 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$。請計算有多少種可能的 $y_1, \dots, y_m$ 方案（由 $1$ 到 $k$ 之間的正整數組成），使得該地鐵線路是高效的。由於答案可能很大，請輸出答案模 $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$ 行包含兩個整數 $p_i$ ($1 \le p_i < n$) 和 $x_i$ ($1 \le x_i \le k$)，表示第 $i$ 種列車服務的兩個參數。

輸出格式

輸出一個整數，表示可能的陣列 $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