ノート

問題文

2人の魔法少女MamiとHomuraは幅 \(W\) メートル、奥行き \(H\) メートルの密室で銃撃戦を繰り広げていた。

Homuraは時間を止め、同時に最後の一発を発射した。
時間停止した世界ではHomuraと弾丸しか動くことができず、弾丸は壁にあたると入射角と同じ角度で反射し速度を落とすことなく無限に飛び続ける。

Mamiがいる位置を \((Mx, My)\)、Homuraが発砲した位置を \((Hx, Hy)\)、弾丸の発射時の速度ベクトルを \((Vx, Vy)\) とし \(D\) 秒間時間を止めるとき、
\(D\) 秒以内に弾丸がMamiに当たることはあるか判定せよ。

ただしMamiと弾丸の大きさは無視できるものとし、Homuraが弾丸に当たることはないとする。

図: 配置例

入力

\(Q\)
\(W_{1}\) \(H_{1}\) \(D_{1}\) \(Mx_{1}\) \(My_{1}\) \(Hx_{1}\) \(Hy_{1}\) \(Vx_{1}\) \(Vy_{1}\)
\(W_{2}\) \(H_{2}\) \(D_{2}\) \(Mx_{2}\) \(My_{2}\) \(Hx_{2}\) \(Hy_{2}\) \(Vx_{2}\) \(Vy_{2}\)
\(\ldots\)
\(W_{Q}\) \(H_{Q}\) \(D_{Q}\) \(Mx_{Q}\) \(My_{Q}\) \(Hx_{Q}\) \(Hy_{Q}\) \(Vx_{Q}\) \(Vy_{Q}\)

入力は全て整数で与えられる。

• \(1 \leq Q \leq 10000\) はテストケースの数を表す。
• 2行目からの \(Q\) 行では \(W, H, D, Mx, My, Hx, Hy, Vx, Vy\) の組が与えられる。
• \(2\leq W, H\leq 10^9\)
• \(1 \leq D \leq 10^9\)
• \(0 < Mx, Hx < W\)
• \(0 < My, Hy < H\)
• \(-10^9 \leq Vx, Vy \leq 10^9\)
• \((Mx, My) \neq (Hx, Hy)\) が保証されている。
• \((Vx, Vy) \neq (0, 0)\) が保証されている。

出力

サンプル

5
9 9 74 7 6 4 1 -5 2
7 11 30 5 4 5 10 13 8
15 4 17 10 3 12 3 -3 1
3 9 22 2 2 1 1 13 12
8 11 2 6 5 1 9 -2 -4

Miss
Hit
Miss
Miss
Miss

5
2 15 19 1 2 1 4 1 5
5 5 11 3 1 4 2 9 -7
13 6 68 8 2 11 2 -13 0
2 15 90 1 2 1 8 0 -7
11 4 77 9 1 10 1 -6 13

Miss
Miss
Hit
Hit
Miss