Его мечта вместе с экспрессом в городе 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