#include #define rep(i, j, k) for (int i = (j); i <= (k); ++i) #define per(i, j, k) for (int i = (j); i >= (k); --i) #define SZ(v) int((v).size()) #define ALL(v) (v).begin(),(v).end() #define fi first #define se second using ll = long long; using pii = std::pair; using pll = std::pair; template void chkmn(T &x, T y) { if (y < x) x = y; } template void chkmx(T &x, T y) { if (y > x) x = y; } using namespace std; const int maxn = 2100; int n, X, Y, tot, delta[maxn][maxn], f[maxn][maxn], pos[maxn], L[maxn], R[maxn], dis[maxn], t[maxn << 2], lz[maxn << 2]; string str, s[maxn]; vector ans, vec[maxn]; #define mid ((l + r) >> 1) void build(int c, int l, int r, int k) { lz[c] = 0; if (l == r) return t[c] = f[k - 1][l - 1], void(); build(c << 1, l, mid, k), build(c << 1 | 1, mid + 1, r, k); t[c] = max(t[c << 1], t[c << 1 | 1]); } void down(int c) { if (!lz[c]) return; t[c << 1] += lz[c], lz[c << 1] += lz[c]; t[c << 1 | 1] += lz[c], lz[c << 1 | 1] += lz[c]; lz[c] = 0; } void upd(int c, int l, int r, int x, int y, int v) { if (l == x && r == y) return t[c] += v, lz[c] += v, void(); down(c); if (y <= mid) upd(c << 1, l, mid, x, y, v); else if (x > mid) upd(c << 1 | 1, mid + 1, r, x, y, v); else upd(c << 1, l, mid, x, mid, v), upd(c << 1 | 1, mid + 1, r, mid + 1, y, v); t[c] = max(t[c << 1], t[c << 1 | 1]); } int qry(int c, int l, int r, int x, int y) { if (l == x && r == y) return t[c]; down(c); if (y <= mid) return qry(c << 1, l, mid, x, y); else if (x > mid) return qry(c << 1 | 1, mid + 1, r, x, y); else return max(qry(c << 1, l, mid, x, mid), qry(c << 1 | 1, mid + 1, r, mid + 1, y)); } #undef mid int main() { cin.tie(nullptr) -> ios::sync_with_stdio(false); cin >> n >> X >> Y >> str, tot = 1; for (char c : str) { if (c == 'S') tot++; else s[tot] += c; } if (tot <= Y) return cout << "-1\n", 0; rep (i, 1, tot) { int pos = 0; rep (j, i, tot) { for (char c : s[j]) pos += (c == 'L' ? -1 : 1), chkmx(pos, 0); delta[i][j] = pos; } } rep (i, 1, tot) { for (char c : s[i]) { if (c == 'L') { int lim = 0; while (lim < i && dis[lim + 1] > 0) lim++; rep (j, 1, lim) dis[j]--; if (lim > 0) vec[i].emplace_back(lim, -1); } else { rep (j, 1, i) dis[j]++; vec[i].emplace_back(i, 1); } } } rep (i, 0, Y + 1) rep (j, 0, tot) f[i][j] = -1e9; f[0][0] = 0; rep (i, 1, Y + 1) { build(1, 1, tot, i); rep (j, 1, tot) { for (auto [p, v] : vec[j]) upd(1, 1, tot, 1, p, v); f[i][j] = qry(1, 1, tot, 1, j); } } if (f[Y + 1][tot] < X) return cout << "-1\n", 0; int cur = tot; per (i, Y + 1, 1) { int nxt = -1; rep (j, 0, cur - 1) if (f[i - 1][j] + delta[j + 1][cur] == f[i][cur]) nxt = j; cur = nxt, pos[i - 1] = cur + 1; } pos[Y + 1] = tot + 1, cur = 0; rep (i, 0, Y) { int mn = cur, mx = cur, pre = cur; rep (j, pos[i], pos[i + 1] - 1) { for (char c : s[j]) { if (c == 'L') cur--; else cur++; chkmx(cur, pre), chkmn(mn, cur), chkmx(mx, cur); } } L[i] = mn, R[i] = mx; } while (true) { cur = 0; int id = -1, lst = -1; rep (i, 0, Y) { rep (j, pos[i], pos[i + 1] - 1) { for (char c : s[j]) { if (c == 'L') cur--; else cur++; chkmx(cur, L[i]), chkmn(cur, R[i]); } if (L[i] < R[i]) id = i, lst = cur; } } if (cur == X) break; assert(id != -1); R[id]--, cur = 0; rep (i, 0, id) { rep (j, pos[i], pos[i + 1] - 1) { for (char c : s[j]) { if (c == 'L') cur--; else cur++; chkmx(cur, L[i]), chkmn(cur, R[i]); } } } if (cur < lst) { rep (i, id + 1, Y) L[i]--, R[i]--; } } rep (i, 0, Y) { ans.emplace_back(L[i] - 1, i), ans.emplace_back(R[i] + 1, i); rep (j, L[i], R[i]) if (i == Y || j < L[i + 1] || j > R[i + 1]) ans.emplace_back(j, i + 1); } sort(ALL(ans)), ans.erase(unique(ALL(ans)), ans.end()); cout << SZ(ans) << '\n'; for (auto s : ans) cout << s.fi << ' ' << s.se << '\n'; }