חלומו, יחד עם רכבת האקספרס בעיר 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