問題文

高橋君は、$H × W$のグリッドの上に住んでいます。左下のマスは$(1,1)$で、右上のマスは$(W,H)$です。 しかし、このグリッドは少々厄介で、たまにビームが飛んできます。 人間である高橋君はビームに当たると「たいへんなこと」になってしまうので、できればビームには当たりたくありません。

ビームは、$(時刻、方向、座標)$の組で与えられます。時刻とは、そのビームが飛んでくる時刻、方向とは、縦または横です。

具体的には、ビーム$(t,縦,a)$は、時刻$t$に、$1 ≦ i ≦ H$を満たすすべての$i$に対してマス$(a,i)$を、 ビーム$(t,横,a)$は、時刻$t$に、$1 ≦ i ≦ W$を満たすすべての$i$に対してマス$(i,a)$を通過します。それ以外のマスは通過しません。

幸い高橋君は、いつ、どのようなビームが飛んでくるかの情報をすべて持っています。そのため、すべてのビームを、最短の移動回数でよけようと思っています。 高橋君は、辺を介して隣り合うマスに、$1$回で移動することができます。

高橋君は日頃からトレーニングに勤しんでいるので、単位時間に任意の回数移動することができます。 また、高橋君は、初期位置を自由に選ぶことができ、最後にどのマスにいてもよいこととします。なお、高橋君はグリッドの外に出ることはできません。

高橋君の移動回数の最小値を求めてください。もし高橋君がビームに当たらずに移動することが不可能ならば、かわりに$\-1$を出力してください。

入力

入力は以下の形式で標準入力から与えられる。

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

• $1$ 行目には、整数$W,H,Q(1 ≦ W,H ≦ 10^5, 0 ≦ Q ≦10^5)$が与えられる。これらはそれぞれ、グリッドの横の長さ、縦の長さ、ビームが飛んでくる回数を表す。
• $2$ 行目から$Q+1$行目には、ビームの情報が与えられる。このうち$i$行目には、$T_i,D_i,X_i(1 ≦ T_i ≦10^5, 0 ≦ D_i ≦ 1, D_i=0のとき1 ≦ X_i ≦ W, D_i=1のとき1 ≦ X_i ≦ H)$が与えられる。$D_i=0$のときビーム$(T_i,縦,X_i)$が、$D_i=1$のときビーム$(T_i,横,X_i)$が飛んでくることを表す。また、任意の$i,j$に対し、$(T_i,D_i,X_i) ≠ (T_j,D_j,X_j)$を満たす。

部分点

この問題には部分点が設定されている。

• $1 ≦ W,H,Q ≦ 100, T_i ≦ 100(1 ≦ i ≦ Q)$ を満たすデータセットに正解した場合は $30$ 点が与えられる。

出力

ビームに一度も当たらないような移動が可能な場合、高橋君の移動回数の最小値を出力せよ。そうでない場合、$\-1$を出力せよ。

出力の末尾に改行を入れること。(21:40修正)

入力例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

出力例1

3

高橋君は以下の動きで、すべてのビームをよけることができます。

• はじめ、高橋君は$(3,2)$にいる
• 時刻$1.5$に、$(2,2)$に移動し、さらに$(2,1)$に移動する
• 時刻$2.5$に、$(1,1)$に移動する

入力例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

出力例2

4

入力例3

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

出力例3

-1