Mimpinya, bersama dengan Kereta Ekspres di Kota C, menderu melewati stasiun tempat ia menunggu, meninggalkannya sendirian di belakang.

Kota C membuka jalur kereta bawah tanah baru dengan $n$ stasiun. Stasiun ke-$i$ memiliki tingkat $1 \le a_i \le k$, yang menyatakan tingkat kepentingan stasiun tersebut. Secara umum, semakin tinggi tingkat suatu stasiun, semakin banyak kereta yang berhenti di sana.

Kota C berencana membuka $m$ layanan kereta pada jalur kereta bawah tanah baru tersebut. Layanan ke-$i$ memiliki titik peralihan $p_i$, serta dua parameter tingkat $x_i$ dan $y_i$, yang menyatakan bahwa kereta dari layanan tersebut akan berhenti di semua stasiun dengan tingkat setidaknya $x_i$ dari stasiun ke-$1$ hingga stasiun ke-$p_i$, dan semua stasiun dengan tingkat setidaknya $y_i$ dari stasiun ke-$(p_i + 1)$ hingga stasiun ke-$n$. Secara lebih formal, kereta berhenti di semua stasiun $j$ yang memenuhi setidaknya salah satu dari kondisi berikut:

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

Mari kita perhatikan beberapa contoh:

• Jika $x_i = y_i = 1$, kereta akan berhenti di setiap stasiun. Layanan kereta semacam ini juga dikenal sebagai Layanan Lokal (Local Service).
• Jika $x_i = y_i = k$, kereta hanya akan berhenti di stasiun dengan tingkat $k$. Layanan kereta semacam ini juga dikenal sebagai Ekspres Terbatas (Limited Express) atau Kereta Tolok Ukur (Benchmark Train).
• Jika $x_i = 1, y_i = k$, layanan tersebut merupakan Layanan Lokal antara $1$ dan $p_i$, serta Ekspres Terbatas antara $(p_i + 1)$ dan $n$. Ini bisa berupa Layanan Terusan (Through Service) yang berhenti di setiap stasiun di pusat kota dan melaju cepat di pinggiran kota.

Dua stasiun berbeda dikatakan dapat dijangkau secara langsung jika setidaknya satu layanan kereta berhenti di kedua stasiun tersebut. Kita menyebut jalur kereta bawah tanah tersebut efisien jika semua pasangan $(i, j)$ dari stasiun berbeda dengan tingkat yang sama ($a_i = a_j$) dapat dijangkau secara langsung.

Anda diberikan $p_1, \dots, p_m$ dan $x_1, \dots, x_m$. Hitunglah banyaknya susunan $y_1, \dots, y_m$ yang mungkin, yang terdiri dari bilangan bulat positif antara $1$ dan $k$, sedemikian sehingga jalur kereta bawah tanah tersebut efisien. Karena jumlahnya mungkin besar, keluarkan jawabannya modulo $998\,244\,353$.

Masukan

Baris pertama berisi tiga bilangan bulat $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$), dan $k$ ($1 \le k \le 500$), yang menyatakan banyaknya stasiun, banyaknya layanan kereta, dan batas atas tingkat stasiun. TIDAK dijamin bahwa terdapat setidaknya satu stasiun untuk setiap tingkat.

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), yang menyatakan tingkat dari masing-masing stasiun.

$m$ baris berikutnya mendeskripsikan layanan kereta. Baris ke-$i$ dari baris-baris ini berisi dua bilangan bulat $p_i$ ($1 \le p_i < n$) dan $x_i$ ($1 \le x_i \le k$), yang menyatakan dua parameter dari layanan kereta ke-$i$.

Keluaran

Keluarkan sebuah bilangan bulat yang menyatakan banyaknya larik $y_1, \dots, y_m$ yang mungkin, modulo $998\,244\,353$.

Contoh

Masukan 1

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

Keluaran 1

48

Penjelasan

Penjelasan Contoh 1: Di bawah ini adalah ilustrasi untuk salah satu konfigurasi yang mungkin, $y = [2, 3, 4]$:

Ilustrasi Contoh 1

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

Masukan 2

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

Keluaran 2

80

Masukan 3

4 2 10
3 7 2 5
1 4
3 3

Keluaran 3

100