Drømmen hans, sammen med ekspresstoget i By C, dundret gjennom stasjonen han ventet på, og etterlot ham alene tilbake.

By C åpnet en ny T-banelinje med $n$ stasjoner. Den $i$-te stasjonen har nivå $1 \le a_i \le k$, som representerer viktigheten av stasjonen. Generelt gjelder det at jo høyere nivå en stasjon har, desto flere tog stopper der.

By C planlegger å åpne $m$ togtjenester på den nye T-banelinjen. Den $i$-te tjenesten har et byttepunkt $p_i$ og to nivåparametere $x_i$ og $y_i$, som angir at togene på den tjenesten vil stoppe på alle stasjoner med nivå minst $x_i$ fra den $1$-ste stasjonen til den $p_i$-te stasjonen, og på alle stasjoner med nivå minst $y_i$ fra den $(p_i + 1)$-te stasjonen til den $n$-te stasjonen. Mer formelt stopper de på alle stasjoner $j$ som tilfredsstiller minst én av følgende betingelser:

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

La oss se på noen eksempler:

• Hvis $x_i = y_i = 1$, vil togene stoppe på hver stasjon. Denne typen togtjeneste er også kjent som Lokaltog (Local Service).
• Hvis $x_i = y_i = k$, vil togene kun stoppe på stasjoner med nivå $k$. Denne typen togtjeneste er også kjent som Hurtigtog (Limited Express) eller Referansetog (Benchmark Train).
• Hvis $x_i = 1, y_i = k$, er tjenesten et Lokaltog mellom $1$ og $p_i$, og et Hurtigtog mellom $(p_i + 1)$ og $n$. Dette kan være en Gjennomgående tjeneste (Through Service) som stopper på hver stasjon i sentrum og øker farten i forstedene.

To forskjellige stasjoner er direkte nåbare hvis minst én togtjeneste stopper på begge stasjonene. Vi kaller T-banelinjen effektiv hvis alle par $(i, j)$ av forskjellige stasjoner med samme nivå ($a_i = a_j$) er direkte nåbare.

Du får oppgitt $p_1, \dots, p_m$ og $x_1, \dots, x_m$. Beregn antall mulige oppsett av $y_1, \dots, y_m$, bestående av positive heltall mellom $1$ og $k$, slik at T-banelinjen er effektiv. Siden tallet kan være stort, skal du skrive ut svaret modulo $998\,244\,353$.

Inndata

Den første linjen inneholder tre heltall $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$) og $k$ ($1 \le k \le 500$), som angir antall stasjoner, antall togtjenester og den øvre grensen for stasjonenes nivåer. Det er IKKE garantert at det finnes minst én stasjon med hvert nivå.

Den andre linjen inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), som angir nivået til hver stasjon.

De følgende $m$ linjene beskriver togtjenestene. Den $i$-te av disse linjene inneholder to heltall $p_i$ ($1 \le p_i < n$) og $x_i$ ($1 \le x_i \le k$), som angir to av parameterne til den $i$-te togtjenesten.

Utdata

Skriv ut et heltall som representerer antall mulige tabeller $y_1, \dots, y_m$, modulo $998\,244\,353$.

Eksempler

Inndata 1

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

Utdata 1

48

Forklaring

Forklaring av eksempel 1: Nedenfor er illustrasjonen for en mulig konfigurasjon, $y = [2, 3, 4]$:

Illustrasjon av eksempel 1

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

Inndata 2

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

Utdata 2

80

Inndata 3

4 2 10
3 7 2 5
1 4
3 3

Utdata 3

100