QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#392126#3039. CleaningzlxFTHAC ✓436ms361336kbC++143.0kb2024-04-17 09:26:552024-04-17 09:26:55

Judging History

你现在查看的是最新测评结果

  • [2024-04-17 09:26:55]
  • 评测
  • 测评结果:AC
  • 用时:436ms
  • 内存:361336kb
  • [2024-04-17 09:26:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)

const int N = 2e3 + 5, M = N * N;
const int BN = 5e4 + 5;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
using Bitset = bitset<BN>;

int n, m, q;
int ti, cnt, dfn[M], low[M], sd[M], siz[M];
int in[M], mnR[M], mxR[M], mnC[M], mxC[M];
char s[N][N];
vector<int> G[M], E[M];
Bitset from[BN], to[BN];

void tarjan(int u) {
  static int tp, st[M];
  low[u] = dfn[u] = ++ti, st[++tp] = u;
  for (auto v : G[u]) {
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (!sd[v]) low[u] = min(low[u], dfn[v]);
  }
  if (low[u] == dfn[u]) {
    ++cnt, sd[u] = cnt;
    while (st[tp] != u) sd[st[tp--]] = cnt;
    --tp;
  }
}
void preWork() {
  static int h = 1, t = 0, q[M];
  for (int i = 1; i <= cnt; ++i) if (!in[i]) q[++t] = i;
  map<pair<int, int>, int> mp;
  while (h <= t) {
    int u = q[h++];
    for (auto v : E[u]) {
      mnR[v] = min(mnR[v], mnR[u]);
      mxR[v] = max(mxR[v], mxR[u]);
      mnC[v] = min(mnC[v], mnC[u]);
      mxC[v] = max(mxC[v], mxC[u]);
      if (!mp.count({u, v})) {
        G[v].push_back(u);
        mp[{u, v}] = 1;
        from[v] |= from[u];
      }
      if (--in[v] == 0) q[++t] = v;
    }
  }
  for (int i = cnt; i >= 1; --i) {
    int u = q[i];
    for (auto v : G[u]) {
      to[v] |= to[u];
    }
  }
}

#define id(i, j) ((i - 1) * m + j)
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> q;
  for (int i = 1; i <= n; ++i) cin >> (s[i] + 1);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      for (int d = 0; d < 4; ++d) {
        int x = i + dx[d], y = j + dy[d];
        if (x <= 0 || y <= 0 || x > n || y > m) continue;
        if (s[i][j] == 'U' && d == 1) continue;
        if (s[i][j] == 'D' && d == 0) continue;
        if (s[i][j] == 'L' && d == 3) continue;
        if (s[i][j] == 'R' && d == 2) continue;
        G[id(i, j)].push_back(id(x, y));
      }
  for (int i = 1; i <= n * m; ++i) if (!dfn[i]) tarjan(i);
  for (int i = 1; i <= cnt; ++i)
    mnR[i] = mnC[i] = 1e9, mxR[i] = mxC[i] = 1;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      int u = id(i, j);
      for (auto v : G[u]) if (sd[u] != sd[v]) {
        E[sd[u]].push_back(sd[v]);
        in[sd[v]] += 1;
      }
      u = sd[u];
      mnR[u] = min(mnR[u], i);
      mxR[u] = max(mxR[u], i);
      mnC[u] = min(mnC[u], j);
      mxC[u] = max(mxC[u], j);
      siz[u] += 1;
    }
  for (int i = 1; i <= cnt; ++i) from[i][i] = to[i][i] = 1;
  for (int i = 1; i <= cnt; ++i) G[i].clear();
  preWork();
  Bitset tmp;
  while (q--) {
    int a, b, x, y;
    cin >> a >> b >> x >> y;
    int u = sd[id(x, y)];
    int v = sd[id(a, b)];
    tmp = from[u] & to[v];
    int ans = 0;
    for (int i = tmp._Find_first(); i <= cnt; i = tmp._Find_next(i)) {
      ans += siz[i];
    }
    cout << ans << "\n";
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 23ms
memory: 216548kb

input:

1 1 1
L
1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 16ms
memory: 214640kb

input:

5 5 5
DDDDD
RDDDL
RRDLL
RUUUL
UUUUU
1 1 5 5
2 2 5 5
3 3 5 5
4 4 5 5
5 5 5 5

output:

0
14
20
14
5

result:

ok 5 number(s): "0 14 20 14 5"

Test #3:

score: 0
Accepted
time: 28ms
memory: 214648kb

input:

10 10 15
DDDDDDDDLU
LRDLRRDLLU
DDDLRRDLLD
RRLLDUULLD
RRLLURLRLD
RRLLRRLDLU
RRLLURLULU
UULLURLULU
DRULUUUULD
RRRLDRLRLD
7 4 2 5
4 7 6 8
6 6 5 6
5 6 9 6
9 10 5 5
2 5 4 3
7 9 4 4
10 9 1 5
9 9 8 9
1 4 7 8
10 2 5 10
7 9 1 3
7 6 7 7
5 6 10 2
2 6 4 2

output:

41
41
41
41
0
0
0
0
20
0
88
0
41
0
0

result:

ok 15 numbers

Test #4:

score: 0
Accepted
time: 379ms
memory: 326784kb

input:

1000 1000 300000
RLLLURUDLURULUURLUDDLDDDRDDRUUDLLURRDDLLDRDLLRRRULUULLRRLRURRLLUUUUDUDDLUURDULDUDRRRUDLULRLDRDDUDULUUURLDUDDDUULLURUDRLRDLRULDUDUDDDLDUULRUUDLRLDURURLDDLLRRUURLULLRULLDURUDDDRUUUURUULRRRLLDLLUURUULDDLDRDLLDURLRDURLRLLDLUDLRULDUUDLDLULLULDDLUDLLLRURRRUUDLRLDLDLRDULRUDDURDRRLDRLRULDUL...

output:

0
0
0
0
0
0
245868
0
0
0
0
0
0
0
0
0
0
0
0
98541
0
0
0
89575
0
361225
0
262684
0
0
0
0
0
0
0
0
0
0
0
0
311462
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
361225
0
0
0
0
0
0
0
0
0
62676
0
0
136413
0
0
0
0
246844
0
178165
0
62676
361225
136413
0
0
361225
0
361225
0
0
0
199089
0
0
0
311462
0
0
262684
0
199...

result:

ok 300000 numbers

Test #5:

score: 0
Accepted
time: 409ms
memory: 328820kb

input:

1000 1000 300000
RRUDRRRRRDUULRUDLLULDRUDLDUDUDRUUUDURDDDRLURUURDURLDRDUUDUDLLUDDLRUDULUDDULDUULRRLUUDLLURLLRLDRLLDRDLUUDRDDUDRLLRDDDRURLRRDUDRRURRUDRRURRLLDULULRUDLLURDDULURDUULLUUUULLRURLLUURRUDLDUDRLLUDLDUDRLUUUUURLDRUDLRRLLLRRDLLDLRDUULDUDDULRURRDLRUDDRDLDLDDRLDRLRUDUURDURUURRDRRDLDLDDLRDRDLDDLL...

output:

0
0
321495
0
0
321495
0
321495
321495
0
0
505626
0
0
0
79631
0
0
0
0
0
0
0
0
371285
79628
0
321495
155278
0
0
0
0
0
0
469795
0
72655
0
0
0
0
0
0
0
0
71676
469795
0
321495
0
0
371285
54713
0
321495
0
0
0
0
0
0
589228
505626
321495
321495
0
0
0
321495
425998
0
589228
0
0
0
0
0
0
100484
0
0
321495
0
0
...

result:

ok 300000 numbers

Test #6:

score: 0
Accepted
time: 394ms
memory: 323712kb

input:

1000 1000 300000
RDLURLRUDLRRLRDULRLRLULDDLRRLDLRRRLLDDUDULDLLRLURUURUUDRRRURDURLRULRRUDDLLUDRDLDLULDLDLULRDRDDLDRURLDRDRLLURRDLRDRRRUURRRURDRUDLRDDDLRULULDLDLRDDRRLDURLLLURRLLLULRLLRRDDDLRDDDLRDRDDUDDDUDRDRURDRRULDURLRLDDLURLUURUUURLRUDRRURDLDLUDDLLDRRULLULULRRLLDLLLUDRRDUULUDRRRRUUDDDUULRURLUDLULD...

output:

0
0
142351
0
366329
0
0
0
0
0
0
0
0
0
0
154199
0
154199
0
0
0
0
0
119290
0
54685
0
0
0
0
366329
0
142351
0
0
0
0
0
0
280656
212130
0
0
0
0
0
0
0
0
0
0
0
366329
0
69779
0
0
0
280656
0
139334
0
0
0
0
223978
0
0
366329
0
0
0
0
157316
0
0
223978
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
119450
227095
0
...

result:

ok 300000 numbers

Test #7:

score: 0
Accepted
time: 395ms
memory: 326100kb

input:

1000 1000 300000
LLLUDDULLDLRDLUURDUDURLDDURRLLRLRDDLURLDLRLLDLDLUDDRRLRLLDRRRLUULRLLLLDULDUDURURDURRURLDLRULUULURRLRLULUUUUDRURRUULRUUUDDURULUDLUUUULUUURUDLRRDURULLURLDUDUDUUDLDRLDDRRUURDRRRURLURDRRURRRLDLURURRRUDRUDLLLUDDRRDULDLUDUDDRRLRRLDULLLURULDDLDDLDULRDLULLDUUDUULRURULULRLRUDLLLURRRDLRUULURD...

output:

0
0
202971
223079
0
0
0
0
0
0
0
142349
0
0
0
223079
0
223079
0
0
0
0
0
142349
0
197961
90544
47763
0
0
0
223079
0
0
0
241901
0
0
0
0
0
241901
223079
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
223079
0
0
0
223079
90544
0
0
0
0
0
0
0
0
0
0
90544
0
0
215933
0
0
0
0
99552
0
367428
0
0
0
0
0
99552
0
0
0
0
0
223079
...

result:

ok 300000 numbers

Test #8:

score: 0
Accepted
time: 403ms
memory: 327608kb

input:

1000 1000 300000
URRLURLRLRDDDULLDDLDLLRRUDLRLRDDDRLURRDRDULLUDUDUDRDUUDUDUURRRDDRDLDURLURDLRRLRURLLDUDUDDLRUDDLDDRDLUULRRULUDUDUDUURDUDDLDRDLRDLDRRRDDDUUDLRURULLLUDLRDUULRRDUDLLDDRURLDDLRLUDRUDRDRRDLLUDULDUDLDLDLLURRRLDRRDLLDURLLRLDDLRULDUURLRLDRLULDLRRULUURULRULDLUDLLUDULRDULRDLLDLDRLLRLRLLLDLUDLU...

output:

0
0
190077
0
0
298685
0
0
229985
0
0
94594
0
0
0
72683
0
0
0
0
0
0
0
0
229985
0
0
0
0
0
0
72683
0
0
229985
0
0
229985
0
0
0
0
0
0
65663
190077
0
229985
0
0
0
229985
0
0
148298
0
0
0
298685
0
0
159235
0
0
0
0
0
0
0
0
0
0
0
0
0
0
229985
0
94594
0
0
0
0
0
0
0
0
0
0
0
0
229985
0
0
0
0
0
0
0
0
54726
0
72...

result:

ok 300000 numbers

Test #9:

score: 0
Accepted
time: 403ms
memory: 319932kb

input:

1000 1000 300000
LULDDDLUULDUDLRURDURLDRDLLURLRRRURLRLURDUULDUDLULLLDLUUURURLRLDRDUDLLLUULURURLRRDURDDDDDDRUDRDDRLDDULDDULRURULUUDLDRRRUUDLUUUUDULLUDDDRULLLLRUDDRRDDLDRULLUUDLLDDURUDULLRUDUURLLRUDRRUUDDURDURDDRRRUDUUDRDLULDLRLDDUURRURURLDDLLUDLUULRRLLRLUDDRUDDLDDLURULDRLRRLURUDRDDRLDURDRDUULRUURUURR...

output:

0
0
0
174103
209015
0
0
0
0
0
0
0
0
0
0
88503
0
0
0
0
125408
0
0
0
0
0
0
0
33830
0
0
0
0
0
0
0
0
301590
0
0
0
0
0
0
0
0
301590
0
0
0
0
0
209015
0
0
0
0
0
0
0
0
0
0
0
161244
0
0
125408
0
0
0
0
0
0
0
0
0
0
0
0
0
252895
0
0
125408
0
62707
0
0
252895
90581
0
0
0
0
0
0
0
0
0
301590
237813
85600
0
57768
0...

result:

ok 300000 numbers

Test #10:

score: 0
Accepted
time: 401ms
memory: 329368kb

input:

1000 1000 300000
LRDRULDLURLUDRLRUULUURRDRUURLRLLLDRRDRDUDUUDDRDDLLUDLDRDDRDLUURRDDDDLDULDLRRDDUUDUDDUDRDRDRRULDURLLDRRUDDDLULRDLRRDUDLDULUURDDUUUULURRLDLUDLDULLRULDDLDRRRLRULLRULRRULUURUUDDDLDLRURRUUURURLDDULURURLDUDDURDRRDRLRLUDULLLDLDDULDDDRDDDUUDRUDUDURLDURRLDURDRLLLRUDLRDDRLDDLDRLLRLRDLLDRUULUU...

output:

189161
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
313577
313577
0
189161
0
313578
0
0
0
0
0
414142
0
0
0
0
0
0
0
0
0
0
0
0
0
0
527591
0
313577
313577
181089
0
0
0
0
0
0
0
0
181089
0
0
0
80635
181090
502738
0
0
80635
0
189161
313577
0
0
0
502738
527591
0
0
0
0
0
0
0
0
0
0
0
0
133381
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 300000 numbers

Test #11:

score: 0
Accepted
time: 409ms
memory: 321796kb

input:

1000 1000 300000
DUDDRRLDLURDURULDRDLDLLLRURUDRDDLULLLUDDLRRDRLULDRLDURULURLURDDDRLUURUDLRDDRRRDDUURDDRULLDUURUDURRDRRLDRDURLLDRUULLRRLDRURRUULUURDRULDRRLRULRLULUUUDLUDRRRRLUDLULDRRLLLURRDRRLURURLDLLUDLDDUDURDRLUDUURLDRLLUDUDLLDDLRUULLURLRLDRLUDDDLLLUDURLLLDUUDULRULDDUDLRURRURUURUDULLRRDUDRDLDLRRUUR...

output:

0
0
0
0
0
0
0
166267
152266
152266
160281
160281
0
0
0
0
0
0
0
0
0
0
160281
335415
22868
43787
0
561433
0
0
562410
0
166267
0
166267
0
0
0
0
318533
0
0
318533
318533
0
0
0
0
0
0
0
160281
0
160281
27835
0
0
118463
0
0
0
0
0
0
114452
0
0
90628
0
114453
0
0
312547
0
0
152266
0
0
0
478814
478814
0
0
0
0...

result:

ok 300000 numbers

Test #12:

score: 0
Accepted
time: 411ms
memory: 322704kb

input:

1000 1000 300000
DRLDLRLLUDRRDURLLRRURDLURDULULRRDRRDURRRLRDLLLLDLDUDDDLUDDULRRLDURUURDDURDULUULRDDDRDRLUURDURDDLLDDURDUDLLUURUUUDDLLUURRDUULRRLRUDURULURRRULRURLRUDRLLDRLRLRDUDRLRRLLLUURUDLUURLDRDULDLUULULDULDLRLURLRRRLUDRRUUDRDLLLLRULDRDRUULLDLRULLUUDUDLLURDRUUUUUDLURRLLLLLRRUURURLDRRULDDUDDDLRULLR...

output:

0
0
0
0
0
0
0
95604
0
0
75639
0
102531
0
216065
89502
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
81641
239793
0
0
0
239793
0
0
0
0
148364
0
0
0
0
0
0
0
0
0
0
116469
0
0
0
0
0
0
0
0
0
0
0
0
0
0
113499
0
0
0
0
0
0
0
0
0
0
266649
0
0
0
0
216065
0
0
0
0
0
0
0
0
0
0
113499
0
102531
0
0
0
0
95604
0
0
0
0
0
0...

result:

ok 300000 numbers

Test #13:

score: 0
Accepted
time: 394ms
memory: 320744kb

input:

1000 1000 300000
LULDRUUUUDLRDRRURLDRURRLUDRLDRLLRUULRRRDLDULRDDDLDUDRRURLDUDDLRDRDDLURRDURDRULLDDLDDDUUUDDRUUULUDUDLURRDULLUDDUDULUDURRRLULDLRRDRUURDLLDRLDUUURDDLLLLURUURULRRLLUDDLRDRRDLLLURULDURDRRDUDURDDUDUUULLUDUUUDDLRLLLLLDURDDLURDDRRLRULDLRDUDLDUDLRULDUDLDDURRRLLLRRLDDRLURUULLULRDDRDDULLULLRRU...

output:

0
0
0
94537
0
0
0
0
207008
0
0
0
0
0
0
0
138343
0
272749
0
0
0
0
0
0
0
0
0
0
0
0
0
0
138343
195091
0
0
57674
0
0
0
0
122445
0
109498
0
0
0
0
182144
70638
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
94537
0
0
0
86607
0
0
0
0
0
0
0
0
239818
0
0
0
0
136370
0
136370
0
122445
0
0
0
0
0
0
0
0
0
0
272749
0
0
0
0
0
18114...

result:

ok 300000 numbers

Test #14:

score: 0
Accepted
time: 402ms
memory: 328244kb

input:

1000 1000 300000
LUULDLLDURULUUUDRLRUDLLLRLDUDLDRRRRDLDDDLUDDULDULURDUDRDLDDLRRUURULDDUURULLRDDDURDDRRULRLRDLLRLLDLUUURUDRRLRDUULRLDDRRDLRLULDUDRULDLLLLRLDLRURULRDDLRLUDRDRLDLRDRDURUURDUDDLLRUUDRDLUDDLURURULUDUDDRRLUDDDDURLDRRLDULRDDRLLRULUDULDRDDRULULRDDULUULRRDDDDURUURLRULRLLLUUUUUULDUUULUDRDRURRU...

output:

0
0
0
0
218951
132405
0
429984
0
0
218951
211033
0
0
201044
429984
0
412077
0
0
0
0
0
0
0
412077
0
0
0
0
0
68649
412077
0
429984
0
0
0
0
0
333363
412077
218951
429984
412077
218951
201044
0
0
63756
412077
0
0
544396
218951
218951
201044
0
0
0
0
0
0
201044
0
429984
0
218951
0
117448
429984
0
0
0
0
0
...

result:

ok 300000 numbers

Test #15:

score: 0
Accepted
time: 419ms
memory: 324392kb

input:

1000 1000 300000
LLUDDULUUUURRRRUDLLUURULLLUULDDLRUDDRRLDRUUURUULDLULDLUULLUDRDURUURULLUDUDDULRLRDDURLDDRRDLUUDURDUDUDRRRUDRRULDDRUULRUDLLLLULDLURLUURDULRLDLDUUDLRLUDDDRUUUUDLDDDDURDULLUDLUUDRLDRLDDDUDRDDDDDULURRRLDRULRLULRRULDLLLRLDRURUUDDRUDDDLRRDLRDDLDLUDUUUDUUDDRLURLRLLUURRDRLRULRLLDDDLRDURURDUR...

output:

116440
0
137326
0
0
0
0
172193
0
0
0
0
0
0
0
172193
0
0
0
0
56716
116440
0
0
0
0
0
0
0
245819
0
0
163205
361188
0
0
104496
0
0
0
0
0
0
178126
405970
0
0
304472
0
0
0
0
0
0
0
0
0
0
172193
0
0
0
0
0
0
0
0
0
0
238861
0
304472
0
0
163205
0
0
0
0
0
0
175165
99473
0
222965
163205
0
0
0
0
0
0
141267
219921...

result:

ok 300000 numbers

Test #16:

score: 0
Accepted
time: 388ms
memory: 322044kb

input:

1000 1000 300000
LDDDURLRUULLRUUUURLDRDRLDDLLUDRLDLDDRLLDUUDUDRRDDLLDUUDLUDDRDDDRULUDDDLURLDUDUDDUULRRDRDDUULLRRURULUUDDURULRUUULDLLLRLDRUDLDRDRDRRLDDRDDRUDDLLLRRLLDDURLDRRLRRLUDUURLDRUULDRURULDDRRLLDURURUDURULRLLLDRRRRLRLUUURUDRLDLRDRDUUUURLULURRLDDLUDDDLURDDRDUULRDUDDDDUDLLURDDRDLUDDLLUULDLULRRDLU...

output:

0
0
202010
0
278655
171249
0
0
0
0
0
121419
0
140299
0
0
0
0
0
353337
0
0
0
0
415019
0
0
0
415019
0
0
0
0
138351
0
0
0
0
0
0
0
395115
0
0
0
138351
0
0
0
0
0
0
0
0
0
77615
0
0
0
140299
0
0
0
0
0
0
0
0
0
198042
0
0
0
0
0
0
0
0
0
0
493641
0
0
214986
0
140299
0
338374
0
57743
0
0
0
0
0
0
0
64613
0
0
138...

result:

ok 300000 numbers

Test #17:

score: 0
Accepted
time: 384ms
memory: 358456kb

input:

1000 1000 300000
DUULULRDLLRDLLULRDLULRDUURRDDDDURRRLLRLRULDLUURLDDULDRLLURRDLRUDURURUDLDDRRLLLLRRRLUURDDDUDLRLDDRDLUDRLDLUUDDUDDUULLLDDRDLUULLRUDRDRDLURLLDLDRDLUUUDURRDDLLRUDRULULURLRRRDRRDULUURRURDLRDDULULLDULDRUDURRULRDULULRRRDLDURRURLDLLRLLRRDDUDDDDUURURLUUUUDRUDRLUDRRRDRRULLDDLDDDDRDRDDUDLRDULR...

output:

995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108
995108...

result:

ok 300000 numbers

Test #18:

score: 0
Accepted
time: 414ms
memory: 352708kb

input:

1000 1000 300000
UDURLRDULUDRRLDUUUUDRUDDRDRDDLLDRUURRLLLDDDDLUULDRDDLLDURDDLLDDULDULLRRDDURLLDRUULRRRLLDURDRLRDULRUULLRLLLLURLDUUULDDDLDDRUDDLLDLDDLLRLUDURUUURDDUDULUURDDUULULULDLUULDRLLUDDUDRLRRRRRRLDDDDURLLLDRURDRRLULDDDDLLDURRDURURRLUDLDDUDRDLLLDURDUDDDUULLRLDLUULRRDULLUDUDLUDUDRDDRRULULDUUDUDDL...

output:

995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238...

result:

ok 300000 numbers

Test #19:

score: 0
Accepted
time: 392ms
memory: 354592kb

input:

1000 1000 300000
LRLRURRURRRLLLLUURULDLURLURDULRDDDRUDDRURULRRURDLRLDLDDLUULULUURRRDDURLDDDLDURRUUUDUULRRUULDRDDURDDRDUULLRUULDDRRUULRUDLRUUUDDULDLRRUURRDLDLDRDLLDRUURDLLRRDRDDDLLLRRLLRRDURRLLLDURRUUDDULRDUULUDULLUULDDUDULLRDDRUDDDLLURDLULULRRURRRRRRUUULRLRRRDDULLDRRRLULLRDUDDRDLURLUDDRRUDLUDLRDRURR...

output:

995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285
995285...

result:

ok 300000 numbers

Test #20:

score: 0
Accepted
time: 398ms
memory: 354880kb

input:

1000 1000 300000
LRRLDUUURRDLUDDLUUDRDRURRULDLDRDDLRLDUDDRULRULLDULRDRDUDUDDDRDLLULURLUUDDDLUUULRUURULLDDDURLULLRLDUURDRRLLURULRRURLULRRDLDULDLRLULLRDDURURDRULDUDRLDDRLRURLRLUDRULDUUURRRRRDRUDDRLDUUDRDUDLUUDLDLLLDULULDRLUDLUULLULRDUUULDUDDDLRUUDUDRRULURDULRUDUUDDDRRDLLDULUDDUUURRULDLDRRUDRDULULDRULL...

output:

995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080
995080...

result:

ok 300000 numbers

Test #21:

score: 0
Accepted
time: 412ms
memory: 353696kb

input:

1000 1000 300000
DDRLURULRULLDRLLLLDDULRRRRLLDRUDLUULLLDDLRLRLRUUDLRDRLRRLDURRLRDRURUURRDDLRURURRLLLLUDRDUURRLRRLULRULLRDDLUDLUUUURDUUULLRLLLDDRDRLRRURUUDLLUULLRDRDULLDRDDLURUDDLDLLDLDURDRLUDUDRDRLDDURRLULURLDRUUUUURLLUUDURULDLRRRLLLRLRDLUDLDLLDDURLLURLDDDDLRUULRLRDURURDLLLURLUURURLLDLLUDLDUULDLRRDD...

output:

995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161
995161...

result:

ok 300000 numbers

Test #22:

score: 0
Accepted
time: 379ms
memory: 355000kb

input:

1000 1000 300000
URDLDRLLLDDURDLLLULLDDLRULLURURUDLDUDURUURLDDLURRUDUDDDUURURLDUDDLRDLRLULDLUURUUUULLRLDDRUDRLLRULUULLUUDDUUDLRUDRDULLRLDRDLULLLURULUDDDRRUDLDLLDRDLULRURLDLRLRRRDUDUDDDDUDDLLDRDLUDRDURLLLRLRDULRUULULDLRULDRLDDUDLLLUDRLDDULULDUDLULLULDRDRULDURRULDLRDUUURRUDRUDDURUUUUUUDRULRLLRDLDULDUD...

output:

995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208
995208...

result:

ok 300000 numbers

Test #23:

score: 0
Accepted
time: 392ms
memory: 354180kb

input:

1000 1000 300000
UUDRLLDLLULRRLRRUDLDDLUDDUUULURRRLRUDUDRRRDUURRDLUURRURDLLURRURLUUULUURDDLURDLUURRUDLRRLDLULULDDRLUDLLDDURRLUULLDUDDDUDRRRLLLRRDLDUDDLRRUDUDDLDURUDLDURRUDUDDRUUDURRDDLRRURRRLRDURRRULURLLRUURLUUUUDRRLLLULURLRDLLLRUDURLURUDLLURUUDLLLRDDURDDLLURRUUUDRRDDLRUDUDRDDRLUUDDRDULDRDLULDULULUU...

output:

995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260
995260...

result:

ok 300000 numbers

Test #24:

score: 0
Accepted
time: 400ms
memory: 356068kb

input:

1000 1000 300000
RRDDLULLDDLRLUURDRDDDRLLRDURDRRUDDUDRDULURURRDDLDULDURLLUUDDRURRRDLRURLUDUUDUDDDULULURRLRLLLDUULDLRDURLDRLRURUDURLDRLURRLLRRDLRRLUUULDUDUUDUULDDLULLDLDUDDUDURDLLDDDRDDLUURDUDLRDLRDRRUDLLRDLUURDLDDDDLDDULRLDUURDRRUUDLUDLDULLRURURRLDDDRULDDRLDURDRDRLURUUDUULLULRRRRDLRRRDLULRRUDLLUDURL...

output:

995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
0
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995202
995203
995202
995202
995202
995202
995202
9952...

result:

ok 300000 numbers

Test #25:

score: 0
Accepted
time: 395ms
memory: 355720kb

input:

1000 1000 300000
RRLRRULULDRUDRUDLDRDDLDULURLDRULLRULRUDDUDDLLUDULDLUDURULLLUDDDURDULLDRRDDLLUDUURURRURUURLRDUDDRLULDDLURRRURLDDDDDLLDRDLLDDRDRRLRDULULUDDDRDUDDULRDURLRUUDDLUDDURLRDLRDUULDUDDLLRRULUDDDDUDRUUDUUDDDDUUUDRUDRDLDDLRRULRLDDDDUDRDDLRDRLULLLURLLDRLDDDURDLURURRDLRLDDUULRLDULRDUDLLUDURLRRURR...

output:

995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182...

result:

ok 300000 numbers

Test #26:

score: 0
Accepted
time: 380ms
memory: 356296kb

input:

1000 1000 300000
LDLUDDRUULRDDURUUDUDDDULLLDLDLUDDDDUUDUURLDDLUUDRLLRLDDRLDULRRRRRRURDULDULURUDRRLUDRURRDULDLDLDRUDUUULDDRDRUDDDDLLLURDDRURRRDRUDRUDUULUDRDDRDRUUUDRLUUULLRDLLULLRDRLRLLRUUUDLLLUUUDLULDRULDDRRDDUDUDLLDRDLDULDRLDRLRDDULLLUUDRRRLDLULLRRDRUULLRDURRRLULLDDLLDULRURDRUDLLUURLLRURUDURURRUUDD...

output:

995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241
995241...

result:

ok 300000 numbers

Test #27:

score: 0
Accepted
time: 397ms
memory: 357920kb

input:

1000 1000 300000
UURLRRURLLULLLURDLURUDDRDLDRLRURDRRURDUDDDDDLLLUDLRDDRDRUUDURUDDRRULDULDLDUUDDRLRRULUDLDLUUURDRLURUUULLUUDUUDLUDUUUDURULUUULLRDUDDULLLURLURURLUULRLUULRUDRURLDLLDDURLLRULLDUURUUDDDULLUURUURDUDDLLUURRLULDLUDDDUDLRDRRLRUUUDUURDURUDLDRLULUUULRDLLDDRRDDRRURULLURDUDUDDURLRUDDRLLRLURLUDRUL...

output:

995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090
995090...

result:

ok 300000 numbers

Test #28:

score: 0
Accepted
time: 371ms
memory: 357532kb

input:

1000 1000 300000
RDURUDLRURLLLDDLDRULRRDRRLLDLDLLRRDDDDRRULULDDLRRLULUURLDRRDDUUURLUUULRDRRLRLUUDULRDRRDURDRURLRLLRUULDULUURLDDURUDRLDURDUULLDRURRDRLRRULUULLLLLRLLDRLULDDLLDDLRUDDDRDDDUUUULLLRULRLLDDDLRDURLLUURLLULLLLULRLRLRLLDRDDLDRRURRLUDDLDLLLDURRURDRRRLDDLLULLRLLUUURDLUUDRULRRUURDLUDDUDDDDULRDLD...

output:

995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
0
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
9951...

result:

ok 300000 numbers

Test #29:

score: 0
Accepted
time: 416ms
memory: 356508kb

input:

1000 1000 300000
UUDLRRDLLLDLRULRRLLDUUUDLRRDDLLURRLRLDRDDLDURLUDULRURDLULLLRDLRRURRLUURRLRRURRLRUUDDDLLLRDUDRURLLLUDDLDLRDLDDDLLDLDRDDRRLRRULRLRLUDRLRDRRRLULLRLLLURLDDRLDLRLLRRRDDLRRULRUULULUDUDDLDURURLDLLRDULDRLUURUDDDRUULLLULULLRRDUDLDULLLDLLLRURRDRLRUURRLULLRLLLLLLUDRURUUDLRDLULURDUDRLURLDLDURDR...

output:

995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052
995052...

result:

ok 300000 numbers

Test #30:

score: 0
Accepted
time: 388ms
memory: 356652kb

input:

1000 1000 300000
DULDUDLLURDURLURDUDULRDUULLLRUDDLRUUDLDLDULLLRDRRDLURRRDDDDLDLRRDLLULRDULRULLRRRDRRRLLLURLRRDUDDRUUULLLRLUUUUDDLLDULLLRRDLDRUDUDLLULRLRLDURRRRDLLLRDUDUDLDLLRDLLURDLUURLDULDDDDLDDLLRLLUDRRUURUDDRDDURUDLURLLULLULLRUDLUDULLUUULUDLUUDLUDUDLDRUULULUULLLULDUDDRDUDDLLRUUURLRUDDDLDURULLDUDU...

output:

995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
995073
0
995073
995073
9950...

result:

ok 300000 numbers

Test #31:

score: 0
Accepted
time: 420ms
memory: 350532kb

input:

1000 1000 300000
DUURUDLUULUULUUDLLULRLLDRRUULRLRLDUURLUUDRDUDLULRUDRULURLUUUDUURDDDLRURURLURUDURLLUULLURUDLRDLLUDRUDLRLDRLDRRDDUDURUUDRDULRULRRULLDLLDDDRULLRLLRLDRLDLRDRURDDUDLUURLLLRRLDDUUDRLRDRULDULLDUDLDUDLLRULURRLLDDLRDRDULULURDUURLDURUDUDLULUDRDUURDULLRRDUDDDLDDLDUUDUULDUURUDRRLLRLDRLURUUURURU...

output:

995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182
995182...

result:

ok 300000 numbers

Test #32:

score: 0
Accepted
time: 397ms
memory: 354344kb

input:

1000 1000 300000
LUURUDLULLRLDURUUDLLLULRLULUULDDDRUDRULDLDLRRLULDRDRURDRRLUDDDRURDLLRDLUDDDLRURDLUDURRDRDLURRDUULLLRULRDLRRLDULRDDDUDDDRURDUUDLRDURLLRRURRLULDRLURLUUDDDDULRLDDLRDRLUDULRDDUDULLLDLDLLLLLRLUUURRLRDDUDUURDURDLLURLURURDLURLRDLLLDRDDLDDRULDRUULDRRUDUUDLDURDURLDUDDURLRLUDRRLDLRLULLDDDRDLL...

output:

995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232
995232...

result:

ok 300000 numbers

Test #33:

score: 0
Accepted
time: 374ms
memory: 355456kb

input:

1000 1000 300000
RRURLLDDUULDULLRLRRRDRLUUUUDDLULDUDDDRDLURDDLDLLUDRRRLUDRDRRDUDUUDRDUUDRULUUUDLUURLLRDDULDLRLDUDDURLRLRULRDUDLDDDRRULDLRLDDUUUDLRLRDDLLRDURRRLLLDDUDRUUDLDLLUUUURLURDLUUUUUUURLULLURLDDULRLRDUUURRLRDLRDDRRUUUUDDURDLULLDURLDLLLRLRUDDDRRUDLDUDDRDDRLUUULRRDUDDDDLRUURRLURRRULRDDRRLRUDRDUR...

output:

995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995164
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995163
995164
995163
995163
995163...

result:

ok 300000 numbers

Test #34:

score: 0
Accepted
time: 384ms
memory: 355380kb

input:

1000 1000 300000
DUURRDDDDRLLDDLDDRRDLRLURLDURLDLLRURDUUURULDLLLRDUDDUUDRRURLDLDLDLRDDRLLLDUUDLRDUURDLRDDDRLLDULDDRDUUDUURLUDULLLLLDRLUDDUULDLRDDRRDDLUULRDRUDRDDRDUUUURDDLLLLULLULLDDUUDRUUUURLLULDRLLDUDLDLUURLDLLLRRLDLLULLDRRRUDLRULRDLUDULRDUDDUURUDRURRRRDRLDRUDLLRURURDLURDRLUULLDRLURURDRLDDLRLURRUU...

output:

995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212...

result:

ok 300000 numbers

Test #35:

score: 0
Accepted
time: 395ms
memory: 354820kb

input:

1000 1000 300000
DRUUURRDRLLDULRUURRRRDUDUULUUDRUDLLDLDDURDDLULRLRLURUDULDLDRLRDUDRLLRRURDDURURLRUURLRLRUUDDDULRLDULRULDRLDLDRULRRLRUDDLRULLULLRULDULDURUUDUUDUULULLUDULURRLULDRDUDLUUURRLLLURUUUULUDLDRUDUUDLDURRLLUDUDUURDRURDRDRURUUDLRDRLRULDLLLLULLRRURRUDRRRLRUDRLUURLURDLULDULDDDRUDDRULDDDDULRDRRRDU...

output:

995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
0
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
995200
9952...

result:

ok 300000 numbers

Test #36:

score: 0
Accepted
time: 386ms
memory: 357688kb

input:

1000 1000 300000
LRLLLLLDRRDRLRDDLLULRUDUUDURRDDLDURRUULLUULUDDUDRDLUDDRDLRLLLUDRURLRLUDLLRRDRUDUURRDUURUDRLRUUUULLLURURUDUDUURRRRULURUDURLDRDDDUULUURRDDLLRLLLDDLRLDUUUUURRRULDRLRDDULDURDDRRDUDDLUUDRUULURRDLULLRURULLDURULURDURRDUDRRLDDLURURDRDUDLDDDUDLURUDLULRRUULRULDDLURDLRLDLLRRLLLDRLRLRUDUDRURRRL...

output:

995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
0
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
995192
9951...

result:

ok 300000 numbers

Test #37:

score: 0
Accepted
time: 436ms
memory: 349800kb

input:

1000 1000 300000
DRDRLDLLLURUDLDLDRDUURDUULUDRLURDUDDRLLDDRRRUULLURURULDUUUDDLRDLLLUDLDULDURURDLDLRLLDDULRDLLUUDRUDLULULDDULURUDRDRLLURRUULULURDLRUUDLULULLRDUUUURRLDDUULRDULRDULURRRLRDLLDRLUUDRDULULRUDURUULLDDURLLRDUDUUUDRLRLRLRUDDULLLRURLDRULRULUUDDDDDURRULRUDLRLLDLDDRRDUDRRUULULDDDDURLDULRLUUDLDDR...

output:

995169
995169
995169
995169
995169
995169
995169
995169
0
995169
995169
995169
995169
995169
995169
995169
995169
995169
0
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
995169
99...

result:

ok 300000 numbers

Test #38:

score: 0
Accepted
time: 392ms
memory: 353672kb

input:

1000 1000 300000
LDDDUDLRLUUUULRDLRDRRRLLRRUDLUULURUULRRDDDLULDUURDRLDRRRULURRDDDLLDDDLRLDLLLULRRLURDDRDLUDDRLLRDRULUDDDRLDDDDLUDDRRDURULLRURRULRUUULLURDUDLDDUULDLUUDUUURLDDRRDDUUUURRDUUDLRDRDUDLDLLUDDRDDRLUDLLRUUDLDRDLDURLRURRLLDDLLRRUULLUUURDDLDDRUDLUUUUDRUDDLDURDRDDDRURRULLRURRDUDURLRDLRRLUULRRLU...

output:

995162
995162
995162
995162
995162
995162
995162
995162
995162
0
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
995162
9951...

result:

ok 300000 numbers

Test #39:

score: 0
Accepted
time: 413ms
memory: 358504kb

input:

1000 1000 300000
UDRRLDDRLULDRLLLRUURLDRUDLLRUURRLRLDUDRLRUDUDURUUUDDRLDULLDRDURLUDUDLULLRLDRLDURRRDUDLURRUULULLURRUULLUDUUDRDDRULLRDRDURDRRDLURRRLUURULRUDUUDDDULRLDURDDDLDUDLRRRLDLUURURUULRUUURDDULDDUDRULRRURRLLRLLLRDLUDLULUDURRDLUURLDLLRDLRUDRRDRURRRDLLUUDLUDLLLRLLRLLRLLRURURLDRLULUDDDRDRRULLRLDDR...

output:

995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087
995087...

result:

ok 300000 numbers

Test #40:

score: 0
Accepted
time: 400ms
memory: 355432kb

input:

1000 1000 300000
DRURLURUDURDUDUDULDUUDULUDRLDDRULULUDUUUUDUULLDRLRURLDDRUDLDLUULDULURUULUDURLURRLDLUDLUDRRULRLRLDUUDRRRULDDRDLRLRLDRDUUDDLRRRDLLRRULULLDUDRDDLRDLRURLLLUDLDDRLLDURLLDRDDRRLRRRRLDRUDDDRURDLUUURLUDRLDULLUULDUDUULUDDRUURDDRRUUULDUDULDLLULURDDURDLRLDRLLULUDUDRULLUDRRDLDUUDLUDURUULLDDLLRL...

output:

995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085
995085...

result:

ok 300000 numbers

Test #41:

score: 0
Accepted
time: 401ms
memory: 355820kb

input:

1000 1000 300000
ULULLRLRRDUDLRRUDLRDRUUUDUDRLLRLLUDUDULLDULRUUDLRLRDDRLRDRLLLULUDRRRLDRUDLLLRUDLLULRUURRRDDLLLLUDLDRRRUURDLURDDLRDDULLLDLDLUUULRDDLRLRRLULULDULRLDUDLRULUDDLDULDDLDLDDDRDDLLDUDDDRRRLDDDRDLLDDURLRDLURDRLDULDDRURRULDUULDDULRDRUUURRURRUDRLUUUUDRDLRDULRDDDLRLDRLUDLULLURULLLDDUUDLURURURRR...

output:

995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
995101
0
995101
995101
995101
995101
995101
995101
995101
995101
995101
9951...

result:

ok 300000 numbers

Test #42:

score: 0
Accepted
time: 379ms
memory: 352892kb

input:

1000 1000 300000
URDDUULLDLRLRLLRRULDURULLDRRUDDLURUULDURDUDDLLURRUULLRDLRDULLLDRLURURLRULRLUDRRRDDUDDURLLLRRRDLRLUUDRDULRRULLDDDULLURDDRRDURDUDLDLRDLURDDURDURUDDDLLDURURRRRLULRURUURUURDLDRLDDLRRLRUDURDDDUDDLULDRRDULDDLDULLLULRLURLRRUDDDULRULLDRRRLDLURRLUULDUUDRLLRLURRURLLUDRUULULURDRRUULDLUDLRDURLD...

output:

995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004
995004...

result:

ok 300000 numbers

Test #43:

score: 0
Accepted
time: 375ms
memory: 352844kb

input:

1000 1000 300000
RURLLDRUURDLLLUDRDDUDDURLULDRURLRLULRRURURUULDDRRDDDRLRDRULLLRLDRUDUDLDULUDDLRULLDUDLDRRRDRUURDLLLLDUDULLRRLLURUDLLRLLLRUDDURDLUURULUUUDUDDRRURRLLLLRUDLLUURURRLDDRULDDDURLUUDLUDDRUULRLRLDRLLLUDDURULDDRLLRULDURDRDLLUUURLLRDRLURURRURUDUDULDDDURRLUULULUDRULDRDLLDDDDURRLRLUDDLRRULUDLURD...

output:

995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063
995063...

result:

ok 300000 numbers

Test #44:

score: 0
Accepted
time: 393ms
memory: 357340kb

input:

1000 1000 300000
UULDRDRDDUDLDLRDRDRLUULDLRRLDDDLDLDLDUDUULUULRDURUDRDRUULLRLLDDUUDLLULLLUULRUDRUDDDURLDDULUDDRLRUULRRRDUULRULURURURLRDDLDLRRRURULRURUDDLURDDDUUDDRLUULRUUULLUUDRUDRLLRLRRLRRLRLRDRDUURURLUDULRULRLRLRDRULUULLDRLDUURDUURULDDRRRLRLLLULDLLLRLLLUUDDDLLURLLRRLUDRLULDLULLDDDDRRRRDRDRDULURRLL...

output:

995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199
995199...

result:

ok 300000 numbers

Test #45:

score: 0
Accepted
time: 396ms
memory: 359004kb

input:

1000 1000 300000
ULURULLLRULDULDLRDLRRLLDULRLDDURRURRLLUDRUDLDULUDDLLRDDDURULUDULDRRLRLDDLLRRLLRDRURURUUULDRDUDDDURLLRULLULLUDLLRLUULULRDDUURLLLDLDLLDRULDRUDUULRDLDRULDDURRLULLUUDUDDURLLLLRUDRDLLLUULLDDRLDLDDDLLDLDURRLRDUURLULDULRDRUDRUULURRDUURLULDUULDURDRDRRRURRRURUURUDLLULUDRUUULLDRDUULLLLUUDDURD...

output:

994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
0
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
994992
9949...

result:

ok 300000 numbers

Test #46:

score: 0
Accepted
time: 400ms
memory: 351872kb

input:

1000 1000 300000
LUULULRLLRURUDDLURURDLDRLRULRRDRDDRLLURLULDDLDULDRURUUUULDDLLDLULRUDLLLLLUDURLLUUDURLDDRULUDLRUURLRURDDLUURDLDDDRLUDLDLRLRURUULUDURDDUURDDLRUULLDDDULLLUURLLRDDUUDDURURULLRURULDRDRDLDDRRRDUUDRDLLRLRDLDRRDLDLDUDURDRUDLLDUDRLRUDLDLLDUULUDUDUDRRRURDLURRLURDUDULUDLRUDRRULDLLRDLDUDLRRLRLL...

output:

995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224
995224...

result:

ok 300000 numbers

Test #47:

score: 0
Accepted
time: 417ms
memory: 354604kb

input:

1000 1000 300000
LRLRRUUURLLUULDUUURLRULUUDDUDLRDDRDULDLRLLLRUDDUDRLRDDULDRRLLUUUULRLDLDUUDDLUUUDRULLRURDRLDRURDRUDRDULRULDLURDDLLLRUDRDDRDUDULLUDLUURURRUUDRURURURLUDDLULRRDDDRLURLLLUDULLRDRRLRLDLDUURDULLDURDRDDDDLDLRDLLDURDUULDDUDDDRUUULLULUUDLUUURLLULDRDDRRDURLULLDRRLRDURUUDDRLDLURDDLDRDLULUDDUUDR...

output:

995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212
995212...

result:

ok 300000 numbers

Test #48:

score: 0
Accepted
time: 404ms
memory: 349504kb

input:

1000 1000 300000
UULLRRDRRURDULUUUUDUULLLDRDLLLDDLLURULDDRRDDURLRRLUDURLURDUUDUDRRLUULRDLLLLLLRUURRDURULDUURUUDUDRLLLRULDUDDRURRDDDLRLRUUURDRRDDDLRDRLLLDLLLURRLURULRUUULLLDRDDRDURULULRLLURDRRLULRDLRRLUUUUDULUULRRULLLRLURULLUDLLDUURLDLULDDURLURRRDLLRDRRRDURDULRDLRDRULURUUDDLRDLURRURULLULRDLLRUUUDUURR...

output:

995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995128
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127...

result:

ok 300000 numbers

Test #49:

score: 0
Accepted
time: 384ms
memory: 358484kb

input:

1000 1000 300000
LDRUDDRUUDRRUUDURRDUUURURURDULRUURRDUUDLLRUURDRUULURRLUULULDLLUULDDDDLUDLUDDLRUULRUUULURDDRRLRRRRLUURUURLLUURLLDULRDDURRUDULULLRRLUULDUURUUUULURRDRURDULLUDLDRRRRRUDURULDLRLLULRDRRUULURRRDUUULLLLUUULLDLDDDDDRRRLDRRDUUDRLRURDUULRLLLRULLRRLURDLDUDURRUULULDURLUURLDURLLUDRDRULLLDLLRRDDUU...

output:

994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962
994962...

result:

ok 300000 numbers

Test #50:

score: 0
Accepted
time: 408ms
memory: 352860kb

input:

1000 1000 300000
DDDLLDRURLULDURRDLULLDRLDLLLURURUDLRDDUDUDRUDDRDRLRURULLLDURRLRULDDLLURURUDLDULDUDUDRLURRRUDLURULDRDUULLRULRRURULULDLDLDURUDDDULLLDRDLRUURDUDUDURRULDLRULRUURDUULULRRDRUUDRLRRRLRDRRULRLRRRLLULDDDLURURLDDLLURDUULRDDULRURDDLLRDUDLULRURLUDLUUDRUDDRLLDRRRLULDULRUDRUULLRUDURLDLLLRRURRURRU...

output:

995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
0
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
995110
9951...

result:

ok 300000 numbers

Test #51:

score: 0
Accepted
time: 396ms
memory: 353784kb

input:

1000 1000 300000
RUULUULLRUDRDUULDLURLLRLUURDURDLLURUULLLRUULDUDUURRLDULRRDDRDUURDLULRURLLLDDLDRUUDUULLLULDDLUUUUDLUDLDDLDRDDLLRLRRDRDLLUDDLRRLDDDUULDDLDUDLDURRDLLULDRUDRURUURUURRLLRRDLUDRDRLLULDULLULRRURLDDRRRDURDRURLDUURUUDULDDDULRRRLUDDDURDRDUULULLUULDULRLLLUUUDDLLUUDLLDLLLLURUDLUDDLLRUUDDRRURDRL...

output:

995149
995149
995149
995149
0
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995149
995150
995149
995149
995149
995149
9951...

result:

ok 300000 numbers

Test #52:

score: 0
Accepted
time: 376ms
memory: 348724kb

input:

1000 1000 300000
LDURURRLDLURDLLDDURDDLLUDUDULDRDUDUDRRUURRLULRRLUURRRRRUURDLRDRDLLUDLUDLRURRDDDDRURDLRRRURLRRLULURURUUDULDLUDDDLLULURRLRLLRLRDULLRRRUDDRDRLDLRRDLUURDLULDDURLRUULLRUUDLRDLRURRUDURULLUULLLLLLUDDUUUDRLLLRDRRLLDUURDUDRDDULUDLRRRLRUDLRDLRRLRLLULDRRRDURRDUDDRDDRDRRUUUULDURDUUURLURRLLRDRRR...

output:

995206
995206
995206
995206
995206
995207
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995207
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206
995206...

result:

ok 300000 numbers

Test #53:

score: 0
Accepted
time: 399ms
memory: 355224kb

input:

1000 1000 300000
DLRLULDDDDURUUULURLDRUULULUUUDRLLRLULURRLULRURDRDDRUDLUURDULRUDDDURLDDRURUULURLRURRRLDDUDRUDDURURRDULDUDDUUUDURDRLDUURRRUDDUUURLLLLRLURRRULRRLUDRRLDRULLRDUULLDRRRDRRDLRLLLDRRLULULULUDRLRUUDDDDDDDDDRULURDDDLUDLLDDDURRRLRRLRDRULDLLRRULDRDDLLURLRRLDRLDLUUUDRURUUURLLLLUULDLRLLLURLDURUUR...

output:

995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211
995211...

result:

ok 300000 numbers

Test #54:

score: 0
Accepted
time: 391ms
memory: 356564kb

input:

1000 1000 300000
LLDDLRUDULDUDDRURRRULDRRUUDDRRDDRRUUUDDDRUUDLLLUURDURLLLDLLDLUULLURRUUDDRDLDDDLDRDRLDRRDULRRRUURLUDLRUULDURLDRRLLRUUUUDLDUDURLDDLDRDRUDULRRLRLUUUDDLRLLDRLLUUULRRRULRRLLULLUUDUDDDDDRUDURLULRURDRLDRLDDDRRRUDRULRURUURRURRDDRLULLLLULUUUURLRRUDLRDLDDLUUDRDULDUDLUUULUUURRDRRUURUUUUDDDLULU...

output:

995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166
995166...

result:

ok 300000 numbers

Test #55:

score: 0
Accepted
time: 407ms
memory: 361336kb

input:

1000 1000 300000
DLULRURURUDRLDRRRLRLLLDRDUDLDULDRUDDRDDLDDDDDLRDUDRLDDULRLULRRLRRUDLDURULRDUUDRDLRLUDRUUDRDDDRLUDRRDRUDRRRUUUULURRLUDDUUDLRLURDDUUDULUULRLRRLLUURRLRDRDDLDLRDDURDURRUDUULRUURRUUDDDLLDRDURRLDDRRLDLRUDDLDRLRUDRLDULDLLDLUULLDDLLLRLLDRUDDLLUDLDRUUUUUURUDDURLRLLDULLLLUDRRUDUDLLLURDRDDLDLU...

output:

995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127
995127...

result:

ok 300000 numbers

Test #56:

score: 0
Accepted
time: 412ms
memory: 332932kb

input:

1000 1000 300000
DDRULLDULLUURRULRRRDLLDRDUDDDUUULRUUDLDUDLRRURRDDLULLDUDDDLDULDLULDURLDRLRDLRURLLDDRRRDDURULLUDRURUDLRDDLDDUUDURULURRRLDLDRDRDULDDDRDRULLURUURLLLDLRRRUDUULDDDDRDUUULDRRDDLRDRDLUURRLDRRDRDRDUUDLLUDUDRRRDURLRDDDDDUDRURDDUDURRLDUUDRLRRRDLDLRULRUDLRLLLDDLLURLRULLUDLLDDRDUDRRURLURRDLDLRR...

output:

0
417921
273585
498479
0
417921
417921
0
273585
0
0
0
417921
0
0
417921
0
498479
0
273585
0
0
0
417921
417921
498480
0
273585
0
0
0
0
577131
0
417921
0
417921
0
498479
417921
417921
0
0
417921
0
417921
224894
0
224894
273585
0
417921
0
0
0
417921
273585
417921
267682
0
0
498479
577131
267682
0
0
417...

result:

ok 300000 numbers

Test #57:

score: 0
Accepted
time: 417ms
memory: 334208kb

input:

1000 1000 300000
DDLRLULLULRRLUUULRLLRDDLDRDUDDDURULRDDUULDLDRRDLRDRLRRLUURRUDUDRLLULLLDRULLLDLDDDDUULURLDRULRDLLRLURRLRUDRRLUDLDULRUUULDURLRDLRDULURRRDLLDDRLLDULLLRLUUDLLRLDDUULLRDDUDDRLDDRLUURDDURLUDLDLLULLLDDUUULLRLDDLRRLDDUDUUDLRRRRLLDLDURUUDUDRLRLULULURDULRUULDDDDLRLRLRRURLRURRLLURUULLRLLLRURRL...

output:

0
0
892790
558339
558339
0
0
558339
558339
334451
579191
0
0
0
334451
558339
0
558339
974359
558339
558339
0
892790
0
558339
334451
0
334451
558339
0
558339
558339
0
558339
334451
0
0
892790
0
0
974359
334451
558339
334451
558339
558339
892790
558339
892790
558339
0
558339
0
334451
334451
0
558339
8...

result:

ok 300000 numbers

Test #58:

score: 0
Accepted
time: 415ms
memory: 337884kb

input:

1000 1000 300000
DUDLUULDLDULUDLRUDRDLUUUUDDLULLUULRUUULRUUDDDURDDDULRUDUDRUUUULUURUDDURRDDDDDUDLLURRLRURUUDUDLDUUDRRLUULUULLDRDUDDRDDRDRUDUURLLRDRULUDRDRLDUUULRUUUUDLDRRLLRLLULRULRRLLLDUDLLULDUUURUDLLRUDRDDDDLRULLURRLRLLURLRLRUURLLDRDURLLDUULDLDUULLLLDRULLURDDRLUDULUDURDUUDLLUDLRUULUUURDDRDLUUUDRUU...

output:

0
545320
545320
0
545320
545320
545320
0
545320
0
0
0
0
545320
545320
0
545320
0
0
545320
0
0
545320
0
0
0
0
545320
545320
0
0
545320
0
0
0
0
545320
0
0
0
265766
545320
0
545320
0
0
545320
545320
0
0
545320
545320
545320
265766
545320
0
0
435959
545320
265766
545320
0
545320
545320
0
0
545320
0
0
0
...

result:

ok 300000 numbers

Test #59:

score: 0
Accepted
time: 377ms
memory: 356388kb

input:

1000 1000 300000
RUDULDDULLRRURRDUUDDRDDURDLLLDLLLDLDRRURDULDDURLDURLLURUDURLUUUDURDRDDDLDRRLDLDLDDRDUUUDRUULULUUDRDLDLDUDDLLDDURRULDRUDLURLUULLLDDDRDUDRUURURLULULRUUDURLLDRDLRUULDDRULDULLURRLLDRRRULULRRRLDURDUDDURLRUULULLLDUDLDRLLRDRULDULURDUUDDDRRURDLRRURLUUULDRULLDUDDLRRRDLUURRURULURDDLLRDLLLUDRR...

output:

995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995146
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145
995145...

result:

ok 300000 numbers

Test #60:

score: 0
Accepted
time: 404ms
memory: 353636kb

input:

1000 1000 300000
LDRURURLLDLLLDURLDDRRLDDDRLLLDRULLDDULRUDRLUULRRUDRULDDRLRUDURLLUDDRRUURURRURRDUDDURDRRUDDRLRUURLRDDLDDRRDRURRRULUURDDRDDRUUURDLULDDDRUDRUDDDRULRRLRDRRDLUDDRLRULDRRRUDLDRRDULURLDDDDULRUUUDRLLDLRDDUURLUULRDDRDDUDLUDDDURLULRUDUULRRLUDDLURRDUUDRLLLUDULLRDDLLLULRRURURRUULRDLLLLDRUDDDRLU...

output:

995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198...

result:

ok 300000 numbers

Test #61:

score: 0
Accepted
time: 431ms
memory: 357220kb

input:

1000 1000 300000
RUULRRUULRRLULLDDDDRURDDDRLDUDRURURRDLUDUDDRLURUDUDRDUUDDRUUDLDURRUDUURURUULDRUDUDUDURLLRLRRRUDUUUURLDURDDLDRURLRLRRDUDURDRDUUURRUDLDDURUUURDULDRDDURDLUUULUDDLDULLRLDULLRDRRLUUURURDDDUDDRRUULRDLLLDDDDRRLULRUUDUDLURLDRRUUDRRUDRUURULUULULDURDLRURDDDURRLRDDUUULRUDDDRLDLLLULLRURDURDURLL...

output:

995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017
995017...

result:

ok 300000 numbers

Test #62:

score: 0
Accepted
time: 428ms
memory: 354524kb

input:

1000 1000 300000
DDDRLULLLDRRUULLRRDDDRRDRUUDRULLUUULDLDRDLLUDDLRLLRRRLDLUURURUURDURRDDUUUDDLUDUDURRDLUUURULLRULURDRDDURLLLLUULUUDRLLRRUDLLULRDUULLLLRLRRDRRDULUURDLRLLDRLRRLRUDLUUDLRDDRLRDDDRDRDDDDUUDRLLDDDLLRRRLDRUDDULRLDLLRDULLRULULLDRLUDUDDDDLUDLLRURULRLRDDUDLDLUURDLDDRRRLRURDDRULRLDLUUULUDURDLDL...

output:

995238
995238
995239
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238
995238...

result:

ok 300000 numbers

Test #63:

score: 0
Accepted
time: 397ms
memory: 357368kb

input:

1000 1000 300000
URLDDUURURDLLUUUDULLRURLDLLDLDUULRRRRLLLRUDDDRLLDDRDUDDULULDURRRLLDRUUURLDDDLLDLRLUDDUDUUDLUDDDRLLDLRULLLDRRLDRDRRRLRULULDDLLDULDURURDDLURRULULUUDRDLDDDUDUUDDLLRUUDURRLDUURDRUURLULLULDLLRLLDRRLRRLRDLDLRLRDRRUULRLLDUULLRLULRULUUULLDRUDLRDULRRDLUURLRRRRURDRUDDDLURRRDULLRRDULLDULDRDLRU...

output:

995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147
995147...

result:

ok 300000 numbers

Test #64:

score: 0
Accepted
time: 417ms
memory: 353032kb

input:

1000 1000 300000
LUDDLUUDRUDDRUUDDRDDRLRUUDLDRRUDRDRULULRLRDUURLRULRUDUUDULLDLLDDUDULLDUDLRLUULLRRDDUDDDDLRLUDDLLRRDRULDLRLDLURLRRLULULLRUDDUULURDRUDDDLDURRDLRRRRUDLLDURDDLLDDLRULDUDDUDDRDDRDRLLLULULLLULURRLLDDULLRULDDULDDURDRRDURRRRLURLLDULRUDUDDLULRRDDRRDUUDDLUULRRRLDLLLRRDURDUDDLDULRLLRUDRRLDRUUR...

output:

995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250
995250...

result:

ok 300000 numbers

Test #65:

score: 0
Accepted
time: 390ms
memory: 356908kb

input:

1000 1000 300000
DUUURRLUDLRULURRRDRLUUULRDUDDLLUULUDULDRDRULRLULRLUUDRRURLUDRLULRRLUUULLDDRDRULDDRLURLLLURRURUULRRDRRDLUDURRLLLULDRRDUDURDLDUULDUURLUULULDLLDDUURUDLDRDLLLDURDRRULLLLULDDRLRULLDLURDDLRURDURLDDUURRDURLLUDLLDLLUDRLLURUURDLDDRRDLDRLULLDRLRDLLRRUDRDLRRRLDRLRLRLLDDRDURLRUUUDURRULULURURDUU...

output:

995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995137
995136
0
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
995136
9951...

result:

ok 300000 numbers

Test #66:

score: 0
Accepted
time: 386ms
memory: 349140kb

input:

1000 1000 300000
URULRLDUDUURRLDLUDUDLRULLUUDDLURRUUDUUURLDLLLRDUUUURRDULLLDURDRDRLDRULDRLRLLRURUURLRDDRDULLUDLDURDDDLDRDRDLDLUURRULLDULUUUDLDLUDDLLULLUURDUURDRDDUULLLDRLUULRUUDRDDRDRUDDLRRUULUURUDDDULLULRUDRUULRURULLLLUUDULDLLDRULLLLRDUURUDULDULUDURUDULRRLLUDUULLUDLULDDDDRDULDRDRLLURRLUDURLUDLDRDDR...

output:

995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107
995107...

result:

ok 300000 numbers

Test #67:

score: 0
Accepted
time: 381ms
memory: 357116kb

input:

1000 1000 300000
URDRLLLDRUDLDLURRLRRRLRULRRUDDUUDLLRDLDULUDDLLLLULLULLDLUUUDRUULDLDLDURRURRUUDRRULUURLLLLLDRULRDDDLUDULDULLDLRLDLULLURLLLRDUUDDUDUUURRDUUDRDUDURRUDUDLDDRRDUDDURLURLURDDRUUDLUULRLLDDLURRURRURDDRLDDLDLLULDRRRRRDUDRLLUUULUURLDLLUDDRLRLDDUUDLDLRDLLLDULUDDRURLDDLDRRUDDRLLRDRDRDRRDRUUULUR...

output:

995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203
995203...

result:

ok 300000 numbers

Test #68:

score: 0
Accepted
time: 379ms
memory: 353340kb

input:

1000 1000 300000
RDDLLUDULDDRRUUURLDRULRDDLLRRLLRLDRLLRULRRULUUDRUULUULUUDLRLLRURLURULRLRDDDRURDDLRRLDRUDDDRRLRLLULDLRDLLULLLDUDULURRUDURLURURLDLULDURRDULURDUDLRLURRDRDDDLULLRRRRRULRRURURDURUULLDRRUULUULDDDRDULRRLRLDUUUURUURURURRDDULURLLRURRDUUUDDRRLDUDUDLLUDLRRRDLLDRDUDULUULDULLLUUURRDURLDDDRDLDUDU...

output:

995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
0
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
995198
9951...

result:

ok 300000 numbers

Test #69:

score: 0
Accepted
time: 383ms
memory: 355088kb

input:

1000 1000 300000
UDRRRRULRLRUDLUURRDRULDDRRDRDRLURDLDLLDULLLULULLLULURLLURLLRUUUDLLUDURLDRDUDRLUURRRDLDRLDLLLDRDRURLLRUDRRRLLRURDDRUDLUDDURDLLDRDUDULLUDRRUDLLRLRLURLURRDLULUURURUDRDRULLLDULUUDUUDDRULDDRLLLRDLRRLRLULUUULRDURRLUDRLLRLDUDDRRDLRRLRLUDLRRDUUDRDRDURURRUUULUDLDULDRDDLURDLUUUDULLDLDULLDRDLD...

output:

995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084
995084...

result:

ok 300000 numbers

Test #70:

score: 0
Accepted
time: 405ms
memory: 355032kb

input:

1000 1000 300000
LRLRRUULUDULRDLDLRUUDDULDDULLLRRRDLDRLDLURLUUULDLLDLDRULULDRUUDDDURLRRULRDLDULUDUDDUURUUDLUDDDUULULRDDRRRLLLRULRDRRLDLDLUDDUUULLRDRRRDDRRDRRRDDLDRUDDDLRRRDLLLRRDDUDDURUDURDDRDDDDUDRLLDRRRDULUULRURUUDRRLUURDLRUDRRLURDDDULUUUURRLDRLLURLUDRLDLDLUDRUUDLUUDLRULUDRULUDLDUDRDRLULUURRDLURUR...

output:

995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118
995118...

result:

ok 300000 numbers

Test #71:

score: 0
Accepted
time: 394ms
memory: 355252kb

input:

1000 1000 300000
UDDLDULRRLULRLRRRUDRDRRLDULRDURRRRRDRULURLURLLDLDRDDRDRRURRDRULUURRURULLLRRUDDRRLLURLDDRRLUDLRDULLUULDDRUULLURLRUULRRLDDULLDUDDDUUULURLLDUDRDLLLLDRLURURLDDLRLDULLRUUDLULURRULRULRUULDDULRDLDRRUDLLUULLRURRDRRRDUULLURDULLRRLDDULRULLLLULULURDLURLUUULLRLRLRRDRDULUULLURURRLLLDRDLRLUUDRDDR...

output:

995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178
995178...

result:

ok 300000 numbers

Test #72:

score: 0
Accepted
time: 420ms
memory: 360784kb

input:

1000 1000 300000
RURURUUDLLDURRLLURRRRURRRDDLDLRDLRURRLDDDRUDRLURRULULDDDRRDLRDDDRDDLULRULURUURRRURURDLLDRUDDLUDDDLRRLRRLLRLDDLURDDLRRRLDDULDLLRLDLRDLDRDDDDLLDURRUDLDLUUUDLRDDLLRLLRDURRURDLRUULDUURUDURRRRURRURLRDDDUUDRDURRLURLDDUUDUDLDRDLDDDRUULLULRURLRRULLRDDDDRRDDRUUUULLDDUDUULULLDDRUULUDDDRUURURD...

output:

994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994978
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976
994976...

result:

ok 300000 numbers

Test #73:

score: 0
Accepted
time: 416ms
memory: 331248kb

input:

1000 1000 300000
LDRRDLRDDLRUDULUDRULRUDRUURDURURDULDLLRDRULUUDLRRUDDDLUUDLDRUDUUUUDRULLULRUDRULLDRLLDLLLRULDLRLRUDULUDULRDRDLRRDDRULRLLDUDDURRUDRURUUULLDLURDRUDUULUURLUULUULULDRLUDRRULULRLLLRLLLRRRUULLRRUDRDDRULLRUDULRDRDDUULLDLLLLUUUDULURRDRLLDLLLLUDRULDDDDULDDRDLRLURULLULLLDULDUUDRLUDRRRUUURLLDDR...

output:

0
658918
148289
329421
0
329421
279692
0
0
314475
0
83633
0
0
0
680784
0
680784
0
329421
574279
0
609113
0
329421
0
0
680784
0
0
0
96569
0
0
680784
329421
0
793191
0
695706
0
0
0
0
0
0
0
695706
562349
562349
0
338435
0
574279
876824
329421
574279
425990
0
0
329421
0
0
0
0
148289
574279
0
108499
0
54...

result:

ok 300000 numbers

Test #74:

score: 0
Accepted
time: 392ms
memory: 328968kb

input:

1000 1000 300000
RLLRLUUDDLUUUDDRUDDULLLLDLUDUUUDDULLDUDLRDULURULUDRRRLRLURURUDLUULLDLLLUDLLLRRRULDDLDRDDRRURDLDLURLLUUULLLLRUUDRULDDLRULLDLDLLDLLRDDDRDRULURUULURRURDDURLUDURLLUUUDUURLRUULLLDURRRLLLUDRLRRDRDDLLRUDDLLUDDDDLRULDDRLDLULDRDUDDRRRRDUDUDDLUURUURULLURUUDRLDUDRDRDRDURLDRRDLRRDRLLUUUURDRUUDR...

output:

0
0
0
0
0
0
0
0
0
0
351389
0
0
0
0
238865
0
0
90550
0
0
0
368245
351389
0
112524
0
368245
203074
294665
0
0
0
0
0
0
294665
137397
0
0
0
0
0
256807
0
294665
0
0
112524
0
294665
294665
0
294665
0
294665
0
0
0
0
0
294665
0
294665
0
0
0
294665
0
0
0
0
294665
294665
0
0
351389
0
294665
191131
0
351389
0
...

result:

ok 300000 numbers

Test #75:

score: 0
Accepted
time: 403ms
memory: 325820kb

input:

1000 1000 300000
LRDUUULUDRLULLRRLUDLDDRULDLURLLUDDLLRDRLLRRRRRRUDRDRLDRDDRRRULURLLUUUDULDRLUDUUUURUDRDLLDRDDDLURDURDDUDLRUDDRDLDLRDULRRRRDLLDUDDLUDULUUULRRDRUDRURRRURRLURLUURDLDDRURLRDURDLDLULRLRUDULUUDDUUUUUUULUUDLDURRLLDURLUURRLDRRLUDDRRUDLDRLRDRLRRLURUUUDRRRLDURDLULLRURURDRUDURURRLDRDDDLRUDRLLUD...

output:

0
509533
0
0
0
0
332513
131411
0
0
201102
0
0
0
0
401188
187052
0
187052
509533
0
0
332513
0
0
0
0
0
0
509533
0
100495
0
112443
0
0
0
0
0
0
100495
332513
0
239756
0
0
0
267691
0
0
0
0
0
0
640944
308431
0
640944
0
0
0
201102
509533
0
0
0
0
187052
0
0
0
640944
0
267691
0
0
0
231906
0
0
0
380134
0
0
0
...

result:

ok 300000 numbers

Test #76:

score: 0
Accepted
time: 416ms
memory: 320672kb

input:

1000 1000 300000
RLLDDDDRLLDULLDUUDLLRRDRUURUULDRLLUUDULDLRDRRLURRDLDURULURURRDULRDDLUDDRUUULRDDRURDRLRDRRDLDLDLRRURRUDDDRDLLLDRDULLRLURRLUULLURDDDRDLULURLLLRRDUUDLUULRLRRDUURUDDDDURRUUDRLDRDUUUDRDRRUUDDLUDDUULRDDLLDLRDLDLRDURRULRLLDRRURDDDLLURLUUURLRLURLULRUURRDUDDLRDDUULLDUDLUDLLRRUUULLRDDDDUURLRU...

output:

0
0
562105
0
0
0
0
65708
379035
0
168194
0
379035
0
168151
0
0
0
148220
0
0
413885
0
0
148220
0
0
0
0
413885
94572
0
148220
0
0
117407
562105
329337
0
0
0
0
168151
0
0
0
562105
0
146267
0
0
0
0
0
168151
168151
0
0
0
0
0
0
148220
232768
0
0
183070
14919
0
148220
315528
324418
0
0
0
0
413885
0
0
0
0
3...

result:

ok 300000 numbers

Test #77:

score: 0
Accepted
time: 413ms
memory: 326512kb

input:

1000 1000 300000
ULDRRRUDUUDRRLRRRRURDDDUDDDRLDLUDLLLULUDRDRULDRLLUULUURLDLDLRDLULUDUUDUDDUDLDURLLRRLDURUUDDDRULRDLRLDDDDDDLRRURRLDRRLDLUDDDDRULDRLURUUDLRRRRULLRDDDLLLLUULLLLLDDDUURLRUDULLDRRLURDDLDRULUDDURDUURDURULRUUUDDDULRUDRDUDRRDRURURRDRULRRRUULLDLULDDDLLUULULLULDDUDLRURRLULDLDUURUDDDLRDUULRRDL...

output:

0
0
0
0
0
124424
0
268684
153254
0
0
0
153254
416927
0
0
0
0
268684
320419
0
153254
121376
0
268684
93519
0
0
0
148243
0
138366
0
0
0
416927
468662
0
0
0
0
0
352256
0
0
0
352256
0
268684
0
0
0
0
0
0
0
0
268684
0
0
0
0
0
0
124424
0
0
0
0
0
0
230880
416929
268684
0
0
0
0
0
0
117409
0
0
0
0
0
268684
15...

result:

ok 300000 numbers

Test #78:

score: 0
Accepted
time: 417ms
memory: 328840kb

input:

1000 1000 300000
DRLRRRRRLURRRLRLRULULUUUDUURDRUUULDURURURRURULRUDDDLLDRDLURLDLLDRLDDRDRLRURURULUURRUULRLDULUDDULRULULDLLRURURDURLLLDLURLDDDULRUULRLDUDDLLLLURUDLRLLLLLUDRRRDLLDDLDDULLRLLRRRRURDDDLDUDURRLRRLULDRURDLRURULULLLLUURUUDDRLRLDUDLUDRDRURLLLUURUULLURUURLRDURDRDDDLRURLLULUDURDLULUDLDUDULLUULL...

output:

0
0
0
0
0
201013
753433
0
0
387193
256843
0
0
448774
0
0
0
0
0
0
0
0
201013
544477
0
448774
0
0
0
0
239815
0
0
0
0
0
544477
256843
753433
544477
0
0
0
0
0
0
0
0
0
448774
256843
201013
239818
448774
0
0
552420
0
239818
0
0
0
0
0
0
544477
753434
239818
0
387193
201013
0
0
239818
0
239818
448774
0
2568...

result:

ok 300000 numbers

Test #79:

score: 0
Accepted
time: 406ms
memory: 324644kb

input:

1000 1000 300000
URULLRDURURLDDLDULRULUDDUUDUDLRDLRULLULDDURRDULULLLURURRDRURLRUURLDRURUURDULRDULLLDDDLLRUUULDRLLDRDULDRLLRRLDDDLDRRRUULULRUDLRUDULURLDRRRULDDDLRDRLRRULRULRDDDDLLRLURRLDRLRULULDDDDUUDDRULLUUDDUULLUDRUDLDDRULRRLRDDUDLLLURLRRDURRDDLLRDLLRDLRLULRULLURDLRRDLRDURDRDUDULUDULRRRDLURDLLLDRUR...

output:

0
202060
141304
0
0
217973
0
141304
0
0
0
0
296595
0
141304
0
478686
296595
0
0
0
0
257722
0
281639
420033
0
459782
0
0
160208
0
420033
0
0
0
0
0
0
0
0
63666
94535
0
0
0
0
0
0
0
0
0
420033
0
141304
0
0
0
0
0
0
0
0
0
0
63666
420033
217973
202060
232892
296595
0
0
217973
217973
221950
0
0
459782
0
0
2...

result:

ok 300000 numbers

Test #80:

score: 0
Accepted
time: 417ms
memory: 323224kb

input:

1000 1000 300000
DULUDDLLRLDLLUDULUDLLLUULLDRLLUDRULRURLUUDDLRDUUULULURRDLRUUDLDRLRUULUURDRUDRDLUURDLRLDRUDULRDDDRRRDRRUURDLDDULULURDDDUUUUULDUULLRUULUULDRRURULDRUULRLULDUUUULURDLDDLUDLDDULRDULDDULRRULRRLLURRULDUULLDDDLUDDLULDDRLRDDRRLLDDLRRULRRRLRDUDLLRRLRLRLLDLRDDURDLUURULUDDUULLRRURURDDLUUDRUUDDD...

output:

0
0
0
187081
0
189164
0
0
189164
0
189164
0
0
0
0
0
0
111476
0
0
0
111476
0
0
0
37777
0
346370
0
0
0
0
130370
0
0
0
0
0
0
0
0
298557
457846
0
0
0
0
0
0
0
0
0
0
0
187081
0
0
187081
0
258860
229941
457846
0
0
0
0
0
0
0
0
0
0
0
0
159289
0
0
0
0
0
0
0
0
0
258860
346370
258860
0
0
0
130370
0
219998
25886...

result:

ok 300000 numbers

Test #81:

score: 0
Accepted
time: 413ms
memory: 330404kb

input:

1000 1000 300000
DULRDLDLRULRUULLDLUUDLULUULLLULRLLDLDLDURLULDLULLDLULLDDDLLURLDDDDDRDURRDDRLLULLRLDRLDURURDRUDDURUDLLLLRLUULRDDDRLRDDDUDULUUDDUULUURDDRUURRLLUDUDLRURULDDRDULUURLRUDLURLRLUUDURDLLULRULRRRLUDLDDRDDURLDLLDULUDDDUURLRUURRRLLUULDRLDRRDLLLLLRLUDLRUUDUULDDRLUUURLDLLURDDRLLUDDULLRLLRLURLDDL...

output:

0
89609
281641
0
89609
0
0
0
0
0
121468
0
0
0
0
0
0
488659
0
0
0
423963
281641
0
0
0
0
0
281641
0
0
0
0
0
203966
0
0
0
251701
0
0
134420
0
0
281641
0
0
0
0
114333
0
0
0
281641
0
0
281641
0
0
134420
89609
114333
0
0
0
0
0
165183
263790
0
114333
488659
0
0
0
0
0
0
0
0
0
203966
0
263790
0
0
0
281641
26...

result:

ok 300000 numbers