#include using namespace std; #define REP(i,a,b) for(i=a;i=BIG_INT_BASE){ k=a.a[i-1]/BIG_INT_BASE; a.a[i-1]-=k*BIG_INT_BASE; if(a.a[i-1]<0) k--, a.a[i-1]+=BIG_INT_BASE; a.a[i]+=k; } if(a.a[BIG_INT_SIZE-1]<0){ rep(i,BIG_INT_SIZE) a.a[i]=-a.a[i]; a=bigIntOrder(a); rep(i,BIG_INT_SIZE) a.a[i]=-a.a[i]; } return a; } bigInt llToBigInt(ll a){ bigInt c; int i; REP(i,1,BIG_INT_SIZE) c.a[i]=0; c.a[0]=a; return bigIntOrder(c); } int bigIntGreaterThan(bigInt a,bigInt b){ int i; for(i=BIG_INT_SIZE-1;i>=0;i--){ if(a.a[i]>b.a[i]) return 1; if(a.a[i]a[i]=a.a[i]; for(i=BIG_INT_SIZE-1;i;i--) c->a[i-1]+=(c->a[i]%b)*BIG_INT_BASE, c->a[i]/=b; *d = c->a[0]%b; c->a[0]/=b; } /* c=a/b, d=a%b */ void bigIntDivisions(bigInt a,bigInt b,bigInt *c,bigInt *d){ int i,j,s,sa,sb; ll ma,mb,mc; bigInt tmp; sa=bigIntSign(a); sb=bigIntSign(b); if(sa==-1) a=bigIntMultipleLL(a,-1); if(sb==-1) b=bigIntMultipleLL(b,-1); for(j=BIG_INT_SIZE-1;j;j--) if(b.a[j]) break; if(!j){ REP(i,1,BIG_INT_SIZE) d->a[i]=0; bigIntDivisionsLL(a,b.a[0],c,&(d->a[0])); }else{ for(i=BIG_INT_SIZE-1;i;i--) if(a.a[i]) break; s=i-j; if(s<0) s=0; rep(i,BIG_INT_SIZE) c->a[i]=0; while(s>=0){ ma=0; mb=BIG_INT_BASE-1; while(ma!=mb){ mc = (ma+mb)/2 + (ma+mb)%2; c->a[s]=mc; tmp=bigIntMultiple(*c,b); if(bigIntGreaterThan(tmp,a)) mb=mc-1; else ma=mc; } c->a[s]=ma; s--; } tmp = bigIntMultiple(b,*c); *d = bigIntMinus(a,tmp); } if(sa==-1 && sb==-1){ *d=bigIntMultipleLL(*d,-1); } else if(sa==-1 && sb!=-1){ *c=bigIntMultipleLL(*c,-1); *d=bigIntMultipleLL(*d,-1); } else if(sa!=-1 && sb==-1){ *c=bigIntMultipleLL(*c,-1); } } bigInt bigIntDivision(bigInt a,bigInt b){ bigInt c,d; bigIntDivisions(a,b,&c,&d); return c; } bigInt bigIntModular(bigInt a,bigInt b){ bigInt c,d; bigIntDivisions(a,b,&c,&d); return d; } int bigIntSign(bigInt a){ int i; for(i=BIG_INT_SIZE-1;i>=0;i--) if(a.a[i]){ if(a.a[i]<0) return -1; else return 1; } return 0; } bigInt bigIntAbs(bigInt a){ if(bigIntSign(a)==-1) return bigIntMultipleLL(a,-1LL); return a; } bigInt bigIntGCD(bigInt a,bigInt b){ if(bigIntSign(a)==-1) a=bigIntMultipleLL(a,-1); if(bigIntSign(b)==-1) b=bigIntMultipleLL(b,-1); if(bigIntIsZero(a)) return b; return bigIntGCD(bigIntModular(b,a),a); } int bigIntToChar(bigInt a,char ret[]){ int i,j,s=0,len=0; char ct[BIG_INT_CHAR_SIZE]; ll lt; if(bigIntSign(a)==-1){ ret[0]='-'; len=bigIntToChar(bigIntMultipleLL(a,-1LL),ret+1); return len+1; } rep(i,BIG_INT_SIZE){ lt=a.a[i]; rep(j,BIG_INT_DIGITS) ct[s++]=lt%10, lt/=10; } j=0; while(s--){ if(ct[s]) j=1; if(j) ret[len++]=ct[s]+'0'; } if(!len) ret[len++]='0'; ret[len]='\0'; return len; } void printBigInt(bigInt a){ int i,k; char tmp[BIG_INT_CHAR_SIZE]; k=bigIntToChar(a,tmp); rep(i,k) putchar(tmp[i]); } void putBigInt(bigInt a){ char tmp[BIG_INT_CHAR_SIZE]; bigIntToChar(a,tmp); puts(tmp); } bigInt bigIntDivisionLL(bigInt a,ll b){ bigInt res; ll tmp; bigIntDivisionsLL(a, b, &res, &tmp); return res; } bigInt bigIntSqrt(bigInt a){ bigInt c1=bigIntZero(),c2=a,c,mul; while( bigIntGreaterThan(c2,c1) ){ c = bigIntDivisionLL( bigIntPlus(bigIntPlus(c1,c2),bigIntOne()), 2); mul = bigIntMultiple(c,c); if( bigIntGreaterThan(mul,a) ) c2=bigIntMinus(c,bigIntOne()); else c1=c; } return c1; } bigInt bigIntCubicRoot(bigInt a){ bigInt c1=bigIntZero(),c2=a,c,mul; while( bigIntGreaterThan(c2,c1) ){ c = bigIntDivisionLL( bigIntPlus(bigIntPlus(c1,c2),bigIntOne()), 2); mul = bigIntMultiple(c,bigIntMultiple(c,c)); if( bigIntGreaterThan(mul,a) ) c2=bigIntMinus(c,bigIntOne()); else c1=c; } return c1; } void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);} void reader(int *x, int *y){reader(x);reader(y);} void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);} void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);} template T GCD(T a,T b){T r; while(a){r=b; b=a; a=r%a;} return b;} void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){ ll a0,a1,a2,b0,b1,b2,r0,r1,r2,q; r0=x; r1=y; a0=1; a1=0; b0=0; b1=1; while(r1>0){ q=r0/r1; r2=r0%r1; a2=a0-q*a1; b2=b0-q*b1; r0=r1; r1=r2; a0=a1; a1=a2; b0=b1; b1=b2; } *c=r0; *a=a0; *b=b0; } int solve(ll Vx, ll Vy, ll Sx, ll Sy, ll Dx, ll Dy){ if(Vx < 0) return solve(-Vx, Vy, -Sx, Sy, Dx, Dy); if(Vy < 0) return solve(Vx, -Vy, Sx, -Sy, Dx, Dy); int i; ll VVx, VVy, X, Y, g, A, B, C, D, XX, YY, Bx, By; bigInt BBx, BBy, gg, gg1, gg2; // printf("V %lld %lld , S %lld %lld, D %lld %lld\n",Vx,Vy,Sx,Sy,Dx,Dy); g = GCD(Vx, Vy); VVx = Vx / g; VVy = Vy / g; g = Sx / Dx; Sx -= g * Dx; g = Sy / Dy; Sy -= g * Dy; while(Sx < 0) Sx += Dx; while(Sx >= Dx) Sx -= Dx; while(Sy < 0) Sy += Dy; while(Sy >= Dy) Sy -= Dy; A = Dx * VVy; B = Dy * VVx; C = VVx * Sy - VVy * Sx; g = GCD(A,B); if(C%g) return 0; A /= g; B /= g; C /= g; // printf("ABC %lld %lld %lld\n",A,B,C); extended_euclid(A, B, &D, &X, &Y); BBx = bigIntMultiple(llToBigInt(C), llToBigInt(X)); BBy = bigIntMultiple(llToBigInt(-C), llToBigInt(Y)); // printf("XY %lld %lld\n",X,Y); // printf("XYB %lld %lld\n",Bx,By); if(A && B){ gg1 = bigIntDivision(BBx, llToBigInt(B)); gg2 = bigIntDivision(BBy, llToBigInt(A)); if(bigIntGreaterThan(gg1,gg2)) gg = gg2; else gg = gg1; BBx = bigIntMinus(BBx, bigIntMultiple(gg, llToBigInt(B))); BBy = bigIntMinus(BBy, bigIntMultiple(gg, llToBigInt(A))); if(bigIntGreaterThan(BBx, llToBigInt(2000000000000000000LL))) return 0; if(bigIntGreaterThan(BBy, llToBigInt(2000000000000000000LL))) return 0; Bx = By = 0; rep(i,BIG_INT_SIZE) Bx = Bx * BIG_INT_BASE + BBx.a[BIG_INT_SIZE-1-i]; rep(i,BIG_INT_SIZE) By = By * BIG_INT_BASE + BBy.a[BIG_INT_SIZE-1-i]; while(Bx-B >= 0 && By-A >= 0) Bx -= B, By -= A; while(Bx < 0 || By < 0) Bx += B, By += A; } else { Bx = By = 0; } // printf("XYB %lld %lld\n",Bx,By); if((double)Bx * Dx > 2e18) return 0; if((double)By * Dy > 2e18) return 0; XX = Sx + Bx * Dx; YY = Sy + By * Dy; // printf("XY %lld %lld\n",XX,YY); if(XX <= Vx && YY <= Vy) return 1; return 0; } int Q; int W, H, D, HX, HY, MX, MY, VX, VY; int main(){ int i, j, k; reader(&Q); while(Q--){ reader(&W,&H,&D); reader(&MX,&MY); reader(&HX,&HY); reader(&VX,&VY); k = 0; if(!k) k |= solve((ll)VX*D, (ll)VY*D, MX-HX, MY-HY, 2*W, 2*H); if(!k) k |= solve((ll)VX*D, (ll)VY*D, (2*W-MX)-HX, MY-HY, 2*W, 2*H); if(!k) k |= solve((ll)VX*D, (ll)VY*D, MX-HX, (2*H-MY)-HY, 2*W, 2*H); if(!k) k |= solve((ll)VX*D, (ll)VY*D, (2*W-MX)-HX, (2*H-MY)-HY, 2*W, 2*H); writer(k?"Hit\n":"Miss\n"); } return 0; }