#ifndef TEMPLATE_HPP #define TEMPLATE_HPP #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include #define impl_overload4(a, b, c, d, e, ...) e #define impl_overload5(a, b, c, d, e, f, ...) f #define impl_overload6(a, b, c, d, e, f, g, ...) g #define impl_overload7(a, b, c, d, e, f, g, h, ...) h // clang-format off #define impl_rep4(i, a, b, c) for (int i = (a); i < (b); i += (c)) #define impl_rep3(i, a, b) impl_rep4(i, a, b, 1) #define impl_rep2(i, n) impl_rep3(i, 0, n) #define impl_rep1(n) for (int _ = 0; _ < (n); ++_) #define rep(...) impl_overload4(__VA_ARGS__, impl_rep4, impl_rep3, impl_rep2, impl_rep1)(__VA_ARGS__) #define impl_rrep4(i, a, b, c) for (int i = (b) - 1; i >= (a); i -= (c)) #define impl_rrep3(i, a, b) impl_rrep4(i, a, b, 1) #define impl_rrep2(i, n) impl_rrep3(i, 0, n) #define rrep(...) impl_overload4(__VA_ARGS__, impl_rrep4, impl_rrep3, impl_rrep2)(__VA_ARGS__) // clang-format on #define all(v) std::begin(v), std::end(v) template constexpr int bit(T x, unsigned int k) { return (x >> k) & 1; } template constexpr bool chmax(T& a, const T& b) { return a < b ? a = b, true : false; } template constexpr bool chmin(T& a, const T& b) { return a > b ? a = b, true : false; } void yesno(bool b) { std::cout << (b ? "Yes" : "No") << "\n"; } void yes() { yesno(true); } void no() { yesno(false); } struct Setup { Setup() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(11); } } setup; #ifdef LOCAL #include "template_local.hpp" #else #define show(...) ((void)0) #endif using uint = unsigned int; using lint = long long; using ulint = unsigned long long; using namespace std; #endif // TEMPLATE_HPP int main() { int r, c; string s; cin >> r >> c >> s; // delete redundant moves (e.g., LRLRLR -> R) { int f[128]; f['U'] = f['D'] = 0; f['L'] = f['R'] = 1; string t; for (char c: s) { if (not t.empty() and f[t.back()] == f[c]) { t.pop_back(); } t += c; } s = t; } int n = size(s); if (count(all(s), 'U') == 0 or count(all(s), 'L') == 0) { cout << -1 << endl; return 0; } if (s.substr(n - 2) == "DR" or s.substr(n - 2) == "RD") { cout << -1 << endl; return 0; } vector> ans; int idx = min(s.find_last_not_of('U'), s.find_last_not_of('L')); ans.emplace_back(r, c + 1); ans.emplace_back(r + 1, c); if (s[idx] == 'U') { ans.emplace_back(r - 1, c); ans.emplace_back(r + 1, 1); ans.emplace_back(r + 2, 0); ans.emplace_back(0, 1); } else { // s[idx] == 'L' ans.emplace_back(r, c - 1); ans.emplace_back(1, c + 1); ans.emplace_back(0, c + 2); ans.emplace_back(1, 0); } sort(all(ans)); ans.erase(unique(all(ans)), end(ans)); cout << size(ans) << "\n"; for (auto [x, y]: ans) { cout << x << " " << y << "\n"; } return 0; }