結果

問題 No.62 リベリオン(Extra)
ユーザー Yang33
提出日時 2018-04-15 16:56:44
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 899 ms / 5,000 ms
コード長 22,164 bytes
コンパイル時間 2,998 ms
コンパイル使用メモリ 165,300 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-30 12:17:56
合計ジャッジ時間 4,444 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0