くるくるくるりん

ヘリリンは二次元平面上における長さ$2L$の線分の形状をしている。ヘリリンのまわりには、線分の形状をしたいくつかの障害物が存在している。

ヘリリンは障害物に接すると体力が削られてしまう。完璧主義のヘリリンは無傷でゴールすることにした。

ヘリリンは以下の行動ができる。

• 平行移動

• ヘリリンを表す線分の中点を中心として、反時計周りにちょうど $180 / r$ 度だけ回転する

ただし、二次元平面は上方向に$y$軸をとる。

ヘリリンのまわりに、2 点 S, G がある。始めはヘリリンの中心は点 S にあって、$x$軸に平行な状態になっている。

ヘリリンは、平行移動するのは得意だが、回転するのは不得意である。あなたの仕事は、ヘリリンが中心を点 S から点 G まで移動させるまでに必要な、最小の回転行動の回数を求めることである。移動させることができない場合は、そのことも検出せよ。

ただし、以下のことに注意せよ。

• ヘリリンは移動しながら回転することはできない。

• ヘリリンが回転する途中で障害物にぶつかりうる場合は、回転することはできない。

• 障害物が互いに交差していることはあり得る。

• 線分は十分小さい有限の太さを持つものとして扱う。最後のサンプルを見よ。

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

$L$ $r$

$s\_{x}$ $s\_{y}$

$g\_{x}$ $g\_{y}$

$n$

$x\_{11}$ $y\_{11}$ $x\_{12}$ $y\_{12}$

...

$x\_{n1}$ $y\_{n1}$ $x\_{n2}$ $y\_{n2}$

$L$はヘリリンの半分の長さを表す。 $r$は回転角度を定めるものである。 $(s\_{x}, s\_{y})$は点 S、$(g\_{x}, g\_{y})$は点 G の座標である。 $n$は障害物の数を表す。 $(x\_{i1}, y\_{i1})$と$(x\_{i2}, y\_{i2})$は$i$番目の障害物を表す線分の端点である。

スタート地点からゴール地点まで移動するために必要な最小の回転行動の回数を1行に出力せよ。 移動させることができない場合は、-1を1行に出力せよ。

入力は以下の制約を満たす。

• $1 \leq n \leq 30$

• $2\leq r \leq 11$

• $1 \leq L \leq 10^{5}$

• 入力に含まれる座標の各成分は絶対値が$10^{5}$以下

• 入力に含まれる数値はすべて整数

• $i = 1, ..., n$について$(x\_{i1}, y\_{i1}) \neq (x\_{i2}, y\_{i2})$

• ヘリリンをスタート地点にx軸に水平な状態で配置したとき、障害物との（線分と線分との）距離は$10^{-3}$より大きい

• 障害物を表す線分の端点を、両方向に$10^{-3}$だけ延ばしても縮めても解は変わらない

• $L$を $10^{-3}$だけ増減させても解は変わらない

• 障害物の線分を$l\_{i}$と書くことにすると、$1 \leq i \leq j \leq n$であって、$l\_{i}$と$l\_{j}$の距離が$2L$以下であるような組$(i, j)$は高々100個

• ゴール地点は障害物に乗っていることはない