佢嘅夢想，伴隨住 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