/** * date : 2020-12-12 01:07:19 */ #define NDEBUG using namespace std; // intrinstic #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // utility namespace Nyaan { using ll = long long; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; template using V = vector; template using VV = vector>; using vi = vector; using vl = vector; using vd = V; using vs = V; using vvi = vector>; using vvl = vector>; template struct P : pair { template P(Args... args) : pair(args...) {} using pair::first; using pair::second; T &x() { return first; } const T &x() const { return first; } U &y() { return second; } const U &y() const { return second; } P &operator+=(const P &r) { first += r.first; second += r.second; return *this; } P &operator-=(const P &r) { first -= r.first; second -= r.second; return *this; } P &operator*=(const P &r) { first *= r.first; second *= r.second; return *this; } P operator+(const P &r) const { return P(*this) += r; } P operator-(const P &r) const { return P(*this) -= r; } P operator*(const P &r) const { return P(*this) *= r; } P operator*(ll n) const { return P(this->x() * n, this->y() * n); } }; using pl = P; using pi = P; using vp = V; constexpr int inf = 1001001001; constexpr long long infLL = 4004004004004004004LL; template int sz(const T &t) { return t.size(); } template void mem(T (&a)[N], int c) { memset(a, c, sizeof(T) * N); } template inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template int lb(const vector &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template int ub(const vector &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } constexpr long long TEN(int n) { long long ret = 1, x = 10; for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1); return ret; } template pair mkp(const T &t, const U &u) { return make_pair(t, u); } template vector mkrui(const vector &v, bool rev = false) { vector ret(v.size() + 1); if (rev) { for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1]; } else { for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; } return ret; }; template vector mkuni(const vector &v) { vector ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template vector mkord(int N, F f) { vector ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template vector reord(const vector &v, const vector &ord) { int N = v.size(); vector ret(N); for (int i = 0; i < N; i++) ret[i] = v[ord[i]]; return ret; }; template vector mkiota(int N) { vector ret(N); iota(begin(ret), end(ret), 0); return ret; } template vector mkinv(vector &v, int max_val = -1) { if (max_val < (int)v.size()) max_val = v.size() - 1; vector inv(max_val + 1, -1); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } } // namespace Nyaan // bit operation namespace Nyaan { __attribute__((target("popcnt"))) inline int popcnt(const u64 &a) { return _mm_popcnt_u64(a); } __attribute__((target("bmi"))) inline int lsb(const u64 &a) { return _tzcnt_u64(a); } __attribute__((target("bmi"))) inline int ctz(const u64 &a) { return _tzcnt_u64(a); } __attribute__((target("lzcnt"))) inline int msb(const u64 &a) { return 63 - _lzcnt_u64(a); } __attribute__((target("lzcnt"))) inline int clz64(const u64 &a) { return _lzcnt_u64(a); } template inline int gbit(const T &a, int i) { return (a >> i) & 1; } template inline void sbit(T &a, int i, bool b) { a ^= (gbit(a, i) == b ? 0 : (T(b) << i)); } constexpr long long PW(int n) { return 1LL << n; } constexpr long long MSK(int n) { return (1LL << n) - 1; } } // namespace Nyaan // inout namespace Nyaan { template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template void outr(const T &t, const U &... u) { cout << t; outr(u...); } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; } // namespace Nyaan // debug namespace DebugImpl { template struct is_specialize : false_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize::value, void>> : true_type { }; void dump(const char& t) { cerr << t; } void dump(const string& t) { cerr << t; } template ::value, nullptr_t> = nullptr> void dump(const U& t) { cerr << t; } template void dump(const T& t, enable_if_t::value>* = nullptr) { string res; if (t == Nyaan::inf) res = "inf"; if (is_signed::value) if (t == -Nyaan::inf) res = "-inf"; if (sizeof(T) == 8) { if (t == Nyaan::infLL) res = "inf"; if (is_signed::value) if (t == -Nyaan::infLL) res = "-inf"; } if (res.empty()) res = to_string(t); cerr << res; } template void dump(const pair&); template void dump(const pair&); template void dump(const T& t, enable_if_t::value>* = nullptr) { cerr << "[ "; for (auto it = t.begin(); it != t.end();) { dump(*it); cerr << (++it == t.end() ? "" : ", "); } cerr << " ]"; } template void dump(const pair& t) { cerr << "( "; dump(t.first); cerr << ", "; dump(t.second); cerr << " )"; } template void dump(const pair& t) { cerr << "[ "; for (int i = 0; i < t.second; i++) { dump(t.first[i]); cerr << (i == t.second - 1 ? "" : ", "); } cerr << " ]"; } void trace() { cerr << endl; } template void trace(Head&& head, Tail&&... tail) { cerr << " "; dump(head); if (sizeof...(tail) != 0) cerr << ","; trace(forward(tail)...); } } // namespace DebugImpl #ifdef NyaanDebug #define trc(...) \ do { \ cerr << "## " << #__VA_ARGS__ << " = "; \ DebugImpl::trace(__VA_ARGS__); \ } while (0) #else #define trc(...) #endif // macro #define each(x, v) for (auto&& x : v) #define each2(x, y, v) for (auto&& [x, y] : v) #define all(v) (v).begin(), (v).end() #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--) #define repc(i, a, cond) for (long long i = (a); (cond); i++) #define enm(i, val, vec) \ for (long long i = 0; i < (long long)(vec).size(); i++) \ if (auto& val = vec[i]; false) \ ; \ else #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define inc(...) \ char __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define die(...) \ do { \ Nyaan::out(__VA_ARGS__); \ return; \ } while (0) namespace Nyaan { void solve(); } int main() { Nyaan::solve(); } using namespace Nyaan; void Nyaan::solve() { vl sq(40000); rep(i, 40000) sq[i] = i * i; pl D(1, 0), U(-1, 0), R(0, 1), L(0, -1); auto cnv = [&](ll X) -> pl { ll ls = lb(sq, X); if (ls % 2 == 0) ls--; if (ls * ls == X) return pl(ls / 2, ls / 2); ll mx = ls / 2 + 1; pl res(mx, mx); X -= ls * ls; mx *= 2; res += U * min(X, mx), X -= min(X, mx); res += R * min(X, mx), X -= min(X, mx); res += D * min(X, mx), X -= min(X, mx); res += L * min(X, mx), X -= min(X, mx); return res; }; auto rstr = [&](ll x, ll y) -> ll { if (x == 0 and y == 0) return 1; int mx = max(abs(x), abs(y)); if (x == mx and y == mx) return (mx * 2 + 1) * (mx * 2 + 1); ll X = (mx * 2 - 1) * (mx * 2 - 1); pl p(mx, mx); if (y == mx) return X + abs(p.x() - x); X += mx << 1, p.x() = -mx; if (x == -mx) return X + abs(p.y() - y); X += mx << 1, p.y() = -mx; if (y == -mx) return X + abs(p.x() - x); X += mx << 1, p.x() = mx; if (x == mx) return X + abs(p.y() - y); X += mx << 1, p.y() = mx; return X; }; auto rstr2 = [&](pl p) -> ll { return rstr(p.x(), p.y()); }; auto f = [&](ll X) -> tuple> { V ans; auto [sx, sy] = cnv(X); if (X != 1) { auto u = X ^ 1; auto [ux, uy] = cnv(u); trc(u,ux,uy); pl d = pl(ux, uy) - pl(sx, sy); ans.push_back(d); X = u; sx = ux, sy = uy; } int cnt = 1; auto nyaan = [&](int x, int y) { if (abs(x) == abs(y)) { if (x > 0 and y > 0) return mkp(U, U); if (x > 0 and y < 0) return mkp(R, R); if (x < 0 and y < 0) return mkp(D, D); return mkp(L, L); } int mx = max(abs(x), abs(y)); pl first_move; if (mx == x) first_move = U; else if (mx == -x) first_move = D; else if (mx == y) first_move = L; else first_move = R; pl first_pos = pl(x, y) + first_move; ll first_val = rstr2(first_pos); pl sec_pos = cnv(first_val ^ 1); pl sec_mov = sec_pos - first_pos; return mkp(first_move, sec_mov); }; while (max(abs(sx), abs(sy)) > 1) { auto [_f, _s] = nyaan(sx, sy); cnt ^= 1; pl nx = pl(sx, sy) + _f + _s; tie(sx, sy) = nx; ans.push_back(_f); ans.push_back(_s); } return {cnt, pl(sx, sy), ans}; }; inl(S, T); int mustgo1 = S % 2 == T % 2; auto [sc, sp, smv] = f(S); auto [tc, tp, tmv] = f(T); trc(sc,sp,smv); trc(tc,tp,tmv); map drc; drc[D] = 'D', drc[U] = 'U'; drc[R] = 'R', drc[L] = 'L'; // 疲れた }