Draumur hans, ásamt hraðlestinni í Borg C, þaut með drunum í gegnum stöðina þar sem hann beið og skildi hann einan eftir.

Borg C opnaði nýja neðanjarðarlestarlínu með $n$ stöðvum. $i$-ta stöðin hefur stig $1 \le a_i \le k$, sem táknar mikilvægi stöðvarinnar. Almennt gildir að því hærra sem stig stöðvar er, því fleiri lestir stoppa þar.

Borg C áformar að opna $m$ lestarþjónustur á nýju neðanjarðarlestarlínunni. $i$-ta þjónustan hefur skiptipunkt $p_i$ og tvo stigstika $x_i$ og $y_i$, sem gefa til kynna að lestir þeirrar þjónustu muni stoppa á öllum stöðvum með stig að minnsta kosti $x_i$ frá $1$-stu stöðinni til $p_i$-tu stöðvarinnar, og á öllum stöðvum með stig að minnsta kosti $y_i$ frá $(p_i + 1)$-tu stöðinni til $n$-tu stöðvarinnar. Formlegra sagt stoppa þær á öllum stöðvum $j$ sem uppfylla að minnsta kosti annað af eftirfarandi:

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

Skoðum nokkur dæmi:

• Ef $x_i = y_i = 1$, munu lestirnar stoppa á hverri stöð. Þessi tegund lestarþjónustu er einnig þekkt sem Staðbundin þjónusta (Local Service).
• Ef $x_i = y_i = k$, munu lestirnar aðeins stoppa á stöðvum með stig $k$. Þessi tegund lestarþjónustu er einnig þekkt sem Takmörkuð hraðlest (Limited Express) eða Viðmiðunarlest (Benchmark Train).
• Ef $x_i = 1, y_i = k$, þá er þjónustan Staðbundin þjónusta á milli $1$ og $p_i$, og Takmörkuð hraðlest á milli $(p_i + 1)$ og $n$. Þetta gæti verið Gegnumstreymisþjónusta (Through Service) sem stoppar á hverri stöð í miðbænum og eykur hraðann í úthverfunum.

Tvær ólíkar stöðvar eru beint aðgengilegar ef að minnsta kosti ein lestarþjónusta stoppar á báðum stöðvunum. Við köllum neðanjarðarlestarlínuna skilvirka ef öll pör $(i, j)$ af ólíkum stöðvum með sama stig ($a_i = a_j$) eru beint aðgengileg.

Þér eru gefin $p_1, \dots, p_m$ og $x_1, \dots, x_m$. Vinsamlegast reiknaðu fjölda mögulegra uppsetninga á $y_1, \dots, y_m$, sem samanstanda af jákvæðum heiltölum á milli $1$ og $k$, þannig að neðanjarðarlestarlínan sé skilvirk. Þar sem talan getur verið stór skal prenta svarið módúló $998\,244\,353$.

Inntak

Fyrsta línan inniheldur þrjár heiltölur $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$) og $k$ ($1 \le k \le 500$), sem gefa til kynna fjölda stöðva, fjölda lestarþjónusta og efri mörk á stigum stöðva. Það er EKKI tryggt að það sé að minnsta kosti ein stöð með hvert stig.

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), sem gefa til kynna stig hverrar stöðvar.

Næstu $m$ línur lýsa lestarþjónustunum. $i$-ta línan af þessum línum inniheldur tvær heiltölur $p_i$ ($1 \le p_i < n$) og $x_i$ ($1 \le x_i \le k$), sem gefa til kynna tvo af stikum $i$-tu lestarþjónustunnar.

Úttak

Prentið heiltölu sem táknar fjölda mögulegra fylkja $y_1, \dots, y_m$, módúló $998\,244\,353$.

Dæmi

Inntak 1

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

Úttak 1

48

Skýring

Skýring á dæmi 1: Hér að neðan er skýringarmynd fyrir mögulega uppsetningu, $y = [2, 3, 4]$:

Skýringarmynd af dæmi 1

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

Inntak 2

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

Úttak 2

80

Inntak 3

4 2 10
3 7 2 5
1 4
3 3

Úttak 3

100