Hans dröm, tillsammans med expresståget i Stad C, dundrade förbi stationen där han väntade och lämnade honom ensam kvar.

Stad C har öppnat en ny tunnelbanelinje med $n$ stationer. Den $i$-te stationen har nivå $1 \le a_i \le k$, vilket representerar stationens betydelse. Generellt gäller att ju högre nivå en station har, desto fler tåg stannar där.

Stad C planerar att öppna $m$ tåglinjer på den nya tunnelbanelinjen. Den $i$-te linjen har en brytpunkt $p_i$ och två nivåparametrar $x_i$ och $y_i$, vilket anger att tågen på den linjen kommer att stanna vid alla stationer med nivå minst $x_i$ från den $1$-a stationen till den $p_i$-te stationen, och vid alla stationer med nivå minst $y_i$ från den $(p_i + 1)$-te stationen till den $n$-te stationen. Mer formellt stannar de vid alla stationer $j$ som uppfyller minst ett av följande villkor:

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

Låt oss betrakta några exempel:

• Om $x_i = y_i = 1$ kommer tågen att stanna vid varje station. Denna typ av tåglinje kallas även Lokaltåg (Local Service).
• Om $x_i = y_i = k$ kommer tågen endast att stanna vid stationer med nivå $k$. Denna typ av tåglinje kallas även Snabbtåg (Limited Express) eller Referenståg (Benchmark Train).
• Om $x_i = 1, y_i = k$ är linjen ett Lokaltåg mellan $1$ och $p_i$, och ett Snabbtåg mellan $(p_i + 1)$ och $n$. Detta kan vara en Genomgående linje (Through Service) som stannar vid varje station i innerstaden och ökar farten i förorten.

Två skilda stationer är direkt nåbara om minst en tåglinje stannar vid båda stationerna. Vi kallar tunnelbanelinjen effektiv om alla par $(i, j)$ av skilda stationer med samma nivå ($a_i = a_j$) är direkt nåbara.

Du får $p_1, \dots, p_m$ och $x_1, \dots, x_m$. Beräkna antalet möjliga uppsättningar av $y_1, \dots, y_m$, bestående av positiva heltal mellan $1$ och $k$, sådana att tunnelbanelinjen är effektiv. Eftersom antalet kan vara stort, skriv ut svaret modulo $998\,244\,353$.

Indata

Den första raden innehåller tre heltal $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$) och $k$ ($1 \le k \le 500$), som anger antalet stationer, antalet tåglinjer respektive den övre gränsen för stationernas nivåer. Det garanteras INTE att det finns minst en station med varje nivå.

Den andra raden innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), som anger nivån för varje station.

De följande $m$ raderna beskriver tåglinjerna. Den $i$-te av dessa rader innehåller två heltal $p_i$ ($1 \le p_i < n$) och $x_i$ ($1 \le x_i \le k$), som anger två av parametrarna för den $i$-te tåglinjen.

Utdata

Skriv ut ett heltal som representerar antalet möjliga fält $y_1, \dots, y_m$, modulo $998\,244\,353$.

Exempel

Indata 1

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

Utdata 1

48

Förklaring

Förklaring av exempel 1: Nedan visas en illustration för en möjlig konfiguration, $y = [2, 3, 4]$:

Illustration av exempel 1

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

Indata 2

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

Utdata 2

80

Indata 3

4 2 10
3 7 2 5
1 4
3 3

Utdata 3

100