ความฝันของเขา พร้อมกับรถไฟด่วนในเมือง C คำรามผ่านสถานีที่เขากำลังรออยู่ ทิ้งให้เขาเหลืออยู่เพียงลำพังข้างหลัง

เมือง C ได้เปิดเส้นทางรถไฟใต้ดินสายใหม่ที่มี $n$ สถานี สถานีที่ $i$ มีระดับ $1 \le a_i \le k$ ซึ่งแทนความสำคัญของสถานี โดยทั่วไปแล้ว ยิ่งสถานีมีระดับสูงเท่าใด ก็จะมีรถไฟจอดที่นั่นมากขึ้นเท่านั้น

เมือง C วางแผนที่จะเปิดบริการเดินรถไฟ $m$ สายบนเส้นทางรถไฟใต้ดินสายใหม่นี้ บริการสายที่ $i$ มีจุดสลับ $p_i$ และพารามิเตอร์ระดับสองตัวคือ $x_i$ และ $y_i$ ซึ่งระบุว่ารถไฟของบริการนั้นจะจอดที่สถานีทั้งหมดที่มีระดับอย่างน้อย $x_i$ ตั้งแต่สถานีที่ $1$ ถึงสถานีที่ $p_i$ และจอดที่สถานีทั้งหมดที่มีระดับอย่างน้อย $y_i$ ตั้งแต่สถานีที่ $(p_i + 1)$ ถึงสถานีที่ $n$ กล่าวอย่างเป็นทางการคือ รถไฟจะจอดที่สถานี $j$ ทั้งหมดที่สอดคล้องกับเงื่อนไขอย่างน้อยหนึ่งข้อต่อไปนี้:

• $j \le p_i$ และ $a_j \ge x_i$
• $j > p_i$ และ $a_j \ge y_i$

ลองพิจารณาตัวอย่างบางส่วน:

• หาก $x_i = y_i = 1$ รถไฟจะจอดทุกสถานี บริการเดินรถไฟประเภทนี้เรียกว่า รถธรรมดา (Local Service)
• หาก $x_i = y_i = k$ รถไฟจะจอดเฉพาะสถานีที่มีระดับ $k$ เท่านั้น บริการเดินรถไฟประเภทนี้เรียกว่า รถด่วนพิเศษ (Limited Express) หรือ รถไฟมาตรฐาน (Benchmark Train)
• หาก $x_i = 1, y_i = k$ บริการนี้จะเป็น รถธรรมดา ระหว่างสถานีที่ $1$ ถึง $p_i$ และเป็น รถด่วนพิเศษ ระหว่างสถานีที่ $(p_i + 1)$ ถึง $n$ ซึ่งอาจเป็น บริการเดินรถต่อเนื่อง (Through Service) ที่จอดทุกสถานีในตัวเมืองและเร่งความเร็วในแถบชานเมือง

สองสถานีที่แตกต่างกันจะสามารถเดินทางถึงกันได้โดยตรง หากมีบริการเดินรถไฟอย่างน้อยหนึ่งสายจอดที่ทั้งสองสถานี เราจะเรียกเส้นทางรถไฟใต้ดินนี้ว่ามีประสิทธิภาพ หากทุกคู่ $(i, j)$ ของสถานีที่แตกต่างกันซึ่งมีระดับเดียวกัน ($a_i = a_j$) สามารถเดินทางถึงกันได้โดยตรง

คุณได้รับ $p_1, \dots, p_m$ และ $x_1, \dots, x_m$ จงคำนวณจำนวนรูปแบบที่เป็นไปได้ของ $y_1, \dots, y_m$ ซึ่งประกอบด้วยจำนวนเต็มบวกระหว่าง $1$ ถึง $k$ ที่ทำให้เส้นทางรถไฟใต้ดินนี้มีประสิทธิภาพ เนื่องจากจำนวนอาจมีค่ามาก ให้แสดงผลคำตอบมอดุโล $998\,244\,353$

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็มสามจำนวน $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$) และ $k$ ($1 \le k \le 500$) แทนจำนวนสถานี จำนวนบริการเดินรถไฟ และขีดจำกัดบนของระดับสถานี ตามลำดับ ไม่รับประกันว่าจะมีสถานีอย่างน้อยหนึ่งแห่งในแต่ละระดับ

บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$) แทนระดับของแต่ละสถานี

อีก $m$ บรรทัดถัดไปอธิบายบริการเดินรถไฟ บรรทัดที่ $i$ ของบรรทัดเหล่านี้ประกอบด้วยจำนวนเต็มสองจำนวน $p_i$ ($1 \le p_i < n$) และ $x_i$ ($1 \le x_i \le k$) แทนพารามิเตอร์สองตัวของบริการเดินรถไฟสายที่ $i$

ข้อมูลส่งออก

แสดงผลจำนวนเต็มหนึ่งจำนวนที่แทนจำนวนอาร์เรย์ $y_1, \dots, y_m$ ที่เป็นไปได้ มอดุโล $998\,244\,353$

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

48

คำอธิบาย

คำอธิบายตัวอย่างที่ 1: ด้านล่างนี้คือภาพประกอบสำหรับโครงแบบหนึ่งที่เป็นไปได้ $y = [2, 3, 4]$:

ภาพประกอบตัวอย่างที่ 1

• บริการสายที่ 1: $p_1 = 1, x_1 = 2, y_1 = 2$
• บริการสายที่ 2: $p_2 = 2, x_2 = 2, y_2 = 3$
• บริการสายที่ 3: $p_3 = 2, x_3 = 3, y_3 = 4$

ข้อมูลนำเข้า 2

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

ข้อมูลส่งออก 2

80

ข้อมูลนำเข้า 3

4 2 10
3 7 2 5
1 4
3 3

ข้อมูลส่งออก 3

100