Ruudukko

input/code.cpp: In function 'bool valid(std::string, int, int, std::pair<int, int>, std::pair<int, int>)':
input/code.cpp:183:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  183 |     if (res.size() != n * m - 1) return false;
      |         ~~~~~~~~~~~^~~~~~~~~~~~
input/code.cpp: In function 'std::string solve_m(int, int, std::pair<int, int>, std::pair<int, int>, std::pair<int, int>)':
input/code.cpp:578:22: warning: variable 'x1' set but not used [-Wunused-but-set-variable]
  578 |                 auto x1 = make_tuple(n, 2, make_pair(0, 1), make_pair(0,1));
      |                      ^~
input/code.cpp:591:22: warning: variable 'x1' set but not used [-Wunused-but-set-variable]
  591 |                 auto x1 = make_tuple(n, 2, make_pair(0, m - j), make_pair(0,2));
      |                      ^~
input/code.cpp: In function 'std::pair<int, int> step(char, std:...

#include <bits/stdc++.h>
 
typedef long long ll;
 
#define M 1000000007
#define N (1 << 18)
 
#define y first
#define x second
 
using namespace std;
 
int s2 = 0;
 
const int MAX_N = 5000;
 
char result[MAX_N + 1][MAX_N + 1];
 
map<tuple<int, int, pair<int, int>, pair<int, int>>, string> mem;
 
void st(char c, pair<int, int> pos, pair<int, int> offset) {
    result[pos.y + offset.y][pos.x + offset.x] = c;
}
 
char gt(pair<int, int> pos, pair<int, int> offset) {
    return result[pos.y + offset.y][pos.x + offset.x];
}
 
pair<int, int> step(char c, pair<int, int> pos) {
    if (c == 'U') return {pos.y - 1, pos.x};
    if (c == 'D') return {pos.y + 1, pos.x};
    if (c == 'R') return {pos.y, pos.x + 1};
    if (c == 'L') return {pos.y, pos.x - 1};
    cout << "Unknown char: " << c << endl;
}
 
char gt_rev(char c) {
    if (c == 'U') return 'D';
    if (c == 'D') return 'U';
    if (c == 'R') return 'L';
    if (c == 'L') return 'R';
    cout << "Unknown char: " << c << endl;
}
 
void rev_from(pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
    // s = start in the wrong order
 
    // means that pos[t] will be empty
    // but pos[s] should be empty
 
    char c = gt(s, offset);
    s = step(gt(s, offset), s);
 
    while (s != t) {
        char nxt = gt(s, offset);
        st(gt_rev(c), s, offset);
        c = nxt;
        s = step(nxt, s);
    }
 
    st(gt_rev(c), s, offset);
}
 
namespace mango {
    void solveSmall(int h, int w, int y0, int x0, int y1, int x1, pair<int, int> offset) {
        if (x0 > x1 || (x0 == x1 && y0 > y1)) {
            char c = gt({y1, x1}, offset);
            solveSmall(h, w, y1, x1, y0, x0, offset);
            rev_from({y1, x1}, {y0, x0}, offset);
            st(c, {y1, x1}, offset);
            return;
        }
    
        if (h == 1) {
            if (x0 == 1 && x1 == w) {
                for (int i = 0; i < w - 1; ++i) {
                    st('R', {y0, x0}, offset);
                    offset.x++;
                }
                return;
            }
            if (x0 == w && x1 == 1) {
                for (int i = 0; i < w - 1; ++i) {
                    st('L', {y0, x0}, offset);
                    offset.x--;
                }
                return;
            }
        } else {    
            string res;
            if (x0 == x1 && x0 == 1) {
                for (int i = 0; i < w-1; ++i) {
                    st('R', {y0, x0}, offset);
                    offset.x++;
                }
    
                if (y0 == 1) {
                    st('D', {y0, x0}, offset);
                    offset.y++;
                }
                else {
                    st('U', {y0, x0}, offset);
                    offset.y--;
                }
    
                for (int i = 0; i < w-1; ++i) {
                    st('L', {y0, x0}, offset);
                    offset.x--;
                }
            } else {
                for (int i = 1; i < x0; ++i) {
                    st('L', {y0, x0}, offset);
                    offset.x--;
                }
    
                if (y0 == 1) {
                    st('D', {y0, x0}, offset);
                    offset.y++;
                }
                else {
                    st('U', {y0, x0}, offset);
                    offset.y--;
                }
    
                for (int i = 1; i < x0; ++i) {
                    st('R', {y0, x0}, offset);
                    offset.x++;
                }
    
                if (x0 == x1) return;
    
                for (int i = 1; i < x1 - x0; ++i) {
                    st('R', {y0, x0}, offset);
                    offset.x++;
                    if (((i - 1) ^ (y0 - 1)) & 1) {
                        st('D', {y0, x0}, offset);
                        offset.y++;
                    }
                    else {
                        st('U', {y0, x0}, offset);
                        offset.y--;
                    }
                }
                st('R', {y0, x0}, offset);
                offset.x++;
    
                for (int i = 0; i < w - x1; ++i) {
                    st('R', {y0, x0}, offset);
                    offset.x++;
                }
    
                if (y1 == 1) {
                    st('U', {y0, x0}, offset);
                    offset.y--;
                }
                else {
                    st('D', {y0, x0}, offset);
                    offset.y++;
                }
    
                for (int i = 0; i < w - x1; ++i) {
                    st('L', {y0, x0}, offset);
                    offset.x--;
                }
            }    
        }
    }
 
    void solve2(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
        s2++;
        solveSmall(n, m, s.y, s.x, t.y, t.x, offset);
    }
};
 
bool valid(string res, int n, int m, pair<int, int> s, pair<int, int> t) {
    map<char, pair<int, int>> dir_to_dif;
    dir_to_dif['U'] = {-1, 0};
    dir_to_dif['D'] = {1, 0};
    dir_to_dif['R'] = {0, 1};
    dir_to_dif['L'] = {0, -1};
    map<pair<int, int>, bool> mp;
 
    if (res.size() != n * m - 1) return false;
 
    int idx = 0;
 
    while (s != t) {
        if (mp[s] == 1) {
            return false;
        }
        mp[s] = 1;
 
        char c = res[idx++];
        s.y += dir_to_dif[c].y;
        s.x += dir_to_dif[c].x;
 
        if (s.y <= 0 || s.y > n || s.x <= 0 || s.x > m) return false;
    }
 
    return true;
}
 
bool check_small(int h, int w, int y0, int x0, int y1, int x1) {
	if (x0 > x1 || (x0 == x1 && y0 > y1)) return check_small(h, w, y1, x1, y0, x0);
 
	if (h == 1) {
		if (x0 == 0 && x1 == w-1) return true;
		if (x0 == w-1 && x1 == 0) return true;
		return false;
	} else {
		if (x0 == x1 && 0 < x0 && x0 < w-1) return false;
		return true;
	}
}
 
bool works(int h, int w, int y0, int x0, int y1, int x1) {
	if (y0 == y1 && x0 == x1) return false;
	if (w < h) return works(w, h, x0, y0, x1, y1);
	if (! ((h*w ^ abs(x0 - x1) ^ abs(y0 - y1)) & 1)) return false;
	if ((h*w & 1) && ((x0 + y0) & 1)) return false;
 
	if (h <= 2) return check_small(h, w, y0, x0, y1, x1);
	if (h == 3 && (!(w & 1))) {
		if (y0 == 1) {
			if ((x0 & 1) && x1 < x0) return false;
			if (!(x0 & 1) && x1 > x0) return false;
		} else {
			if (!(x0 & 1) && (x1 < x0 - 1)) return false;
			if ((x0 & 1) && (x1 > x0 + 1)) return false;
		}
	}   
	return true;
}
 
bool inside(int n, int m, pair<int, int> p) {
    return p.x <= m && p.y <= n && p.x > 0 && p.y > 0;
}
 
bool ok(int h, int w, pair<int, int> s, pair<int, int> t) {
    if (h == 0) return s.x == t.x;
    return works(h, w, s.y - 1, s.x - 1, t.y - 1, t.x - 1);
}
 
pair<int, int> ot(pair<int, int> p, pair<int, int> off) {
    return {p.y + off.y, p.x + off.x};
}
 
const int cutoff = 20;
 
bool vis[MAX_N + 1][MAX_N + 1];
 
bool run_brute(int n, int m, pair<int, int> c, pair<int, int> t, int left, pair<int, int> offset) {
    if (c.x < 1 || c.x > m || c.y < 1 || c.y > n) return false;
    if (vis[c.y][c.x]) return false;
    if (left == 0) {
        if (c != t) return false;
        st('E', c, offset);
        return true;
    }
 
    vis[c.y][c.x] = 1;
 
    if (run_brute(n, m, {c.y - 1, c.x}, t, left - 1, offset)) {
        st('U', c, offset);
        return true;
    }
 
    if (run_brute(n, m, {c.y + 1, c.x}, t, left - 1, offset)) {
        st('D', c, offset);
        return true;
    }
 
    if (run_brute(n, m, {c.y, c.x - 1}, t, left - 1, offset)) {
        st('L', c, offset);
        return true;
    }
 
    if (run_brute(n, m, {c.y, c.x + 1}, t, left - 1, offset)) {
        st('R', c, offset);
        return true;
    }
 
    vis[c.y][c.x] = 0;
    return false;
}
 
int c = 0;
 
void brute(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
    c++;
 
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) vis[i][j] = 0;
    }
 
    run_brute(n, m, s, t, n * m - 1, offset);
 
    /*cout << "solved: " << n << " " << m << " " << s.y << " " << s.x << " " << t.y << " " << t.x << endl;
 
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cout << gt({i, j}, offset);
        }
        cout << endl;
    }*/
}
 
string c2(int n, int m, pair<int, int> s, pair<int, int> t, int times) {
    for (int i = 0; i < n * m; ++i) {
        result[0][0] = 'X';
    }
 
    return "";
    pair<int, int> dif = {s.y - t.y, s.x - t.x};
 
    string ans_first;
    string ans_mid;
    string ans_second;
 
    if (dif == make_pair(0, -1)) {
        ans_first += string(s.x - 1, 'L');
        ans_first += s.y == 2 ? "U" : "D";
        ans_first += string(s.x - 1, 'R');
        ans_first += s.y == 2 ? "U" : "D";
 
        ans_mid = "R";
 
        ans_second += string(m - t.x, 'R');
        ans_second += s.y == 2 ? "D" : "U";
        ans_second += string(m - t.x, 'L');
        ans_second += s.y == 2 ? "D" : "U";
    }
    if (dif == make_pair(0, 1)) {
        ans_first += string(m - s.x, 'R');
        ans_first += s.y == 2 ? "U" : "D";
        ans_first += string(m - s.x, 'L');
        ans_first += s.y == 2 ? "U" : "D";
 
        ans_mid = "L";
 
        ans_second += string(t.x - 1, 'L');
        ans_second += s.y == 2 ? "D" : "U";
        ans_second += string(t.x - 1, 'R');
        ans_second += s.y == 2 ? "D" : "U";
    }
    if (dif == make_pair(-1, 0)) {
        ans_first += string(s.y - 1, 'U');
        ans_first += s.x == 2 ? "L" : "R";
        ans_first += string(s.y - 1, 'D');
        ans_first += s.x == 2 ? "L" : "R";
 
        ans_mid = "D";
 
        ans_second += string(n - t.y, 'D');
        ans_second += s.x == 2 ? "R" : "L";
        ans_second += string(n - t.y, 'U');
        ans_second += s.x == 2 ? "R" : "L";
    }
    if (dif == make_pair(1, 0)) {
        ans_first += string(n - s.y, 'D');
        ans_first += s.x == 2 ? "L" : "R";
        ans_first += string(n - s.y, 'U');
        ans_first += s.x == 2 ? "L" : "R";
 
        ans_mid = "U";
 
        ans_second += string(t.y - 1, 'U');
        ans_second += s.x == 2 ? "R" : "L";
        ans_second += string(t.y - 1, 'D');
        ans_second += s.x == 2 ? "R" : "L";
    }
 
    string ans;
    // ans.reserve(n * m * times - 1);
 
    for (int i = 0; i < times; ++i) ans += ans_first;
    ans.pop_back();
    ans += ans_mid;
    for (int i = 0; i < times; ++i) ans += ans_second;
    ans.pop_back();
 
    return ans;
}
 
int ss = 0;
 
string solve_strip(tuple<int, int, pair<int, int>, pair<int, int>> p1, string path, pair<int, int> pos, int times) {
    ss++;
    map<char, pair<int, int>> dir_to_dif;
    dir_to_dif['U'] = {-1, 0};
    dir_to_dif['D'] = {1, 0};
    dir_to_dif['R'] = {0, 1};
    dir_to_dif['L'] = {0, -1};
 
    string res;
 
    pair<int, int> tgt = get<2>(p1);
 
    if (pos.x == tgt.x || pos.y == tgt.y) {
        bool begin = 0;
        if (get<3>(p1).y == 1 && path[0] == 'D') {
            begin = 1;
        } else if (get<3>(p1).y > 1 && path[0] == 'U') {
            begin = 1;
        } else if (get<3>(p1).x == 1 && path[0] == 'R') {
            begin = 1;
        } else if (get<3>(p1).x > 1 && path[0] == 'L') {
            begin = 1;
        }
 
        if (begin) {
            pair<int, int> dif = dir_to_dif[path[res.size()]];
            pos = make_pair(pos.y + dif.y, pos.x + dif.x);
            res += (path[res.size()]);
        }
    }
 
    while (pos.x != tgt.x && pos.y != tgt.y) {
        pair<int, int> dif = dir_to_dif[path[res.size()]];
        pos = make_pair(pos.y + dif.y, pos.x + dif.x);
        res += (path[res.size()]);
    }
 
    string end_path = path.size() > res.size() + 1 ? path.substr(res.size() + 1, 1e8) : "";
 
    if (get<3>(p1).y == 1) {
        res = res + "U" + c2(2, get<1>(p1), {2, pos.x}, {2, pos.x + dir_to_dif[path[res.size()]].x}, times) + "D";
    } else if (get<3>(p1).y > 1) {
        res = res + "D" + c2(2, get<1>(p1), {1, pos.x}, {1, pos.x + dir_to_dif[path[res.size()]].x}, times) + "U";
    } else if (get<3>(p1).x == 1) {
        res = res + "L" + c2(get<0>(p1), 2, {pos.y, 2}, {pos.y + dir_to_dif[path[res.size()]].y, 2}, times) + "R";
    } else if (get<3>(p1).x > 1) {
        res = res + "R" + c2(get<0>(p1), 2, {pos.y, 1}, {pos.y + dir_to_dif[path[res.size()]].y, 1}, times) + "L";
    }
 
    return res + end_path;
}
 
void solve_strip_hor(bool left, int n, int m, pair<int, int> offset) {
    int s_idx;
    bool up;
    pair<int, int> cp;
 
    cout << "here " << left << " " << n << " "  << m << " " << offset.y << " " << offset.x << endl; 
 
    if (left) {
        for (int i = 1; i <= n; ++i) {
            char c = gt({i, m + 1}, offset);
            if (c == 'D') {
                up = 1;
                s_idx = i;
                break;
            } else if (c == 'U') {
                up = 0;
                s_idx = i;
                break;
            }
        }
 
        st('L', {s_idx, m + 1}, offset);
        cp = {s_idx, m};
    } else {
        for (int i = 1; i <= n; ++i) {
            char c = gt({i, 0}, offset);
            if (c == 'D') {
                up = 1;
                s_idx = i;
                break;
            } else if (c == 'U') {
                up = 0;
                s_idx = i;
                break;
            }
        }
 
        st('R', {s_idx, 0}, offset);
        cp = {s_idx, m};
    }
 
    if (up) {
        while (cp.y != 1) {
            st('U', cp, offset);
            cp.y--;
        }
    } else {
        while (cp.y != n) {
            st('D', cp, offset);
            cp.y++;
        }
    }
 
    if (left) {
        st('L', cp, offset);
        cp.x--;
    } else {
        st('R', cp, offset);
        cp.x++;
    }
    
 
    if (up) {
        while (cp.y != n) {
            st('D', cp, offset);
            cp.y++;
        }
    } else {
        while (cp.y != 1) {
            st('U', cp, offset);
            cp.y--;
        }
    }
 
    if (left) {
        st('R', cp, offset);
        cp.x++;
    } else {
        st('L', cp, offset);
        cp.x--;
    }
 
    if (up) {
        while (cp.y != s_idx + 1) {
            st('U', cp, offset);
            cp.y--;
        }
    } else {
        while (cp.y != s_idx - 1) {
            st('D', cp, offset);
            cp.y++;
        }
    }
 
    if (left) {
        st('R', cp, offset);
        cp.x++;
    } else {
        st('L', cp, offset);
        cp.x--;
    }
}
 
pair<int, int> rotate_right(int n, int m, pair<int, int> pos) {
    int ny = pos.x;
    int nx = n - (pos.y - 1);
 
    return {ny, nx};
}
 
string convert_rotate(string res) {
    map<char, char> sw;
    sw['D'] = 'R';
    sw['U'] = 'L';
    sw['R'] = 'U';
    sw['L'] = 'D';
 
    string ans;
    for (char c : res) ans += sw[c];
    return ans;
}
 
string solve_m(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {  
    // cout << "here: " << n << " " << m << " " << s.y << " " << s.x << " " << t.y << " " << t.x << endl;
    if (s.x > t.x) {
        // cout << "reversed: " << s.y << " " << s.x << " " << t.y << " " << t.x << endl;
        char c = gt(t, offset);
        solve_m(n, m, t, s, offset);
        rev_from(t, s, offset);
        st(c, t, offset);
        return "";
    }
    int min_j = min(s.x, t.x);
    int max_j = max(s.x, t.x);
 
    /*for (int j = min_j - min_j % 2; j > 0; j -= 2) {*/
    for (int j = 2; j > 0; j -= 2) {
        if (min_j > j) {
            if (ok(n, m - j, ot(s, {0, -j}), ot(t, {0, -j}))) {
                auto x1 = make_tuple(n, 2, make_pair(0, 1), make_pair(0,1));
                solve_m(n, m - j, ot(s, {0, -j}), ot(t, {0, -j}), ot(offset, {0, j}));
 
                solve_strip_hor(true, n, j, offset);
                return "";
            }
        }
    }
    
    /*for (int j = (m - max_j) / 2 * 2; j > 0; j -= 2) {*/
    for (int j = 2; j > 0; j -= 2) {
        if (max_j <= m - j) {
            if (ok(n, m - j, s, t)) {
                auto x1 = make_tuple(n, 2, make_pair(0, m - j), make_pair(0,2));
                string path = solve_m(n, m - j, s, t, offset);
 
                solve_strip_hor(false, n, j, ot(offset, {0, m - j}));
                return "";
            }
        }
    }
    
 
    vector<int> st_i;
    st_i.push_back(1);
    st_i.push_back(2);
    
    if (n % 2 == 0) st_i.push_back(n);
    else st_i.push_back(n - 1);
    for (int i : st_i) {
        int first_m = 2;
        int second_m = m - 2;
 
        pair<int, int> first_e = {i, first_m};
        pair<int, int> second_e = {i, first_m + 1};
 
        if (inside(n, first_m, s) 
            && inside(n, second_m, ot(t, {0, -first_m}))
            && ok(n, first_m, s, first_e) 
            && ok(n, second_m, ot(t, {0, -first_m}), ot(second_e, {0, -first_m}))
        ) { 
            string s1 = solve_m(n, first_m, s, first_e, offset);
            //string s1 = mango::solve2(first_m, n, rotate_right(n, first_m, s), rotate_right(n, first_m, first_e));
            //s1 = convert_rotate(s1);
            st('R', first_e, offset);
            string s2 = solve_m(n, second_m, ot(second_e, {0, -first_m}), ot(t, {0, -first_m}), ot(offset, {0, first_m}));
 
            return "";
        }
    }
 
    brute(n, m, s, t, offset);
    return "";
}
 
int ckmid = 0;
int ckmidloop = 0;
 
string solve_mid(int n, int m, int j1, int j2, pair<int, int> offset) {
    string res;
 
    while (n > 2) {
        ckmidloop++;
        if (n * m <= cutoff) {
            brute(n, m, {1, j1}, {n, j2}, offset);
            return "";
        }
        for (int j = 2 - (j1 % 2); j <= m; j += 2) {
            ckmid++;
            if (j == j1 && j1 != 1 && j1 != m) continue;
            if (ok(n - 2, m, {1, j}, {2, j2})) {
                mango::solve2(2, m, {1, j1}, {2, j}, offset);
                offset.y += 2;
                j1 = j; 
                break;
            }
        }
 
        res += "D";
        n -= 2;
    }
 
    mango::solve2(2, m, {1, j1}, {2, j2}, offset);
 
    return res;
}
 
int scc = 0;
int chc = 0;
 
string solve(int n, int m, pair<int, int> s, pair<int, int> t, pair<int, int> offset) {
    scc++;
    if (s > t) {
        char c = gt(t, offset);
        solve(n, m, t, s, offset);
        rev_from(t, s, offset);
        st(c, t, offset);
        return "";
    }
    int min_i = min(s.y, t.y);
    int max_i = max(s.y, t.y);
 
    //cout << n << " " << m << " " << min_i << " " << max_i << endl;
 
    /*for (int i = min_i - min_i % 2; i > 0; i -= 2) {*/
    /*for (int i = 2; i > 0; i -= 2) {
        if (min_i > i) {
            if (ok(n - i, m, ot(s, {-i, 0}), ot(t, {-i, 0}))) {
                auto x1 = make_tuple(2, m, make_pair(1, 0), make_pair(1,0));
                solve(n - i, m, ot(s, {-i, 0}), ot(t, {-i, 0}), ot(offset, {i, 0}));
 
                solve_strip(x1, ot(s, {-i, 0}), i / 2, offset);
                return ""
            }
        }
    }*/
 
    for (int i = (n - max_i) / 2 * 2; i > 0; i -= 2) {
        if (max_i <= n - i) {
            if (ok(n - i, m, s, t)) {
                //cout << i << " " << n << " " << max_i << endl;
                auto x1 = make_tuple(2, m, make_pair(n - i, 0), make_pair(2,0));
 
                string path = solve(n - i, m, s, t, offset);
 
                return solve_strip(x1, path, s, i / 2);
            }
        }
    }
 
    if (n <= 3 || max_i <= 2 || min_i > 2) {
        return solve_m(n, m, s, t, offset);
    }
 
    // Assume s.y <= 2 and t.y >= n - 1
 
    int left_n = 2;
    int right_n = 2 + (n % 2);
 
    int mid = n - left_n - right_n;
 
    // check for color compatibility before
    // B always even for all
    // (1) B is even and s and t have a different color
 
    // for j1:
    // must have different color than s.
    // since it is always at y == 2, the x coordinate only affects the color
 
    // for j2:
    // must have same parity as j1.
 
    int color = (s.x + s.y) % 2;
 
    for (int j1 = 1 + color; j1 <= m; j1 += 2) {
        for (int j2 = 1 + color; j2 <= m; j2 += 2) {
            chc++;
            pair<int, int> first_e = {left_n, j1};
            pair<int, int> second_e = {1, j2};
 
            if (mid == 0 && j1 != j2) continue;
            if (mid == 2 && j1 == j2 && j1 != 1 && j1 != m) continue;
 
            if (ok(left_n, m, s, first_e) 
                && ok(right_n, m, second_e, ot(t, {-(left_n + mid), 0}))
            ) {
                
                mango::solve2(left_n, m, s, first_e, offset);
                string ans;
                if (mid != 0) ans += "D" + solve_mid(mid, m, j1, j2, ot(offset, {2, 0}));
                // if (mid != 0) ans += "D" + solve(mid, m, {1, j1}, {mid, j2});
                ans += "D" + solve_m(right_n, m, second_e, ot(t, {-(left_n + mid), 0}), ot(offset, {left_n + mid, 0}));
                //auto e1 = rotate_right(right_n, m, second_e);
                //auto e2 = rotate_right(right_n, m, ot(t, {-(left_n + mid), 0}));
                //ans += "D" + convert_rotate(solve(m, right_n, e1, e2));
 
                return ans;
            }
        }
    }
 
    return solve_m(n, m, s, t, offset);
}
 
string collect_path(pair<int, int> s) {
    string ans;
 
    char nxt = gt(s, {0, 0});
    while (nxt != 'E') {
        ans.push_back(nxt);
        s = step(nxt, s);
        nxt = gt(s, {0, 0});
    }
 
    return ans;
}
 
void test_case() {
    int n, m;
    pair<int, int> s, t;
 
    cin >> n >> m >> s.y >> s.x >> t.y >> t.x;
 
    if (!ok(n, m, s, t)) {
        cout << "NO" << endl;
        return;
    }
 
    cout << "YES" << endl;
 
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            result[i][j] = '?';
        }
    }
 
    if (s <= t) {
        solve(n, m, s, t, {0, 0});
    } else {
        solve(n, m, t, s, {0, 0});
        rev_from(t, s, {0, 0});
        st('E', t, {0, 0});
    }
 
    /*for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cout << result[i][j];
        }
        cout << endl;
    }*/
 
    cout << collect_path(s) << endl;
}
 
int main() {
    /*ios_base::sync_with_stdio(false);
    cin.tie(nullptr);*/
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        test_case();
    }
 
    /*cout << "Brute called: " << c << endl;
    cout << "Solve called: " << scc << endl;
    cout << "mango::solve2 called: " << s2 << " mem size: " << mem.size() << endl;
    cout << "Solve strip called: " << ss << endl;
    cout << "Checked: " << chc << endl;
    cout << "Solve mid called: " << ckmid << " loop " << ckmidloop << endl;*/
 
    return 0;
}