Його мрія разом з експресом у місті 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