#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
#include <iostream>
#include <vector>
using namespace atcoder;
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vc = vector<char>;
using vvc = vector<vc>;
using lll = __int128_t;
using vs = vector<string>;
using pii = pair<long long, long long>;
using mint = modint1000000007;
#define mp make_pair
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) n.begin(), n.end()
#define rALL(n) n.rbegin(), n.rend()
#define fore(i, a) for (auto &i : a)
#define IN(a, x, b) (a <= x && x < b)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                        \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(0);
template <class T>
inline T CHMAX(T &a, const T b) {
  return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T &a, const T b) {
  return a = (a > b) ? b : a;
}
#include <algorithm>  // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>     // bitset
#include <cctype>     // isupper, islower, isdigit, toupper, tolower
#include <cstdint>    // int64_t, int*_t
#include <cstdio>     // printf
#include <deque>      // deque
#include <iostream>   // cout, endl, cin
#include <map>        // map
#include <queue>      // queue, priority_queue
#include <set>        // set
#include <stack>      // stack
#include <string>     // string, to_string, stoi
#include <tuple>      // tuple, make_tuple
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <utility>        // pair, make_pair
#include <vector>         // vector
using namespace std;
const long double PI = acos(-1.0L);
const long double EPS = 1e-10;
const double INF = 1e18;
#include <type_traits>

#define LOOP(n) REPI($_, (n))

#define REPI(i, n) \
  for (int i = 0, i##_length = static_cast<int>(n); i < i##_length; ++i)
#define REPF(i, l, r)                                                        \
  for (std::common_type_t<decltype(l), decltype(r)> i = (l), i##_last = (r); \
       i < i##_last; ++i)
#define REPIS(i, l, r, s)                                        \
  for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
           i = (l),                                              \
           i##_last = (r);                                       \
       i < i##_last; i += (s))

#define REPR(i, n) for (auto i = (n); --i >= 0;)
#define REPB(i, l, r)                                                        \
  for (std::common_type_t<decltype(l), decltype(r)> i = (r), i##_last = (l); \
       --i >= i##_last;)
#define REPRS(i, l, r, s)                                        \
  for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
           i = (l) + ((r) - (l)-1) / (s) * (s),                  \
           i##_last = (l);                                       \
       i >= i##_last; (i -= (s)))

#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)

#define FORO(i, n) \
  for (int i = 0, i##_last = static_cast<int>(n); i <= i##_last; ++i)
#define FORI(i, l, r)                                                        \
  for (std::common_type_t<decltype(l), decltype(r)> i = (l), i##_last = (r); \
       i <= i##_last; ++i)
#define FORIS(i, l, r, s)                                        \
  for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
           i = (l),                                              \
           i##_last = (r);                                       \
       i <= i##_last; i += (s))

#define FORRO(i, n) for (auto i = (n); i >= 0; --i)
#define FORR(i, l, r)                                                        \
  for (std::common_type_t<decltype(l), decltype(r)> i = (r), i##_last = (l); \
       i >= i##_last; --i)
#define FORRS(i, l, r, s)                                        \
  for (std::common_type_t<decltype(l), decltype(r), decltype(s)> \
           i = (l) + ((r) - (l)) / (s) * (s),                    \
           i##_last = (l);                                       \
       i >= i##_last; i -= (s))

#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)

#define ITR1(e0, v) for (const auto &e0 : (v))
#define ITRP1(e0, v) for (auto e0 : (v))
#define ITRR1(e0, v) for (auto &e0 : (v))

#define ITR2(e0, e1, v) for (const auto [e0, e1] : (v))
#define ITRP2(e0, e1, v) for (auto [e0, e1] : (v))
#define ITRR2(e0, e1, v) for (auto &[e0, e1] : (v))

#define ITR3(e0, e1, e2, v) for (const auto [e0, e1, e2] : (v))
#define ITRP3(e0, e1, e2, v) for (auto [e0, e1, e2] : (v))
#define ITRR3(e0, e1, e2, v) for (auto &[e0, e1, e2] : (v))

#define ITR4(e0, e1, e2, e3, v) for (const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0, e1, e2, e3, v) for (auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0, e1, e2, e3, v) for (auto &[e0, e1, e2, e3] : (v))

#define ITR(...) $OVERLOAD5(__VA_ARGS__, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) \
  $OVERLOAD5(__VA_ARGS__, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) \
  $OVERLOAD5(__VA_ARGS__, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
template <class Type>
class WeightedUnionFind {
 public:
  WeightedUnionFind() = default;

  /// @brief 重み付き Union-Find 木を構築します。
  /// @param n 要素数
  explicit WeightedUnionFind(size_t n)
      : m_parentsOrSize(n, -1), m_diffWeights(n) {}

  /// @brief 頂点 i の root のインデックスを返します。
  /// @param i 調べる頂点のインデックス
  /// @return 頂点 i の root のインデックス
  int find(int i) {
    if (m_parentsOrSize[i] < 0) {
      return i;
    }

    const int root = find(m_parentsOrSize[i]);

    m_diffWeights[i] += m_diffWeights[m_parentsOrSize[i]];

    // 経路圧縮
    return (m_parentsOrSize[i] = root);
  }

  /// @brief a のグループと b のグループを統合します。
  /// @param a 一方のインデックス
  /// @param b 他方のインデックス
  /// @param w (b の重み) - (a の重み)
  /// a を含むグループと b を含むグループを併合し、b の重みは a と比べて w
  /// 大きくなるようにする
  void merge(int a, int b, Type w) {
    w += weight(a);
    w -= weight(b);

    a = find(a);
    b = find(b);

    if (a != b) {
      // union by size (小さいほうが子になる）
      if (-m_parentsOrSize[a] < -m_parentsOrSize[b]) {
        std::swap(a, b);
        w = -w;
      }

      m_parentsOrSize[a] += m_parentsOrSize[b];
      m_parentsOrSize[b] = a;
      m_diffWeights[b] = w;
    }
  }

  /// @brief (b の重み) - (a の重み) を返します。
  /// @param a 一方のインデックス
  /// @param b 他方のインデックス
  /// @remark a と b が同じグループに属さない場合の結果は不定です。
  /// @return (b の重み) - (a の重み)
  ///(b の重み) - (a の重み) を返す。a と b
  /// が同じグループに属さない場合の結果は不定
  Type diff(int a, int b) { return (weight(b) - weight(a)); }

  /// @brief a と b が同じグループに属すかを返します。
  /// @param a 一方のインデックス
  /// @param b 他方のインデックス
  /// @return a と b が同じグループに属す場合 true, それ以外の場合は false
  /// a と b が同じグループに属すかを返す
  bool connected(int a, int b) { return (find(a) == find(b)); }

  /// @brief i が属するグループの要素数を返します。
  /// @param i インデックス
  /// @return i が属するグループの要素数
  int size(int i) { return -m_parentsOrSize[find(i)]; }

 private:
  // m_parentsOrSize[i] は i の 親,
  // ただし root の場合は (-1 * そのグループに属する要素数)
  std::vector<int> m_parentsOrSize;

  // 重み
  std::vector<Type> m_diffWeights;

  Type weight(int i) {
    find(i);  // 経路圧縮
    return m_diffWeights[i];
  }
};

__int128 parse(string &s) {
  __int128 ret = 0;
  for (int i = 0; i < s.length(); i++)
    if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0';
  return ret;
}

ll GCD(ll m, ll n) {
  // ベースケース
  if (n == 0) return m;

  // 再帰呼び出し
  return GCD(n, m % n);
}

ll minlong = 0;

long long Power(long long a, long long b, long long m) {
  long long p = a, Answer = 1;
  for (int i = 0; i < 63; i++) {
    ll wari = (1LL << i);
    if ((b / wari) % 2 == 1) {
      Answer %= m;
      Answer = (Answer * p) % m;  // 「a の 2^i 乗」が掛けられるとき
    }
    p %= m;
    p = (p * p) % m;
  }
  return Answer;
}

// a ÷ b を m で割った余りを返す関数
long long Division(long long a, long long b, long long m) {
  return (a * Power(b, m - 2, m)) % m;
}

// nCr mod 998244353 を返す関数
long long nCk(ll n, ll r) {
  const long long M = 998244353;

  // 手順 1: 分子 a を求める
  long long a = 1;
  for (int i = 1; i <= n; i++) a = (a * i) % M;

  // 手順 2: 分母 b を求める
  long long b = 1;
  for (int i = 1; i <= r; i++) b = (b * i) % M;
  for (int i = 1; i <= n - r; i++) b = (b * i) % M;

  // 手順 3: 答えを求める
  return Division(a, b, M);
}
using Interval = pair<ll, ll>;
// nCk mint を返す関数。
modint1000000007 modnCk(ll n, ll r) {
  modint1000000007 a = 1;
  for (ll i = n; i > n - r; i--) {
    a *= i;
    a /= n + 1 - i;
  }
  return a;
}
// 終点時間でsortをかけるのに必要(区間スケジューリング問題など)
bool cmp(const Interval &a, const Interval &b) { return a.second < b.second; }
vll dycstra(vector<vector<pair<ll, ll>>> G, ll N, ll K) {
  vb kaku(N, false);
  vll cur(N, INF);
  cur[K] = 0;
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;
  Q.push(make_pair(cur[K], K));
  while (!Q.empty()) {
    ll pos = Q.top().second;
    Q.pop();
    if (kaku[pos]) continue;
    kaku[pos] = true;
    for (ll i = 0; i < G[pos].size(); i++) {
      ll nex = G[pos][i].first;
      ll cost = G[pos][i].second;
      if (cur[nex] > cur[pos] + cost) {
        cur[nex] = cur[pos] + cost;
        Q.push(make_pair(cur[nex], nex));
      }
    }
  }
  return cur;
}
template <typename T>
void Print(vector<T> &A) {
  rep(i, A.size()) { cout << A[i] << ' '; }
  cout << endl;
}
template <typename xy>
class BIT {
 public:
  BIT() = default;

  // 長さ size の数列で初期化
  explicit BIT(size_t size) : m_bit(size + 1) {}

  // 数列で初期化
  explicit BIT(const std::vector<xy> &v) : BIT(v.size()) {
    for (int i = 0; i < v.size(); ++i) {
      add((i + 1), v[i]);
    }
  }

  // 閉区間 [1, r] の合計を返す (1-based indexing)
  xy sum(int r) const {
    xy ret = 0;

    for (; 0 < r; r -= (r & -r)) {
      ret += m_bit[r];
    }

    return ret;
  }

  // 閉区間 [l, r] の合計を返す (1-based indexing)
  xy sum(int l, int r) const { return (sum(r) - sum(l - 1)); }

  // 数列の i 番目の要素を加算 (1-based indexing)
  void add(int i, xy value) {
    for (; i < m_bit.size(); i += (i & -i)) {
      m_bit[i] += value;
    }
  }

 private:
  std::vector<xy> m_bit;
};

// Binary Indexed Tree (1.2 区間加算対応)
// 1-based indexing
template <typename x>
class BIT_RAQ {
 public:
  BIT_RAQ() = default;

  explicit BIT_RAQ(size_t size) : m_bit0(size), m_bit1(size) {}

  explicit BIT_RAQ(const std::vector<x> &v) : m_bit0(v), m_bit1(v.size()) {}

  // 閉区間 [1, r] の合計を返す (1-based indexing)
  x sum(int r) const { return (m_bit0.sum(r) + m_bit1.sum(r) * r); }

  // 閉区間 [l, r] の合計を返す (1-based indexing)
  x sum(int l, int r) const { return (sum(r) - sum(l - 1)); }

  // 数列の i 番目の要素を加算 (1-based indexing)
  void add(int i, x value) { m_bit0.add(i, value); }

  // 閉区間 [l, r] の要素を加算 (1-based indexing)
  void add(int l, int r, x value) {
    x a = (-value * (l - 1)), b = (value * r);
    m_bit0.add(l, a);
    m_bit0.add((r + 1), b);
    m_bit1.add(l, value);
    m_bit1.add((r + 1), -value);
  }

 private:
  BIT<x> m_bit0;

  BIT<x> m_bit1;
};
vll BFS(vvll &G, ll &x) {
  vll cut(G.size(), INF);
  queue<ll> Q;
  Q.push(x);
  cut[x] = 0;
  while (!Q.empty()) {
    ll a = Q.front();
    Q.pop();
    rep(i, G[a].size()) {
      if (cut[G[a][i]] > cut[a] + 1) {
        cut[G[a][i]] = cut[a] + 1;
        Q.push(G[a][i]);
      }
    }
  }
  return cut;
}

void Yes(bool b) {
  if (b)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}
vector<long long> yaku(long long n) {
  vector<long long> ret;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  sort(ret.begin(), ret.end());  // 昇順に並べる
  return ret;
}
// Moのアルゴリズム　(https://ei1333.hateblo.jp/entry/2017/09/11/211011)
struct Mo {
  int n;
  vector<pair<int, int>> lr;

  explicit Mo(int n) : n(n) {}  // nの値の設定を行う。

  void add(int l, int r) { /* [l, r) */
    lr.push_back({l, r});
  }

  template <typename AL, typename AR, typename EL, typename ER, typename O>
  void build(const AL &add_left, const AR &add_right, const EL &erase_left,
             const ER &erase_right, const O &out) {
    int q = (int)lr.size();  // lr.size()はクエリの数に等しい。
    int bs = n / min<int>(n, sqrt(q));  // 事実上bs>0となるように設定、
    // cout << bs << endl;
    vector<int> ord(q);
    iota(begin(ord), end(ord), 0);
    sort(begin(ord), end(ord), [&](int a, int b) {
      int ablock = lr[a].first / bs, bblock = lr[b].first / bs;
      if (ablock != bblock) return ablock < bblock;  //
      return (ablock & 1) ? lr[a].second > lr[b].second
                          : lr[a].second < lr[b].second;
      // 偶奇で昇順・降順を分けることによって計算量が定数倍高速化する。
    });
    int l = 0, r = 0;
    for (auto idx : ord) {
      //  cout << idx << endl;
      while (l > lr[idx].first) add_left(--l);
      while (r < lr[idx].second) add_right(r++);
      while (l < lr[idx].first) erase_left(l++);
      while (r > lr[idx].second) erase_right(--r);
      out(idx);
    }
  }

  template <typename A, typename E, typename O>
  void build(const A &add, const E &erase, const O &out) {
    build(add, add, erase, erase, out);
  }
};

struct TRI {
  ll a;
  ll b;
  ll c;
};
bool operator>(const TRI &r, const TRI &l) {
  return (r.a > l.a | (r.a == l.a & r.b > l.b) |
          (r.a == l.a & r.b == l.b & r.c > l.c));
}
bool operator<(const TRI &r, const TRI &l) {
  return (r.a < l.a | (r.a == l.a & r.b < l.b) |
          (r.a == l.a & r.b == l.b & r.c < l.c));
}
struct TR {
  ll a;
  ll b;
  ll c;
  ll d;
};
bool operator>(const TR &r, const TR &l) {
  return (r.a > l.a | (r.a == l.a & r.b > l.b) |
          (r.a == l.a & r.b == l.b & r.c > l.c));
}
bool operator<(const TR &r, const TR &l) {
  return (r.a < l.a | (r.a == l.a & r.b < l.b) |
          (r.a == l.a & r.b == l.b & r.c < l.c));
}
// Sはdataを表している。
using S = ll;
using F = ll;

S op(S a, S b) { return max(a, b); }
S e() { return 0; }
S mapping(F f, S x) { return x + f; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }
ll half = 499122177;
// 条件を満たす場合オイラーツアーを考えれば出来る。
// 重要なのは求める次数を満たす辺を構築すること
// G:グラフ,P:オイラーツアーで探索した際に通った辺の番号の配列,in,out:最初と最後に通った時刻
// U[辺の番号]={親,現在いる位置}正の値だったら終点、それ以外親を出力することで頂点で表した経路の復元が可能
// num=辺の番号を記録,cou=時刻を記録

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extGCD(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
struct Edge {
  long long to, cap, rev;
};

class MaximumFlow {
 public:
  int size_ = 0;
  int level[2000];
  int iter[2000];
  vector<Edge> G[2000];

  // 頂点数 N の残余グラフを準備
  void init(int N) {
    size_ = N;
    memset(G, {}, size_);
    for (int i = 0; i <= size_; i++) G[i].clear();
    memset(level, -1, sizeof(level));
    memset(iter, 0, sizeof(iter));
  }

  // 頂点 a から b に向かう、上限 c リットル／秒の辺を追加
  void add_edge(int a, int b, long long c) {
    int Current_Ga = G[a].size();  // 現時点での G[a] の要素数
    int Current_Gb = G[b].size();  // 現時点での G[b] の要素数
    G[a].push_back(Edge{b, c, Current_Gb});
    G[b].push_back(Edge{a, 0, Current_Ga});
  }

  // 頂点 a から b に向かう、上限 c リットル／秒の辺と頂点 b から a
  // に向かう、上限 c リットル／秒の辺を追加
  void Uadd_edge(int a, int b, long long c) {
    int Current_Ga = G[a].size();  // 現時点での G[a] の要素数
    int Current_Gb = G[b].size();  // 現時点での G[b] の要素数
    G[a].push_back(Edge{b, c, Current_Gb});
    G[b].push_back(Edge{a, c, Current_Ga});
  }
  // sからの最短距離をBDSで計算する
  void bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
      int v = que.front();
      que.pop();
      for (int i = 0; i < G[v].size(); i++) {
        Edge &e = G[v][i];
        if (e.cap > 0 && level[e.to] < 0) {
          level[e.to] = level[v] + 1;
          if (e.to == t) goto H;
          que.push(e.to);
        }
      }
    }
  H:;
  }
  // 深さ優先探索（F はスタートから pos に到達する過程での "
  // 残余グラフの辺の容量 " の最小値） 返り値は流したフローの量（流せない場合は
  // 0 を返す）
  long long dfs(int pos, int goal, long long F) {
    // ゴールに到着：フローを流せる！
    if (pos == goal) return F;
    // 探索する
    for (int &i = iter[pos]; i < G[pos].size(); i++) {
      Edge &e = G[pos][i];
      if (e.cap > 0 && level[pos] < level[e.to]) {
        long long d = dfs(e.to, goal, min(F, e.cap));
        // フローを流せる場合、残余グラフの容量を flow だけ増減させる
        if (d > 0) {
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          return d;
        }
      }
    }

    // すべての辺を探索しても見つからなかった ･･･
    return 0;
  }

  // 頂点 s から頂点 t までの最大フローの総流量を返す
  long long max_flow(int s, int t) {
    long long Total_Flow = 0;
    while (true) {
      bfs(s, t);
      if (level[t] < 0) return Total_Flow;
      memset(iter, 0, sizeof(iter));

      long long f = 0;
      while ((f = dfs(s, t, (long long)1e18)) > 0) Total_Flow += f;
    }
  }
};
template <typename T>
vector<T> compress(vector<T> &X) {
  // ソートした結果を vals に
  vector<T> vals = X;
  sort(vals.begin(), vals.end());
  // 隣り合う重複を削除(unique), 末端のゴミを削除(erase)
  vals.erase(unique(vals.begin(), vals.end()), vals.end());
  // 各要素ごとに二分探索で位置を求める
  for (int i = 0; i < (int)X.size(); i++) {
    X[i] = lower_bound(vals.begin(), vals.end(), X[i]) - vals.begin();
  }
  return vals;
}
vll toposo(vvll &G) {
  // 帰りがけでやりたい場合はstack、幅優先でやりたい場合はqueueで行う
  stack<ll> Q;
  ll n = G.size();
  vll A(n, 0);
  rep(i, n) {
    rep(j, G[i].size()) { A[G[i][j]]++; }
  }
  vb han(n, false);
  rep(i, n) {
    if (A[i] == 0) {
      Q.push(i);
      han[i] = true;
    }
  }
  vll B;
  while (!Q.empty()) {
    ll a = Q.top();
    Q.pop();
    B.push_back(a);
    rep(i, G[a].size()) {
      if (!han[G[a][i]]) {
        A[G[a][i]]--;
        if (A[G[a][i]] == 0) {
          Q.push(G[a][i]);
          han[G[a][i]] = true;
        }
      }
    }
  }
  if (B.size() != n) {
    vll C(n, -2);
    return C;
  }
  return B;
}
#include <bits/stdc++.h>
// ax+bのようなグラフの最小値をクエリ一個あたりO(1)で算出することが出来る。
// 条件は２つ存在する。
// 1.追加される順に傾きは単調減少でなければならない(傾きに関してソートする必要性が生じる)
// 2.追加される順にxは単調増加でなければならない(クエリ先読み等のひと手間が必要になる可能性がある)
// ２つの条件が満たせない場合はこのサンプルを使うことが出来ない(クエリが２種類存在し、直線の追加とxを指定して最小値を求める動作を平行して行う場合等)

struct ConvexHullTrick {
  std::deque<std::pair<long long, long long>> dq;  // （傾き、切片）

  void add(long long a, long long b) {
    std::pair<long long, long long> p0 = std::make_pair(a, b);
    while (dq.size() >= 2) {
      int sz = dq.size();
      std::pair<long long, long long> p1 = dq[sz - 1];
      std::pair<long long, long long> p2 = dq[sz - 2];
      if ((p0.second - p1.second) * (p0.first - p2.first) <
          (p0.second - p2.second) * (p0.first - p1.first))
        break;  // 交点のx座標を比較
      dq.pop_back();
    }
    dq.push_back(p0);
  }

  long long query(long long x) {
    while (dq.size() >= 2) {
      long long v1 = dq[0].first * x + dq[0].second;
      long long v2 = dq[1].first * x + dq[1].second;
      if (v1 <= v2) break;
      dq.pop_front();
    }
    return dq[0].first * x + dq[0].second;
  }
};
//  Σ(i=0~N-1)floor(ai+b)/Mを計算するACLにも同じものは存在するが、こちらの方が制約は緩いのでこっちを使うようにしよう。
long long floor_sum1(ll n, ll m, ll a, ll b) {
  long long ans = 0;
  if (a >= m) {
    ans += (n - 1) * n * (a / m) / 2;
    a %= m;
  }
  if (b >= m) {
    ans += n * (b / m);
    b %= m;
  }

  ll y_max = (a * n + b) / m, x_max = (y_max * m - b);
  if (y_max == 0) return ans;
  ans += (n - (x_max + a - 1) / a) * y_max;
  ans += floor_sum1(y_max, a, m, (a - x_max % a) % a);
  return ans;
}

// コピペここから
// Pointは複素数平面上の座標を表す、幾何問題において有効なアルゴリズムである。
//  加減乗除を始め(逆・双曲線)三角関数やeの累乗・累乗や自然対数等の演算子は実装されている。
//  a.rael(): 実部、a.imag() :
//  虚部、a.abs():複素数の絶対値、a.arg():偏角、a.norm():複素数のノルムを表す(簡単にいうと絶対値の２乗)、a.conj()：共役複素数を得る、、Polar(a,b):絶対値がa,偏角がb[rad]の複素数を作成する
using Point = complex<double>;

inline bool equal(const double &a, const double &b) {
  return fabs(a - b) < EPS;
}

// 単位ベクトル(unit vector)を求める
Point unitVector(const Point &a) { return a / abs(a); }

// 法線ベクトル(normal vector)を求める
// 90度回転した単位ベクトルをかける
// -90度がよければPoint(0, -1)をかける
Point normalVector(const Point &a) { return a * Point(0, 1); }

// 内積(dot product) : a・b = |a||b|cosΘ
// 内積が0⇔aとbが垂直
double dot(const Point &a, const Point &b) {
  return (a.real() * b.real() + a.imag() * b.imag());
}

// 外積(cross product) : a×b = |a||b|sinΘ
// 外積が0⇔aとbが平行
double cross(const Point &a, const Point &b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}

// 点pを反時計回りにtheta度回転
Point rotate(const Point &p, const double &theta) {
  return Point(cos(theta) * p.real() - sin(theta) * p.imag(),
               sin(theta) * p.real() + cos(theta) * p.imag());
}

// ラジアン->度
double radianToDegree(const double &radian) { return radian * 180.0 / PI; }

// 度->ラジアン
double degreeToRadian(const double &degree) { return degree * PI / 180.0; }
// Line : 直線を表す構造体
// b - a で直線・線分を表せる
struct Line {
  Point a, b;
  Line() = default;
  Line(Point a, Point b) : a(a), b(b) {}
  // Ax+By=C
  Line(double A, double B, double C) {
    if (equal(A, 0)) {
      a = Point(0, C / B), b = Point(1, C / B);
    } else if (equal(B, 0)) {
      a = Point(C / A, 0), b = Point(C / A, 1);
    } else {
      a = Point(0, C / B), b = Point(C / A, 0);
    }
  }
};

// Segment : 線分を表す構造体
// Lineと同じ
struct Segment : Line {
  Segment() = default;

  Segment(Point a, Point b) : Line(a, b) {}
};

// Circle : 円を表す構造体
// pが中心の位置ベクトル、rは半径
struct Circle {
  Point p;
  double r;

  Circle() = default;

  Circle(Point p, double r) : p(p), r(r) {}
};
// 点の回転方向
// 点a, b, cの位置関係について(aが基準点)
int ccw(const Point &a, Point b, Point c) {
  b -= a, c -= a;
  // 点a, b, c が
  // 反時計回りの時、
  if (cross(b, c) > EPS) {
    return 1;
  }
  // 時計回りの時、
  if (cross(b, c) < -EPS) {
    return -1;
  }
  // c, a, bがこの順番で同一直線上にある時、
  if (dot(b, c) < 0) {
    return 2;
  }
  // a, b,
  // cがこの順番で同一直線上にある場合、(注意点としてaとbが一致しているときも判定に入る)
  if (norm(b) < norm(c)) {
    return -2;
  }
  // cが線分ab上にある場合、(注意点としてcがaとbのいずれかが一致しているときも判定に入る)
  return 0;
}

// 直線s,tの交点判定
bool isStraight(const Line &s, const Line &t) {
  return !(equal(abs(cross(s.b - s.a, t.b - t.a)), 0.0) &&
           ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) == 1);
  //  ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) == 1ならばccw(t.a, t.b, s.a) *
  //  ccw(t.a, t.b, s.b) ==1となる。
}
// 2直線の直交判定 : a⊥b <=> dot(a, b) = 0
bool isOrthogonal(const Line &a, const Line &b) {
  return equal(dot(a.b - a.a, b.b - b.a), 0);
}
// 2直線の平行判定 : a//b <=> cross(a, b) = 0
bool isParallel(const Line &a, const Line &b) {
  return equal(cross(a.b - a.a, b.b - b.a), 0);
}
// 点cが直線ab上にあるか
bool isPointOnLine(const Point &a, const Point &b, const Point &c) {
  return isParallel(Line(a, b), Line(a, c));
}

// 点cが"線分"ab上にあるか
bool isPointOnSegment(const Point &a, const Point &b, const Point &c) {
  // |a-c| + |c-b| <= |a-b| なら線分上
  return (std::abs(a - c) + std::abs(c - b) < std::abs(a - b) + EPS);
}

// 直線lと点pの距離を求める
double distanceBetweenLineAndPoint(const Line &l, const Point &p) {
  return std::abs(cross(l.b - l.a, p - l.a)) / std::abs(l.b - l.a);
}

// 線分lと点pの距離を求める
// 定義：点pから「線分lのどこか」への最短距離
double distanceBetweenSegmentAndPoint(const Segment &l, const Point &p) {
  // 点pから垂線をおろしても線分lとの共有点が出来ず、点pが点l.a側に存在するとき
  if (dot(l.b - l.a, p - l.a) < EPS) return std::abs(p - l.a);
  // 点pから垂線をおろしても線分lとの共有点が出来ず、点pが点l.b側に存在するとき
  if (dot(l.a - l.b, p - l.b) < EPS) return std::abs(p - l.b);
  // 点pから垂線をおろしたら線分lとの共有点が出来るとき
  return std::abs(cross(l.b - l.a, p - l.a)) / std::abs(l.b - l.a);
}

// 直線s, tの交点の計算
Point crossPoint(const Line &s, const Line &t) {
  // 直線の交点が存在しない場合は非数の座標を返す
  if (!isStraight(s, t)) return Point(NAN, NAN);
  double d1 = cross(s.b - s.a, t.b - t.a);
  double d2 = cross(s.b - s.a, s.b - t.a);
  if (equal(abs(d1), 0) && equal(abs(d2), 0)) {
    return t.a;
  }
  return t.a + (t.b - t.a) * (d2 / d1);
}
// 線分sと線分tが交差しているかどうか
// bound:線分の端点を含むか(含む時は1,否なら0)
bool isIntersect(const Segment &s, const Segment &t, int bound) {
  return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) < bound &&
         ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) < bound;
}

// 線分sとtの距離
double distanceBetweenSegments(const Segment &s, const Segment &t) {
  if (isIntersect(s, t, 1)) return (double)(0);
  double ans = distanceBetweenSegmentAndPoint(s, t.a);
  ans = min(ans, distanceBetweenSegmentAndPoint(s, t.b));
  ans = min(ans, distanceBetweenSegmentAndPoint(t, s.a));
  ans = min(ans, distanceBetweenSegmentAndPoint(t, s.b));
  return ans;
}

// 射影(projection)
// 直線(線分)lに点pから引いた垂線の足を求める
Point projection(const Line &l, const Point &p) {
  double t = dot(p - l.a, l.b - l.a) / norm(l.a - l.b);
  return l.a + (l.a - l.b) * t;
}
Point projection(const Segment &l, const Point &p) {
  double t = dot(p - l.a, l.b - l.a) / std::norm(l.a - l.b);
  return l.a + (l.a - l.b) * t;
}

// 反射(reflection)
// 直線lを対称軸として点pと線対称の位置にある点を求める
Point reflection(const Line &l, const Point &p) {
  return p + (projection(l, p) - p) * (double)2.0;
}

// 2つの円の交差判定
// 返り値は共通接線の数
int isIntersect(const Circle &c1, const Circle &c2) {
  double d = abs(c1.p - c2.p);
  // 2つの円が離れている場合
  if (d > c1.r + c2.r + EPS) return 4;
  // 外接している場合
  if (equal(d, c1.r + c2.r)) return 3;
  // 内接している場合
  if (equal(d, std::abs(c1.r - c2.r))) return 1;
  // 内包している場合
  if (d < std::abs(c1.r - c2.r) - EPS) return 0;
  return 2;
}

// 2つの円の交点
vector<Point> crossPoint(const Circle &c1, const Circle &c2) {
  std::vector<Point> res;
  int mode = isIntersect(c1, c2);
  // 2つの中心の距離
  double d = std::abs(c1.p - c2.p);
  // 2円が離れている場合
  if (mode == 4) return res;
  // 1つの円がもう1つの円に内包されている場合
  if (mode == 0) return res;
  // 2円が外接する場合
  if (mode == 3) {
    double t = c1.r / (c1.r + c2.r);
    res.emplace_back(c1.p + (c2.p - c1.p) * t);
    return res;
  }
  // 内接している場合
  if (mode == 1) {
    if (c2.r < c1.r - EPS) {
      res.emplace_back(c1.p + (c2.p - c1.p) * (c1.r / d));
    } else {
      res.emplace_back(c2.p + (c1.p - c2.p) * (c2.r / d));
    }
    return res;
  }
  // 2円が重なる場合
  // rc1=c1.r*cosθ 余弦定理を用いている
  double rc1 = (c1.r * c1.r + d * d - c2.r * c2.r) / (2 * d);
  // rs1=c1.r*sinθ
  double rs1 = std::sqrt(c1.r * c1.r - rc1 * rc1);
  if (c1.r - std::abs(rc1) < EPS) rs1 = 0;
  // c1.p→c2.pベクトルの単位ベクトル
  Point e12 = (c2.p - c1.p) / std::abs(c2.p - c1.p);
  // 加法定理を用いて求めていることが分かる
  res.emplace_back(c1.p + rc1 * e12 + rs1 * e12 * Point(0, 1));
  res.emplace_back(c1.p + rc1 * e12 + rs1 * e12 * Point(0, -1));
  return res;
}

// 点pが円cの内部(円周上も含む)に入っているかどうか
bool isInCircle(const Circle &c, const Point &p) {
  double d = std::abs(c.p - p);
  return (equal(d, c.r) || d < c.r - EPS);
}

// 円cと直線lの交点
std::vector<Point> crossPoint(const Circle &c, const Line &l) {
  std::vector<Point> res;
  double d = distanceBetweenLineAndPoint(l, c.p);
  // 交点を持たない
  if (d > c.r + EPS) return res;
  // 接する
  Point h = projection(l, c.p);
  if (equal(d, c.r)) {
    res.emplace_back(h);
    return res;
  }
  Point e = unitVector(l.b - l.a);
  double ph = std::sqrt(c.r * c.r - d * d);
  res.emplace_back(h - e * ph);
  res.emplace_back(h + e * ph);
  return res;
}

// 点pを通る円cの接線
// 2本あるので、接点のみを返す
std::vector<Point> tangentToCircle(const Point &p, const Circle &c) {
  return crossPoint(c, Circle(p, std::sqrt(std::norm(c.p - p) - c.r * c.r)));
}

// 円の共通接線
std::vector<Line> tangent(const Circle &a, const Circle &b) {
  std::vector<Line> ret;
  // 2円の中心間の距離
  double g = std::abs(a.p - b.p);
  // 円が内包されている場合
  if (equal(g, 0)) return ret;
  Point u = unitVector(b.p - a.p);
  Point v = rotate(u, PI / 2);
  for (int s : {-1, 1}) {
    double h = (a.r + b.r * s) / g;
    if (equal(h * h, 1)) {
      ret.emplace_back(a.p + (h > 0 ? u : -u) * a.r,
                       a.p + (h > 0 ? u : -u) * a.r + v);

    } else if (1 - h * h > 0) {
      Point U = u * h, V = v * std::sqrt(1 - h * h);
      ret.emplace_back(a.p + (U + V) * a.r, b.p - (U + V) * (b.r * s));
      ret.emplace_back(a.p + (U - V) * a.r, b.p - (U - V) * (b.r * s));
    }
  }
  return ret;
}

// 多角形の面積を求める
double PolygonArea(const std::vector<Point> &p) {
  double res = 0;
  int n = p.size();
  for (int i = 0; i < n - 1; i++) res += cross(p[i], p[i + 1]);
  res += cross(p[n - 1], p[0]);
  return res * 0.5;
}

// 凸多角形かどうか
bool isConvex(const std::vector<Point> &p) {
  int n = p.size();
  int now, pre, nxt;
  for (int i = 0; i < n; i++) {
    pre = (i - 1 + n) % n;
    nxt = (i + 1) % n;
    now = i;
    if (ccw(p[pre], p[now], p[nxt]) == -1) return false;
  }
  return true;
}

// 凸包 O(NlogN)
// 　蟻本参考
std::vector<Point> ConvexHull(std::vector<Point> p) {
  int n = (int)p.size(), k = 0;
  std::sort(p.begin(), p.end(), [](const Point &a, const Point &b) {
    return (a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag());
  });
  std::vector<Point> ch(2 * n);
  // 一直線上の3点を含める -> (< -EPS)
  // 含め無い -> (< EPS)
  for (int i = 0; i < n; ch[k++] = p[i++]) {  // lower
    // ch[1]はx座標の最大値であるため必ず採用されるから
    // 点を追加したことで凹んだ場所を削除することをへこんでいる所がなくなるまで繰り返す。
    while (k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS) --k;
  }
  for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {  // upper
    // ch[t-1]はx座標の最大値であるため必ず採用されるから
    // 点を追加したことで凹んだ場所を削除することをへこんでいる所がなくなるまで繰り返す。
    while (k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS) --k;
  }
  // k個の場合だと左端を２回含んでしまうためよろしくない。
  ch.resize(k - 1);
  return ch;
}

// 多角形gに点pが含まれているか?
// 含まれる:2, 辺上にある:1, 含まれない:0
int isContained(const std::vector<Point> &g, const Point &p) {
  bool in = false;
  int n = (int)g.size();
  for (int i = 0; i < n; i++) {
    Point a = g[i] - p, b = g[(i + 1) % n] - p;
    if (imag(a) > imag(b)) swap(a, b);
    if (imag(a) <= EPS && EPS < imag(b) && cross(a, b) < -EPS) in = !in;
    if (cross(a, b) == 0 && dot(a, b) <= 0) return 1;
  }
  return (in ? 2 : 0);
}

// 凸多角形pを直線lで切断し、その左側を返す
std::vector<Point> ConvexCut(std::vector<Point> p, Line l) {
  std::vector<Point> ret;
  int sz = (int)p.size();
  for (int i = 0; i < sz; i++) {
    Point now = p[i];
    Point nxt = p[i == sz - 1 ? 0 : i + 1];
    if (ccw(l.a, l.b, now) != -1) ret.emplace_back(now);
    if (ccw(l.a, l.b, now) * ccw(l.a, l.b, nxt) < 0) {
      ret.emplace_back(crossPoint(Line(now, nxt), l));
    }
  }
  return ret;
}
// 線分s, tの交点の計算
Point crossPoint(const Segment &s, const Segment &t) {
  return crossPoint(Line(s), Line(t));
}
int main() {
   cout << fixed << setprecision(20);
   ll a = 0, b = 0;
   ll a2, b2;
   ll c = 0;
   ll p = 1;
   ll H, W;
   ll K;
   string S, T;
   long double N, M, t1, t2;
   ll t;
   char a1, b1;
   cin >> t;
   long double n, m;
   rep(_, t) {
     cin >> N >> M >> a1;
     cin >> n >> m >> b1;
     if (a1 == 'U' && b1 == 'D') {
       if (N == M && M < m) {
         cout << "Yes" << endl;

       } else
         cout << "No" << endl;
       continue;
     }
     swap(N, n), swap(M, m), swap(a1, b1);
     if (a1 == 'U' && b1 == 'D') {
       if (N == M && M < m) {
         cout << "Yes" << endl;

       } else
         cout << "No" << endl;
       continue;
     }
     swap(N, n), swap(M, m), swap(a1, b1);
     if (a1 == 'R' && b1 == 'L') {
       if (M == m && N < n) {
         cout << "Yes" << endl;
       } else
         cout << "No" << endl;
       continue;
     }
     swap(N, n), swap(M, m), swap(a1, b1);
     if (a1 == 'R' && b1 == 'L') {
       if (M == m && N < n) {
         cout << "Yes" << endl;
       } else
         cout << "No" << endl;
       continue;
     }
     swap(N, n), swap(M, m), swap(a1, b1);
     Line A, B;
     if (a1 == 'R') A = {Point(N, M), Point(N + 1, M)};
     if (a1 == 'L') A = {Point(N, M), Point(N - 1, M)};
     if (a1 == 'U') A = {Point(N, M), Point(N, M + 1)};
     if (a1 == 'D') A = {Point(N, M), Point(N, M - 1)};
     if (b1 == 'R') B = {Point(n, m), Point(n + 1, m)};
     if (b1 == 'L') B = {Point(n, m), Point(n - 1, m)};
     if (b1 == 'U') B = {Point(n, m), Point(n, m + 1)};
     if (b1 == 'D') B = {Point(n, m), Point(n, m - 1)};
     Point KO = crossPoint(A, B);
  
     if (a1 == 'R') {
       if (abs(M - KO.imag()) > EPS || N - EPS > KO.real()) {
         cout << "No" << endl;
         continue;
       }
     }
     if (a1 == 'L') {
       if (abs(M - KO.imag())> EPS || N + EPS < KO.real()) {
         cout << "No" << endl;
         continue;
       }
     }
     if (a1 == 'U') {
       if (M-EPS > KO.imag() ||abs(N -  KO.real() )>EPS) {
         cout << "No" << endl;
         continue;
       }
     }
        
     if(a1=='D'){
       if (M+EPS < KO.imag() || abs(N -  KO.real())>EPS) {
         cout << "No" << endl;
         continue;
       }
     }
     swap(N, n), swap(M, m), swap(a1, b1);
        if (a1 == 'R') {
       if (M - KO.imag() > EPS || N - EPS > KO.real()) {
         cout << "No" << endl;
         continue;
       }
     }
        if (a1 == 'R') {
       if (abs(M - KO.imag()) > EPS || N - EPS > KO.real()) {
         cout << "No" << endl;
         continue;
       }
     }
     if (a1 == 'L') {
       if (abs(M - KO.imag())> EPS || N + EPS < KO.real()) {
         cout << "No" << endl;
         continue;
       }
     }
  
     if (a1 == 'U') {
       if (M-EPS > KO.imag() ||abs(N -  KO.real() )>EPS) {
         cout << "No" << endl;
         continue;
       }
     }
        
     if(a1=='D'){
       if (M+EPS < KO.imag() || abs(N -  KO.real())>EPS) {
         cout << "No" << endl;
         continue;
       }
     }
     cout << "Yes" << endl;
   }
}