謝罪

Python3 は想定解法で TLE しました.

問題文

正三角形の内部に何本か, 3辺のいずれかに平行な線分を書き加えます.

$i$ 番目に書き加える線分は, パラメータ $p_i,a_i,b_i$ を用いて次のように表されます.

• $p_i$ は $0$ または $1$ または $2$ であり, 正三角形の各頂点に反時計回りに対応している.
• 頂点 $p_i$ から伸びる2辺をそれぞれ $a_i:b_i$ に内分する点を考え, それぞれ $A$, $B$ とおく.
• このとき線分 $AB$ が $i$ 番目に書き加える線分である.

（サンプルも参考にしてください.）

全ての線分を書き加えたのち, 存在する線分を用いて作られる正三角形の個数がいくつとなるか出力してください.

入力

$N$
$p_1{a}_1{b}_1$
:
$p_N{a}_N{b}_N$

1行目に, 加える線分の本数 $N$ が与えられます.

$N$ が1以上の場合, 続いて2行目から $N$ 行の間, 加える線分の情報 $p_i,a_i,b_i$ が空白区切りで与えられます.

入力は全て整数で, 以下の制約を満たします.

• $0\le N\le 4000$
• $0\le p_i\le 2$
• $1\le a_i,b_i$
• $a_i+b_i\le 4\times {10}^5$
• $(i\ne j)$ ならば, $(p_i\ne p_j)$ または $(a_i:b_i\ne a_j:b_j)$

出力

最終的な図形に正三角形がいくつあるかを出力してください.

最後に改行してください.

サンプル

サンプル1

入力サンプルをコピー

入力

3
0 1 1
1 1 1
2 1 1

出力

5

以下のように線分が足されていき, 最終的な図形の中に正三角形は5つあります.

→ →

サンプル2

入力サンプルをコピー

入力

4
2 1 1
1 3 1
2 9 3
0 6 2

出力

11

$a_i$ と $b_i$ が互いに素とは限りません.

3
0 12 12
1 21 212
2 12 1212

4

0

1