According to the script, fateicest wants to go shopping. Naturally, he must head to the Pigeon Nest to do so.

The Pigeon Nest mall is an $H \times W$ grid, with the northwest corner labeled $(1,1)$ and the southeast corner labeled $(H,W)$. Rows are labeled $1 \dots H$ from north to south, and columns are labeled $1 \dots W$ from west to east. Each cell contains a shop, and every shop sells a unique item. The mall is divided into $n+2$ functional areas, labeled $0 \dots n+1$. Each area is a rectangle; the $i$-th rectangle has its top-left corner at $(x_{l_i},y_{l_i})$ and its bottom-right corner at $(x_{r_i},y_{r_i})$. These $n+2$ rectangles satisfy the following conditions:

$$x_{l_0} \le x_{r_0} < x_{l_1} \le x_{r_1} < \dots < x_{l_{n+1}} \le x_{r_{n+1}}$$

$$y_{l_0} \le y_{r_0} < y_{l_1} \le y_{r_1} < \dots < y_{l_{n+1}} \le y_{r_{n+1}}$$

In the $0$-th area, every cell contains a portal that can transport fateicest into the mall; in the $(n+1)$-th area, every cell can transport fateicest out of the mall. The areas from $1$ to $n$ are food streets, where every cell contains a restaurant. Note that every cell in the mall contains a shop, regardless of whether it is part of a functional area. Areas $0$ and $n+1$ do not contain restaurants.

Since fateicest is a shopaholic, he buys an item from every shop he passes, including the starting and ending points. If he passes a restaurant, he can choose to enter it or not. However, he is very eager to taste the food here, so he decides to visit at least one restaurant in every area from $1$ to $n$.

fateicest can choose any cell in area $0$ to enter the mall and any cell in area $n+1$ to exit. He can choose any path he likes. However, because he does not want to spend too much time in the mall, he can only move east or south, i.e., he must follow a shortest path to the exit.

fateicest wants to know how many different experiences he can have after completing this shopping trip. Two experiences are different if and only if the set of items he bought is different or the set of restaurants he visited is different.

fateicest immediately calculated the answer, but he wants to test you. Since fateicest believes you cannot calculate the answer as quickly as he can, he only requires you to report the answer modulo $998244353$.

Input

The input is read from standard input.

The first line contains two integers $H$ and $W$, representing the grid size.

The second line contains an integer $n$, representing the number of areas.

The next $n+2$ lines (from the 3rd line to the $n+4$-th line) each contain four integers $x_{l_i}, y_{l_i}, x_{r_i}, y_{r_i}$, representing the range of an area. The $i$-th line (where $i$ ranges from $3$ to $n+4$) represents the $(i-3)$-th area.

Output

Output to standard output.

Output a single integer representing the number of ways modulo $998244353$.

Examples

Input 1

1000 1000
2
1 1 1 1
3 3 3 3
5 5 5 5
7 7 7 7

Output 1

216

Note 1

The top-left corner of the grid looks like this:

0......
.......
..1....
.......
....2..
.......
......3

He must enter from $0$ and exit from $3$, and he must pass through $1$ and $2$. There are $6$ ways to go from $0$ to $1$, $6$ ways from $1$ to $2$, and $6$ ways from $2$ to $3$. In total, there are $6^3 = 216$ ways.

Input 2

1000 1000
0
1 1 2 2
4 4 5 5

Output 2

366

Input 3

50 50
1
1 1 10 12
20 17 25 32
30 42 47 45

Output 3

545916062

Constraints

This problem uses bundled testing.

Let $$ AMX = \max_{0 \le i \le n+1} \{ \max \{ x_{r_i} - x_{l_i} + 1, y_{r_i} - y_{l_i} + 1 \} \} $$

For all data, the following holds:

• $2 \le H, W \le 2 \times 10^5$
• $0 \le n \le \min \{ H, W \} - 2$
• For $\forall$ $0 \le i \le n+1$, $1 \le x_{l_i} \le x_{r_i} \le H, 1 \le y_{l_i} \le y_{r_i} \le W$
• For $\forall$ $0 \le i \le n$, $x_{r_i} < x_{l_{i+1}}, y_{r_i} < y_{l_{i+1}}$

There are $9$ subtasks. The special constraints and scores for each subtask are as follows: