Il suo sogno, insieme al Treno Espresso nella Città C, sfrecciò ruggendo attraverso la stazione in cui stava aspettando, lasciandolo indietro da solo.

La Città C ha aperto una nuova linea della metropolitana con $n$ stazioni. La $i$-esima stazione ha livello $1 \le a_i \le k$, che rappresenta l'importanza della stazione. In generale, più alto è il livello di una stazione, più treni vi si fermano.

La Città C prevede di attivare $m$ servizi ferroviari sulla nuova linea della metropolitana. Il $i$-esimo servizio ha un punto di scambio $p_i$ e due parametri di livello $x_i$ e $y_i$, i quali indicano che i treni di quel servizio si fermeranno in tutte le stazioni di livello almeno $x_i$ dalla $1$-ª stazione alla $p_i$-esima stazione, e in tutte le stazioni di livello almeno $y_i$ dalla $(p_i + 1)$-esima stazione alla $n$-esima stazione. Più formalmente, si fermano in tutte le stazioni $j$ che soddisfano almeno una delle seguenti condizioni:

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

Consideriamo alcuni esempi:

• Se $x_i = y_i = 1$, i treni si fermeranno in ogni stazione. Questo tipo di servizio ferroviario è noto anche come Servizio Locale (Local Service).
• Se $x_i = y_i = k$, i treni si fermeranno solo nelle stazioni di livello $k$. Questo tipo di servizio ferroviario è noto anche come Espresso Limitato (Limited Express) o Treno di Riferimento (Benchmark Train).
• Se $x_i = 1, y_i = k$, il servizio è un Servizio Locale tra $1$ e $p_i$, e un Espresso Limitato tra $(p_i + 1)$ e $n$. Questo potrebbe essere il Servizio Diretto (Through Service) che si ferma in ogni stazione del centro e accelera in periferia.

Due stazioni distinte sono direttamente raggiungibili se almeno un servizio ferroviario si ferma in entrambe le stazioni. Chiamiamo efficiente la linea della metropolitana se tutte le coppie $(i, j)$ di stazioni distinte con lo stesso livello ($a_i = a_j$) sono direttamente raggiungibili.

Ti vengono dati $p_1, \dots, p_m$ e $x_1, \dots, x_m$. Calcola il numero di possibili configurazioni di $y_1, \dots, y_m$, composte da interi positivi compresi tra $1$ e $k$, tali che la linea della metropolitana sia efficiente. Poiché il numero potrebbe essere grande, stampa la risposta modulo $998\,244\,353$.

Input

La prima riga contiene tre interi $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$) e $k$ ($1 \le k \le 500$), che indicano il numero di stazioni, il numero di servizi ferroviari e il limite superiore dei livelli delle stazioni. NON è garantito che ci sia almeno una stazione per ciascun livello.

La seconda riga contiene $n$ interi $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), che indicano il livello di ciascuna stazione.

Le successive $m$ righe descrivono i servizi ferroviari. La $i$-esima di queste righe contiene due interi $p_i$ ($1 \le p_i < n$) e $x_i$ ($1 \le x_i \le k$), che indicano due dei parametri del $i$-esimo servizio ferroviario.

Output

Stampa un intero che rappresenta il numero di possibili array $y_1, \dots, y_m$, modulo $998\,244\,353$.

Esempi

Input 1

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

Output 1

48

Spiegazione

Spiegazione dell'Esempio 1: Di seguito è riportata l'illustrazione di una possibile configurazione, $y = [2, 3, 4]$:

Illustrazione dell'Esempio 1

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

Input 2

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

Output 2

80

Input 3

4 2 10
3 7 2 5
1 4
3 3

Output 3

100