His dream, together with the Express Train in City C, roared through the station he was waiting at, leaving him the only one behind.

City C opened a new subway line with $n$ stations. The $i$-th station has level $1 \le a_i \le k$, which represents the importance of the station. In general, the higher the level of a station, the more trains stop there.

City C plans to open $m$ train services on the new subway line. The $i$-th service has a switching point $p_i$, and two level parameters $x_i$ and $y_i$, indicating that the trains of that service will stop at all the stations with level at least $x_i$ from the $1$-st station to the $p_i$-th station, and all the stations with level at least $y_i$ from the $(p_i + 1)$-th station to the $n$-th station. More formally, they stop at all stations $j$ satisfying at least one of the following:

• $j \le p_i$ and $a_j \ge x_i$;
• $j > p_i$ and $a_j \ge y_i$.

Let's consider some examples:

• If $x_i = y_i = 1$, the trains will stop at every station. This kind of train service is also known as Local Service.
• If $x_i = y_i = k$, the trains will only stop at stations with level $k$. This kind of train service is also known as Limited Express or Benchmark Train.
• If $x_i = 1, y_i = k$, the service is a Local Service between $1$ and $p_i$, and a Limited Express between $(p_i + 1)$ and $n$. This could be the Through Service that stops at every station in the downtown and speeds up in the suburb.

Two distinct stations are directly reachable if at least one train service stops at both stations. We call the subway line efficient if all pairs $(i, j)$ of distinct stations with the same level ($a_i = a_j$) are directly reachable.

You are given $p_1, \dots, p_m$ and $x_1, \dots, x_m$. Please calculate the number of possible layouts of $y_1, \dots, y_m$, consisting of positive integers between $1$ and $k$, such that the subway line is efficient. As the number might be large, output the answer modulo $998\,244\,353$.

Input

The first line contains three integers $n$ ($2 \le n \le 10^3$), $m$ ($1 \le m \le 10^3$), and $k$ ($1 \le k \le 500$), indicating the number of stations, the number of train services, and the upper limit of the levels of stations. It is NOT guaranteed that there is at least one station with each level.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), indicating the level of each station.

The following $m$ lines describe the train services. The $i$-th of these lines contains two integers $p_i$ ($1 \le p_i < n$) and $x_i$ ($1 \le x_i \le k$), indicating two of the parameters of the $i$-th train service.

Output

Output an integer representing the number of possible arrays $y_1, \dots, y_m$, modulo $998\,244\,353$.

Examples

Input 1

4 3 4
2 3 3 2
1 2
2 2
2 3

Output 1

48

Explanation

Explanation of Sample 1: Below is the illustration for a possible configuration, $y = [2, 3, 4]$:

Illustration of Sample 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$.

Input 2

7 3 5
2 4 3 2 4 2 3
2 2
4 3
5 2

Output 2

80

Input 3

4 2 10
3 7 2 5
1 4
3 3

Output 3

100