Su sueño, junto con el Tren Expreso de la Ciudad C, pasó rugiendo por la estación en la que él esperaba, dejándolo atrás como al único.

La Ciudad C inauguró una nueva línea de metro con $n$ estaciones. La $i$-ésima estación tiene un nivel $1 \le a_i \le k$, que representa la importancia de la estación. En general, cuanto mayor es el nivel de una estación, más trenes se detienen allí.

La Ciudad C planea abrir $m$ servicios de tren en la nueva línea de metro. El $i$-ésimo servicio tiene un punto de cambio $p_i$ y dos parámetros de nivel $x_i$ e $y_i$, lo que indica que los trenes de ese servicio se detendrán en todas las estaciones con nivel de al menos $x_i$ desde la $1$-ª estación hasta la $p_i$-ésima estación, y en todas las estaciones con nivel de al menos $y_i$ desde la $(p_i + 1)$-ésima estación hasta la $n$-ésima estación. Más formalmente, se detienen en todas las estaciones $j$ que satisfacen al menos una de las siguientes condiciones:

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

Consideremos algunos ejemplos:

• Si $x_i = y_i = 1$, los trenes se detendrán en todas las estaciones. Este tipo de servicio de tren también se conoce como Servicio Local (Local Service).
• Si $x_i = y_i = k$, los trenes solo se detendrán en las estaciones con nivel $k$. Este tipo de servicio de tren también se conoce como Expreso Limitado (Limited Express) o Tren de Referencia (Benchmark Train).
• Si $x_i = 1, y_i = k$, el servicio es un Servicio Local entre $1$ y $p_i$, y un Expreso Limitado entre $(p_i + 1)$ y $n$. Este podría ser el Servicio Directo (Through Service) que se detiene en cada estación del centro y acelera en los suburbios.

Dos estaciones distintas son directamente alcanzables si al menos un servicio de tren se detiene en ambas estaciones. Llamamos eficiente a la línea de metro si todos los pares $(i, j)$ de estaciones distintas con el mismo nivel ($a_i = a_j$) son directamente alcanzables.

Se te dan $p_1, \dots, p_m$ y $x_1, \dots, x_m$. Calcula el número de configuraciones posibles de $y_1, \dots, y_m$, formadas por enteros positivos entre $1$ y $k$, tales que la línea de metro sea eficiente. Como el número puede ser grande, imprime la respuesta módulo $998\,244\,353$.

Entrada

La primera línea contiene tres enteros $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$) y $k$ ($1 \le k \le 500$), que indican el número de estaciones, el número de servicios de tren y el límite superior de los niveles de las estaciones. NO se garantiza que haya al menos una estación con cada nivel.

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), que indican el nivel de cada estación.

Las siguientes $m$ líneas describen los servicios de tren. La $i$-ésima de estas líneas contiene dos enteros $p_i$ ($1 \le p_i < n$) y $x_i$ ($1 \le x_i \le k$), que indican dos de los parámetros del $i$-ésimo servicio de tren.

Salida

Imprime un entero que represente el número de arreglos posibles $y_1, \dots, y_m$, módulo $998\,244\,353$.

Ejemplos

Entrada 1

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

Salida 1

48

Explicación

Explicación del Ejemplo 1: A continuación se muestra la ilustración de una configuración posible, $y = [2, 3, 4]$:

Ilustración del Ejemplo 1

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

Entrada 2

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

Salida 2

80

Entrada 3

4 2 10
3 7 2 5
1 4
3 3

Salida 3

100