#include using namespace std; //bigint用のNTT 268行目まで. const long long mod = 998244353; //入力が必ずmod未満の時に使う. struct mint{ long long v = 0; mint(){} mint(int a){v = a;} mint(long long a){v = a;} mint(unsigned long long a){v = a;} long long val(){return v;} void modu(){v %= mod;} mint repeat2mint(const long long a,long long b){ mint ret = 1,p = a; while(b){ if(b&1) ret *= p; p *= p; b >>= 1; } return ret; }; mint operator+(const mint b){return mint(v)+=b;} mint operator-(const mint b){return mint(v)-=b;} mint operator*(const mint b){return mint(v)*=b;} mint operator/(const mint b){return mint(v)/=b;} mint operator+=(const mint b){ v += b.v; if(v >= mod) v -= mod; return *this; } mint operator-=(const mint b){ v -= b.v; if(v < 0) v += mod; return *this; } mint operator*=(const mint b){v = v*b.v%mod; return *this;} mint operator/=(mint b){ if(b == 0) assert(false); int left = mod-2; while(left){if(left&1) *this *= b; b *= b; left >>= 1;} return *this; } mint operator++(int){*this += 1; return *this;} mint operator--(int){*this -= 1; return *this;} bool operator==(const mint b){return v == b.v;} bool operator!=(const mint b){return v != b.v;} bool operator>(const mint b){return v > b.v;} bool operator>=(const mint b){return v >= b.v;} bool operator<(const mint b){return v < b.v;} bool operator<=(const mint b){return v <= b.v;} mint pow(const long long x){return repeat2mint(v,x);} mint inv(){return mint(1)/v;} }; namespace to_fold{ //纏めて折り畳むためのやつ 苦労したが結局ほぼACLの写経. __int128_t safemod(__int128_t a,long long m){a %= m; if(a < 0) a += m; return a;} pair invgcd(long long a,long long b){ //return {gcd(a,b),x} (xa≡g(mod b)) a = safemod(a,b); if(a == 0) return {b,0}; long long x = 0,y = 1,memob = b; while(a){ long long q = b/a; b -= a*q; swap(x,y); y -= q*x; swap(a,b); } if(x < 0) x += memob/b; return {b,x}; } long long Garner(vector &A,vector &M){ __int128_t mulM = 1,x = A.at(0)%M.at(0); //Mの要素のペア互いに素必須. for(int i=1; i root,iroot; array rate2,irate2; array rate3,irate3; fftinfo(mint g){ root[rank2] = g.pow((mod-1)>>rank2); iroot[rank2] = root[rank2].inv(); for(int i=rank2-1; i>=0; i--){ root[i] = root[i+1]*root[i+1]; iroot[i] = iroot[i+1]*iroot[i+1]; } mint mul = 1,imul = 1; for(int i=0; i<=rank2-2; i++){ rate2[i] = root[i+2]*mul; irate2[i] = iroot[i+2]*imul; mul *= iroot[i+2],imul *= root[i+2]; } mul = 1,imul = 1; for(int i=0; i<=rank2-3; i++){ rate3.at(i) = root[i+3]*mul; irate3.at(i) = iroot[i+3]*imul; mul *= iroot[i+3],imul *= root[i+3]; } } }; mint findroot(){ if(mod == 998244353) return mint(3); else if(mod == 754974721) return mint(11); else if(mod == 167772161) return mint(3); else if(mod == 469762049) return mint(3); long long p = mod-1; vector P; for(long long i=2; i*i<=p; i++){ if(p%i) continue; while(p%i == 0) p /= i; P.push_back(i); } if(p != 1) P.push_back(p); p = mod-1; random_device rnd; mt19937 mt(rnd()); while(true){ mint ret = mt()%mod; if(ret == 1 || ret == 0) continue; if(ret.pow(p) != 1) continue; bool ok = true; for(auto check : P) if(ret.pow(p/check) == 1){ok = false; break;} if(ok) return ret; } //O(√P)らしいです. } void NTT(vector &A,fftinfo &info){ int N = A.size(),ln = countzero(N); int dep = 0; while(dep < ln){ if(ln-dep == 1){ int p = 1<<(ln-dep-1); mint rot = 1; for(int o=0; o<(1< &A,fftinfo &info){ int N = A.size(),ln = countzero(N); int dep = ln; while(dep){ if(dep == 1){ int p = 1<<(ln-dep); mint irot = 1; for(int o=0; o<(1<<(dep-1)); o++){ int offset = o<<(ln-dep+1); for(int i=0; i convolutionnaive(vector &A,vector &B){ vector ret(A.size()+B.size()-1); for(int i=0; i convolution(vector &A,vector &B){ int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1; if(siza == 0 || sizb == 0) return {}; while(N <= sizc) N <<= 1; vector ca = A,cb = B; ca.resize(N),cb.resize(N); if(min(siza,sizb) <= 40) return convolutionnaive(A,B); assert((mod-1)%N == 0); mint root = findroot(); fftinfo info(root); NTT(ca,info); NTT(cb,info); for(int i=0; i convolution_int(vector &A,vector B){ if(A.size() == 0 || B.size() == 0) return {}; vector ret; if(min(A.size(),B.size()) <= 40){ ret.resize(A.size()+B.size()-1); for(int i=0; i X,Y,Z; for(auto &a : A) X.push_back(a); for(auto &b : B) Y.push_back(b); Z = convolution(X,Y); for(auto &z : Z) ret.push_back(z.v); } return ret; } } using namespace to_fold; struct bigint{ //__int128_t以上の数にも対応. //計算量 普通O(桁数),掛け算O(桁数log桁数),割り算O(桁数log桁数)(重い). public: bool isMinus; //負かどうか. vector V;//絶対値. //先頭の要素の方が小さい位 5108->{8,0,1,5}. private: void slide(){ for(int i=0; i|a|<|b|,1->|a|>|b|,2->|a|==|b|. if(V.size() < b.V.size()) return 0; if(V.size() > b.V.size()) return 1; for(int i=V.size(); i--;){ if(V.at(i) == b.V.at(i)) continue; return V.at(i)>b.V.at(i); } return 2; } public: bigint():isMinus(false),V({}){} template bigint(T a){ if(a < 0) isMinus = true,a = -a; else isMinus = false; V = {}; while(a) V.push_back(a%10),a /= 10; } bigint(const string &s){ V = {}; if(s.size() == 0) isMinus = false; else{ if(s.at(0) == '-') isMinus = true; else isMinus = false; for(int i=s.size(); i--;) V.push_back(s.at(i)-'0'); if(isMinus) V.pop_back(); while(V.size() && V.back() == '0') V.pop_back(); } } bigint(const bigint &n){isMinus = n.isMinus; V = n.V;} bigint &operator=(const bigint &b) = default; bigint operator+(const bigint &b){ bigint ret; if(isMinus == b.isMinus){ ret = *this; ret.V.resize(max(V.size(),b.V.size())); for(int i=0; i one.V.size()) two.V.pop_back(); two.V.push_back(2); bigint next = invB*(two-one); invB.V.assign(2,0); invB.V.at(1) = next.V.back(); next.V.pop_back(); invB.V.at(0) = next.V.back(); } while(accu < need){ //精度倍々になる. bigint one = invB*b; two.V.pop_back(); while(two.V.size() < one.V.size()) two.V.push_back(0); two.V.push_back(2); bigint next = invB*(two-one); accu = min(accu<<1,need); invB.V.clear(); for(int i=max(0,(int)next.V.size()-accu); i= b){ //+1の可能性. int digit = 0; ret.V.push_back(0); ret.V.at(digit)++; while(ret.V.at(digit) == 10) ret.V.at(digit) = 0,ret.V.at(++digit)++; if(ret.V.back() == 0) ret.V.pop_back(); } return ret; } bigint operator%(const bigint &b){ //a>=0,b>0を仮定. bigint ret = *this; if(isMinus){ ret.isMinus = false; ret -= ret/b*b; if(ret != 0) ret.isMinus = true; } else ret -= ret/b*b; return ret; } bigint operator+=(const bigint &b){return *this=*this+b;} bigint operator-=(const bigint &b){return *this=*this-b;} bigint operator*=(const bigint &b){return *this=*this*b;} bigint operator/=(const bigint &b){return *this=*this/b;} bigint operator%=(const bigint &b){return *this=*this%b;} bool operator==(const bigint &b){ if(V.size() != b.V.size() || isMinus != b.isMinus) return false; return V == b.V; } bool operator<(const bigint &b){ if(isMinus && !b.isMinus) return true; if(!isMinus && b.isMinus) return false; if(!isMinus && !b.isMinus){ if(V.size() < b.V.size()) return true; if(V.size() > b.V.size()) return false; for(int i=V.size(); i--;){ if(V.at(i) == b.V.at(i)) continue; return V.at(i) < b.V.at(i); } return false; } else{ if(V.size() > b.V.size()) return true; if(V.size() < b.V.size()) return false; for(int i=V.size(); i--;){ if(V.at(i) == b.V.at(i)) continue; return V.at(i) > b.V.at(i); } return false; } } bool operator<=(const bigint &b){ if(isMinus && !b.isMinus) return true; if(!isMinus && b.isMinus) return false; if(!isMinus && !b.isMinus){ if(V.size() < b.V.size()) return true; if(V.size() > b.V.size()) return false; for(int i=V.size(); i--;){ if(V.at(i) == b.V.at(i)) continue; return V.at(i) < b.V.at(i); } return true; } else{ if(V.size() > b.V.size()) return true; if(V.size() < b.V.size()) return false; for(int i=V.size(); i--;){ if(V.at(i) == b.V.at(i)) continue; return V.at(i) > b.V.at(i); } return true; } } bool operator>(const bigint &b){return !(*this<=b);} bool operator>=(const bigint &b){return !(*this>(istream &is,bigint &a){ string s; cin >> s; a = bigint(s); return is; } ostream &operator<<(ostream &os,bigint a){ if(a.isMinus) cout << "-"; if(a.V.size() == 0) cout << 0; for(int i=a.V.size(); i--;) cout << a.V.at(i); return os; } __int128_t extgcd(__int128_t a, __int128_t b, __int128_t &x,__int128_t &y){ if(b == 0){x = 1,y = 0; return a;} __int128_t g = extgcd(b,a%b,y,x); y -= a/b*x; return g; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int Q; cin >> Q; while(Q--){ long long W,H,D,Mx,My,Hx,Hy,Vx,Vy; cin >> W >> H >> D >> Mx >> My >> Hx >> Hy >> Vx >> Vy; if(Vx < 0) Vx = -Vx,Mx = W-Mx,Hx = W-Hx; if(Vy < 0) Vy = -Vy,My = H-My,Hy = H-Hy; if(Vx == 0){ if(Mx == Hx && ((My > Hy && (My-Hy) <= D*Vy) || (My < Hy && (2*H-My-Hy) <= D*Vy))) cout << "Hit\n"; else cout << "Miss\n"; continue; } if(Vy == 0){ if(My == Hy && ((Mx > Hx && (Mx-Hx) <= D*Vx) || (Mx < Hx && (2*W-Mx-Hx) <= D*Vx))) cout << "Hit\n"; else cout << "Miss\n"; continue; } auto solve = [&](long long Gx,long long Gy) -> bool { __int128_t A = 2*W*Vy,B = -2*H*Vx,C = (Gy-Hy)*Vx-(Gx-Hx)*Vy; __int128_t x,y,g = gcd(A,-B); if(C%g != 0) return false; A /= g,B /= g,C /= g; extgcd(A,B,x,y); bigint m = C*y%A; assert((m*H*2+Gy-Hy)%Vy == 0); bigint t = (m*H*2+Gy-Hy)/Vy; t %= A*2*H/Vy; if(t < 0) t += A*2*H/Vy; return t<=D; }; long long g = gcd(Vx,Vy); D *= g; Vx /= g,Vy /= g; if(solve(Mx,My)||solve(Mx,2*H-My)||solve(2*W-Mx,My)||solve(2*W-Mx,2*H-My)) cout << "Hit\n"; else cout << "Miss\n"; } }