Оның арманы C қаласындағы экспресс пойызымен бірге ол күтіп тұрған станциядан гүрілдеп өте шығып, оны жалғыз өзін артта қалдырды.

C қаласы $n$ станциясы бар жаңа метро желісін ашты. $i$-ші станцияның деңгейі $1 \le a_i \le k$, бұл станцияның маңыздылығын білдіреді. Жалпы алғанда, станцияның деңгейі неғұрлым жоғары болса, соғұрлым онда көп пойыз тоқтайды.

C қаласы жаңа метро желісінде $m$ пойыз бағытын (қызметін) ашуды жоспарлап отыр. $i$-ші бағыттың ауысу нүктесі $p_i$ және екі деңгей параметрі $x_i$ мен $y_i$ бар, бұл осы бағыттағы пойыздар $1$-ші станциядан $p_i$-ші станцияға дейін деңгейі кемінде $x_i$ болатын барлық станцияларда, ал $(p_i + 1)$-ші станциядан $n$-ші станцияға дейін деңгейі кемінде $y_i$ болатын барлық станцияларда тоқтайтынын білдіреді. Формалды түрде айтқанда, олар келесі шарттардың кемінде біреуін қанағаттандыратын барлық $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) болуы мүмкін.

Егер кемінде бір пойыз бағыты екі түрлі станцияның екеуінде де тоқтаса, бұл екі станция тікелей қолжетімді деп аталады. Егер деңгейлері бірдей ($a_i = a_j$) әртүрлі станциялардың барлық $(i, j)$ жұптары тікелей қолжетімді болса, біз метро желісін тиімді деп атаймыз.

Сізге $p_1, \dots, p_m$ және $x_1, \dots, x_m$ берілген. Метро желісі тиімді болатындай, $1$ мен $k$ аралығындағы оң бүтін сандардан тұратын $y_1, \dots, y_m$ жиындарының мүмкін болатын санын есептеңіз. Сан үлкен болуы мүмкін болғандықтан, жауапты $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$-шісінде $i$-ші пойыз бағытының екі параметрін білдіретін екі бүтін сан $p_i$ ($1 \le p_i < n$) және $x_i$ ($1 \le x_i \le k$) берілген.

Шығыс деректер

Мүмкін болатын $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