結果
| 問題 | No.62 リベリオン(Extra) |
| ユーザー |
 Yang33
|
| 提出日時 | 2018-04-15 16:56:44 |
| 言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 896 ms / 5,000 ms |
| コード長 | 22,164 bytes |
| コンパイル時間 | 2,865 ms |
| コンパイル使用メモリ | 165,296 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-05-07 17:36:32 |
| 合計ジャッジ時間 | 4,707 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 61 ms
5,376 KB |
| testcase_03 | AC | 63 ms
5,376 KB |
| testcase_04 | AC | 896 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using VS = vector<string>; using LL = long long;
using VI = vector<int>; using VVI = vector<VI>;
using PII = pair<int, int>; using PLL = pair<LL, LL>;
using VL = vector<LL>; using VVL = vector<VL>;
#define ALL(a) begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9; const LL LINF = 1e16;
const LL MOD = 1000000007; const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 }; int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
/* ----- 2018/04/15 Problem: yukicoder 061 / Link: http://yukicoder.me/problems/no/061 ----- */
/* ------問題------
-----問題ここまで----- */
/* -----解説等-----
----解説ここまで---- */
//const int base = 1000000000; //blockの幅
//const int base_digits = 9; //
//
//struct BigInt {
// vector<int> a;
// int sign;
//
// BigInt() :
// sign(1) {
// }
//
// BigInt(long long v) {
// *this = v;
// }
//
// BigInt(const string &s) {
// read(s);
// }
//
// void operator=(const BigInt &v) {
// sign = v.sign;
// a = v.a;
// }
//
// void operator=(long long v) {
// sign = 1;
// if (v < 0)
// sign = -1, v = -v;
// a.clear();
// for (; v > 0; v = v / base)
// a.push_back(v % base);
// }
//
// BigInt operator+(const BigInt &v) const {
// if (sign == v.sign) {
// BigInt res = v;
//
// for (int i = 0, carry = 0; i < (int)max(a.size(), v.a.size()) || carry; ++i) {
// if (i == (int)res.a.size())
// res.a.push_back(0);
// res.a[i] += carry + (i < (int)a.size() ? a[i] : 0);
// carry = res.a[i] >= base;
// if (carry)
// res.a[i] -= base;
// }
// return res;
// }
// return *this - (-v);
// }
//
// BigInt operator-(const BigInt &v) const {
// if (sign == v.sign) {
// if (abs() >= v.abs()) {
// BigInt res = *this;
// for (int i = 0, carry = 0; i < (int)v.a.size() || carry; ++i) {
// res.a[i] -= carry + (i < (int)v.a.size() ? v.a[i] : 0);
// carry = res.a[i] < 0;
// if (carry)
// res.a[i] += base;
// }
// res.trim();
// return res;
// }
// return -(v - *this);
// }
// return *this + (-v);
// }
//
// void operator*=(int v) {
// if (v < 0)
// sign = -sign, v = -v;
// for (int i = 0, carry = 0; i < (int)a.size() || carry; ++i) {
// if (i == (int)a.size())
// a.push_back(0);
// long long cur = a[i] * (long long)v + carry;
// carry = (int)(cur / base);
// a[i] = (int)(cur % base);
// //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
// }
// trim();
// }
//
// BigInt operator*(int v) const {
// BigInt res = *this;
// res *= v;
// return res;
// }
//
// friend pair<BigInt, BigInt> divmod(const BigInt &a1, const BigInt &b1) {
// int norm = base / (b1.a.back() + 1);
// BigInt a = a1.abs() * norm;
// BigInt b = b1.abs() * norm;
// BigInt q, r;
// q.a.resize(a.a.size());
//
// for (int i = a.a.size() - 1; i >= 0; i--) {
// r *= base;
// r += a.a[i];
// int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
// int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
// int d = ((long long)base * s1 + s2) / b.a.back();
// r -= b * d;
// while (r < 0)
// r += b, --d;
// q.a[i] = d;
// }
//
// q.sign = a1.sign * b1.sign;
// r.sign = a1.sign;
// q.trim();
// r.trim();
// return make_pair(q, r / norm);
// }
//
// friend BigInt sqrt(const BigInt &a1) {
// BigInt a = a1;
// while (a.a.empty() || a.a.size() % 2 == 1)
// a.a.push_back(0);
//
// int n = a.a.size();
//
// int firstDigit = (int)sqrt((double)a.a[n - 1] * base + a.a[n - 2]);
// int norm = base / (firstDigit + 1);
// a *= norm;
// a *= norm;
// while (a.a.empty() || a.a.size() % 2 == 1)
// a.a.push_back(0);
//
// BigInt r = (long long)a.a[n - 1] * base + a.a[n - 2];
// firstDigit = (int)sqrt((double)a.a[n - 1] * base + a.a[n - 2]);
// int q = firstDigit;
// BigInt res;
//
// for (int j = n / 2 - 1; j >= 0; j--) {
// for (; ; --q) {
// BigInt r1 = (r - (res * 2 * base + q) * q) * base * base + (j > 0 ? (long long)a.a[2 * j - 1] * base + a.a[2 * j - 2] : 0);
// if (r1 >= 0) {
// r = r1;
// break;
// }
// }
// res *= base;
// res += q;
//
// if (j > 0) {
// int d1 = res.a.size() + 2 < r.a.size() ? r.a[res.a.size() + 2] : 0;
// int d2 = res.a.size() + 1 < r.a.size() ? r.a[res.a.size() + 1] : 0;
// int d3 = res.a.size() < r.a.size() ? r.a[res.a.size()] : 0;
// q = ((long long)d1 * base * base + (long long)d2 * base + d3) / (firstDigit * 2);
// }
// }
//
// res.trim();
// return res / norm;
// }
//
// BigInt operator/(const BigInt &v) const {
// return divmod(*this, v).first;
// }
//
// BigInt operator%(const BigInt &v) const {
// return divmod(*this, v).second;
// }
//
// void operator/=(int v) {
// if (v < 0)
// sign = -sign, v = -v;
// for (int i = (int)a.size() - 1, rem = 0; i >= 0; --i) {
// long long cur = a[i] + rem * (long long)base;
// a[i] = (int)(cur / v);
// rem = (int)(cur % v);
// }
// trim();
// }
//
// BigInt operator/(int v) const {
// BigInt res = *this;
// res /= v;
// return res;
// }
//
// int operator%(int v) const {
// if (v < 0)
// v = -v;
// int m = 0;
// for (int i = a.size() - 1; i >= 0; --i)
// m = (a[i] + m * (long long)base) % v;
// return m * sign;
// }
//
// void operator+=(const BigInt &v) {
// *this = *this + v;
// }
// void operator-=(const BigInt &v) {
// *this = *this - v;
// }
// void operator*=(const BigInt &v) {
// *this = *this * v;
// }
// void operator/=(const BigInt &v) {
// *this = *this / v;
// }
//
// bool operator<(const BigInt &v) const {
// if (sign != v.sign)
// return sign < v.sign;
// if (a.size() != v.a.size())
// return a.size() * sign < v.a.size() * v.sign;
// for (int i = a.size() - 1; i >= 0; i--)
// if (a[i] != v.a[i])
// return a[i] * sign < v.a[i] * sign;
// return false;
// }
//
// bool operator>(const BigInt &v) const {
// return v < *this;
// }
// bool operator<=(const BigInt &v) const {
// return !(v < *this);
// }
// bool operator>=(const BigInt &v) const {
// return !(*this < v);
// }
// bool operator==(const BigInt &v) const {
// return !(*this < v) && !(v < *this);
// }
// bool operator!=(const BigInt &v) const {
// return *this < v || v < *this;
// }
//
// void trim() {
// while (!a.empty() && !a.back())
// a.pop_back();
// if (a.empty())
// sign = 1;
// }
//
// bool isZero() const {
// return a.empty() || (a.size() == 1 && !a[0]);
// }
//
// BigInt operator-() const {
// BigInt res = *this;
// res.sign = -sign;
// return res;
// }
//
// BigInt abs() const {
// BigInt res = *this;
// res.sign *= res.sign;
// return res;
// }
//
// long long longValue() const {
// long long res = 0;
// for (int i = a.size() - 1; i >= 0; i--)
// res = res * base + a[i];
// return res * sign;
// }
//
// friend BigInt gcd(const BigInt &a, const BigInt &b) {
// return b.isZero() ? a : gcd(b, a % b);
// }
// friend BigInt lcm(const BigInt &a, const BigInt &b) {
// return a / gcd(a, b) * b;
// }
//
// void read(const string &s) {
// sign = 1;
// a.clear();
// int pos = 0;
// while (pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')) {
// if (s[pos] == '-')
// sign = -sign;
// ++pos;
// }
// for (int i = s.size() - 1; i >= pos; i -= base_digits) {
// int x = 0;
// for (int j = max(pos, i - base_digits + 1); j <= i; j++)
// x = x * 10 + s[j] - '0';
// a.push_back(x);
// }
// trim();
// }
//
// friend istream& operator>>(istream &stream, BigInt &v) {
// string s;
// stream >> s;
// v.read(s);
// return stream;
// }
//
// friend ostream& operator<<(ostream &stream, const BigInt &v) {
// if (v.sign == -1 && !v.isZero())
// stream << '-';
// stream << (v.a.empty() ? 0 : v.a.back());
// for (int i = (int)v.a.size() - 2; i >= 0; --i)
// stream << setw(base_digits) << setfill('0') << v.a[i];
// return stream;
// }
//
// static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
// vector<long long> p(max(old_digits, new_digits) + 1);
// p[0] = 1;
// for (int i = 1; i < (int)p.size(); i++)
// p[i] = p[i - 1] * 10;
// vector<int> res;
// long long cur = 0;
// int cur_digits = 0;
// for (int i = 0; i < (int)a.size(); i++) {
// cur += a[i] * p[cur_digits];
// cur_digits += old_digits;
// while (cur_digits >= new_digits) {
// res.push_back(int(cur % p[new_digits]));
// cur /= p[new_digits];
// cur_digits -= new_digits;
// }
// }
// res.push_back((int)cur);
// while (!res.empty() && !res.back())
// res.pop_back();
// return res;
// }
//
// typedef vector<long long> vll;
//
// static vll karatsubaMultiply(const vll &a, const vll &b) {
// int n = a.size();
// vll res(n + n);
// if (n <= 32) {
// for (int i = 0; i < n; i++)
// for (int j = 0; j < n; j++)
// res[i + j] += a[i] * b[j];
// return res;
// }
//
// int k = n >> 1;
// vll a1(a.begin(), a.begin() + k);
// vll a2(a.begin() + k, a.end());
// vll b1(b.begin(), b.begin() + k);
// vll b2(b.begin() + k, b.end());
//
// vll a1b1 = karatsubaMultiply(a1, b1);
// vll a2b2 = karatsubaMultiply(a2, b2);
//
// for (int i = 0; i < k; i++)
// a2[i] += a1[i];
// for (int i = 0; i < k; i++)
// b2[i] += b1[i];
//
// vll r = karatsubaMultiply(a2, b2);
// for (int i = 0; i < (int)a1b1.size(); i++)
// r[i] -= a1b1[i];
// for (int i = 0; i < (int)a2b2.size(); i++)
// r[i] -= a2b2[i];
//
// for (int i = 0; i < (int)r.size(); i++)
// res[i + k] += r[i];
// for (int i = 0; i < (int)a1b1.size(); i++)
// res[i] += a1b1[i];
// for (int i = 0; i < (int)a2b2.size(); i++)
// res[i + n] += a2b2[i];
// return res;
// }
//
// BigInt operator*(const BigInt &v) const {
// vector<int> a6 = convert_base(this->a, base_digits, 6);
// vector<int> b6 = convert_base(v.a, base_digits, 6);
// vll a(a6.begin(), a6.end());
// vll b(b6.begin(), b6.end());
// while (a.size() < b.size())
// a.push_back(0);
// while (b.size() < a.size())
// b.push_back(0);
// while (a.size() & (a.size() - 1))
// a.push_back(0), b.push_back(0);
// vll c = karatsubaMultiply(a, b);
// BigInt res;
// res.sign = sign * v.sign;
// for (int i = 0, carry = 0; i < (int)c.size(); i++) {
// long long cur = c[i] + carry;
// res.a.push_back((int)(cur % 1000000));
// carry = (int)(cur / 1000000);
// }
// res.a = convert_base(res.a, 6, base_digits);
// res.trim();
// return res;
// }
//
// friend BigInt pow(const BigInt &x, BigInt a) {
// BigInt res = 1;
// BigInt e = x;
// for (; !a.isZero(); a /= BigInt(2)) {
// if (a % 2 == 1) {
// res *= e;
// }
// e *= e;
// }
// return res;
// }
// friend BigInt powmod(const BigInt &x, BigInt a, const BigInt &mod) {
// BigInt X = x%mod;
// BigInt res = 1;
// BigInt e = X;
// for (; !a.isZero(); a /= BigInt(2)) {
// if (a % 2 == 1) {
// res = (res*e) % mod;
// }
// e = (e*e) % mod;
// }
// return res%mod;
// }
//
//
// // 拡張ユークリッド互除法 a*x+b*y=1となる整数解x,yを求める
// // 返却値: gcd(a,b)
// friend BigInt extgcd(BigInt a, BigInt b, BigInt &x, BigInt &y) {
// BigInt gcd_ = a;
// if (b != 0) {
// gcd_ = extgcd(b, a%b, y, x);
// y -= (a / b)*x;
// }
// else {
// x = 1; y = 0;
// }
// return gcd_;
// }
//
//};
struct BigInt {
public:
using LL = long long int;
static const LL BASE = 1000000000;
const int DIG = 9;
bool neg;
std::vector<LL> dig;
BigInt() : neg(false), dig(1, 0ll) {}
BigInt(const char* str) : BigInt(std::string(str)) {}
BigInt(const std::string& str) : neg(false) {
if (str.empty()) {
dig.assign(1, 0);
return;
}
int b = 0;
if (str[b] == '-') {
neg = true;
++b;
}
LL crt = 0;
LL p = 1;
for (int i = (int)(str.size()) - 1; i >= b; --i, p *= 10) {
if (p == BASE) {
dig.emplace_back(crt);
crt = 0;
p = 1;
}
if (!isdigit(str[i])) {
throw "Non digit is given.";
}
crt += p * (str[i] - '0');
}
dig.emplace_back(crt);
norm();
}
BigInt(LL x) : neg(x < 0), dig(1, std::abs(x)) {
for (unsigned int i = 0; i < dig.size(); ++i) {
if (dig[i] >= BASE) {
dig.emplace_back(dig[i] / BASE);
dig[i] %= BASE;
}
}
}
BigInt& operator=(const BigInt& rhs) {
neg = rhs.neg;
dig = rhs.dig;
return *this;
}
BigInt& operator=(LL x) { return *this = BigInt(x); }
BigInt& operator=(const char* s) { return *this = BigInt(s); }
BigInt& operator=(const std::string& s) { return *this = BigInt(s); }
bool iszero() const {
return dig.size() == 1 && dig[0] == 0;
}
BigInt operator-() const {
BigInt res = *this;
if (!res.iszero())
res.neg = !res.neg;
return res;
}
//! ignoring sign
static int comp(const BigInt& l, const BigInt& r) {
if (l.dig.size() != r.dig.size())
return (l.dig.size() < r.dig.size() ? -1 : 1);
for (int i = (int)(l.dig.size()) - 1; i >= 0; --i) {
if (l.dig[i] != r.dig[i])
return (l.dig[i] < r.dig[i] ? -1 : 1);
}
return 0;
}
//! add ignoring sign
static void add(BigInt& l, const BigInt& rhs) {
unsigned int i;
for (i = 0; i < rhs.dig.size(); ++i) {
if (l.dig.size() <= i) {
l.dig.emplace_back(rhs.dig[i]);
}
else {
l.dig[i] += rhs.dig[i];
if (l.dig[i] >= BASE) {
l.dig[i] -= BASE;
if (l.dig.size() <= i + 1)
l.dig.emplace_back(0);
l.dig[i + 1]++;
}
else if (l.dig[i] < 0) {
l.dig[i] += BASE;
if (l.dig.size() <= i + 1)
l.dig.emplace_back(0);
l.dig[i + 1]--;
}
}
}
for (; i < l.dig.size(); ++i)
if (l.dig[i] >= BASE) {
l.dig[i] -= BASE;
if (l.dig.size() <= i + 1)
l.dig.emplace_back(0);
l.dig[i + 1]++;
}
}
// subtract ignoring sign, supposed to l >= rhs
static void sub(BigInt& l, const BigInt& rhs) {
unsigned int i;
for (i = 0; i < rhs.dig.size(); ++i) {
l.dig[i] -= rhs.dig[i];
if (l.dig[i] < 0) {
l.dig[i] += BASE;
l.dig[i + 1]--;
}
}
for (; i < l.dig.size(); ++i)
if (l.dig[i] < 0) {
l.dig[i] += BASE;
l.dig[i + 1]--;
}
}
void flip() {
for (unsigned int i = 0; i < dig.size(); ++i)
dig[i] *= -1;
}
void norm() {
while (dig.size() > 1 && dig.back() == 0) dig.pop_back();
if (iszero()) neg = false;
}
bool operator==(const BigInt& rhs) const {
if (neg != rhs.neg || dig.size() != rhs.dig.size()) return false;
return comp(*this, rhs) == 0;
}
bool operator<(const BigInt& rhs) const {
if (neg != rhs.neg) return neg ? true : false;
if (neg) return comp(rhs, *this) == -1;
return comp(*this, rhs) == -1;
}
bool operator<=(const BigInt& rhs) const {
if (neg != rhs.neg) return neg ? true : false;
if (neg) return comp(rhs, *this) <= 0;
return comp(*this, rhs) <= 0;
}
bool operator!=(const BigInt& rhs) const { return !(*this == rhs); }
bool operator>(const BigInt& rhs) const { return rhs < *this; }
bool operator>=(const BigInt& rhs) const { return rhs <= *this; }
// ignoring sign
void incl() {
for (unsigned int i = 0; i < dig.size(); ++i)
if (++dig[i] == BASE) {
dig[i] = 0;
if (i + 1 == dig.size()) {
dig.push_back(1);
break;
}
}
else break;
}
// ignoring sign
void decl() {
if (iszero()) {
dig[0] = 1;
neg = true;
return;
}
for (unsigned int i = 0; i < dig.size(); ++i)
if (--dig[i] == -1)
dig[i] = BASE - 1;
else break;
norm();
}
BigInt& operator++() {
if (!neg) incl(); else decl();
return *this;
}
BigInt operator++(int) {
BigInt res = *this;
if (!neg) incl(); else decl();
return res;
}
BigInt& operator--() {
if (!neg) decl(); else incl();
return *this;
}
BigInt operator--(int) {
BigInt res = *this;
if (!neg) decl(); else incl();
return res;
}
BigInt& operator+=(const BigInt& rhs) {
if (!this->neg) {
if (!rhs.neg)
add(*this, rhs);
else {
if (comp(*this, rhs) >= 0)
sub(*this, rhs);
else {
flip();
add(*this, rhs);
neg = true;
}
}
}
else {
if (!rhs.neg) {
if (comp(rhs, *this) >= 0) {
flip();
add(*this, rhs);
neg = false;
}
else
sub(*this, rhs);
}
else
add(*this, rhs);
}
norm();
return *this;
}
BigInt& operator-=(const BigInt& rhs) { return *this += -rhs; }
BigInt operator+(const BigInt& rhs) const { BigInt res = *this; return res += rhs; }
BigInt operator-(const BigInt& rhs) const { BigInt res = *this; return res -= rhs; }
BigInt operator*(const BigInt& rhs) const {
BigInt res;
res.dig.assign(dig.size() + rhs.dig.size() + 1, 0ll);
res.neg = neg ^ rhs.neg;
for (unsigned i = 0; i < rhs.dig.size(); ++i) {
if (rhs.dig[i] == 0) continue;
for (unsigned j = 0; j < dig.size(); ++j) {
res.dig[i + j] += rhs.dig[i] * dig[j];
if (res.dig[i + j] >= BASE) {
res.dig[i + j + 1] += res.dig[i + j] / BASE;
res.dig[i + j] %= BASE;
}
}
}
res.norm();
return res;
}
BigInt operator*=(const BigInt& rhs) { return *this = *this * rhs; }
static void divll(BigInt& x, LL& r, LL d) {
bool lneg = x.neg;
x.neg ^= (d < 0);
if (d < 0) d *= -1;
r = 0;
for (int i = (int)x.dig.size() - 1; i >= 0; --i) {
r = r * BASE + x.dig[i];
x.dig[i] = r / d;
r %= d;
}
x.norm();
if (r != 0 && lneg)
r *= -1;
}
void powB(LL x) {
if (iszero()) return;
while (x > 0) {
dig.insert(dig.begin(), 0ll);
--x;
}
}
static void divmod(BigInt& q, BigInt& r, const BigInt& lhs, const BigInt& rhs) {
int cmp = comp(lhs, rhs);
if (cmp < 0) {
q.dig = std::vector<LL>(1, 0ll);
q.neg = false;
r = lhs;
return;
}
else if (cmp == 0) {
q.dig = std::vector<LL>(1, 1ll);
q.neg = false;
r.dig = std::vector<LL>(1, 0ll);
r.neg = false;
return;
}
if (rhs.dig.size() == 1) {
LL rl;
q = lhs;
divll(q, rl, rhs.dig[0] * (rhs.neg ? -1ll : 1ll));
r = rl;
return;
}
q.neg = r.neg = false;
int u = lhs.dig.size() - rhs.dig.size() + 1;
q.dig.assign(u + 1, 0ll);
LL K = BASE / (rhs.dig.back() + 1);
BigInt ltmp = lhs, rtmp = rhs;
ltmp.neg = rtmp.neg = false;
if (K > 1) {
ltmp *= K;
rtmp *= K;
}
LL x = ltmp.dig.back() / rtmp.dig.back();
if (x == 0) {
--u;
x = (ltmp.dig.back() * BASE + ltmp.dig[ltmp.dig.size() - 2]) / rtmp.dig.back();
}
BigInt w = 0ll;
while (true) {
w = rtmp;
w.powB(u);
if (comp(w, ltmp) > 0) {
--u;
continue;
}
while (true) {
w = rtmp * x;
w.powB(u);
if (comp(w, ltmp) <= 0) break;
--x;
}
q.dig[u--] = x;
ltmp -= w;
if (ltmp == 0ll || u < 0) break;
x = std::min(BASE - 1,
(ltmp.dig.back() * BASE + ltmp.dig[ltmp.dig.size() - 2]) / rtmp.dig.back());
}
q.norm();
r = ltmp;
if (ltmp != 0ll) divll(r, x, K);
q.neg = lhs.neg ^ rhs.neg;
r.neg = lhs.neg;
r.norm();
}
BigInt operator/(const BigInt& rhs) const {
BigInt q, r;
divmod(q, r, *this, rhs);
return q;
}
BigInt operator%(const BigInt& rhs) const {
BigInt q, r;
divmod(q, r, *this, rhs);
return r;
}
BigInt& operator/=(BigInt rhs) { return *this = *this / rhs; }
BigInt& operator%=(BigInt rhs) { return *this = *this % rhs; }
std::string to_string() const {
assert(!dig.empty());
std::string res = neg ? "-" : "";
std::ostringstream os;
os << std::to_string(dig.back());
for (int i = (int)(dig.size()) - 2; i >= 0; --i) {
os << std::setfill('0') << std::setw(DIG) << dig[i];
}
res += os.str();
return res;
}
// convert long long int anyway
LL to_ll() const {
LL res = 0, p = 1;
for (unsigned int i = 0; i < dig.size(); ++i) {
res += dig[i] * p;
p *= BASE;
}
return res * (neg ? -1ll : 1);
}
};
int xx = 0;
BigInt zero(xx);
BigInt gcd(const BigInt &a, const BigInt &b) {
return b == zero ? a : gcd(b, a % b);
}
// 拡張ユークリッド互除法 a*x+b*y=1となる整数解x,yを求める
// 返却値: gcd(a,b)
BigInt extgcd(BigInt a, BigInt b, BigInt &x, BigInt &y) {
BigInt gcd_ = a;
if (!b.iszero()) {
gcd_ = extgcd(b, a%b, y, x);
y -= (a / b)*x;
}
else {
x = 1; y = zero;
}
return gcd_;
}
std::ostream& operator<<(std::ostream& os, const BigInt& x) { return os << x.to_string(); }
BigInt W, H, D, Mx, My, Hx, Hy, Vx, Vy;
int f(BigInt tx, BigInt ty) {
BigInt A = W * 2 * Vy;
BigInt B = -H * 2 * Vx;
BigInt C = ty*Vx - tx*Vy + Hx*Vy - Hy*Vx;
BigInt g = gcd(A, -B);
if (!(C % g).iszero()) {
return 0;
}
A /= g; B /= g; C /= g;
BigInt x, y;
g = extgcd(B, A, y, x);
if (g < zero) {
g *= -1; y *= -1; x *= -1;
}
BigInt m = C*y%A;
BigInt tv = (ty + H*m * 2 - Hy) / Vy;
tv = tv % (H * 2 * A / Vy);
if (tv < zero)tv += H * 2 * A / Vy;
return (tv <= D);
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int Q; cin >> Q;
FOR(q, 0, Q) {
string w, h, d, mx, my, hx, hy, vx, vy;
cin >> w >> h >> d >> mx >> my >> hx >> hy >> vx >> vy;
W = w, H = h, D = d, Mx = mx, My = my, Hx = hx, Hy = hy, Vx = vx, Vy = vy;
if (Vx < zero) {
Mx = W - Mx;
Hx = W - Hx;
Vx = -Vx;
}
if (Vy < zero) {
My = H - My;
Hy = H - Hy;
Vy = -Vy;
}
int res = 0;
if (Vx == zero) {
if (Mx == Hx && ((My > Hy && My - Hy <= D*Vy) || (My < Hy && H * 2 - My - Hy <= D*Vy))) {
res = 1;
}
else {
res = -1;
}
}
else if (Vy == zero) {
if (My == Hy && ((Mx > Hx && Mx - Hx <= D*Vx) || (Mx < Hx && W * 2 - Mx - Hx <= D*Vx))) {
res = 1;
}
else {
res = -1;
}
}
if (res) {
if (res == 1)printf("Hit\n");
else printf("Miss\n");
//cout << (res == 1 ? "Hit" : "Miss") << endl;
}
else {
BigInt g = gcd(Vx, Vy);
D *= g;
Vx /= g, Vy /= g;
if (f(Mx, My) || f(W * 2 - Mx, My) || f(Mx, H * 2 - My) || f(W * 2 - Mx, H * 2 - My)) {
res = 1;
}
if (res == 1)printf("Hit\n");
else printf("Miss\n");
//cout << (res != 0 ? "Hit" : "Miss") << endl;
}
}
return 0;
}