QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#639429#6615. Cross the Mazejty233TL 21ms3956kbC++235.7kb2024-10-13 19:32:062024-10-13 19:32:13

Judging History

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

  • [2024-10-13 19:32:13]
  • 评测
  • 测评结果:TL
  • 用时:21ms
  • 内存:3956kb
  • [2024-10-13 19:32:06]
  • 提交

answer

#include "bits/stdc++.h"

using ll = long long;

struct MCFGraph {
    struct Edge {
        int v, c;
        double f;
        Edge(int v, int c, double f) : v(v), c(c), f(f) {}
    };
    const int n;
    std::vector<Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<double> h, dis;
    std::vector<int> pre;
    bool dijkstra(int s, int t) {
        dis.assign(n, std::numeric_limits<double>::max());
        pre.assign(n, -1);
        std::priority_queue<std::pair<double, int>, std::vector<std::pair<double, int>>, std::greater<>> que;
        dis[s] = 0;
        que.emplace(0, s);
        while (!que.empty()) {
            double d = que.top().first;
            int u = que.top().second;
            que.pop();
            if (dis[u] < d) continue;
            for (int i : g[u]) {
                int v = e[i].v;
                int c = e[i].c;
                double f = e[i].f;
                if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
                    dis[v] = d + h[u] - h[v] + f;
                    pre[v] = i;
                    que.emplace(dis[v], v);
                }
            }
        }
        return dis[t] != std::numeric_limits<double>::max();
    }
    MCFGraph(int n) : n(n), g(n) {}
    void addEdge(int u, int v, int c, int f) {
        g[u].push_back(e.size());
        e.emplace_back(v, c, f);
        g[v].push_back(e.size());
        e.emplace_back(u, 0, -f);
    }
    std::pair<int, double> flow(int s, int t) {
        int flow = 0;
        double cost = 0;
        h.assign(n, 0);
        while (dijkstra(s, t)) {
            for (int i = 0; i < n; ++i) h[i] += dis[i];
            int aug = std::numeric_limits<int>::max();
            for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = std::min(aug, e[pre[i]].c);
            for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
                e[pre[i]].c -= aug;
                e[pre[i] ^ 1].c += aug;
            }
            flow += aug;
            cost += double(aug) * h[t];
        }
        return std::make_pair(flow, cost);
    }
};

std::vector<std::pair<int, int>> players, ropes;
using std::cin, std::cout;

int h_dis(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    return std::abs(a.first - b.first) + std::abs(a.second - b.second);
}

double e_dis(const std::pair<int, int> &a, const std::pair<int, int> &b) {
    return std::sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

bool check(int mid, std::vector<std::pair<int, int>> &ans) {
    MCFGraph g(players.size() * 2 + 5);
    std::vector<std::tuple<int, int, int>> edge_id;
    edge_id.reserve(players.size() * ropes.size());
    for(int i = 0; i < players.size(); i++) {
        for(int j = 0; j < ropes.size(); j++) {
            if(h_dis(players[i], ropes[j]) > mid) {
                continue;
            }
            edge_id.emplace_back(i, j, g.e.size());
            g.addEdge(i, j + players.size(), 1, e_dis(players[i], ropes[j]));
        }
    }
    int s = players.size() * 2;
    int t = s + 1;
    for(int i = 0; i < players.size(); i++) {
        g.addEdge(s, i, 1, 0);
        g.addEdge(i + players.size(), t, 1, 0);
    }
    auto [flow, cost] = g.flow(s, t);
    if(flow != players.size()) {
        return false;
    } else {
        ans.clear();
        for(auto &[u, v, id] : edge_id) {
            if(g.e[id].c == 0) {
                ans.emplace_back(u, v);
            }
        }
        return true;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, a, b;
    cin >> n >> a >> b;
    players.resize(n);
    ropes.resize(n);
    for(auto &[x, y] : players) {
        cin >> x >> y;
    }
    for(auto &[x, y] : ropes) {
        cin >> x >> y;
    }
    std::vector<std::pair<int, int>> match;
    int l = 0, r = a + b;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(check(mid, match)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l << std::endl;
    std::vector<std::string> moves(n);
    auto pp = players;
    std::mt19937 eng(std::random_device{}());
    for(int _=0; _<l; _++){
        std::vector vis(a+1, std::vector<bool>(b+1, false));
        auto ppp = pp;
        bool fl = true;
        for(auto[u, v] : match) {
            auto&[x, y] = ppp[u];
            auto[a, b] = ropes[v];

            auto c = std::abs(x-a) + std::abs(y-b);
            if(x > a && !vis[x-1][y]) {
                moves[u] += 'U';
                x--;
                goto nxt;
            }
            if(y < b && !vis[x][y+1]) {
                moves[u] += 'R';
                y++;
                goto nxt;
            }
            if(x < a && !vis[x+1][y]) {
                moves[u] += 'D';
                x++;
                goto nxt;
            }
            if(y > b && !vis[x][y-1]) {
                moves[u] += 'L';
                y--;
                goto nxt;
            }
            if(x != a || y != b){
                moves[u] += 'S';
                if(vis[x][y]) fl = false;
                if(c+_>=l || eng()%10) fl = false;
            }else{
                moves[u] += 'P';
            }
            nxt:;
            vis[x][y] = true;
        }
        if(!fl){
            _--;
            for(int j=0; j<n; j++) moves[j].pop_back();
            std::shuffle(match.begin(), match.end(), eng);
            continue;
        }
        swap(ppp, pp);
    }
    for(auto[u, v] : match) {
        auto[x, y] = players[u];
        auto[a, b] = ropes[v];
        std::cout << x << ' ' << y << ' '
        << a << ' ' << b << ' ' << moves[u] << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3648kb

input:

3 4 4
1 1
1 4
4 4
1 3
2 3
2 4

output:

2
1 1 1 3 RR
1 4 2 3 DL
4 4 2 4 UU

result:

ok answer 2

Test #2:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

3 2 2
1 1
1 2
2 2
1 1
2 1
2 2

output:

1
1 1 2 1 D
1 2 1 1 L
2 2 2 2 P

result:

ok answer 1

Test #3:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

2 3 3
1 1
1 3
1 2
2 2

output:

2
1 1 1 2 RP
1 3 2 2 DL

result:

ok answer 2

Test #4:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

2 10 10
2 9
3 8
10 5
10 10

output:

10
2 9 10 10 RDDDDDDDDP
3 8 10 5 DDDDDDDLLL

result:

ok answer 10

Test #5:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

6 10 10
4 9
4 2
3 6
10 1
10 10
4 1
6 8
5 10
6 3
5 1
2 9
3 2

output:

5
4 9 2 9 UUPPP
4 2 6 3 RDDPP
3 6 6 8 RRDDD
10 1 5 1 UUUUU
10 10 5 10 UUUUU
4 1 3 2 URPPP

result:

ok answer 5

Test #6:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

8 10 10
5 1
6 8
6 3
6 4
3 10
9 5
6 7
4 1
3 8
7 3
1 2
8 6
5 8
7 6
9 4
4 1

output:

4
5 1 4 1 UPPP
6 8 5 8 UPPP
6 3 7 3 DPPP
6 4 8 6 RRDD
3 10 3 8 LLPP
9 5 9 4 LPPP
6 7 7 6 DLPP
4 1 1 2 UUUR

result:

ok answer 4

Test #7:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

1 10 10
8 3
8 4

output:

1
8 3 8 4 R

result:

ok answer 1

Test #8:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

1 10 10
10 1
6 6

output:

9
10 1 6 6 UUUURRRRR

result:

ok answer 9

Test #9:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

8 10 10
7 8
4 6
10 9
4 7
4 3
10 6
3 3
2 7
3 7
2 10
3 8
1 9
6 1
3 10
10 2
6 4

output:

7
7 8 3 10 UUUURRP
4 6 2 10 UURRRRP
10 9 10 2 LLLLLLL
4 7 3 8 URPPPPP
4 3 6 1 DDLLPPP
10 6 6 4 UUUULLP
3 3 3 7 RRRRPPP
2 7 1 9 URRPPPP

result:

ok answer 7

Test #10:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

1 10 10
10 3
2 6

output:

11
10 3 2 6 UUUUUUUURRR

result:

ok answer 11

Test #11:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

3 10 10
7 8
4 4
3 1
7 10
6 7
2 4

output:

5
7 8 7 10 RRPPP
4 4 6 7 RRRDD
3 1 2 4 URRRP

result:

ok answer 5

Test #12:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

9 10 10
6 4
1 7
2 1
5 6
10 8
3 5
9 9
9 2
4 9
5 3
3 2
6 9
2 2
9 4
7 8
2 8
1 1
4 8

output:

5
6 4 3 2 UUULL
1 7 2 8 RDPPP
2 1 1 1 UPPPP
5 6 5 3 LLLPP
10 8 7 8 UUUPP
3 5 2 2 ULLLP
9 9 6 9 UUUPP
9 2 9 4 RRPPP
4 9 4 8 LPPPP

result:

ok answer 5

Test #13:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

2 10 10
9 8
3 3
5 8
4 9

output:

7
9 8 5 8 UUUUPPP
3 3 4 9 RRRRRRD

result:

ok answer 7

Test #14:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

8 10 10
10 5
8 4
2 8
2 4
10 8
6 6
1 7
10 1
8 6
10 5
10 2
5 9
8 10
10 4
3 9
4 2

output:

4
10 5 10 5 PPPP
8 4 10 4 DDPP
2 8 5 9 RDDD
2 4 4 2 DDLL
10 8 8 10 UURR
6 6 8 6 DDPP
1 7 3 9 RRDD
10 1 10 2 RPPP

result:

ok answer 4

Test #15:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

1 10 10
1 9
2 10

output:

2
1 9 2 10 RD

result:

ok answer 2

Test #16:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

8 10 10
5 10
3 8
2 8
3 5
4 2
8 2
7 9
3 4
8 9
9 6
3 6
10 2
4 10
10 6
6 5
5 5

output:

6
3 8 4 10 RRDPPP
8 2 10 6 RRRRDD
3 5 6 5 DDDPPP
2 8 3 6 DLLPPP
3 4 5 5 RDDPPP
5 10 8 9 DDDLPP
4 2 10 2 DDDDDD
7 9 9 6 DDLLSL

result:

ok answer 6

Test #17:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

1 10 10
8 6
1 8

output:

9
8 6 1 8 UUUUUUURR

result:

ok answer 9

Test #18:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

10 10 10
7 10
4 4
9 10
5 7
10 7
4 1
1 5
6 7
6 4
5 3
5 7
1 9
1 6
8 3
5 1
10 8
2 6
4 2
3 10
3 1

output:

5
7 10 3 10 UUUUP
4 4 3 1 ULLLP
9 10 10 8 DLLPP
5 7 1 6 UUUUL
10 7 5 7 UUUUU
4 1 5 1 DPPPP
1 5 1 9 RRRRP
6 7 2 6 UUUUL
6 4 8 3 DDLPP
5 3 4 2 ULPPP

result:

ok answer 5

Test #19:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

7 10 10
4 5
1 5
6 5
9 6
5 5
9 3
1 10
10 6
6 2
5 1
2 7
8 1
7 10
6 3

output:

6
5 5 6 2 DLLLPP
1 10 7 10 DDDDDD
4 5 5 1 DLLLLP
6 5 6 3 LLPPPP
9 3 8 1 ULLPPP
9 6 10 6 DPPPPP
1 5 2 7 RRDPPP

result:

ok answer 6

Test #20:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

6 10 10
9 7
4 1
9 1
7 9
2 6
9 5
5 1
4 1
2 10
4 10
3 1
1 7

output:

8
9 7 4 10 UUUUURRR
9 5 5 1 UUUULLLL
9 1 3 1 UUUUSUUP
4 1 4 1 PPPPPPPP
2 6 1 7 URPPPPPP
7 9 2 10 UUUUURPP

result:

ok answer 8

Test #21:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

10 10 10
7 7
8 6
10 3
6 2
10 8
1 10
9 5
1 2
8 3
10 9
8 9
8 10
6 4
7 8
4 3
3 5
3 9
6 1
8 7
10 2

output:

5
7 7 7 8 RPPPP
8 6 8 7 RPPPP
10 3 10 2 LPPPP
6 2 4 3 UURPP
10 8 8 9 UURPP
1 10 3 9 DDLPP
9 5 6 4 UUULP
1 2 3 5 RRRDD
8 3 6 1 UULLP
10 9 8 10 UURPP

result:

ok answer 5

Test #22:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

10 10 10
2 9
1 2
3 9
6 9
3 3
9 2
2 4
5 8
1 6
4 9
1 10
6 10
3 6
2 5
4 2
7 3
10 2
9 1
2 9
5 8

output:

8
2 9 2 9 PPPPPPPP
1 2 7 3 RDDDDDDP
3 9 1 10 RUUPPPPP
6 9 6 10 RPPPPPPP
3 3 9 1 DDDDDDLL
9 2 10 2 DPPPPPPP
2 4 4 2 DDLLPPPP
5 8 5 8 PPPPPPPP
1 6 2 5 DLPPPPPP
4 9 3 6 ULLLPPPP

result:

ok answer 8

Test #23:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

10 10 10
10 6
9 2
7 7
7 3
6 8
5 4
2 10
1 1
5 9
4 6
5 1
9 9
9 1
7 6
3 2
4 8
7 7
9 7
3 1
6 10

output:

4
10 6 9 7 URPP
9 2 9 1 LPPP
7 7 7 7 PPPP
7 3 5 1 UULL
6 8 9 9 RDDD
5 4 3 2 UULL
2 10 4 8 DDLL
1 1 3 1 DDPP
5 9 6 10 RDPP
4 6 7 6 DDDP

result:

ok answer 4

Test #24:

score: 0
Accepted
time: 1ms
memory: 3736kb

input:

10 1 100
1 17
1 49
1 12
1 37
1 83
1 44
1 75
1 78
1 72
1 3
1 75
1 47
1 55
1 81
1 6
1 59
1 17
1 68
1 28
1 24

output:

13
1 37 1 28 LLLLLLLLLPPPP
1 44 1 47 RRRPPPPPPPPPP
1 78 1 68 LLLLLLLLLLPPP
1 72 1 59 LLLLLLLLLLLLL
1 12 1 24 RRRRRRRRRRRRP
1 75 1 75 PPPPPPPPPPPPP
1 17 1 17 PPPPPPPPPPPPP
1 3 1 6 RRRPPPPPPPPPP
1 83 1 81 LLPPPPPPPPPPP
1 49 1 55 RRRRRRPPPPPPP

result:

ok answer 13

Test #25:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

10 1 100
1 43
1 75
1 59
1 42
1 26
1 33
1 88
1 7
1 24
1 95
1 68
1 31
1 39
1 74
1 66
1 67
1 28
1 70
1 86
1 58

output:

25
1 75 1 74 LPPPPPPPPPPPPPPPPPPPPPPPP
1 88 1 86 LLPPPPPPPPPPPPPPPPPPPPPPP
1 24 1 39 RRRRRRRRRRRRRRRPPPPPPPPPP
1 26 1 28 RRPPPPPPPPPPPPPPPPPPPPPPP
1 7 1 31 RRRRRRRRRRRRRRRRRRRRRRRRP
1 42 1 67 RRRRRRRRRRRRRRRRRRRRRRRRR
1 95 1 70 LLLLLLLLLLLLLLLLLLLLLLLLL
1 43 1 68 RRRRRRRRRRRRRRRRRRRRRRRRR
1 59 1 66 ...

result:

ok answer 25

Test #26:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

10 1 100
1 88
1 38
1 43
1 99
1 63
1 24
1 44
1 31
1 47
1 52
1 6
1 14
1 55
1 15
1 82
1 57
1 73
1 74
1 97
1 51

output:

23
1 52 1 74 RRRRRRRRRRRRRRRRRRRRRRP
1 24 1 6 LLLLLLLLLLLLLLLLLLPPPPP
1 31 1 14 LLLLLLLLLLLLLLLLLPPPPPP
1 44 1 57 RRRRRRRRRRRRRPPPPPPPPPP
1 43 1 55 RRRRRRRRRRRRPPPPPPPPPPP
1 99 1 97 LLPPPPPPPPPPPPPPPPPPPPP
1 88 1 82 LLLLLLPPPPPPPPPPPPPPPPP
1 47 1 51 RRRRPPPPPPPPPPPPPPPPPPP
1 38 1 15 LLLLLLLLLLLLLLLL...

result:

ok answer 23

Test #27:

score: 0
Accepted
time: 1ms
memory: 3544kb

input:

10 100 1
6 1
96 1
41 1
76 1
97 1
72 1
94 1
82 1
23 1
40 1
31 1
33 1
84 1
77 1
41 1
24 1
39 1
68 1
8 1
82 1

output:

35
94 1 84 1 UUUUUUUUUUPPPPPPPPPPPPPPPPPPPPPPPPP
72 1 39 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUPP
82 1 82 1 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
97 1 68 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUPPPPPP
6 1 8 1 DDPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
76 1 41 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
40 1 31 1 UUUUUUUUUPPPP...

result:

ok answer 35

Test #28:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

10 100 1
19 1
23 1
29 1
11 1
44 1
87 1
68 1
56 1
35 1
34 1
34 1
63 1
40 1
90 1
8 1
69 1
81 1
41 1
18 1
82 1

output:

28
19 1 18 1 UPPPPPPPPPPPPPPPPPPPPPPPPPPP
23 1 40 1 DDDDDDDDDDDDDDDDDPPPPPPPPPPP
29 1 41 1 DDDDDDDDDDDDPPPPPPPPPPPPPPPP
11 1 8 1 UUUPPPPPPPPPPPPPPPPPPPPPPPPP
44 1 69 1 DDDDDDDDDDDDDDDDDDDDDDDDDPPP
87 1 90 1 DDDPPPPPPPPPPPPPPPPPPPPPPPPP
68 1 82 1 DDDDDDDDDDDDDDPPPPPPPPPPPPPP
56 1 81 1 DDDDDDDDDDDDDDD...

result:

ok answer 28

Test #29:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

10 100 1
42 1
4 1
64 1
31 1
92 1
45 1
60 1
24 1
8 1
35 1
57 1
70 1
42 1
17 1
72 1
51 1
56 1
87 1
52 1
88 1

output:

34
4 1 17 1 DDDDDDDDDDDDDPPPPPPPPPPPPPPPPPPPPP
35 1 52 1 DDDDDDDDDDDDDDDSDDPPPPPPPPPPPPPPPP
42 1 70 1 DDDDDDDDDDDDDDDDDDDDDDDDDDDDPPPPPP
60 1 72 1 DDDDDDDDDDDDPPPPPPPPPPPPPPPPPPPPPP
64 1 87 1 DDDDDDDDDDDDDDDDDDDDDDDPPPPPPPPPPP
92 1 88 1 UUUUPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
8 1 42 1 DDDDDDDDDDDDDDDDDDD...

result:

ok answer 34

Test #30:

score: 0
Accepted
time: 3ms
memory: 3808kb

input:

50 10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
8 1
...

output:

5
1 1 6 1 DDDDD
1 2 6 2 DDDDD
1 3 6 3 DDDDD
1 4 6 4 DDDDD
1 5 6 5 DDDDD
1 6 6 6 DDDDD
1 7 6 7 DDDDD
1 8 6 8 DDDDD
1 9 6 9 DDDDD
1 10 6 10 DDDDD
2 1 7 1 DDDDD
2 2 7 2 DDDDD
2 3 7 3 DDDDD
2 4 7 4 DDDDD
2 5 7 5 DDDDD
2 6 7 6 DDDDD
2 7 7 7 DDDDD
2 8 7 8 DDDDD
2 9 7 9 DDDDD
2 10 7 10 DDDDD
3 1 8 1 DDDDD
...

result:

ok answer 5

Test #31:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

1 1 2
1 1
1 2

output:

1
1 1 1 2 R

result:

ok answer 1

Test #32:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

1 1 100
1 1
1 100

output:

99
1 1 1 100 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR

result:

ok answer 99

Test #33:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

2 2 50
1 1
2 50
1 50
2 1

output:

1
1 1 2 1 D
2 50 1 50 U

result:

ok answer 1

Test #34:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

2 1 100
1 23
1 54
1 67
1 26

output:

13
1 23 1 26 RRRPPPPPPPPPP
1 54 1 67 RRRRRRRRRRRRR

result:

ok answer 13

Test #35:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

2 2 50
1 21
1 41
2 36
1 11

output:

10
1 21 1 11 LLLLLLLLLL
1 41 2 36 DLLLLLPPPP

result:

ok answer 10

Test #36:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

2 3 33
3 17
2 13
1 23
1 24

output:

11
3 17 1 24 UURRRRRRRPP
2 13 1 23 URRRRRRRRRR

result:

ok answer 11

Test #37:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

2 4 25
3 15
2 22
1 22
1 11

output:

6
3 15 1 11 UULLLL
2 22 1 22 UPPPPP

result:

ok answer 6

Test #38:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

2 5 20
2 18
5 2
5 7
3 8

output:

11
2 18 3 8 DLLLLLLLLLL
5 2 5 7 RRRRRPPPPPP

result:

ok answer 11

Test #39:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

2 6 16
5 12
6 4
1 11
5 15

output:

12
5 12 5 15 RRRPPPPPPPPP
6 4 1 11 UUUUURRRRRRR

result:

ok answer 12

Test #40:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

2 7 14
3 14
7 1
1 12
6 4

output:

4
3 14 1 12 UULL
7 1 6 4 URRR

result:

ok answer 4

Test #41:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

2 8 12
8 4
1 4
5 12
2 6

output:

11
8 4 5 12 UUURRRRRRRR
1 4 2 6 RRDPPPPPPPP

result:

ok answer 11

Test #42:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

2 9 11
1 7
3 4
4 3
7 6

output:

7
1 7 7 6 DDDDDDL
3 4 4 3 DLPPPPP

result:

ok answer 7

Test #43:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

2 10 10
4 5
10 7
4 2
2 10

output:

11
4 5 4 2 LLLPPPPPPPP
10 7 2 10 UUUUUUUURRR

result:

ok answer 11

Test #44:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

5 100 1
94 1
75 1
91 1
13 1
65 1
76 1
89 1
86 1
92 1
19 1

output:

11
94 1 92 1 UUPPPPPPPPP
75 1 86 1 DDDDDDDDDDD
91 1 89 1 UUPPPPPPPPP
13 1 19 1 DDDDDDPPPPP
65 1 76 1 DDDDDDDDDDD

result:

ok answer 11

Test #45:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

5 50 2
33 1
12 2
39 1
36 1
19 2
6 1
41 2
32 2
34 2
9 2

output:

10
33 1 32 2 URPPPPPPPP
12 2 6 1 UUUUUULPPP
39 1 41 2 RDDPPPPPPP
36 1 34 2 UURPPPPPPP
19 2 9 2 UUUUUUUUUU

result:

ok answer 10

Test #46:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

5 33 3
33 3
4 1
23 1
23 3
27 1
32 2
4 1
20 2
21 3
28 1

output:

4
33 3 32 2 ULPP
4 1 4 1 PPPP
23 1 21 3 UURR
23 3 20 2 UUUL
27 1 28 1 DPPP

result:

ok answer 4

Test #47:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

5 25 4
23 3
22 3
9 4
18 3
1 3
23 4
9 2
7 3
19 3
13 2

output:

6
23 3 23 4 RPPPPP
22 3 19 3 UUUPPP
9 4 9 2 LLPPPP
18 3 13 2 UUUUUL
1 3 7 3 DDDDDD

result:

ok answer 6

Test #48:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

5 20 5
11 5
15 3
16 5
12 2
15 2
20 2
8 2
19 1
3 2
15 5

output:

9
11 5 8 2 UUULLLPPP
15 3 19 1 DDDDLLPPP
16 5 15 5 UPPPPPPPP
12 2 3 2 UUUUUUUUU
15 2 20 2 DDDDDPPPP

result:

ok answer 9

Test #49:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

5 16 6
13 2
5 2
2 6
16 2
3 4
3 4
2 3
14 2
1 4
1 2

output:

12
13 2 1 2 UUUUUUUUUUUU
5 2 2 3 UUURPPPPPPPP
2 6 1 4 ULLPPPPPPPPP
16 2 14 2 UUPPPPPPPPPP
3 4 3 4 PPPPPPPPPPPP

result:

ok answer 12

Test #50:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

5 14 7
4 3
1 1
3 3
3 4
13 7
3 3
8 3
12 7
1 5
2 7

output:

4
4 3 8 3 DDDD
1 1 1 5 RRRR
3 3 3 3 PPPP
3 4 2 7 URRR
13 7 12 7 UPPP

result:

ok answer 4

Test #51:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

5 12 8
12 7
11 8
1 7
4 8
11 4
7 6
5 8
6 3
10 4
2 1

output:

7
12 7 10 4 UULLLPP
11 8 7 6 UUUULLP
1 7 2 1 DLLLLLL
4 8 5 8 DPPPPPP
11 4 6 3 UUUUULP

result:

ok answer 7

Test #52:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

5 11 9
3 3
1 1
10 6
1 4
10 4
7 3
2 6
4 5
6 7
1 4

output:

5
3 3 4 5 RRDPP
1 1 1 4 RRRPP
10 6 6 7 UUUUR
1 4 2 6 RRDPP
10 4 7 3 UUULP

result:

ok answer 5

Test #53:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

5 10 10
2 2
1 3
9 9
7 4
6 5
9 5
6 5
10 6
2 5
1 10

output:

7
2 2 2 5 RRRPPPP
1 3 1 10 RRRRRRR
9 9 10 6 DLLLPPP
7 4 9 5 RDDPPPP
6 5 6 5 PPPPPPP

result:

ok answer 7

Test #54:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

10 1 100
1 67
1 1
1 86
1 24
1 75
1 82
1 55
1 84
1 26
1 40
1 4
1 62
1 73
1 77
1 5
1 14
1 42
1 98
1 48
1 38

output:

19
1 75 1 62 LLLLLLLLLLLLLPPPPPP
1 40 1 38 LLPPPPPPPPPPPPPPPPP
1 84 1 73 LLLLLLLLLLLPPPPPPPP
1 82 1 77 LLLLLPPPPPPPPPPPPPP
1 1 1 4 RRRPPPPPPPPPPPPPPPP
1 67 1 48 LLLLLLLLLLLLLLLLLLL
1 26 1 14 LLLLLLLLLLLLPPPPPPP
1 24 1 5 LLLLLLLLLLLLLLLLLLL
1 86 1 98 RRRRRRRRRRRRPPPPPPP
1 55 1 42 LLLLLLLLLLLLLPPPPPP

result:

ok answer 19

Test #55:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

10 2 50
2 47
1 48
1 33
1 22
1 10
2 5
1 49
1 11
2 11
1 47
2 48
2 42
1 48
2 17
1 23
1 12
2 23
1 6
2 29
1 32

output:

15
2 47 2 42 LLLLLPPPPPPPPPP
1 48 1 48 PPPPPPPPPPPPPPP
1 33 2 29 DLLLLPPPPPPPPPP
1 22 1 23 RPPPPPPPPPPPPPP
1 10 2 23 RRRRRRRRRRRRDRP
2 5 1 6 URPPPPPPPPPPPPP
1 49 2 48 DLPPPPPPPPPPPPP
1 11 1 12 RPPPPPPPPPPPPPP
2 11 2 17 RRRRRRPPPPPPPPP
1 47 1 32 LLLLLLLLLLLLLLL

result:

ok answer 15

Test #56:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

10 3 33
1 16
1 4
1 30
2 8
1 8
2 16
3 33
2 12
2 20
1 15
2 10
3 10
3 28
3 33
1 18
2 11
3 9
2 2
2 6
3 31

output:

9
1 8 2 6 DLLPPPPPP
1 4 2 2 DLLPPPPPP
2 8 3 9 RDPPPPPPP
1 15 3 10 LLLLLDDPP
1 16 1 18 RRPPPPPPP
2 16 2 10 LLLLLSLPP
1 30 3 31 RDDPPPPPP
2 20 3 28 RRRRRRRRD
3 33 3 33 PPPPPPPPP
2 12 2 11 LPPPPPPPP

result:

ok answer 9

Test #57:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

10 4 25
4 13
2 1
1 6
2 2
2 15
3 12
3 19
4 18
4 23
4 10
3 3
4 4
2 13
2 6
2 18
2 4
1 22
3 7
4 15
1 24

output:

6
2 1 4 4 RRRDDP
3 19 1 22 UURRRP
4 13 4 15 RRPPPP
4 18 2 18 UUPPPP
4 10 2 6 UULLLL
2 15 2 13 LLPPPP
4 23 1 24 UUURPP
2 2 3 3 RDPPPP
1 6 2 4 DLSLPP
3 12 3 7 LLLLLP

result:

ok answer 6

Test #58:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

10 5 20
3 4
2 18
4 11
3 16
5 13
5 20
1 7
5 4
3 14
2 1
1 9
2 11
3 7
1 12
2 6
5 8
1 20
4 2
3 17
3 1

output:

6
3 4 4 2 DLLPPP
2 18 1 20 URRPPP
4 11 1 9 UUULLP
3 16 2 11 ULLLLL
5 13 5 8 LLLLLP
5 20 3 17 UULLLP
1 7 2 6 DLPPPP
5 4 3 7 RUURRP
3 14 1 12 UULLPP
2 1 3 1 DPPPPP

result:

ok answer 6

Test #59:

score: 0
Accepted
time: 1ms
memory: 3740kb

input:

10 6 16
6 15
6 10
4 13
5 10
2 7
2 16
1 11
5 9
2 1
1 1
4 6
4 2
2 2
6 3
2 16
2 14
4 14
2 9
2 11
2 4

output:

7
6 15 4 14 UULPPPP
6 10 6 3 LLLLLLL
4 13 2 14 UURPPPP
5 10 2 9 UUULPPP
2 7 2 4 LLLPPPP
2 16 2 16 PPPPPPP
1 11 2 11 DPPPPPP
5 9 4 6 ULLLPPP
2 1 4 2 RDDPPPP
1 1 2 2 RDPPPPP

result:

ok answer 7

Test #60:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

10 7 14
7 4
4 10
4 8
6 12
2 13
1 5
4 1
2 9
5 4
6 14
6 11
3 7
7 5
3 9
2 4
7 1
3 12
6 13
2 7
4 5

output:

3
7 4 7 5 RPP
4 10 3 9 ULP
4 8 3 7 ULP
6 12 6 11 LPP
2 13 3 12 DLP
1 5 2 4 DLP
4 1 7 1 DDD
2 9 2 7 LLP
5 4 4 5 URP
6 14 6 13 LPP

result:

ok answer 3

Test #61:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

10 8 12
1 12
5 2
5 1
4 4
8 10
3 11
5 10
1 11
7 4
8 2
2 8
3 7
8 4
4 11
5 8
7 11
1 12
6 4
7 7
7 1

output:

4
1 12 1 12 PPPP
5 2 6 4 RRDP
5 1 7 1 DDPP
4 4 3 7 URRR
8 10 7 11 URPP
3 11 4 11 DPPP
5 10 5 8 LLPP
1 11 2 8 DLLL
7 4 7 7 RRRP
8 2 8 4 RRPP

result:

ok answer 4

Test #62:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

10 9 11
5 4
4 4
9 10
5 6
8 11
3 9
3 1
2 7
9 6
6 3
6 8
8 8
2 9
5 9
7 4
7 7
4 5
9 7
4 7
2 7

output:

5
5 4 7 7 RRRDD
4 4 4 7 RRRPP
9 10 8 8 ULLPP
5 6 6 8 RRDPP
8 11 5 9 UUULL
3 9 2 9 UPPPP
3 1 4 5 RRRRD
2 7 2 7 PPPPP
9 6 9 7 RPPPP
6 3 7 4 RDPPP

result:

ok answer 5

Test #63:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

10 10 10
2 9
10 7
4 6
4 10
2 8
8 2
1 1
2 3
7 6
8 8
4 8
8 7
5 9
5 7
7 1
7 7
8 1
7 6
6 6
4 10

output:

7
2 9 4 8 DDLPPPP
10 7 8 7 UUPPPPP
4 6 5 7 RDPPPPP
4 10 4 10 PPPPPPP
2 8 5 9 RDDDPPP
8 2 8 1 LPPPPPP
1 1 7 1 DDDDDDP
2 3 6 6 RRRDDDD
7 6 7 6 PPPPPPP
8 8 7 7 ULPPPPP

result:

ok answer 7

Test #64:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

20 100 1
77 1
38 1
67 1
91 1
60 1
34 1
32 1
56 1
76 1
57 1
22 1
26 1
49 1
61 1
86 1
16 1
79 1
21 1
28 1
73 1
32 1
90 1
8 1
58 1
70 1
28 1
65 1
85 1
20 1
84 1
93 1
98 1
2 1
19 1
96 1
95 1
49 1
47 1
17 1
42 1

output:

17
73 1 90 1 DDDDDDDDDDDDDDDDD
22 1 19 1 UUUPPPPPPPPPPPPPP
57 1 58 1 DPPPPPPPPPPPPPPPP
60 1 70 1 DDDDDDDDDDPPPPPPP
28 1 28 1 PPPPPPPPPPPPPPPPP
56 1 47 1 UUUUUUUUUPPPPPPPP
16 1 2 1 UUUUUUUUUUUUUUPPP
67 1 84 1 DDDDDDDDDDDDDDDDD
21 1 8 1 UUUUUUUUUUUUUPPPP
34 1 20 1 UUUUUUUUUUUUUUPPP
76 1 93 1 DDDDDDDDD...

result:

ok answer 17

Test #65:

score: 0
Accepted
time: 1ms
memory: 3696kb

input:

20 50 2
8 1
23 2
17 2
46 1
38 1
47 1
33 1
45 2
24 1
16 1
18 1
44 1
25 1
13 1
40 1
15 1
45 1
32 1
27 1
26 1
5 1
38 1
16 1
15 2
19 2
16 2
47 2
27 2
37 1
8 1
28 2
21 2
26 1
8 2
14 2
19 1
10 1
22 2
29 2
10 2

output:

17
13 1 10 1 UUUPPPPPPPPPPPPPP
45 1 37 1 UUUUUUUUPPPPPPPPP
15 1 14 2 URPPPPPPPPPPPPPPP
24 1 10 2 UUUUUUUUUUUUUURPP
17 2 16 2 UPPPPPPPPPPPPPPPP
18 1 5 1 UUUUUUUUUUUUUPPPP
46 1 38 1 UUUUUUUUPPPPPPPPP
8 1 8 1 PPPPPPPPPPPPPPPPP
47 1 47 2 RPPPPPPPPPPPPPPPP
40 1 26 1 UUUUUUUUUUUUUUPPP
32 1 16 1 UUUUUUUUUU...

result:

ok answer 17

Test #66:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

20 33 3
32 1
20 2
18 2
32 2
3 2
23 3
2 2
8 3
8 1
28 2
23 1
17 1
7 3
16 1
27 1
1 2
24 1
19 3
30 2
28 1
5 1
25 2
30 2
17 3
4 2
12 1
12 3
4 1
13 2
19 2
8 2
19 1
21 1
9 3
31 3
10 1
33 1
15 3
22 2
10 3

output:

7
20 2 13 2 UUUUUUU
32 1 33 1 DPPPPPP
23 1 19 1 UUUUPPP
30 2 30 2 PPPPPPP
2 2 4 1 DLDPPPP
3 2 4 2 DPPPPPP
28 2 22 2 UUSUUUU
23 3 17 3 UUUUUUP
27 1 25 2 UURPPPP
8 1 10 3 RRDDPPP
32 2 31 3 URPPPPP
28 1 21 1 UUUUUUU
16 1 10 1 UUUUUUP
18 2 12 1 UULUUUU
19 3 12 3 UUUUUUU
7 3 8 2 DLPPPPP
24 1 19 2 UUUURUP...

result:

ok answer 7

Test #67:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

20 25 4
23 2
8 2
24 3
12 2
11 4
13 3
13 1
23 3
2 2
20 2
10 4
17 1
24 2
25 2
2 1
6 1
3 4
5 2
9 3
10 1
21 4
10 3
9 2
21 1
23 4
25 1
2 4
20 4
12 2
8 2
3 2
16 1
22 2
16 3
24 4
7 3
20 1
19 2
9 3
19 3

output:

7
2 2 3 2 DPPPPPP
23 2 22 2 UPPPPPP
6 1 9 2 RDDDPPP
24 3 23 4 URPPPPP
10 1 16 1 DDDDDDP
3 4 2 4 UPPPPPP
24 2 21 4 URUURPP
10 4 12 2 DDLLPPP
11 4 16 3 DDDDDLP
5 2 10 3 RDDDDDP
20 2 21 1 DLPPPPP
9 3 9 3 PPPPPPP
23 3 24 4 RDPPPPP
12 2 19 2 DDDDDDD
13 3 19 3 DDDDDDP
17 1 20 4 RRRDDDP
8 2 8 2 PPPPPPP
25 ...

result:

ok answer 7

Test #68:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

20 20 5
16 1
5 2
7 4
12 5
10 5
16 5
9 1
1 3
11 5
12 1
15 5
15 3
6 3
8 1
14 1
3 3
11 3
7 1
4 2
10 4
19 2
15 3
6 2
13 1
2 1
14 4
8 4
11 5
9 1
13 3
3 4
5 5
18 4
7 4
8 1
3 5
5 4
14 5
17 5
18 3

output:

4
8 1 8 1 PPPP
3 3 3 4 RPPP
15 3 18 3 DDDP
10 5 8 4 UULP
7 4 7 4 PPPP
1 3 3 5 RRDD
12 1 13 1 DPPP
7 1 6 2 URPP
10 4 13 3 LDDD
4 2 2 1 UULP
16 1 19 2 RDDD
11 3 14 4 RDDD
9 1 9 1 PPPP
12 5 14 5 DDPP
5 2 5 5 RRRP
14 1 15 3 RRDP
16 5 17 5 DPPP
11 5 11 5 PPPP
6 3 5 4 RSUP
15 5 18 4 DLDD

result:

ok answer 4

Test #69:

score: 0
Accepted
time: 1ms
memory: 3772kb

input:

20 16 6
6 5
5 6
1 2
3 6
8 5
14 3
1 1
4 1
5 2
10 1
13 1
6 3
13 5
1 4
2 5
8 2
2 1
16 2
12 2
14 6
14 1
2 5
10 1
16 1
12 3
3 2
1 6
13 1
12 1
13 3
7 2
1 1
10 4
10 3
16 3
11 3
3 3
15 2
4 4
3 4

output:

6
1 1 1 1 PPPPPP
10 1 12 1 DDPPPP
13 1 13 1 PPPPPP
13 5 13 3 LLPPPP
14 3 15 2 DLPPPP
16 2 16 1 LPPPPP
4 1 10 1 DDDDDD
3 6 4 4 LDLPPP
2 1 3 2 RDPPPP
6 3 12 3 DDDDDD
12 2 14 1 DDLPPP
2 5 2 5 PPPPPP
6 5 10 4 DDDDLP
1 2 3 3 RDDPPP
5 2 7 2 DDPPPP
5 6 3 4 UULLPP
14 6 16 3 DDLLLP
8 5 11 3 DDDLSL
8 2 10 3 R...

result:

ok answer 6

Test #70:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

20 14 7
3 6
3 1
12 6
10 6
6 1
13 2
8 2
12 3
1 2
11 5
5 4
7 4
4 1
11 4
5 3
1 3
6 6
12 1
11 7
11 2
11 1
9 5
7 4
7 6
8 4
14 5
11 4
11 5
12 2
6 3
13 4
4 5
5 1
9 7
6 2
1 1
11 6
11 7
6 5
4 1

output:

4
1 2 4 1 DDDL
12 6 11 6 UPPP
7 4 9 5 RDDP
10 6 9 7 URPP
1 3 1 1 LLPP
11 5 11 5 PPPP
3 1 5 1 DDPP
5 4 6 5 RDPP
12 3 13 4 RDPP
6 1 6 2 RPPP
12 1 11 1 UPPP
11 7 11 7 PPPP
3 6 4 5 DLPP
6 6 7 6 DPPP
13 2 14 5 RDRR
8 2 8 4 RRPP
4 1 6 3 RRDD
5 3 7 4 RDDP
11 2 12 2 DPPP
11 4 11 4 PPPP

result:

ok answer 4

Test #71:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

20 12 8
6 6
12 1
3 6
7 6
8 4
4 5
5 1
5 5
10 3
9 4
8 2
5 8
7 4
5 3
12 2
8 5
10 7
6 4
6 7
8 6
7 6
7 3
5 1
2 3
1 3
12 1
3 2
3 4
1 2
11 2
3 1
3 3
5 8
2 7
12 4
9 7
2 4
9 8
8 4
7 1

output:

5
9 4 7 1 LULUL
6 7 2 7 UUUUP
5 3 3 1 UULLP
7 6 7 6 PPPPP
10 7 9 8 URPPP
8 2 5 1 UUULP
6 4 3 2 UUULL
5 5 2 3 UUULL
10 3 11 2 DLPPP
8 6 9 7 RDPPP
8 5 7 3 ULLPP
8 4 8 4 PPPPP
12 1 12 1 PPPPP
12 2 12 4 RRPPP
6 6 3 4 UUULL
5 1 1 2 UUUUR
5 8 5 8 PPPPP
4 5 1 3 ULLUU
3 6 2 4 ULLPP
7 4 3 3 UUUUL

result:

ok answer 5

Test #72:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

20 11 9
4 3
8 7
5 9
7 1
4 8
10 4
6 6
8 6
9 9
11 2
11 5
4 5
9 6
11 8
10 3
4 7
7 8
5 5
8 5
1 8
2 4
3 1
4 3
6 4
4 2
4 5
10 9
8 7
6 1
7 3
1 9
11 8
9 7
1 6
1 1
10 4
11 2
5 6
11 9
11 6

output:

5
4 7 2 4 UULLL
8 6 9 7 DRPPP
1 8 1 9 RPPPP
5 5 4 2 ULLLP
8 7 8 7 PPPPP
9 6 11 9 RRRDD
8 5 6 4 UULPP
10 3 7 3 UUUPP
4 5 3 1 ULLLL
4 3 1 1 UUULL
11 2 11 2 PPPPP
7 8 5 6 UULLP
4 8 1 6 UUULL
6 6 4 3 UULLL
7 1 6 1 UPPPP
11 5 11 6 RPPPP
11 8 11 8 PPPPP
9 9 10 9 DPPPP
10 4 10 4 PPPPP
5 9 4 5 ULLLL

result:

ok answer 5

Test #73:

score: 0
Accepted
time: 1ms
memory: 3696kb

input:

20 10 10
7 9
3 1
1 8
1 7
9 9
8 4
2 5
4 2
4 4
2 4
8 3
8 2
4 6
6 10
8 1
3 6
9 2
5 2
9 3
10 8
6 9
5 2
4 2
5 3
9 6
10 5
7 3
7 5
7 6
7 7
2 4
1 6
10 2
6 5
3 2
2 8
7 2
2 6
2 10
4 3

output:

3
7 9 7 7 LLP
3 1 3 2 RPP
1 8 2 10 RRD
1 7 2 8 RDP
9 9 9 6 LLL
8 4 7 6 URR
2 5 1 6 URP
4 2 4 2 PPP
4 4 5 3 DLP
2 4 2 4 PPP
8 3 7 5 URR
8 2 5 2 UUU
4 6 6 5 DDL
6 10 6 9 LPP
8 1 7 2 URP
3 6 2 6 UPP
9 2 10 2 DPP
5 2 4 3 RUP
9 3 7 3 UUP
10 8 10 5 LLL

result:

ok answer 3

Test #74:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

30 1 100
1 85
1 59
1 11
1 17
1 95
1 98
1 38
1 47
1 5
1 92
1 33
1 30
1 26
1 50
1 8
1 86
1 64
1 49
1 93
1 35
1 21
1 77
1 65
1 54
1 60
1 56
1 70
1 6
1 44
1 55
1 48
1 84
1 75
1 26
1 53
1 6
1 80
1 49
1 31
1 51
1 72
1 41
1 45
1 83
1 73
1 93
1 8
1 16
1 24
1 20
1 37
1 14
1 39
1 85
1 43
1 42
1 34
1 87
1 86
1...

output:

8
1 60 1 62 RRPPPPPP
1 11 1 14 RRRPPPPP
1 65 1 73 RRRRRRRR
1 59 1 53 LLLLLLPP
1 55 1 51 LLLLPPPP
1 64 1 72 RRRRRRRR
1 56 1 48 LLLLLLLL
1 33 1 34 RPPPPPPP
1 70 1 75 RRRRRPPP
1 92 1 84 LLLLLLLL
1 49 1 41 LLLLLLLL
1 95 1 87 LLLLLLLL
1 50 1 42 LLLLLLLL
1 98 1 93 LLLLLPPP
1 26 1 26 PPPPPPPP
1 54 1 49 LLL...

result:

ok answer 8

Test #75:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

30 2 50
2 40
2 29
2 44
1 23
2 48
1 31
1 15
1 38
1 9
2 3
1 30
2 7
2 13
2 19
1 7
2 20
1 46
1 50
2 11
2 14
1 33
2 1
2 38
2 22
1 47
1 36
2 17
2 36
2 35
2 28
1 17
2 27
2 50
2 5
1 21
2 1
2 31
1 35
2 36
1 13
1 28
2 33
2 29
2 26
1 38
2 41
1 2
2 16
1 40
2 39
1 27
2 13
2 17
2 44
2 19
2 35
2 2
1 14
2 46
1 36

output:

6
2 19 2 19 PPPPPP
2 17 2 17 PPPPPP
2 38 1 35 LULLPP
1 30 1 28 LLPPPP
1 50 2 50 DPPPPP
2 44 1 40 ULLLLP
1 15 2 16 RDPPPP
1 47 2 46 LSDPPP
2 35 2 35 PPPPPP
2 1 2 1 PPPPPP
2 13 2 13 PPPPPP
1 33 2 33 DPPPPP
1 46 2 41 DLLLLL
1 7 2 2 DLLLLL
2 29 2 29 PPPPPP
2 36 2 36 PPPPPP
2 14 1 17 URRRPP
1 31 2 31 DPP...

result:

ok answer 6

Test #76:

score: 0
Accepted
time: 2ms
memory: 3744kb

input:

30 3 33
1 14
2 12
3 24
2 29
1 30
1 22
1 29
1 9
3 28
3 7
3 11
1 17
1 23
2 21
2 6
3 6
1 21
1 20
3 15
1 8
3 21
3 32
2 23
2 17
3 9
2 20
3 31
1 27
1 6
1 5
2 25
1 33
2 4
1 4
3 3
2 5
1 20
3 19
3 26
3 24
1 7
1 31
2 15
3 18
3 8
3 25
3 4
3 29
3 6
2 21
3 30
3 32
3 23
2 20
2 2
1 17
3 15
1 1
2 14
1 13

output:

5
3 9 2 5 ULLLL
1 17 2 14 DLLLP
1 22 1 17 LLLLL
1 27 3 25 DDLLP
2 23 3 23 DPPPP
3 15 3 15 PPPPP
1 6 1 1 LLLLL
1 23 2 25 RRDPP
3 7 3 4 LLLPP
3 24 3 24 PPPPP
3 6 1 4 UULLP
1 5 3 3 LLDDP
1 14 1 13 LPPPP
2 20 2 20 PPPPP
1 9 1 7 LLPPP
3 28 3 26 LLPPP
1 8 2 4 DLLLL
1 21 3 19 LDDLP
1 29 3 30 RDDPP
3 11 3 6...

result:

ok answer 5

Test #77:

score: 0
Accepted
time: 2ms
memory: 3724kb

input:

30 4 25
4 1
1 7
3 12
3 4
4 9
3 22
3 7
1 20
2 17
4 21
4 4
1 14
1 1
2 22
1 25
2 4
1 13
3 18
3 20
4 3
1 3
2 2
2 21
3 14
1 6
4 16
1 2
1 24
1 4
4 14
1 22
4 7
2 4
3 13
2 10
1 8
4 6
1 16
3 18
1 7
4 4
3 6
2 24
3 24
1 10
1 4
2 25
4 14
3 8
1 21
2 19
1 5
1 20
2 11
1 3
4 10
4 2
3 15
2 16
3 19

output:

3
3 14 3 13 LPP
1 4 1 7 RRR
4 16 3 15 ULP
2 4 3 6 RRD
3 7 3 8 RPP
4 3 4 4 RPP
3 12 2 10 ULL
4 14 4 14 PPP
2 22 1 22 UPP
1 13 2 11 DLL
2 17 1 16 ULP
1 24 2 25 RDP
2 21 1 21 UPP
1 25 2 24 DLP
3 18 3 18 PPP
1 20 1 20 PPP
1 1 1 4 RRR
1 6 1 8 RRP
4 21 3 19 ULL
4 9 4 10 RPP
1 3 1 3 PPP
4 4 4 7 RRR
3 22 3 ...

result:

ok answer 3

Test #78:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

30 5 20
1 9
4 18
5 11
4 11
3 10
4 5
3 9
1 15
2 12
5 3
1 18
3 17
5 20
1 20
5 17
1 7
3 6
2 8
1 3
2 13
5 6
2 19
1 12
1 2
3 11
5 14
3 8
3 18
4 7
5 8
4 6
4 1
2 7
5 14
3 10
5 18
2 14
5 19
1 1
4 9
4 2
2 5
3 8
2 11
5 4
5 1
5 9
2 4
4 13
1 15
5 5
2 10
2 16
5 7
1 13
3 17
2 20
3 7
2 15
4 4

output:

4
1 12 2 10 DLLP
1 7 2 4 DLLL
5 8 5 4 LLLL
1 15 2 14 DLPP
5 11 4 9 ULLP
5 6 5 5 LPPP
2 8 3 7 DLPP
1 2 1 1 LPPP
3 17 3 17 PPPP
2 19 2 16 LLLP
5 17 5 14 LLLP
1 9 2 7 DLLP
3 10 3 10 PPPP
4 7 4 6 LPPP
5 20 5 19 LPPP
5 3 5 1 LLPP
2 12 2 11 LPPP
4 5 4 1 LLLL
2 13 1 13 UPPP
4 11 5 9 DLLP
4 18 5 18 DPPP
1 1...

result:

ok answer 4

Test #79:

score: 0
Accepted
time: 2ms
memory: 3872kb

input:

30 6 16
5 13
5 2
1 5
2 11
6 5
4 9
2 1
1 12
1 8
1 13
5 5
3 15
6 13
5 1
5 12
1 3
1 4
4 11
5 4
6 16
6 2
1 11
4 14
5 10
4 13
3 5
2 9
3 9
4 1
3 11
1 12
6 5
5 3
1 16
3 9
3 13
1 11
6 4
5 8
2 7
1 5
6 3
6 14
1 7
6 13
2 13
6 10
1 9
5 10
3 4
3 11
6 16
2 4
4 10
5 2
3 8
5 4
4 4
6 8
4 11

output:

3
4 14 3 13 ULP
3 11 3 11 PPP
6 13 6 13 PPP
1 12 1 12 PPP
2 9 3 8 DLP
5 5 6 5 DPP
4 13 4 10 LLL
5 4 5 4 PPP
1 11 1 11 PPP
1 13 2 13 DPP
2 11 1 9 LUL
1 8 2 7 DLP
5 12 6 10 DLL
6 5 6 8 RRR
2 1 2 4 RRR
5 13 6 14 RDP
1 5 1 5 PPP
3 5 4 4 DLP
5 10 5 10 PPP
4 11 4 11 PPP
6 16 6 16 PPP
6 2 6 4 RRP
1 3 3 4 R...

result:

ok answer 3

Test #80:

score: 0
Accepted
time: 2ms
memory: 3864kb

input:

30 7 14
7 2
7 11
1 6
5 4
2 10
3 11
7 9
5 2
5 14
5 13
2 3
3 10
7 8
2 2
4 9
5 10
2 6
6 8
2 7
3 12
7 4
1 1
6 13
6 5
6 9
6 14
1 3
4 11
4 5
5 8
2 11
2 9
1 6
5 10
3 1
7 2
2 14
6 14
7 4
4 2
4 4
7 1
2 8
3 11
5 11
1 5
4 12
3 7
5 4
3 6
5 8
3 14
7 3
6 9
6 11
5 12
3 9
4 13
3 5
1 1

output:

3
5 10 5 11 RPP
1 1 1 1 PPP
7 9 5 10 UUR
2 3 4 2 DDL
2 10 2 11 RPP
4 11 4 12 RPP
3 11 3 11 PPP
6 5 7 3 DLL
6 13 5 12 ULP
7 4 7 4 PPP
5 8 3 7 UUL
5 14 4 13 ULP
5 13 3 14 UUR
6 14 6 14 PPP
4 9 2 8 UUL
7 8 6 9 URP
2 6 3 5 DLP
4 5 4 4 LPP
5 2 7 1 DDL
5 4 5 4 PPP
3 12 2 14 URR
2 2 3 1 DLP
7 11 6 11 UPP
3...

result:

ok answer 3

Test #81:

score: 0
Accepted
time: 2ms
memory: 3944kb

input:

30 8 12
8 4
4 9
7 8
2 12
8 6
8 1
4 5
3 2
4 8
7 9
4 10
6 9
2 3
5 10
8 12
8 8
1 4
6 11
6 10
5 3
3 1
4 7
8 10
2 7
2 5
7 4
3 6
7 2
6 5
2 4
3 9
3 12
6 11
2 10
2 6
4 2
4 1
3 8
1 7
5 12
8 10
8 2
4 6
4 12
2 7
5 7
2 1
1 10
3 6
2 2
8 7
4 11
7 12
1 6
7 11
6 12
6 9
7 6
8 6
8 11

output:

3
8 4 8 7 RRR
4 9 4 11 RRP
7 8 6 9 URP
2 12 3 12 DPP
8 6 8 6 PPP
8 1 8 2 RPP
4 5 4 6 RPP
3 2 2 1 ULP
4 8 3 9 URP
7 9 8 11 RRD
4 10 1 10 UUU
6 9 6 12 RRR
2 3 2 6 RRR
5 10 4 12 RRU
8 12 7 12 UPP
8 8 8 10 RRP
1 4 1 6 RRP
6 11 6 11 PPP
6 10 5 12 URR
5 3 4 1 ULL
3 1 2 2 URP
4 7 3 8 URP
8 10 7 11 RSU
2 7 ...

result:

ok answer 3

Test #82:

score: 0
Accepted
time: 2ms
memory: 3732kb

input:

30 9 11
3 1
2 10
8 8
9 6
2 1
9 11
5 10
2 8
1 7
7 6
3 9
9 1
3 6
4 2
3 8
9 8
1 10
9 3
7 11
4 4
4 5
5 8
9 7
5 2
6 6
1 11
3 2
8 11
8 9
7 8
2 2
7 3
2 5
5 4
7 5
3 6
6 7
8 4
1 4
8 10
8 2
6 8
1 6
1 2
4 8
6 10
1 5
4 7
6 11
8 7
9 1
9 3
3 8
2 8
5 3
6 9
4 3
5 10
3 11
4 1

output:

3
3 1 2 2 URP
2 10 3 8 DLL
8 8 6 8 UUP
9 6 8 4 ULL
2 1 1 2 URP
9 11 8 10 ULP
5 10 5 10 PPP
2 8 1 6 ULL
1 7 1 5 LLP
7 6 7 3 LLL
3 9 4 8 DLP
9 1 9 1 PPP
3 6 2 5 ULP
4 2 5 3 RDP
3 8 3 6 LLP
9 8 8 7 ULP
1 10 2 8 DLL
9 3 9 3 PPP
7 11 6 10 ULP
4 4 1 4 UUU
4 5 4 3 LLP
5 8 4 7 ULP
9 7 6 7 UUU
5 2 8 2 DDD
6 ...

result:

ok answer 3

Test #83:

score: 0
Accepted
time: 2ms
memory: 3728kb

input:

30 10 10
9 4
1 8
5 8
8 4
8 3
10 2
4 1
5 2
9 7
4 5
8 9
7 7
8 10
7 5
2 8
6 3
8 5
7 2
9 5
6 7
8 1
6 10
4 2
1 1
1 9
2 6
4 3
2 10
6 5
6 8
1 9
7 4
10 6
8 1
5 10
3 4
5 4
7 3
1 3
1 2
10 1
10 3
4 10
3 6
3 2
1 1
1 6
2 6
7 7
6 9
8 3
6 2
4 3
6 5
1 5
10 5
6 4
9 3
5 1
4 9

output:

3
9 4 10 3 DLP
1 8 1 5 LLL
5 8 4 9 URP
8 4 9 3 DLP
8 3 8 3 PPP
10 2 10 1 LPP
4 1 3 2 URP
5 2 5 1 LPP
9 7 10 6 DLP
4 5 3 4 ULP
8 9 7 7 ULL
7 7 7 4 LLL
8 10 5 10 UUU
7 5 6 4 ULP
2 8 3 6 DLL
6 3 4 3 UUP
8 5 7 3 ULL
7 2 6 2 UPP
9 5 10 5 DPP
6 7 6 5 LLP
8 1 8 1 PPP
6 10 4 10 UUP
4 2 1 2 UUU
1 1 1 1 PPP
1...

result:

ok answer 3

Test #84:

score: 0
Accepted
time: 5ms
memory: 3928kb

input:

40 100 1
11 1
51 1
65 1
63 1
1 1
31 1
4 1
66 1
7 1
43 1
42 1
59 1
83 1
40 1
85 1
77 1
45 1
41 1
29 1
37 1
13 1
23 1
98 1
91 1
62 1
30 1
81 1
22 1
72 1
49 1
12 1
47 1
88 1
73 1
28 1
79 1
84 1
54 1
76 1
18 1
91 1
28 1
20 1
89 1
76 1
25 1
12 1
79 1
66 1
70 1
49 1
37 1
17 1
24 1
95 1
64 1
98 1
48 1
84 1...

output:

10
73 1 79 1 DDDDDDPPPP
63 1 73 1 DDDDDDDDDD
76 1 86 1 DDDDDDDDDD
91 1 100 1 DDDDDDDDDP
1 1 1 1 PPPPPPPPPP
22 1 25 1 DDDPPPPPPP
59 1 66 1 DDDDDDDPPP
72 1 78 1 DDDDDDPPPP
85 1 95 1 DDDDDDDDDD
40 1 40 1 PPPPPPPPPP
18 1 20 1 DDPPPPPPPP
45 1 45 1 PPPPPPPPPP
54 1 64 1 DDDDDDDDDD
81 1 91 1 DDDDDDDDDD
47 1...

result:

ok answer 10

Test #85:

score: 0
Accepted
time: 4ms
memory: 3744kb

input:

40 50 2
28 1
32 2
20 2
49 2
43 2
1 1
49 1
28 2
48 2
40 1
30 2
47 2
25 1
5 2
33 1
46 1
12 2
8 2
21 2
14 2
47 1
16 1
13 2
14 1
10 1
15 2
15 1
41 1
39 2
17 1
18 2
25 2
26 2
9 2
23 2
3 2
35 2
26 1
8 1
4 2
41 1
47 1
9 1
6 1
46 2
8 2
25 2
43 1
5 2
21 1
40 2
36 1
42 2
48 2
25 1
48 1
44 2
45 1
47 2
30 1
6 2...

output:

9
8 1 8 1 PPPPPPPPP
48 2 48 2 PPPPPPPPP
14 1 22 2 DDRDDDDDD
26 2 35 2 DDDDDDDDD
33 1 41 1 DDDDDDDDP
32 2 39 1 DDDDDDDLP
41 1 44 1 DDDPPPPPP
13 2 6 1 UUUUUUULP
16 1 18 2 RDDPPPPPP
18 2 25 2 DDDDDDDPP
35 2 43 1 DDDDDDDDL
23 2 27 2 DDDDPPPPP
3 2 2 1 ULPPPPPPP
40 1 42 2 DRDPPPPPP
26 1 26 1 PPPPPPPPP
14 ...

result:

ok answer 9

Test #86:

score: 0
Accepted
time: 3ms
memory: 3772kb

input:

40 33 3
23 3
14 1
32 2
28 2
21 3
26 1
9 2
9 1
7 3
19 3
14 3
12 1
3 3
4 2
16 3
33 1
29 1
11 3
8 3
5 2
29 3
25 3
3 2
27 1
5 1
1 3
25 2
9 3
28 3
16 1
22 3
4 3
17 3
30 1
23 1
24 1
24 2
26 3
4 1
1 1
24 2
22 3
30 2
2 3
4 3
6 3
6 1
11 2
33 3
10 1
7 1
11 3
20 3
14 3
14 1
26 2
15 1
1 3
2 1
10 2
8 1
23 1
13 2...

output:

8
3 2 2 3 URPPPPPP
1 3 1 3 PPPPPPPP
24 2 16 2 UUUUUUUU
1 1 2 1 DPPPPPPP
4 3 4 3 PPPPPPPP
28 2 27 3 URPPPPPP
14 1 14 1 PPPPPPPP
9 3 10 2 DLPPPPPP
29 3 31 3 DDPPPPPP
29 1 30 2 RDPPPPPP
19 3 13 2 UUUUUULP
22 3 14 3 UUUUUUUU
7 3 6 3 UPPPPPPP
11 3 11 3 PPPPPPPP
14 3 12 3 UUPPPPPP
26 3 20 3 UUUUUUPP
3 3 3...

result:

ok answer 8

Test #87:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

40 25 4
9 1
5 4
25 1
1 2
2 3
24 3
19 1
8 2
19 3
5 3
8 1
8 4
8 3
15 3
7 3
18 4
5 1
25 4
12 4
24 2
23 3
3 1
19 4
5 2
13 4
17 4
18 3
11 1
23 4
17 2
18 1
14 4
25 3
3 4
6 2
7 2
21 1
24 4
20 4
9 4
22 4
4 2
15 4
25 1
9 4
19 1
8 4
16 2
10 4
14 1
16 1
17 3
21 1
17 1
19 3
9 1
23 1
18 1
21 3
24 3
6 3
20 3
9 2
...

output:

4
9 1 12 1 DDDP
5 4 6 3 DLPP
25 1 25 1 PPPP
1 2 1 1 LPPP
2 3 4 3 DDPP
24 3 24 3 PPPP
19 1 19 1 PPPP
8 2 10 4 RRDD
19 3 17 1 UULL
5 3 5 3 PPPP
8 1 9 2 RDPP
8 4 12 4 DDDD
8 3 9 3 DPPP
15 3 16 2 DLPP
7 3 9 1 LDLD
18 4 18 4 PPPP
5 1 6 1 DPPP
25 4 22 4 UUUP
12 4 15 4 DDDP
24 2 21 1 UUUL
23 3 20 3 UUUP
3 ...

result:

ok answer 4

Test #88:

score: 0
Accepted
time: 3ms
memory: 3744kb

input:

40 20 5
2 2
13 3
6 2
15 1
2 3
12 2
9 1
13 1
10 5
4 5
14 1
17 1
10 1
2 5
8 3
16 5
6 5
5 3
4 2
11 2
9 3
7 2
18 5
4 3
6 3
7 4
12 4
17 2
9 4
20 1
3 4
8 4
16 4
12 5
9 2
13 5
11 3
1 4
17 4
1 2
8 4
19 4
3 5
15 4
14 4
17 3
13 3
17 4
15 2
11 5
9 5
1 3
20 3
11 3
3 2
1 1
9 4
12 3
2 4
4 2
2 2
6 4
17 5
4 4
12 1
...

output:

2
17 4 17 4 PP
12 2 12 2 PP
11 3 11 3 PP
2 3 3 2 DL
4 3 4 4 RP
18 5 19 4 DL
3 4 2 4 UP
13 3 13 3 PP
6 3 6 1 LL
2 2 2 2 PP
16 5 15 4 UL
9 2 8 1 UL
12 4 12 3 LP
20 1 20 3 RR
4 2 4 2 PP
8 3 9 2 DL
2 5 2 5 PP
12 5 11 5 UP
4 5 3 5 UP
10 5 9 5 UP
5 3 6 4 RD
17 1 17 3 RR
9 3 10 2 DL
14 1 15 2 RD
6 2 6 2 PP...

result:

ok answer 2

Test #89:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

40 16 6
10 6
7 5
5 1
8 1
7 3
16 3
9 1
15 6
16 2
7 2
12 5
4 5
11 3
4 2
9 3
9 4
10 2
15 5
2 1
5 4
2 4
1 6
2 2
6 3
6 5
14 6
7 4
1 2
8 4
11 5
13 5
11 4
10 3
5 2
1 4
15 2
2 5
1 3
12 6
4 6
1 4
7 2
2 4
11 6
9 4
9 6
4 3
5 4
8 6
9 5
1 3
14 3
11 1
11 5
16 2
8 5
2 1
12 3
16 5
8 3
12 2
15 4
3 6
6 3
11 3
15 5
7 ...

output:

3
10 6 11 6 DPP
7 5 9 6 RDD
5 1 7 2 RDD
8 1 11 1 DDD
7 3 8 3 DPP
16 3 16 3 PPP
9 1 12 1 DDD
15 6 16 5 DLP
16 2 16 2 PPP
7 2 9 1 DDL
12 5 12 5 PPP
4 5 5 4 DLP
11 3 14 3 DDD
4 2 4 1 LPP
9 3 11 3 DDP
9 4 9 4 PPP
10 2 13 2 DDD
15 5 16 4 DLP
2 1 2 1 PPP
5 4 8 4 DDD
2 4 4 3 DDL
1 6 2 4 DLL
2 2 3 2 DPP
6 3...

result:

ok answer 3

Test #90:

score: 0
Accepted
time: 3ms
memory: 3712kb

input:

40 14 7
6 4
3 6
6 2
5 6
7 4
7 5
3 3
13 4
9 5
12 3
9 6
8 6
10 6
9 2
4 2
14 5
11 6
11 3
5 2
5 1
2 6
4 4
4 6
9 1
8 3
13 1
3 1
4 5
12 5
12 6
4 7
13 7
8 4
11 2
14 7
7 2
11 7
6 5
1 2
1 3
2 7
5 4
12 2
2 1
14 4
2 6
5 1
14 2
2 4
10 4
1 2
7 2
11 3
6 1
9 7
5 2
13 6
7 5
14 3
9 5
7 4
14 7
2 2
7 1
10 5
6 4
9 1
12...

output:

3
4 5 2 6 UUR
3 3 3 3 PPP
11 7 11 7 PPP
3 6 3 6 PPP
6 4 6 4 PPP
9 1 9 1 PPP
4 4 2 4 UUP
9 2 7 1 UUL
13 4 14 3 DLP
2 6 1 6 UPP
13 7 13 6 LPP
9 6 9 7 RPP
1 2 1 2 PPP
14 7 14 7 PPP
7 2 7 2 PPP
11 6 10 4 ULL
6 5 5 4 ULP
11 2 11 1 LPP
7 5 7 5 PPP
1 3 2 2 DLP
12 3 14 2 DLD
8 4 7 3 ULP
5 2 5 2 PPP
13 1 14 ...

result:

ok answer 3

Test #91:

score: 0
Accepted
time: 2ms
memory: 3940kb

input:

40 12 8
2 3
10 7
4 5
10 1
11 6
2 7
8 5
8 4
4 7
12 2
3 6
5 5
4 4
7 4
8 7
4 1
3 7
9 4
10 3
5 2
3 1
6 6
5 3
2 4
1 1
11 1
6 5
6 2
5 1
12 6
9 6
4 3
3 5
9 3
3 2
6 8
12 7
7 3
1 7
7 1
5 6
10 5
5 1
4 3
2 3
9 7
12 2
2 2
6 5
1 6
9 3
3 5
10 8
4 4
4 6
12 5
10 4
4 7
2 6
7 6
7 3
3 3
2 7
12 6
9 2
8 1
8 5
12 4
1 1
7...

output:

2
8 7 9 8 RD
3 6 2 6 UP
3 2 3 3 RP
2 3 2 3 PP
5 2 4 3 UR
3 7 4 8 RD
10 1 9 2 UR
9 3 10 4 RD
5 1 5 1 PP
12 7 12 5 LL
7 1 8 1 DP
7 4 7 4 PP
11 1 12 2 RD
10 3 11 3 DP
5 3 5 4 RP
11 6 11 5 LP
6 6 7 6 DP
4 3 3 4 RU
8 5 9 6 RD
2 4 3 5 RD
3 5 4 6 RD
12 2 12 4 RR
4 1 2 1 UU
2 7 2 7 PP
6 8 7 8 DP
4 4 4 4 PP
...

result:

ok answer 2

Test #92:

score: 0
Accepted
time: 4ms
memory: 3788kb

input:

40 11 9
3 4
5 7
6 3
4 8
7 8
4 4
2 7
7 1
8 5
1 8
5 4
10 3
2 8
3 2
11 6
4 7
7 5
1 6
10 2
5 6
11 8
2 4
9 8
8 6
4 5
3 5
9 4
2 1
4 6
1 2
6 7
3 7
2 2
2 9
8 3
2 5
4 2
5 5
8 7
3 8
9 2
5 5
8 3
4 8
5 2
7 5
1 9
1 4
2 1
10 7
3 3
4 3
8 9
4 4
4 6
8 7
3 1
7 2
8 4
11 6
10 9
2 6
7 7
7 4
5 6
9 5
11 7
6 5
8 2
3 6
9 4
...

output:

3
10 3 8 4 UUR
9 4 9 4 PPP
3 5 5 6 RDD
8 7 8 7 PPP
4 5 7 5 DDD
3 8 3 8 PPP
11 8 11 7 LPP
7 8 8 9 RDP
3 7 4 6 DSL
7 5 8 6 RDP
5 7 7 6 DDL
4 6 5 5 DLP
3 4 3 4 PPP
6 7 8 8 RDD
4 7 7 7 DDD
2 8 4 8 DDP
1 6 2 6 DPP
8 5 9 5 DPP
6 3 7 2 DLP
11 6 11 6 PPP
4 2 4 2 PPP
9 8 10 9 RDP
5 4 6 3 DLP
2 5 1 4 ULP
5 5 ...

result:

ok answer 3

Test #93:

score: 0
Accepted
time: 3ms
memory: 3720kb

input:

40 10 10
9 6
10 8
2 10
7 1
4 1
4 9
5 5
1 10
8 5
5 1
6 10
10 7
8 4
1 9
8 10
8 7
2 1
2 9
4 10
1 3
9 8
10 5
2 2
8 2
1 1
9 7
9 4
6 4
2 7
5 3
8 3
10 10
6 6
6 8
5 8
3 10
1 4
3 6
3 5
9 2
5 7
8 10
10 5
10 7
10 1
4 9
10 10
4 7
3 8
2 4
6 10
3 2
10 2
10 3
5 6
2 1
7 9
3 5
6 5
9 2
8 2
4 4
7 5
7 1
9 4
5 9
4 1
7 2...

output:

3
9 6 9 5 LPP
10 8 10 8 PPP
2 10 4 9 DDL
7 1 9 1 DDP
4 1 4 1 PPP
4 9 5 7 DLL
5 5 6 5 DPP
1 10 2 8 DLL
8 5 8 5 PPP
5 1 7 1 DDP
6 10 6 10 PPP
10 7 10 7 PPP
8 4 9 2 DLL
1 9 1 6 LLL
8 10 8 10 PPP
8 7 7 7 UPP
2 1 2 1 PPP
2 9 3 8 DLP
4 10 5 9 DLP
1 3 2 4 RDP
9 8 9 8 PPP
10 5 10 3 LLP
2 2 5 2 DDD
8 2 8 2 P...

result:

ok answer 3

Test #94:

score: 0
Accepted
time: 5ms
memory: 3808kb

input:

50 1 100
1 86
1 2
1 25
1 77
1 98
1 59
1 57
1 76
1 38
1 55
1 43
1 64
1 54
1 91
1 16
1 13
1 93
1 26
1 9
1 78
1 42
1 89
1 32
1 23
1 14
1 69
1 63
1 94
1 7
1 46
1 84
1 71
1 41
1 65
1 48
1 17
1 8
1 22
1 39
1 99
1 72
1 73
1 5
1 31
1 83
1 44
1 100
1 15
1 75
1 10
1 42
1 75
1 19
1 43
1 100
1 77
1 40
1 87
1 61...

output:

10
1 7 1 7 PPPPPPPPPP
1 84 1 75 LLLLLLLLLP
1 99 1 99 PPPPPPPPPP
1 86 1 77 LLLLLLLLLP
1 42 1 35 LLLLLLLPPP
1 77 1 67 LLLLLLLLLL
1 13 1 21 RRRRRRRRPP
1 39 1 36 LLLPPPPPPP
1 72 1 70 LLPPPPPPPP
1 57 1 47 LLLLLLLLLL
1 9 1 18 RRRRRRRRRP
1 65 1 56 LLLLLLLLLP
1 10 1 12 RRPPPPPPPP
1 73 1 68 LLLLLPPPPP
1 23 1...

result:

ok answer 10

Test #95:

score: 0
Accepted
time: 2ms
memory: 3956kb

input:

50 2 50
2 29
2 27
1 19
2 24
2 38
1 41
1 44
1 47
1 35
2 8
1 45
2 20
1 7
1 13
2 48
2 36
2 11
2 7
2 49
1 48
2 1
1 34
2 33
1 12
1 31
2 35
1 16
1 15
2 14
2 50
1 1
2 16
2 32
1 49
2 39
1 40
1 38
1 23
2 46
1 5
1 25
1 26
1 42
1 33
1 10
1 39
1 37
2 43
1 21
1 9
2 17
1 16
2 43
2 49
2 28
2 13
1 49
1 17
1 24
1 27...

output:

6
2 36 2 31 LLLLLP
1 37 1 32 LLLLLP
2 32 2 26 LLLLLL
2 35 2 29 LLLLLL
2 50 2 50 PPPPPP
2 14 2 14 PPPPPP
1 42 1 42 PPPPPP
2 16 2 16 PPPPPP
2 1 2 1 PPPPPP
1 19 2 17 LDLPPP
1 45 1 45 PPPPPP
2 29 1 24 ULLLLL
1 16 1 16 PPPPPP
1 39 2 36 LDLLPP
1 1 1 4 RRRPPP
1 9 1 9 PPPPPP
1 25 2 20 DLLLLL
1 26 1 20 LLLLL...

result:

ok answer 6

Test #96:

score: 0
Accepted
time: 5ms
memory: 3892kb

input:

50 3 33
2 20
1 33
1 14
2 25
3 6
2 5
1 18
3 24
2 26
1 13
3 9
2 22
2 30
3 30
1 10
1 6
3 19
3 31
2 15
3 4
1 4
3 32
1 17
3 28
3 17
3 21
1 25
3 14
2 4
1 30
3 15
3 22
2 3
2 10
3 16
3 2
1 9
2 28
1 11
2 6
1 8
3 10
2 17
3 18
2 2
2 9
1 1
3 26
1 20
1 19
1 2
3 16
3 1
1 32
2 11
2 28
2 5
2 1
3 7
1 11
3 9
1 24
1 6...

output:

4
2 30 3 33 RRRD
2 3 1 2 ULPP
3 6 3 7 RPPP
3 32 3 32 PPPP
2 20 3 23 RRRD
3 2 3 2 PPPP
1 17 1 21 RRRR
3 16 2 19 URRR
2 28 1 31 URRR
2 5 3 8 RRRD
3 26 2 28 URRP
1 8 2 8 DPPP
3 18 3 18 PPPP
1 9 1 9 PPPP
1 4 1 4 PPPP
1 20 1 24 RRRR
3 9 3 9 PPPP
1 11 1 11 PPPP
1 1 2 1 SDPP
1 6 1 6 PPPP
3 24 2 27 URRR
2 9...

result:

ok answer 4

Test #97:

score: 0
Accepted
time: 5ms
memory: 3784kb

input:

50 4 25
2 15
2 1
3 15
4 15
3 20
2 14
3 13
1 11
4 19
1 21
2 9
1 14
2 24
3 18
3 3
1 20
2 10
4 25
1 10
2 20
2 18
4 22
4 23
4 12
1 1
3 7
4 1
4 14
1 12
1 3
1 9
1 22
1 18
1 17
1 23
2 22
2 2
4 17
2 16
1 2
3 5
3 25
1 16
4 5
4 16
4 9
3 9
1 13
4 3
2 5
2 15
4 16
2 25
3 16
3 1
2 20
4 14
4 13
3 17
1 16
2 11
4 19...

output:

3
2 15 2 15 PPP
2 1 1 3 URR
3 15 4 14 DLP
4 15 4 13 LLP
3 20 4 21 RDP
2 14 3 13 DLP
3 13 3 10 LLL
1 11 1 11 PPP
4 19 4 19 PPP
1 21 2 20 DLP
2 9 2 9 PPP
1 14 1 14 PPP
2 24 2 24 PPP
3 18 3 17 LPP
3 3 3 5 RRP
1 20 2 19 DLP
2 10 2 10 PPP
4 25 2 25 UUP
1 10 1 10 PPP
2 20 3 19 DLP
2 18 2 18 PPP
4 22 4 22 ...

result:

ok answer 3

Test #98:

score: 0
Accepted
time: 5ms
memory: 3784kb

input:

50 5 20
4 11
1 18
3 13
3 17
2 14
4 17
1 8
2 5
2 12
2 20
1 2
1 5
4 6
3 3
3 4
3 2
2 3
1 20
2 6
1 19
3 7
5 20
3 11
5 17
5 11
2 16
1 1
4 13
5 14
3 19
3 18
4 4
1 9
5 18
5 1
4 15
4 5
4 10
4 3
5 16
2 1
2 18
3 14
3 10
1 4
2 9
5 3
3 8
5 5
5 8
4 10
1 14
1 5
1 11
4 9
4 12
4 2
1 12
4 11
3 20
4 6
2 16
4 18
3 7
2...

output:

3
3 3 1 3 UUP
5 17 5 15 LLP
1 8 2 8 DPP
1 19 3 20 RDD
3 14 2 13 ULP
2 1 3 1 DPP
3 19 3 19 PPP
1 9 2 10 RDP
3 4 4 6 RRD
5 14 4 12 LUL
3 18 4 19 RDP
1 18 1 18 PPP
2 16 2 16 PPP
5 20 5 20 PPP
2 9 1 11 URR
2 18 1 17 ULP
5 18 4 18 UPP
4 6 4 9 RRR
2 12 1 12 UPP
3 13 3 13 PPP
1 5 1 5 PPP
2 14 1 14 UPP
5 3 ...

result:

ok answer 3

Test #99:

score: 0
Accepted
time: 5ms
memory: 3852kb

input:

50 6 16
1 4
3 11
4 3
5 5
2 13
4 14
2 14
3 10
2 8
5 10
4 9
2 16
1 8
3 1
1 14
3 13
6 6
3 9
6 4
2 11
2 2
3 7
6 13
4 11
3 16
5 13
4 7
1 16
1 2
5 9
3 12
1 10
5 15
5 16
2 15
5 11
5 4
1 15
4 6
2 1
4 1
4 15
3 14
1 12
4 13
3 15
4 5
5 7
5 6
2 7
3 16
6 5
5 13
5 9
6 13
6 16
4 2
3 9
3 11
6 9
1 10
4 1
3 15
4 7
4 ...

output:

4
2 11 2 11 PPPP
1 10 2 7 DLLL
4 1 4 1 PPPP
1 16 1 13 LLLP
6 6 5 3 ULLL
2 13 3 10 DLLL
2 8 4 6 DDLL
3 15 3 15 PPPP
2 14 3 11 LDLL
3 12 2 10 ULLP
3 13 3 9 LLLL
3 16 3 16 PPPP
5 7 6 4 DLLL
4 14 6 12 DDLL
4 11 6 9 DDLL
1 12 2 9 LLLD
2 1 2 1 PPPP
1 8 1 5 LLLP
2 16 6 16 DDDD
1 15 2 13 DLLP
5 9 5 5 LLLL
3...

result:

ok answer 4

Test #100:

score: 0
Accepted
time: 4ms
memory: 3852kb

input:

50 7 14
2 9
7 11
3 7
5 9
1 7
1 5
2 13
1 4
3 11
2 12
5 14
4 4
4 3
4 13
3 3
4 11
7 14
6 12
6 13
5 10
3 1
4 9
2 4
6 8
3 8
4 1
6 3
1 6
5 13
7 9
5 3
2 10
3 10
4 10
3 6
4 2
7 5
5 7
2 2
5 6
6 11
6 1
6 9
2 5
5 2
5 4
2 1
5 8
2 3
4 8
3 1
3 7
6 1
7 14
7 6
7 5
6 2
3 4
4 7
4 1
6 5
2 7
4 5
6 14
7 8
1 13
5 5
5 10
...

output:

2
2 9 2 11 RR
7 11 7 11 PP
3 7 3 7 PP
5 9 5 11 RR
1 7 1 7 PP
1 5 2 6 RD
2 13 2 14 RP
1 4 1 4 PP
3 11 2 12 UR
2 12 1 13 UR
5 14 4 13 UL
4 4 5 5 RD
4 3 3 4 UR
4 13 2 13 UU
3 3 3 3 PP
4 11 3 12 UR
7 14 7 14 PP
6 12 7 13 RD
6 13 6 14 RP
5 10 6 11 RD
3 1 3 1 PP
4 9 4 9 PP
2 4 2 4 PP
6 8 7 8 DP
3 8 3 9 RP...

result:

ok answer 2

Test #101:

score: 0
Accepted
time: 5ms
memory: 3860kb

input:

50 8 12
6 7
5 5
3 2
4 9
6 10
8 10
8 9
1 5
5 2
7 12
5 7
2 9
4 10
2 8
1 2
7 5
6 1
2 11
3 5
4 1
5 6
2 12
2 6
7 4
5 12
8 11
1 11
4 12
5 9
1 3
7 2
7 10
4 11
7 6
8 4
1 10
4 7
8 1
1 4
7 11
5 11
3 4
2 4
6 8
4 2
1 7
6 3
1 6
3 1
5 4
5 8
2 3
3 9
4 8
8 12
5 11
3 10
5 1
5 2
2 8
6 2
6 3
1 11
7 5
1 9
2 4
7 12
4 9
...

output:

3
8 4 8 2 LLP
6 10 5 10 UPP
1 4 1 4 PPP
1 2 2 2 DPP
4 10 3 9 ULP
6 1 6 2 RPP
8 1 8 1 PPP
2 12 1 12 UPP
8 9 8 6 LLL
7 5 7 5 PPP
7 4 7 3 LPP
4 9 2 10 UUR
2 11 2 11 PPP
2 8 2 8 PPP
6 7 5 8 URP
3 5 2 7 URR
5 6 6 5 LDP
2 4 2 4 PPP
5 5 6 4 DLP
7 11 6 12 URP
3 4 2 5 URP
5 7 5 7 PPP
4 7 4 7 PPP
8 11 8 12 RP...

result:

ok answer 3

Test #102:

score: 0
Accepted
time: 4ms
memory: 3820kb

input:

50 9 11
3 11
7 6
4 8
3 9
9 6
2 10
8 1
4 7
9 9
3 1
7 10
1 7
5 8
2 11
7 4
9 5
9 3
6 10
9 11
2 6
2 7
8 3
1 1
9 7
2 8
7 5
5 11
2 5
1 2
5 10
2 3
7 3
9 4
1 9
6 7
3 4
5 1
1 5
1 6
5 7
5 5
7 11
5 9
5 6
6 6
7 8
2 4
4 9
1 3
8 4
4 5
6 6
5 3
6 4
9 9
5 9
7 8
1 10
9 10
6 3
2 2
1 8
6 11
1 3
9 1
7 11
1 4
1 7
2 6
6 5...

output:

2
6 10 8 10 DD
2 5 1 4 UL
1 2 2 2 DP
6 6 6 6 PP
1 3 1 3 PP
9 9 9 9 PP
7 3 6 2 UL
5 6 4 5 UL
4 9 3 10 UR
8 4 7 4 UP
5 8 6 9 RD
6 7 7 8 RD
9 6 9 6 PP
4 8 4 10 RR
7 5 6 4 UL
2 7 2 7 PP
9 11 9 10 LP
3 9 3 9 PP
5 1 5 2 RP
5 7 6 8 RD
9 5 9 5 PP
1 6 1 6 PP
7 6 7 6 PP
9 7 9 7 PP
5 11 5 11 PP
7 10 7 10 PP
1 ...

result:

ok answer 2

Test #103:

score: 0
Accepted
time: 4ms
memory: 3924kb

input:

50 10 10
7 4
8 5
10 2
6 7
8 10
9 5
7 6
8 7
7 3
9 8
6 1
10 7
3 5
4 10
9 7
10 6
8 3
7 7
5 1
9 3
1 3
2 7
7 2
6 2
10 4
7 9
2 8
5 2
2 9
3 7
1 4
3 9
3 10
8 8
5 3
7 1
8 9
1 8
2 10
9 10
1 10
9 1
2 6
10 5
5 4
6 5
10 1
5 7
10 8
10 3
8 6
8 8
7 8
7 1
10 9
2 4
7 5
10 5
7 9
6 1
10 6
10 2
7 4
4 1
3 7
2 3
6 10
2 6
...

output:

2
6 5 6 6 RP
7 1 7 1 PP
8 8 8 8 PP
7 6 7 8 RR
10 4 9 5 UR
10 6 10 6 PP
6 1 6 1 PP
2 10 2 9 LP
1 4 2 3 DL
9 5 8 6 UR
5 3 4 4 UR
10 5 10 5 PP
8 7 8 7 PP
1 10 1 10 PP
6 2 6 4 RR
1 3 2 2 DL
7 3 7 5 RR
2 7 2 6 LP
10 1 10 1 PP
5 7 3 7 UU
6 7 5 7 UP
9 7 9 7 PP
5 1 3 1 UU
10 7 10 7 PP
2 8 1 7 UL
10 3 9 3 UP...

result:

ok answer 2

Test #104:

score: 0
Accepted
time: 21ms
memory: 3804kb

input:

60 100 1
65 1
1 1
55 1
98 1
4 1
96 1
91 1
64 1
88 1
62 1
99 1
12 1
18 1
87 1
84 1
6 1
22 1
59 1
66 1
61 1
89 1
24 1
10 1
80 1
9 1
54 1
40 1
78 1
90 1
75 1
74 1
27 1
51 1
56 1
60 1
70 1
86 1
35 1
95 1
41 1
29 1
67 1
30 1
69 1
44 1
34 1
39 1
48 1
85 1
92 1
3 1
58 1
77 1
49 1
43 1
47 1
73 1
16 1
83 1
6...

output:

18
99 1 99 1 PPPPPPPPPPPPPPPPPP
84 1 84 1 PPPPPPPPPPPPPPPPPP
40 1 22 1 UUUUUUUUUUUUUUUUUU
6 1 6 1 PPPPPPPPPPPPPPPPPP
51 1 34 1 UUUUUUUUUUUUUUUUUP
85 1 85 1 PPPPPPPPPPPPPPPPPP
68 1 50 1 UUUUUUUUUUUUUUUUUU
61 1 43 1 UUUUUUUUUUUUUUUUUU
88 1 70 1 UUUUUUUUUUUUUUUUUU
47 1 29 1 UUUUUUUUUUUUUUUUUU
4 1 4 1 P...

result:

ok answer 18

Test #105:

score: -100
Time Limit Exceeded

input:

60 50 2
6 1
2 2
1 2
41 2
20 1
2 1
4 2
48 1
37 1
43 2
40 1
42 1
6 2
36 1
48 2
32 1
7 1
33 1
30 2
27 2
40 2
12 2
17 2
15 2
10 2
11 2
49 2
8 1
28 1
42 2
13 1
46 2
24 2
15 1
46 1
50 1
21 2
29 1
47 2
39 1
35 2
1 1
30 1
37 2
14 2
25 1
25 2
24 1
26 2
45 1
7 2
38 1
3 2
29 2
19 2
12 1
28 2
19 1
49 1
35 1
38 ...

output:

5

result: