Problem Description

Takahashi lives on a grid of size $H \times W$. The bottom-left cell is $(1,1)$ and the top-right cell is $(W,H)$. However, this grid is troublesome as beams occasionally fly across it. If Takahashi gets hit by a beam, it will be "a very bad thing". Therefore, he wants to avoid getting hit by beams if possible.

Beams are given as tuples of $(time, direction, coordinate)$. The time is when the beam arrives, and the direction is either vertical or horizontal.

Specifically, a beam $(t, vertical, a)$ will pass through all cells $(a, i)$ for all $1 \leq i \leq H$ at time $t$. A beam $(t, horizontal, a)$ will pass through all cells $(i, a)$ for all $1 \leq i \leq W$ at time $t$. No other cells will be affected.

Fortunately, Takahashi has all the information about when and how beams will arrive. He wants to avoid all beams with the minimum number of moves. Takahashi can move to an adjacent cell through an edge in one move.

Takahashi, due to his diligent training, can move any number of times per unit time. He can choose his initial position freely and can end up at any cell. Note that Takahashi cannot move outside the grid.

Find the minimum number of moves Takahashi needs to make to avoid all beams. If it is impossible for Takahashi to move without getting hit by a beam, output $-1$ instead.

Input Format

The input is given from the standard input in the following format:

$W$ $H$ $Q$ $T_1$ $D_1$ $X_1$ ... $T_Q$ $D_Q$ $X_Q$

• The first line contains integers $W, H, Q (1 \leq W, H \leq 10^5, 0 \leq Q \leq 10^5)$, representing the width and height of the grid, and the number of beams, respectively.
• The next $Q$ lines contain the beam information. The $i$-th line contains $T_i, D_i, X_i (1 \leq T_i \leq 10^5, 0 \leq D_i \leq 1, 1 \leq X_i \leq W$ if $D_i = 0$, $1 \leq X_i \leq H$ if $D_i = 1)$, representing the time, direction, and coordinate of the beam. $D_i = 0$ means the beam $(T_i, vertical, X_i)$ arrives, and $D_i = 1$ means the beam $(T_i, horizontal, X_i)$ arrives. Additionally, for any $i, j$, $(T_i, D_i, X_i) \neq (T_j, D_j, X_j)$.

Output Format

If it is possible for Takahashi to move without getting hit by any beam, output the minimum number of moves he needs to make. Otherwise, output $-1$.

End your output with a newline.

Sample Input and Output

Sample Input #1

3 2 8
1 0 2
3 0 2
4 1 2
2 1 2
4 0 3
2 0 3
1 1 1
2 0 1

Sample Output #1

3

Sample Input #2

2 4 10
3 1 1
2 1 3
3 0 1
2 1 4
1 1 3
2 1 2
3 1 2
1 0 1
3 1 4
2 0 2

Sample Output #2

4

Sample Input #3

3 3 5
1 0 3
1 0 2
1 1 3
1 1 2
1 0 1

Sample Output #3

-1

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the problem for the dataset where $1 \leq W, H, Q \leq 100, T_i \leq 100 (1 \leq i \leq Q)$, you will be awarded 30 points.

Sample Explanation 1

Takahashi can avoid all beams by moving as follows:
- Initially, Takahashi is at $(3,2)$.
- At time $1.5$, move to $(2,2)$ and then to $(2,1)$.
- At time $2.5$, move to $(1,1)$.

见题面 Input 部分

见题面 Output 部分