Sein Traum raste zusammen mit dem Expresszug in Stadt C donnernd durch den Bahnhof, an dem er wartete, und ließ ihn als Einzigen zurück.

Stadt C hat eine neue U-Bahn-Linie mit $n$ Stationen eröffnet. Die $i$-te Station hat das Level $1 \le a_i \le k$, was die Bedeutung der Station darstellt. Im Allgemeinen gilt: Je höher das Level einer Station, desto mehr Züge halten dort.

Stadt C plant, $m$ Zugverbindungen auf der neuen U-Bahn-Linie einzurichten. Die $i$-te Verbindung hat einen Wechselpunkt $p_i$ und zwei Level-Parameter $x_i$ und $y_i$, was bedeutet, dass die Züge dieser Verbindung von der $1$-ten Station bis zur $p_i$-ten Station an allen Stationen mit mindestens Level $x_i$ halten, und von der $(p_i + 1)$-ten Station bis zur $n$-ten Station an allen Stationen mit mindestens Level $y_i$ halten. Formaler ausgedrückt halten sie an allen Stationen $j$, die mindestens eine der folgenden Bedingungen erfüllen:

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

Betrachten wir einige Beispiele:

• Wenn $x_i = y_i = 1$, halten die Züge an jeder Station. Diese Art von Zugverbindung wird auch als Regionalverkehr (Local Service) bezeichnet.
• Wenn $x_i = y_i = k$, halten die Züge nur an Stationen mit Level $k$. Diese Art von Zugverbindung wird auch als Schnellzug (Limited Express) oder Referenzzug (Benchmark Train) bezeichnet.
• Wenn $x_i = 1, y_i = k$, ist die Verbindung zwischen $1$ und $p_i$ ein Regionalverkehr und zwischen $(p_i + 1)$ und $n$ ein Schnellzug. Dies könnte ein Durchgangsverkehr (Through Service) sein, der in der Innenstadt an jeder Station hält und im Vorort beschleunigt.

Zwei verschiedene Stationen sind direkt erreichbar, wenn mindestens eine Zugverbindung an beiden Stationen hält. Wir nennen die U-Bahn-Linie effizient, wenn alle Paare $(i, j)$ verschiedener Stationen mit demselben Level ($a_i = a_j$) direkt erreichbar sind.

Gegeben sind $p_1, \dots, p_m$ und $x_1, \dots, x_m$. Bitte berechnen Sie die Anzahl der möglichen Belegungen von $y_1, \dots, y_m$, bestehend aus positiven ganzen Zahlen zwischen $1$ und $k$, sodass die U-Bahn-Linie effizient ist. Da die Anzahl groß sein kann, geben Sie die Antwort modulo $998\,244\,353$ aus.

Eingabe

Die erste Zeile enthält drei ganze Zahlen $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$) und $k$ ($1 \le k \le 500$), die die Anzahl der Stationen, die Anzahl der Zugverbindungen und die Obergrenze für die Level der Stationen angeben. Es ist NICHT garantiert, dass es für jedes Level mindestens eine Station gibt.

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), die das Level jeder Station angeben.

Die folgenden $m$ Zeilen beschreiben die Zugverbindungen. Die $i$-te dieser Zeilen enthält zwei ganze Zahlen $p_i$ ($1 \le p_i < n$) und $x_i$ ($1 \le x_i \le k$), die zwei der Parameter der $i$-ten Zugverbindung angeben.

Ausgabe

Geben Sie eine ganze Zahl aus, die die Anzahl der möglichen Arrays $y_1, \dots, y_m$ modulo $998\,244\,353$ darstellt.

Beispiele

Eingabe 1

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

Ausgabe 1

48

Erklärung

Erklärung zu Beispiel 1: Unten sehen Sie die Veranschaulichung einer möglichen Konfiguration, $y = [2, 3, 4]$:

Veranschaulichung von Beispiel 1

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

Eingabe 2

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

Ausgabe 2

80

Eingabe 3

4 2 10
3 7 2 5
1 4
3 3

Ausgabe 3

100