Hänen unelmansa, yhdessä kaupungin C pikajunan kanssa, jyrisi sen aseman läpi, jolla hän odotti, jättäen hänet yksin jälkeensä.

Kaupunki C avasi uuden metrolinjan, jolla on $n$ asemaa. $i$-nnellä asemalla on taso $1 \le a_i \le k$, joka kuvaa aseman tärkeyttä. Yleisesti ottaen mitä korkeampi aseman taso on, sitä useampi juna pysähtyy siellä.

Kaupunki C suunnittelee avaavansa $m$ junavuoroa uudelle metrolinjalle. $i$-nnellä vuorolla on vaihtopiste $p_i$ ja kaksi tasoparametria $x_i$ ja $y_i$, jotka ilmaisevat, että kyseisen vuoron junat pysähtyvät kaikilla asemilla, joiden taso on vähintään $x_i$, $1$-sestä asemasta $p_i$-nteen asemaan, sekä kaikilla asemilla, joiden taso on vähintään $y_i$, $(p_i + 1)$-nnestä asemasta $n$-nteen asemaan. Muodollisemmin junat pysähtyvät kaikilla asemilla $j$, jotka toteuttavat vähintään toisen seuraavista ehdoista:

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

Tarkastellaan muutamia esimerkkejä:

• Jos $x_i = y_i = 1$, junat pysähtyvät jokaisella asemalla. Tällaista junavuoroa kutsutaan myös paikallisjunaksi (Local Service).
• Jos $x_i = y_i = k$, junat pysähtyvät vain tason $k$ asemilla. Tällaista junavuoroa kutsutaan myös erikoispikajunaksi (Limited Express) tai vertailujunaksi (Benchmark Train).
• Jos $x_i = 1, y_i = k$, vuoro on paikallisjuna välillä $1$ ja $p_i$ sekä erikoispikajuna välillä $(p_i + 1)$ ja $n$. Tämä voi olla läpikulkuvuoro (Through Service), joka pysähtyy jokaisella asemalla keskustassa ja nopeuttaa kulkuaan esikaupunkialueella.

Kaksi eri asemaa ovat suoraan saavutettavissa, jos vähintään yksi junavuoro pysähtyy molemmilla asemilla. Kutsumme metrolinjaa tehokkaaksi, jos kaikki saman tason ($a_i = a_j$) omaavien eri asemien parit $(i, j)$ ovat suoraan saavutettavissa.

Sinulle annetaan $p_1, \dots, p_m$ ja $x_1, \dots, x_m$. Laske, kuinka monta mahdollista asetelmaa $y_1, \dots, y_m$, jotka koostuvat positiivisista kokonaisluvuista väliltä $1$ ja $k$, on olemassa siten, että metrolinja on tehokas. Koska lukumäärä voi olla suuri, tulosta vastaus modulo $998\,244\,353$.

Syöte

Ensimmäinen rivi sisältää kolme kokonaislukua $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$) ja $k$ ($1 \le k \le 500$), jotka ilmaisevat asemien lukumäärän, junavuorojen lukumäärän ja asemien tasojen ylärajan. EI ole taattua, että jokaisella tasolla on vähintään yksi asema.

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), jotka ilmaisevat kunkin aseman tason.

Seuraavat $m$ riviä kuvaavat junavuorot. Näistä riveistä $i$-s sisältää kaksi kokonaislukua $p_i$ ($1 \le p_i < n$) ja $x_i$ ($1 \le x_i \le k$), jotka ilmaisevat kaksi $i$-nnen junavuoron parametreista.

Tuloste

Tulosta kokonaisluku, joka kuvaa mahdollisten taulukoiden $y_1, \dots, y_m$ lukumäärää modulo $998\,244\,353$.

Esimerkit

Syöte 1

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

Tuloste 1

48

Selitys

Esimerkin 1 selitys: Alla on havainnekuva yhdestä mahdollisesta asetelmasta, $y = [2, 3, 4]$:

Esimerkin 1 havainnekuva

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

Syöte 2

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

Tuloste 2

80

Syöte 3

4 2 10
3 7 2 5
1 4
3 3

Tuloste 3

100