#include // {{{ // https://codeforces.com/blog/entry/96344 #pragma GCC optimize("O2,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; template [[nodiscard]] static T MIN() { return std::numeric_limits::min(); } template [[nodiscard]] static T MAX() { return std::numeric_limits::max(); } template [[nodiscard]] static T sc(auto &&x) { return static_cast(x); } template [[nodiscard]] static T sz(auto &&x) { return static_cast(x.size()); } #define prln(...) std::println(__VA_ARGS__) #define pr(...) std::print(__VA_ARGS__) #ifdef LOCAL #define dbgln(...) std::println(__VA_ARGS__) #define dbg(...) std::print(__VA_ARGS__) #endif inline static void NO() { prln("NO"); } inline static void YES() { prln("YES"); } using ll = long long; using ld = long double; template using ve = std::vector; template using ar = std::array; template using pa = std::pair; template using tu = std::tuple; template using dq = std::deque; template using qu = std::queue; template using pq = std::priority_queue; template using st = std::stack; auto lb = [](auto... args) { return std::lower_bound(args...); }; auto ub = [](auto... args) { return std::upper_bound(args...); }; #define ff first #define ss second #define eb emplace_back #define pb push_back #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() // }}} #include #include using namespace __gnu_pbds; // https://mirror.codeforces.com/blog/entry/124683 namespace hashing { using i64 = std::int64_t; using u64 = std::uint64_t; static const u64 FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); #if USE_AES std::mt19937 rd(FIXED_RANDOM); const __m128i KEY1{(i64)rd(), (i64)rd()}; const __m128i KEY2{(i64)rd(), (i64)rd()}; #endif template struct custom_hash {}; template inline void hash_combine(u64 &seed, T const &v) { custom_hash hasher; seed ^= hasher(v) + 0x9e3779b97f4a7c15 + (seed << 12) + (seed >> 4); }; template struct custom_hash::value>::type> { u64 operator()(T _x) const { u64 x = _x; #if USE_AES __m128i m{i64(u64(x) * 0xbf58476d1ce4e5b9u64), (i64)FIXED_RANDOM}; __m128i y = _mm_aesenc_si128(m, KEY1); __m128i z = _mm_aesenc_si128(y, KEY2); return z[0]; #else x += 0x9e3779b97f4a7c15 + FIXED_RANDOM; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); #endif } }; template struct custom_hash()))>> { u64 operator()(T const &a) const { u64 value = FIXED_RANDOM; for (auto &x : a) hash_combine(value, x); return value; } }; template struct custom_hash> { u64 operator()(const std::tuple &a) const { u64 value = FIXED_RANDOM; std::apply( [&value](T const &...args) { (hash_combine(value, args), ...); }, a); return value; } }; template struct custom_hash> { u64 operator()(std::pair const &a) const { u64 value = FIXED_RANDOM; hash_combine(value, a.first); hash_combine(value, a.second); return value; } }; }; // namespace hashing #ifdef PB_DS_ASSOC_CNTNR_HPP template using hashtable = gp_hash_table< Key, Value, hashing::custom_hash, std::equal_to, direct_mask_range_hashing<>, linear_probe_fn<>, hash_standard_resize_policy, hash_load_check_resize_trigger<>, true>>; #endif #ifdef PB_DS_TREE_POLICY_HPP template using multitree = tree, rb_tree_tag, tree_order_statistics_node_update>; template using rbtree = tree, rb_tree_tag, tree_order_statistics_node_update>; #endif unordered_map> DIR; void solve() { // NOTE: locked out, stopped thikning. missed key idea that b/c there // are 2 * n * m states, you can manually walk the simulation // extra step for simplicity // continue making conclusions after key insight found int n, m, sr, sc, er, ec; string d; cin >> n >> m >> sr >> sc >> er >> ec >> d; auto [dr, dc] = DIR[d]; set> seen; ll ans = 0; while (true) { if (sr == er && sc == ec) { prln("{}", ans); return; } auto state = make_tuple(sr, sc, dr, dc); if (seen.count(state)) { prln("-1"); return; } seen.insert(state); int steps = MAX(); if (dr > 0) steps = min(steps, n - sr); else if (dr < 0) steps = min(steps, sr - 1); if (dc > 0) steps = min(steps, m - sc); else if (dc < 0) steps = min(steps, sc - 1); int dt_r = er - sr; int dt_c = ec - sc; if (dt_r * dc == dt_c * dr) { int k_r = (dr != 0) ? (dt_r / dr) : MAX(); int k_c = (dc != 0) ? (dt_c / dc) : MAX(); if (k_r == k_c && k_r >= 0 && k_r <= steps) { ans += k_r; prln("{}", ans); return; } } ans += steps; sr += dr * steps; sc += dc * steps; bool is_corner = (sr == 1 || sr == n) && (sc == 1 || sc == m); if (is_corner) { dr *= -1; dc *= -1; } else { if (sr == 1 || sr == n) dr *= -1; if (sc == 1 || sc == m) dc *= -1; } } } int main() { // {{{ cin.tie(nullptr)->sync_with_stdio(false); cin.exceptions(cin.failbit); DIR["DR"] = {1, 1}; DIR["DL"] = {1, -1}; DIR["UR"] = {-1, 1}; DIR["UL"] = {-1, -1}; int t = 1; cin >> t; while (t--) { solve(); } return 0; } // }}}