Giấc mơ của anh, cùng với chuyến Tàu Tốc Hành ở Thành phố C, gầm vang lao qua nhà ga nơi anh đang đứng đợi, bỏ lại mình anh phía sau.

Thành phố C vừa mở một tuyến tàu điện ngầm mới với $n$ nhà ga. Nhà ga thứ $i$ có cấp độ $1 \le a_i \le k$, biểu thị tầm quan trọng của nhà ga đó. Nhìn chung, cấp độ của nhà ga càng cao thì càng có nhiều chuyến tàu dừng ở đó.

Thành phố C dự định mở $m$ tuyến dịch vụ tàu trên tuyến tàu điện ngầm mới. Dịch vụ thứ $i$ có một điểm chuyển đổi $p_i$, và hai tham số cấp độ $x_i$ và $y_i$, cho biết các đoàn tàu của dịch vụ đó sẽ dừng tại tất cả các nhà ga có cấp độ ít nhất là $x_i$ từ nhà ga thứ $1$ đến nhà ga thứ $p_i$, và tất cả các nhà ga có cấp độ ít nhất là $y_i$ từ nhà ga thứ $(p_i + 1)$ đến nhà ga thứ $n$. Một cách hình thức hơn, chúng dừng tại tất cả các nhà ga $j$ thỏa mãn ít nhất một trong hai điều kiện sau:

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

Hãy xét một số ví dụ:

• Nếu $x_i = y_i = 1$, các đoàn tàu sẽ dừng ở mọi nhà ga. Loại dịch vụ tàu này còn được gọi là Tàu Thường (Local Service).
• Nếu $x_i = y_i = k$, các đoàn tàu sẽ chỉ dừng ở các nhà ga có cấp độ $k$. Loại dịch vụ tàu này còn được gọi là Tốc Hành Giới Hạn (Limited Express) hoặc Tàu Chuẩn (Benchmark Train).
• Nếu $x_i = 1, y_i = k$, dịch vụ này là Tàu Thường giữa $1$ và $p_i$, và là Tốc Hành Giới Hạn giữa $(p_i + 1)$ và $n$. Đây có thể là Tàu Xuyên Suốt (Through Service) dừng ở mọi ga trong khu trung tâm và tăng tốc ở vùng ngoại ô.

Hai nhà ga phân biệt là có thể đi đến trực tiếp nếu có ít nhất một dịch vụ tàu dừng ở cả hai nhà ga đó. Chúng ta gọi tuyến tàu điện ngầm là hiệu quả nếu mọi cặp $(i, j)$ gồm hai nhà ga phân biệt có cùng cấp độ ($a_i = a_j$) đều có thể đi đến trực tiếp.

Bạn được cho $p_1, \dots, p_m$ và $x_1, \dots, x_m$. Hãy tính số lượng cách bố trí khả dĩ của $y_1, \dots, y_m$, gồm các số nguyên dương từ $1$ đến $k$, sao cho tuyến tàu điện ngầm là hiệu quả. Vì số lượng có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$), và $k$ ($1 \le k \le 500$), lần lượt cho biết số lượng nhà ga, số lượng dịch vụ tàu, và giới hạn trên của cấp độ các nhà ga. KHÔNG đảm bảo rằng có ít nhất một nhà ga ở mỗi cấp độ.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), cho biết cấp độ của mỗi nhà ga.

$m$ dòng tiếp theo mô tả các dịch vụ tàu. Dòng thứ $i$ trong các dòng này chứa hai số nguyên $p_i$ ($1 \le p_i < n$) và $x_i$ ($1 \le x_i \le k$), cho biết hai trong số các tham số của dịch vụ tàu thứ $i$.

Kết quả

In ra một số nguyên biểu thị số lượng mảng $y_1, \dots, y_m$ khả dĩ, theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

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

Kết quả 1

48

Giải thích

Giải thích Ví dụ 1: Dưới đây là hình minh họa cho một cấu hình khả dĩ, $y = [2, 3, 4]$:

Hình minh họa Ví dụ 1

• Dịch vụ 1: $p_1 = 1, x_1 = 2, y_1 = 2$;
• Dịch vụ 2: $p_2 = 2, x_2 = 2, y_2 = 3$;
• Dịch vụ 3: $p_3 = 2, x_3 = 3, y_3 = 4$.

Dữ liệu vào 2

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

Kết quả 2

80

Dữ liệu vào 3

4 2 10
3 7 2 5
1 4
3 3

Kết quả 3

100