Jego marzenie, wraz z pociągiem ekspresowym w Mieście C, przemknęło z hukiem przez stację, na której czekał, zostawiając go samego w tyle.

Miasto C otworzyło nową linię metra z $n$ stacjami. $i$-ta stacja ma poziom $1 \le a_i \le k$, który oznacza ważność stacji. Ogólnie rzecz biorąc, im wyższy poziom stacji, tym więcej pociągów się na niej zatrzymuje.

Miasto C planuje uruchomić $m$ połączeń kolejowych na nowej linii metra. $i$-te połączenie ma punkt przełączenia $p_i$ oraz dwa parametry poziomu $x_i$ i $y_i$, oznaczające, że pociągi tego połączenia zatrzymują się na wszystkich stacjach o poziomie co najmniej $x_i$ od $1$-szej stacji do $p_i$-tej stacji oraz na wszystkich stacjach o poziomie co najmniej $y_i$ od $(p_i + 1)$-szej stacji do $n$-tej stacji. Bardziej formalnie, zatrzymują się one na wszystkich stacjach $j$ spełniających co najmniej jeden z poniższych warunków:

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

Rozważmy kilka przykładów:

• Jeśli $x_i = y_i = 1$, pociągi zatrzymują się na każdej stacji. Taki rodzaj połączenia jest znany jako pociąg osobowy (Local Service).
• Jeśli $x_i = y_i = k$, pociągi zatrzymują się tylko na stacjach o poziomie $k$. Taki rodzaj połączenia jest znany jako ekspres (Limited Express) lub pociąg wzorcowy (Benchmark Train).
• Jeśli $x_i = 1, y_i = k$, połączenie działa jako pociąg osobowy między $1$ a $p_i$ oraz jako ekspres między $(p_i + 1)$ a $n$. Może to być połączenie przelotowe (Through Service), które zatrzymuje się na każdej stacji w centrum miasta i przyspiesza na przedmieściach.

Dwie różne stacje są bezpośrednio osiągalne, jeśli co najmniej jedno połączenie zatrzymuje się na obu tych stacjach. Linię metra nazywamy wydajną, jeśli wszystkie pary $(i, j)$ różnych stacji o tym samym poziomie ($a_i = a_j$) są bezpośrednio osiągalne.

Dane są wartości $p_1, \dots, p_m$ oraz $x_1, \dots, x_m$. Oblicz liczbę możliwych układów $y_1, \dots, y_m$, składających się z dodatnich liczb całkowitych od $1$ do $k$, takich, że linia metra jest wydajna. Ponieważ liczba ta może być duża, wypisz odpowiedź modulo $998\,244\,353$.

Wejście

Pierwszy wiersz zawiera trzy liczby całkowite $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$) oraz $k$ ($1 \le k \le 500$), oznaczające odpowiednio liczbę stacji, liczbę połączeń kolejowych oraz górne ograniczenie na poziomy stacji. NIE jest zagwarantowane, że istnieje co najmniej jedna stacja każdego poziomu.

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), oznaczających poziom każdej stacji.

Kolejne $m$ wierszy opisuje połączenia kolejowe. $i$-ty z tych wierszy zawiera dwie liczby całkowite $p_i$ ($1 \le p_i < n$) oraz $x_i$ ($1 \le x_i \le k$), oznaczające dwa parametry $i$-tego połączenia kolejowego.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą liczbę możliwych tablic $y_1, \dots, y_m$, modulo $998\,244\,353$.

Przykłady

Wejście 1

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

Wyjście 1

48

Wyjaśnienie

Wyjaśnienie przykładu 1: Poniżej przedstawiono ilustrację dla pewnej możliwej konfiguracji, $y = [2, 3, 4]$:

Ilustracja do przykładu 1

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

Wejście 2

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

Wyjście 2

80

Wejście 3

4 2 10
3 7 2 5
1 4
3 3

Wyjście 3

100