Son rêve, tout comme le train express de la ville C, a traversé en rugissant la gare où il attendait, le laissant tout seul derrière.
La ville C a ouvert une nouvelle ligne de métro comptant $n$ stations. La $i$-ème station a un niveau $1 \le a_i \le k$, qui représente l'importance de la station. En général, plus le niveau d'une station est élevé, plus il y a de trains qui s'y arrêtent.
La ville C prévoit d'ouvrir $m$ services de train sur la nouvelle ligne de métro. Le $i$-ème service possède un point de basculement $p_i$ et deux paramètres de niveau $x_i$ et $y_i$, indiquant que les trains de ce service s'arrêteront à toutes les stations de niveau au moins $x_i$ de la $1$-ère station à la $p_i$-ème station, et à toutes les stations de niveau au moins $y_i$ de la $(p_i + 1)$-ème station à la $n$-ème station. Plus formellement, ils s'arrêtent à toutes les stations $j$ satisfaisant au moins l'une des conditions suivantes :
- $j \le p_i$ et $a_j \ge x_i$ ;
- $j > p_i$ et $a_j \ge y_i$.
Considérons quelques exemples :
- Si $x_i = y_i = 1$, les trains s'arrêteront à chaque station. Ce type de service est également appelé Service Omnibus (Local Service).
- Si $x_i = y_i = k$, les trains ne s'arrêteront qu'aux stations de niveau $k$. Ce type de service est également appelé Express Limité (Limited Express) ou Train de Référence (Benchmark Train).
- Si $x_i = 1, y_i = k$, le service est un Service Omnibus entre $1$ et $p_i$, et un Express Limité entre $(p_i + 1)$ et $n$. Cela peut correspondre à un Service Direct (Through Service) qui s'arrête à chaque station du centre-ville et accélère en banlieue.
Deux stations distinctes sont directement accessibles si au moins un service de train s'arrête aux deux stations. Nous disons que la ligne de métro est efficace si toutes les paires $(i, j)$ de stations distinctes ayant le même niveau ($a_i = a_j$) sont directement accessibles.
On vous donne $p_1, \dots, p_m$ et $x_1, \dots, x_m$. Veuillez calculer le nombre de configurations possibles de $y_1, \dots, y_m$, composées d'entiers positifs compris entre $1$ et $k$, telles que la ligne de métro soit efficace. Comme ce nombre peut être grand, affichez la réponse modulo $998\,244\,353$.
Entrée
La première ligne contient trois entiers $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$) et $k$ ($1 \le k \le 500$), indiquant respectivement le nombre de stations, le nombre de services de train et la limite supérieure des niveaux des stations. Il n'est PAS garanti qu'il y ait au moins une station pour chaque niveau.
La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), indiquant le niveau de chaque station.
Les $m$ lignes suivantes décrivent les services de train. La $i$-ème de ces lignes contient deux entiers $p_i$ ($1 \le p_i < n$) et $x_i$ ($1 \le x_i \le k$), indiquant deux des paramètres du $i$-ème service de train.
Sortie
Affichez un entier représentant le nombre de tableaux possibles $y_1, \dots, y_m$, modulo $998\,244\,353$.
Exemples
Entrée 1
4 3 4 2 3 3 2 1 2 2 2 2 3
Sortie 1
48
Explication
Explication de l'exemple 1 : Ci-dessous se trouve l'illustration d'une configuration possible, $y = [2, 3, 4]$ :
Illustration de l'exemple 1
- Service 1 : $p_1 = 1, x_1 = 2, y_1 = 2$ ;
- Service 2 : $p_2 = 2, x_2 = 2, y_2 = 3$ ;
- Service 3 : $p_3 = 2, x_3 = 3, y_3 = 4$.
Entrée 2
7 3 5 2 4 3 2 4 2 3 2 2 4 3 5 2
Sortie 2
80
Entrée 3
4 2 10 3 7 2 5 1 4 3 3
Sortie 3
100