Problem Statement

高橋君は、$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$を出力してください。

Input

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

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$ 点が与えられる。

Output

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

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