QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#836063#6615. Cross the MazelyxAC ✓16ms10640kbC++143.4kb2024-12-28 16:18:402024-12-28 16:18:46

Judging History

This is the latest submission verdict.

  • [2024-12-28 16:18:46]
  • Judged
  • Verdict: AC
  • Time: 16ms
  • Memory: 10640kb
  • [2024-12-28 16:18:40]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define ri register int
#define fo(i,x,y) for(ri i=(x);i<=(y);++i)
#define fu(i,x,y) for(ri i=(x);i<(y);++i)
#define fd(i,x,y) for(ri i=(x);i>=(y);--i)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N=205,M=2e5+5;
int n,A,B,S,T,tt,to[M],nt[M],hd[M],v[M],cnt;
int cur[M],dis[M],q[M],jl[M],ne[M];
int fx[4][2]={0,1,0,-1,1,0,-1,0};
struct nd{int x,y;}a[N],b[N];
inline void air(){}
inline nd jm(ri x){
	x%=A*B;if(!x)x=A*B;
	nd op;
	op.x=(x-1)/B+1;
	op.y=x-(op.x-1)*B;
	return op;
}
inline int id(ri x,ri y,ri z){return (x-1)*A*B+(y-1)*B+z;}
inline int operator==(nd x,nd y){
	return x.x==y.x&&x.y==y.y;
}
inline int cmp(nd x,nd y){
	if(x.x!=y.x)return x.x<y.x;
	return x.y<y.y;
}
inline void add(ri x,ri y,ri z){
	to[++tt]=y;nt[tt]=hd[x];hd[x]=tt;v[tt]=z;
//	if(tt==478)
//	air();
}
inline void link(ri x,ri y,ri z){add(x,y,z);add(y,x,0);}
inline int bfs(){
	ri h=0,t=1;q[1]=S;
	fo(i,1,T)dis[i]=1e9,cur[i]=hd[i];
	dis[S]=0;
	while(h<t){
		ri x=q[++h];
		for(ri i=hd[x];i;i=nt[i]){
			ri y=to[i];
			if(dis[y]==1e9&&v[i]){
				dis[y]=dis[x]+1;
				q[++t]=y;
			}
		}
	}
	return dis[T]!=1e9;
}
inline int dfs(ri x,ri fw){
	if(x==T||!fw)return fw;
	ri nd=0;
//	if(x==88)
//	air();
	for(ri i=cur[x];i&&fw;i=nt[i]){
		ri y=to[i];cur[x]=i;
		if(dis[y]==dis[x]+1&&v[i]){
			ri Fw=dfs(y,min(v[i],fw));
			if(!Fw)dis[y]=1e9;
			else{
				v[i]-=Fw;v[i^1]+=Fw;
				fw-=Fw;nd+=Fw;
				if(i%2==0)ne[x]=y;
//				if(x==99||y==99)
//				air();
			}
		}
	}
	return nd;
}
inline int check(ri lim){
	fo(i,1,T)hd[i]=0;
	fo(i,1,tt)to[i]=nt[i]=v[i]=0;
	S=2*lim*A*B+n+1;T=S+1;
	tt=1;
	fo(i,1,n){
		link(S,id(1,a[i].x,a[i].y),1);
		link(2*lim*A*B+i,T,1);
	}
	fo(t,1,lim){
		fo(i,1,n){
			link(id(t+lim,b[i].x,b[i].y),2*lim*A*B+i,1);
		}
		fo(i,1,A)fo(j,1,B){
//			if(tt==477)
//			air();
			link(id(t,i,j),id(t+lim,i,j),1);
			if(t<lim){
				fo(k,0,3){
					ri x=i+fx[k][0],y=j+fx[k][1];
					if(!x||!y||x>A||y>B)continue;
					link(id(t+lim,i,j),id(t+1,i,j),1);
					link(id(t+lim,i,j),id(t+1,x,y),1);
				}
			}
		}
	}
	ri s=0;
	while(bfs()){
		s+=dfs(S,1e9);
	}
	return s==n;
}
int main(){
//	freopen("B.in","r",stdin);
//	freopen("B.out","w",stdout);
	scanf("%d%d%d",&n,&A,&B);
	fo(i,1,n){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	fo(i,1,n){
		scanf("%d%d",&b[i].x,&b[i].y);
	}
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+n,cmp);
	ri PD=0;
	fo(i,1,n){
		if(!(a[i]==b[i]))PD=1;
	}
	if(!PD){
		fo(i,1,n){
			printf("%d %d %d %d\n",a[i].x,a[i].y,b[i].x,b[i].y);
		}
		return 0;
	}
	S=2*n+1;T=S+1;
	ri l=1,r=(A+B)*2;
	while(l<=r){
		ri md=l+r>>1;
		if(check(md))r=md-1;
		else l=md+1;
	}
	printf("%d\n",r);
	check(r+1);
	fo(i,1,n){
		ri u=id(1,a[i].x,a[i].y);
		ri m=0,la=0;
		while(u!=T){
			u=ne[u];jl[++m]=u;
		}
		nd o=jm(jl[m-2]);
		printf("%d %d %d %d ",a[i].x,a[i].y,o.x,o.y);
		nd nw=a[i];ri cc=0;
		for(ri j=2;j<m-2;j+=2){
			nd ou=jm(jl[j]);
			if(ou.x-nw.x==1)putchar('D');
			else if(ou.x-nw.x==-1)putchar('U');
			else if(ou.y-nw.y==1)putchar('R');
			else if(ou.y-nw.y==-1)putchar('L');
			else putchar('S');
			++cc;nw=ou;
		}
		fo(j,1,r-cc)putchar('P');
		puts("");
	}
	cerr<<endl<<endl<<"time:"<<(double)clock()/CLOCKS_PER_SEC<<endl;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 10168kb

input:

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

output:

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

result:

ok answer 1

Test #3:

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

input:

2 3 3
1 1
1 3
1 2
2 2

output:

2
1 1 2 2 DR
1 3 1 2 LP

result:

ok answer 2

Test #4:

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

input:

2 10 10
2 9
3 8
10 5
10 10

output:

10
2 9 10 10 DDDDDDDDRP
3 8 10 5 DDDDDDDLLL

result:

ok answer 10

Test #5:

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

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
3 6 6 8 DDDRR
4 1 6 3 DDRRP
4 2 3 2 UPPPP
4 9 2 9 UUPPP
10 1 5 1 UUUUU
10 10 5 10 UUUUU

result:

ok answer 5

Test #6:

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

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
3 10 3 8 LLPP
4 1 1 2 UUUR
5 1 4 1 UPPP
6 3 7 3 DPPP
6 4 8 6 DDRR
6 7 7 6 DLPP
6 8 5 8 UPPP
9 5 9 4 LPPP

result:

ok answer 4

Test #7:

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

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: 2ms
memory: 8272kb

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: 4ms
memory: 8304kb

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
2 7 2 10 RRRPPPP
3 3 3 7 DURRRRP
4 3 6 1 DDSLLPP
4 6 3 10 URRRRPP
4 7 3 8 URPPPPP
7 8 1 9 UUUUUUR
10 6 6 4 LLUUUUP
10 9 10 2 LLLLLLL

result:

ok answer 7

Test #10:

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

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: 8312kb

input:

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

output:

5
3 1 2 4 URRRP
4 4 6 7 DDRRR
7 8 7 10 UDRRP

result:

ok answer 5

Test #12:

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

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
1 7 2 8 DRPPP
2 1 1 1 UPPPP
3 5 2 2 LLLUP
4 9 4 8 LPPPP
5 6 5 3 LLLPP
6 4 3 2 ULUUL
9 2 9 4 RRPPP
9 9 6 9 UUUPP
10 8 7 8 UUUPP

result:

ok answer 5

Test #13:

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

input:

2 10 10
9 8
3 3
5 8
4 9

output:

7
3 3 4 9 DRRRRRR
9 8 5 8 UUUUPPP

result:

ok answer 7

Test #14:

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

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
1 7 3 9 DDRR
2 4 4 2 DDLL
2 8 5 9 DRDD
6 6 8 6 DDPP
8 4 10 4 DDPP
10 1 10 2 RPPP
10 5 10 5 PPPP
10 8 8 10 UURR

result:

ok answer 4

Test #15:

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

input:

1 10 10
1 9
2 10

output:

2
1 9 2 10 DR

result:

ok answer 2

Test #16:

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

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
2 8 3 6 DLLPPP
3 4 5 5 DDRPPP
3 5 6 5 RDDDLP
3 8 8 9 DDDDDR
4 2 10 2 DDDDDD
5 10 4 10 UPPPPP
7 9 9 6 DDLLLP
8 2 10 6 DDRRRR

result:

ok answer 6

Test #17:

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

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: 4ms
memory: 10200kb

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
1 5 1 9 RRRRP
4 1 3 1 UPPPP
4 4 4 2 LLPPP
5 3 5 1 LLPPP
5 7 1 6 UUUUL
6 4 8 3 DDLPP
6 7 2 6 UUUUL
7 10 3 10 UUUUP
9 10 10 8 DLLPP
10 7 5 7 UUUUU

result:

ok answer 5

Test #19:

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

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
1 5 2 7 DRRPPP
1 10 7 10 DDDDDD
4 5 5 1 DLLLLP
5 5 6 2 DLLLPP
6 5 6 3 LLPPPP
9 3 8 1 ULLPPP
9 6 10 6 DPPPPP

result:

ok answer 6

Test #20:

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

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
2 6 1 7 URPPPPPP
4 1 4 1 PPPPPPPP
7 9 2 10 UUURUUPP
9 1 3 1 UUUUUUPP
9 5 5 1 UUUULLLL
9 7 4 10 UUUUURRR

result:

ok answer 8

Test #21:

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

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
1 2 3 5 DDRRR
1 10 3 9 DDLPP
6 2 6 1 LPPPP
7 7 7 8 RPPPP
8 3 4 3 UUUUP
8 6 8 7 RPPPP
9 5 6 4 UUULP
10 3 10 2 LPPPP
10 8 8 10 UURRP
10 9 8 9 UUPPP

result:

ok answer 5

Test #22:

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

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
1 2 7 3 DDDDDDRP
1 6 3 6 DDPPPPPP
2 4 2 5 RPPPPPPP
2 9 2 9 PPPPPPPP
3 3 9 1 DLDDDDDL
3 9 1 10 UURPPPPP
4 9 4 2 LLLLLLLP
5 8 5 8 PPPPPPPP
6 9 6 10 RPPPPPPP
9 2 10 2 DPPPPPPP

result:

ok answer 8

Test #23:

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

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
1 1 3 1 DDPP
2 10 4 8 DDLL
4 6 7 6 DDDP
5 4 3 2 LLUU
5 9 6 10 DRPP
6 8 9 9 DDDR
7 3 5 1 UULL
7 7 7 7 PPPP
9 2 9 1 LPPP
10 6 9 7 URPP

result:

ok answer 4

Test #24:

score: 0
Accepted
time: 9ms
memory: 8980kb

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 3 1 6 RRRPPPPPPPPPP
1 12 1 24 RRRRRRRRRRRRP
1 17 1 17 PPPPPPPPPPPPP
1 37 1 28 LLLLLLLLLPPPP
1 44 1 55 RRRRRRRRRRRPP
1 49 1 47 LLPPPPPPPPPPP
1 72 1 59 LLLLLLLLLLLLL
1 75 1 75 PPPPPPPPPPPPP
1 78 1 68 LLLLLLLLLLPPP
1 83 1 81 LLPPPPPPPPPPP

result:

ok answer 13

Test #25:

score: 0
Accepted
time: 7ms
memory: 10436kb

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 7 1 31 RRRRRRRRRRRRRRRRRRRRRRRRP
1 24 1 39 RRRRRRRRRRRRRRRPPPPPPPPPP
1 26 1 28 RRPPPPPPPPPPPPPPPPPPPPPPP
1 33 1 58 RRRRRRRRRRRRRRRRRRRRRRRRR
1 42 1 67 RRRRRRRRRRRRRRRRRRRRRRRRR
1 43 1 66 RRRRRRRRRRRRRRRRRRRRRRRPP
1 59 1 68 LRRRRRRRRRRPPPPPPPPPPPPPP
1 75 1 74 LPPPPPPPPPPPPPPPPPPPPPPPP
1 88 1 86 ...

result:

ok answer 25

Test #26:

score: 0
Accepted
time: 7ms
memory: 8976kb

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 24 1 6 LLLLLLLLLLLLLLLLLLPPPPP
1 31 1 14 LLLLLLLLLLLLLLLLLPPPPPP
1 38 1 15 LLLLLLLLLLLLLLLLLLLLLLL
1 43 1 51 RRRRRRRRPPPPPPPPPPPPPPP
1 44 1 57 RRRRRRRRRRRRRPPPPPPPPPP
1 47 1 55 RRRRRRRRPPPPPPPPPPPPPPP
1 52 1 73 SRRRRRRRRRRRRRRRRRRRRRP
1 63 1 74 LLLLLRRRRRRRRRRRRRRRRPP
1 88 1 82 LLLLLLPPPPPPPPPP...

result:

ok answer 23

Test #27:

score: 0
Accepted
time: 10ms
memory: 10256kb

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
6 1 8 1 DDPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
23 1 24 1 DPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
40 1 33 1 UUUUUUUPPPPPPPPPPPPPPPPPPPPPPPPPPPP
41 1 31 1 UUUUUUUUUUPPPPPPPPPPPPPPPPPPPPPPPPP
72 1 39 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUPP
76 1 41 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
82 1 82 1 PPPPPPPPPPPPP...

result:

ok answer 35

Test #28:

score: 0
Accepted
time: 7ms
memory: 8680kb

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
11 1 8 1 UUUPPPPPPPPPPPPPPPPPPPPPPPPP
19 1 18 1 UPPPPPPPPPPPPPPPPPPPPPPPPPPP
23 1 40 1 DDDDDDDDDDDDDDDDDPPPPPPPPPPP
29 1 41 1 DDDDDDDDDDDDPPPPPPPPPPPPPPPP
34 1 34 1 PPPPPPPPPPPPPPPPPPPPPPPPPPPP
35 1 63 1 DDDDDDDDDDDDDDDDDDDDDDDDDDDD
44 1 69 1 UDDDDDDDDDDDDDDDDDDDDDDDDDDP
56 1 81 1 DDDDDDDDDDDDDDD...

result:

ok answer 28

Test #29:

score: 0
Accepted
time: 13ms
memory: 10640kb

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
8 1 42 1 DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
24 1 57 1 DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDP
31 1 56 1 DDDDDDDDDDDDDDDDDDDDDDDDDPPPPPPPPP
35 1 52 1 DDDDDDDDDDDDDDDDDPPPPPPPPPPPPPPPPP
42 1 72 1 DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDPPPP
45 1 51 1 DDDDDDPPPPPPPPPPPPP...

result:

ok answer 34

Test #30:

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

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: 8140kb

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: 4ms
memory: 10264kb

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: 10200kb

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: 8608kb

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: 3ms
memory: 8672kb

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: 3ms
memory: 10392kb

input:

2 3 33
3 17
2 13
1 23
1 24

output:

11
2 13 1 23 URRRRRRRRRR
3 17 1 24 UURRRRRRRPP

result:

ok answer 11

Test #37:

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

input:

2 4 25
3 15
2 22
1 22
1 11

output:

6
2 22 1 22 UPPPPP
3 15 1 11 UULLLL

result:

ok answer 6

Test #38:

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

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: 2ms
memory: 8252kb

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: 2ms
memory: 8416kb

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: 8436kb

input:

2 8 12
8 4
1 4
5 12
2 6

output:

11
1 4 2 6 DRRPPPPPPPP
8 4 5 12 UUURRRRRRRR

result:

ok answer 11

Test #42:

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

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: 10204kb

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: 5ms
memory: 9032kb

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
13 1 19 1 DDDDDDPPPPP
65 1 76 1 DDDDDDDDDDD
75 1 86 1 DDDDDDDDDDD
91 1 92 1 DPPPPPPPPPP
94 1 89 1 UUUUUPPPPPP

result:

ok answer 11

Test #45:

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

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
12 2 6 1 UUUUUULPPP
19 2 9 2 UUUUUUUUUU
33 1 32 2 URPPPPPPPP
36 1 34 2 UURPPPPPPP
39 1 41 2 DDRPPPPPPP

result:

ok answer 10

Test #46:

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

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
4 1 4 1 PPPP
23 1 20 2 UUUR
23 3 21 3 UUPP
27 1 28 1 DPPP
33 3 32 2 ULPP

result:

ok answer 4

Test #47:

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

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
1 3 7 3 DDDDDD
9 4 9 2 LLPPPP
18 3 13 2 UUUUUL
22 3 19 3 UUUPPP
23 3 23 4 RPPPPP

result:

ok answer 6

Test #48:

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

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
12 2 3 2 UUUUUUUUU
15 2 20 2 DDDDDPPPP
15 3 19 1 DDDDLLPPP
16 5 15 5 UPPPPPPPP

result:

ok answer 9

Test #49:

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

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
2 6 1 4 ULLPPPPPPPPP
3 4 3 4 PPPPPPPPPPPP
5 2 1 2 UUUUPPPPPPPP
13 2 2 3 UUUUUUUUUUUR
16 2 14 2 UUPPPPPPPPPP

result:

ok answer 12

Test #50:

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

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
1 1 1 5 RRRR
3 3 3 3 PPPP
3 4 2 7 URRR
4 3 8 3 DDDD
13 7 12 7 UPPP

result:

ok answer 4

Test #51:

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

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
1 7 2 1 DLLLLLL
4 8 5 8 DPPPPPP
11 4 6 3 UUUUULP
11 8 7 6 UULUULP
12 7 10 4 UULLLPP

result:

ok answer 7

Test #52:

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

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
1 1 1 4 RRRPP
1 4 2 6 DRRPP
3 3 4 5 DRRPP
10 4 7 3 UUULP
10 6 6 7 UUUUR

result:

ok answer 5

Test #53:

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

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
1 3 1 10 RRRRRRR
2 2 2 5 RRRPPPP
6 5 6 5 PPPPPPP
7 4 9 5 DDRPPPP
9 9 10 6 DLLLPPP

result:

ok answer 7

Test #54:

score: 0
Accepted
time: 10ms
memory: 9056kb

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 1 1 4 RRRPPPPPPPPPPPPPPPP
1 24 1 5 LLLLLLLLLLLLLLLLLLL
1 26 1 14 RRRLLLLLLLLLLLLLLLP
1 40 1 42 LLLLLLLRRRRRRRRRPPP
1 55 1 38 LLLLLLLLLLLLLLLLLPP
1 67 1 48 LLLLLLLLLLLLLLLLLLL
1 75 1 62 LLLLLLLLLLLLLPPPPPP
1 82 1 77 LLLLLPPPPPPPPPPPPPP
1 84 1 73 LLLLLLLLLLLPPPPPPPP
1 86 1 98 RRRRRRRRRRRRPPPPPPP

result:

ok answer 19

Test #55:

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

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
1 10 2 23 DRRRRRRRRRRRRRP
1 11 1 12 RPPPPPPPPPPPPPP
1 22 1 23 RPPPPPPPPPPPPPP
1 33 2 29 LDLLLPPPPPPPPPP
1 47 1 32 LLLLLLLLLLLLLLL
1 48 2 48 DPPPPPPPPPPPPPP
1 49 1 48 LPPPPPPPPPPPPPP
2 5 1 6 URPPPPPPPPPPPPP
2 11 2 17 RRRRRRPPPPPPPPP
2 47 2 42 SLLLLLPPPPPPPPP

result:

ok answer 15

Test #56:

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

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 4 2 2 DLLPPPPPP
1 8 2 6 DLLPPPPPP
1 15 2 10 DLLLLLPPP
1 16 1 18 RRPPPPPPP
1 30 3 31 DDRPPPPPP
2 8 3 9 DRPPPPPPP
2 12 2 11 LPPPPPPPP
2 16 3 10 DLLLLLLPP
2 20 3 28 DRRRRRRRR
3 33 3 33 PPPPPPPPP

result:

ok answer 9

Test #57:

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

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
1 6 4 4 DDDLLP
2 1 2 4 RRRPPP
2 2 3 3 DRPPPP
2 15 4 15 DDPPPP
3 12 3 7 LLLLLP
3 19 1 22 UURRRP
4 10 2 6 ULLLUL
4 13 2 13 UUPPPP
4 18 2 18 UUPPPP
4 23 1 24 UUULRR

result:

ok answer 6

Test #58:

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

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
1 7 3 7 DDPPPP
2 1 3 1 DPPPPP
2 18 1 20 URRPPP
3 4 2 6 URRPPP
3 14 1 12 UULLPP
3 16 2 11 ULLLLL
4 11 1 9 UUULLP
5 4 4 2 ULLPPP
5 13 5 8 LLLLLP
5 20 3 17 UULLLP

result:

ok answer 6

Test #59:

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

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
1 1 4 2 DDDRPPP
1 11 2 11 DPPPPPP
2 1 2 2 RPPPPPP
2 7 2 4 RRLLLLL
2 16 2 16 PPPPPPP
4 13 4 14 RPPPPPP
5 9 4 6 ULLLPPP
5 10 2 9 UUULPPP
6 10 6 3 LLLLLLL
6 15 2 14 UUUULPP

result:

ok answer 7

Test #60:

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

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
1 5 2 4 DLP
2 9 2 7 LLP
2 13 3 12 DLP
4 1 7 1 DDD
4 8 3 7 ULP
4 10 3 9 ULP
5 4 4 5 URP
6 12 6 11 LPP
6 14 6 13 LPP
7 4 7 5 RPP

result:

ok answer 3

Test #61:

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

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 11 2 8 DLLL
1 12 1 12 PPPP
3 11 4 11 DPPP
4 4 3 7 URRR
5 1 7 1 DDPP
5 2 6 4 DRRP
5 10 5 8 LLPP
7 4 7 7 RRRP
8 2 8 4 UDRR
8 10 7 11 URPP

result:

ok answer 4

Test #62:

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

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
2 7 2 7 PPPPP
3 1 4 5 DRRRR
3 9 2 9 UPPPP
4 4 4 7 RRRPP
5 4 7 7 DRDRR
5 6 6 8 URDDR
6 3 7 4 DRPPP
8 11 5 9 UUULL
9 6 9 7 RPPPP
9 10 8 8 ULLPP

result:

ok answer 5

Test #63:

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

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
1 1 7 1 DDDDDDP
2 3 5 7 DDDRRRR
2 8 4 8 DDPPPPP
2 9 5 9 DDDPPPP
4 6 6 6 DDPPPPP
4 10 4 10 PPPPPPP
7 6 7 6 PPPPPPP
8 2 8 1 LPPPPPP
8 8 8 7 LPPPPPP
10 7 7 7 UUUPPPP

result:

ok answer 7

Test #64:

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

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
16 1 2 1 DUUUUUUUUUUUUUUUP
21 1 20 1 UPPPPPPPPPPPPPPPP
22 1 8 1 UUUUUUUUUUUUUUPPP
26 1 17 1 UUUUUUUUUPPPPPPPP
28 1 28 1 PPPPPPPPPPPPPPPPP
32 1 32 1 PPPPPPPPPPPPPPPPP
34 1 19 1 UUUUUUUUUUUUUUUPP
38 1 42 1 DDDDPPPPPPPPPPPPP
49 1 49 1 PPPPPPPPPPPPPPPPP
56 1 47 1 UUUUUUUUUPPPPPPPP
57 1 58 1 DPPPPPPPP...

result:

ok answer 17

Test #65:

score: 0
Accepted
time: 10ms
memory: 10508kb

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
8 1 8 1 PPPPPPPPPPPPPPPPP
13 1 5 1 DUUUUUUUUUPPPPPPP
15 1 14 2 RUPPPPPPPPPPPPPPP
16 1 16 1 PPPPPPPPPPPPPPPPP
17 2 10 2 UUUUUUUPPPPPPPPPP
18 1 19 1 DPPPPPPPPPPPPPPPP
23 2 15 2 UUUUUUUUPPPPPPPPP
24 1 8 2 UUURUUUUUUUUUUUUU
25 1 16 2 DDDRUUUUUUUUUUUUP
26 1 10 1 UUUUUUUUUUUUUUUUP
27 1 27 2 RPPPPPPPPPP...

result:

ok answer 17

Test #66:

score: 0
Accepted
time: 6ms
memory: 8464kb

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
1 2 5 1 DDDDLPP
2 2 4 1 DDLPPPP
3 2 4 2 DPPPPPP
7 3 10 3 DDDPPPP
8 1 8 2 RPPPPPP
8 3 9 3 DPPPPPP
16 1 15 3 URRPPPP
17 1 10 1 UUUUUUU
18 2 12 1 UUUUUUL
19 3 12 3 UUUUUUU
20 2 13 2 UUUUUUU
23 1 19 2 UUUURPP
23 3 17 3 UUUUUUP
24 1 19 1 DUUUUUU
27 1 21 1 UUUUUUP
28 1 25 2 UUURPPP
28 2 22 2 UUUUUUP
30 ...

result:

ok answer 7

Test #67:

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

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 1 8 2 DDDDDDR
2 2 3 2 DPPPPPP
3 4 2 4 UPPPPPP
5 2 7 3 DDRPPPP
6 1 12 2 DDDDDDR
8 2 9 2 SDPPPPP
9 3 9 3 PPPPPPP
10 1 16 1 DDDDDDP
10 4 10 3 LPPPPPP
11 4 16 3 DDDDDLP
12 2 19 2 DDDDDDD
13 1 20 1 DDDDDDD
13 3 19 3 DDDDDDP
17 1 21 1 DDDDPPP
20 2 20 4 UDRRPPP
23 2 22 2 UPPPPPP
23 3 23 4 RPPPPPP
24 2 ...

result:

ok answer 7

Test #68:

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

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
1 3 3 5 DDRR
3 3 3 4 RPPP
4 2 2 1 UULP
5 2 5 4 RRPP
6 3 5 5 RRUP
7 1 6 2 URPP
7 4 7 4 PPPP
8 1 8 1 PPPP
9 1 9 1 PPPP
10 4 8 4 UUPP
10 5 14 5 DDDD
11 3 13 3 DDPP
11 5 11 5 PPPP
12 1 13 1 DPPP
12 5 14 4 DDLP
14 1 15 3 DRRP
15 3 18 3 DDDP
15 5 18 4 DDDL
16 1 19 2 DDDR
16 5 17 5 DPPP

result:

ok answer 4

Test #69:

score: 0
Accepted
time: 6ms
memory: 8424kb

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
1 2 3 2 DDPPPP
1 4 3 4 DDPPPP
2 1 7 2 DDDDDR
2 5 2 5 PPPPPP
3 6 1 6 UUPPPP
4 1 10 1 DDDDDD
5 2 3 3 RUUPPP
5 6 4 4 LULPPP
6 3 11 3 DDDDDP
6 5 10 3 DDDDLL
8 2 13 1 DDDDDL
8 5 10 4 DDLPPP
10 1 14 1 DDDDPP
12 2 12 1 LPPPPP
13 1 16 1 DDDPPP
13 5 12 3 ULLPPP
14 3 13 3 UPPPPP
14 6 16 3 DDL...

result:

ok answer 6

Test #70:

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

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 LDDD
1 3 1 1 LLPP
3 1 6 2 DDDR
3 6 7 6 DDDD
4 1 5 1 DPPP
5 3 6 5 DSRR
5 4 4 5 URPP
6 1 6 3 SRRP
6 6 9 7 DDDR
7 4 7 4 PPPP
8 2 8 4 UDRR
10 6 9 5 ULPP
11 2 12 2 DPPP
11 4 11 4 PPPP
11 5 11 5 PPPP
11 7 11 7 PPPP
12 1 11 1 UPPP
12 3 13 4 DRPP
12 6 11 6 UPPP
13 2 14 5 DRRR

result:

ok answer 4

Test #71:

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

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
3 6 1 3 UULLL
4 5 3 2 ULLLP
5 1 3 1 UUPPP
5 3 1 2 UUUUL
5 5 2 4 UUULP
5 8 5 8 PPPPP
6 4 2 3 UUULU
6 6 3 4 UUULL
6 7 2 7 UUUUP
7 4 3 3 LUUUU
7 6 7 6 PPPPP
8 2 5 1 ULUUP
8 4 8 4 PPPPP
8 5 7 3 USLLP
8 6 9 8 DRRPP
9 4 7 1 UULLL
10 3 12 4 DDRPP
10 7 9 7 UPPPP
12 1 12 1 PPPPP
12 2 11 2 UPPPP

result:

ok answer 5

Test #72:

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

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
1 8 1 9 RPPPP
4 3 1 1 LUUUL
4 5 2 4 UULPP
4 7 1 6 UUULP
4 8 4 3 LLLLL
5 5 4 2 ULLLP
5 9 5 6 LLLPP
6 6 6 1 LLLLL
7 1 3 1 UUUUP
7 8 11 9 DDDDR
8 5 4 5 UUUUP
8 6 6 4 UULLP
8 7 8 7 PPPPP
9 6 9 7 RPPPP
9 9 10 9 DPPPP
10 3 7 3 UUUPP
10 4 10 4 PPPPP
11 2 11 2 PPPPP
11 5 11 6 RPPPP
11 8 11 8 PPPPP

result:

ok answer 5

Test #73:

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

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
1 7 1 6 LPP
1 8 2 10 DRR
2 4 2 4 PPP
2 5 2 6 RPP
3 1 3 2 RPP
3 6 2 8 RUR
4 2 4 3 RPP
4 4 6 5 DDR
4 6 7 6 DDD
5 2 4 2 UPP
6 10 6 9 LPP
7 9 7 7 LLP
8 1 7 2 URP
8 2 5 2 UUU
8 3 5 3 UUU
8 4 7 5 URP
9 2 10 2 DPP
9 3 7 3 UUS
9 9 9 6 LLL
10 8 10 5 LLL

result:

ok answer 3

Test #74:

score: 0
Accepted
time: 10ms
memory: 8772kb

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 5 1 8 RRRPPPPP
1 6 1 6 PPPPPPPP
1 8 1 16 RRRRRRRR
1 11 1 14 RRRPPPPP
1 17 1 24 RRRRRRRP
1 21 1 20 LPPPPPPP
1 26 1 26 PPPPPPPP
1 30 1 31 RPPPPPPP
1 33 1 34 RPPPPPPP
1 35 1 39 RRRRPPPP
1 38 1 37 LPPPPPPP
1 44 1 43 LPPPPPPP
1 47 1 41 LLLLLLPP
1 49 1 42 LLLLLLLP
1 50 1 45 RLLLLLLP
1 54 1 53 LPPPPPPP...

result:

ok answer 8

Test #75:

score: 0
Accepted
time: 8ms
memory: 10208kb

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
1 7 1 2 LLLLLP
1 9 1 14 RRRRRP
1 15 2 16 DRPPPP
1 23 2 27 DRRRRP
1 30 1 27 LLLPPP
1 31 2 31 DPPPPP
1 33 2 33 DPPPPP
1 36 1 36 PPPPPP
1 38 1 38 PPPPPP
1 46 1 40 LLLLLL
1 47 2 46 SDLPPP
1 50 2 50 DPPPPP
2 1 2 1 PPPPPP
2 3 2 2 LPPPPP
2 7 2 5 LLPPPP
2 11 1 13 URRPPP
2 13 2 13 PPPPPP
2 14 1 17 URRRPP
2...

result:

ok answer 6

Test #76:

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

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
1 5 1 1 LLLLP
1 6 2 4 DLLPP
1 8 1 7 LPPPP
1 9 1 4 LLLLL
1 14 2 14 DPPPP
1 17 1 13 LLLLP
1 20 1 20 PPPPP
1 21 2 20 DLPPP
1 22 1 17 LLLLL
1 23 3 25 DDRRP
1 27 2 25 DLLPP
1 29 1 33 RRRRP
1 30 1 31 RPPPP
2 6 2 2 LLLLP
2 12 3 8 DLLLL
2 17 3 18 DRPPP
2 20 2 15 LLLLL
2 21 2 21 PPPPP
2 23 3 23 DPPPP
2 29 ...

result:

ok answer 5

Test #77:

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

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
1 1 1 4 RRR
1 2 1 5 RRR
1 3 1 3 PPP
1 4 1 7 RRR
1 6 1 8 RRP
1 7 1 10 RRR
1 13 2 11 LLD
1 14 1 16 RRP
1 20 1 20 PPP
1 24 2 24 DPP
1 25 2 25 DPP
2 2 4 2 DDP
2 4 2 4 PPP
2 17 2 16 LPP
2 21 1 21 UPP
2 22 1 22 UPP
3 4 3 6 RRP
3 7 3 8 DUR
3 12 2 10 ULL
3 14 3 13 LPP
3 18 3 18 PPP
3 20 2 19 LUP
3 22 3 24...

result:

ok answer 3

Test #78:

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

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 2 1 1 LPPP
1 3 4 2 DDDL
1 7 2 4 DLLL
1 9 2 7 DLLP
1 12 1 13 RPPP
1 15 2 14 DLPP
1 18 1 15 LLLP
1 20 2 20 DPPP
2 8 3 8 DPPP
2 12 2 10 LLPP
2 13 2 11 SLLP
2 19 2 16 LLLP
3 6 2 5 ULPP
3 8 3 7 LPPP
3 9 4 6 DLLL
3 10 3 10 PPPP
3 11 5 9 DDLL
3 17 3 17 PPPP
3 18 2 15 LLLU
4 5 4 1 LLLL
4 7 4 4 LLLP
4 11...

result:

ok answer 4

Test #79:

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

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
1 3 1 5 RRP
1 4 3 4 DDP
1 5 2 7 DRR
1 8 1 7 LPP
1 11 1 11 PPP
1 12 1 12 PPP
1 13 2 13 DPP
2 1 2 4 RRR
2 9 1 9 UPP
2 11 3 9 DLL
3 5 4 4 LDP
3 9 3 8 LPP
3 11 3 11 PPP
3 15 1 16 UUR
4 1 5 2 DRP
4 9 5 8 DLP
4 11 4 10 LPP
4 13 3 13 UPP
4 14 4 11 LLL
5 1 5 3 RRP
5 2 6 4 DRR
5 4 5 4 PPP
5 5 6 5 UDD
5 10 ...

result:

ok answer 3

Test #80:

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

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
1 1 1 1 PPP
1 3 1 5 RRP
1 6 1 6 PPP
2 2 3 1 DLP
2 3 4 2 DDL
2 6 3 6 DPP
2 7 3 5 DLL
2 10 2 9 LPP
3 10 2 11 URP
3 11 3 11 PPP
3 12 2 14 URR
4 5 4 4 UDL
4 9 2 8 UUL
4 11 4 12 RPP
5 2 7 1 DDL
5 4 5 4 PPP
5 8 3 7 UUL
5 10 5 11 RPP
5 13 4 13 UPP
5 14 3 14 UUP
6 5 7 3 DLL
6 8 5 8 UPP
6 9 3 9 UUU
6 13 5 ...

result:

ok answer 3

Test #81:

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

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
1 4 1 7 RRR
2 3 2 6 RRR
2 4 1 6 URR
2 5 2 7 RRP
2 7 2 10 RRR
2 12 3 12 DPP
3 1 2 1 UPP
3 2 2 2 UPP
3 6 3 6 PPP
4 5 4 6 RPP
4 7 3 9 URR
4 8 3 8 UPP
4 9 4 11 RRP
4 10 1 10 UUU
5 3 4 1 ULL
5 10 4 12 RRU
6 5 5 7 URR
6 9 6 12 RRR
6 10 5 12 RRU
6 11 6 11 PPP
7 2 4 2 UUU
7 4 7 6 RRP
7 8 6 9 URP
7 9 7 11 ...

result:

ok answer 3

Test #82:

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

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
1 7 1 4 LLL
1 10 2 8 DLL
1 11 3 11 DDP
2 1 1 2 URP
2 8 1 6 ULL
2 10 3 8 DLL
3 1 4 1 DPP
3 2 2 2 UPP
3 6 1 5 UUL
3 8 3 6 LLP
3 9 4 7 DLL
4 2 4 3 RPP
4 4 5 3 DLP
4 5 2 5 UUP
5 2 8 2 DDD
5 8 4 8 UPP
5 10 5 10 PPP
6 6 5 4 ULL
7 6 7 3 LLL
7 8 7 5 LLL
7 11 6 10 ULP
8 8 6 7 UUL
8 9 6 9 UUP
8 11 8 10 LPP
...

result:

ok answer 3

Test #83:

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

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
1 1 1 1 PPP
1 8 1 5 LLL
1 9 1 6 LLL
2 6 2 6 PPP
2 8 3 6 DLL
2 10 1 9 ULP
4 1 5 1 DPP
4 2 1 2 UUU
4 3 1 3 UUU
4 5 3 4 ULP
5 2 3 2 UUP
5 8 4 9 URP
6 3 4 3 UUP
6 5 5 4 ULP
6 7 6 5 LLP
6 8 6 9 RPP
6 10 4 10 UUP
7 2 6 2 UPP
7 5 6 4 ULP
7 7 7 4 LLL
8 1 8 1 PPP
8 3 8 3 PPP
8 4 7 3 ULP
8 5 10 5 DDP
8 9 7 ...

result:

ok answer 3

Test #84:

score: 0
Accepted
time: 14ms
memory: 9052kb

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
1 1 1 1 PPPPPPPPPP
4 1 3 1 UPPPPPPPPP
7 1 2 1 UUUUUPPPPP
11 1 10 1 UPPPPPPPPP
12 1 12 1 PPPPPPPPPP
13 1 17 1 DDDDPPPPPP
18 1 20 1 DDPPPPPPPP
22 1 25 1 UDDDDPPPPP
23 1 24 1 DPPPPPPPPP
28 1 28 1 PPPPPPPPPP
29 1 29 1 PPPPPPPPPP
30 1 27 1 UUUPPPPPPP
31 1 33 1 DDPPPPPPPP
37 1 37 1 PPPPPPPPPP
40 1 40 1...

result:

ok answer 10

Test #85:

score: 0
Accepted
time: 7ms
memory: 8580kb

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
1 1 2 1 DPPPPPPPP
3 2 2 2 UPPPPPPPP
4 2 1 2 DUUUUPPPP
5 2 5 2 PPPPPPPPP
8 1 8 1 PPPPPPPPP
8 2 6 2 UUPPPPPPP
9 2 7 1 UULPPPPPP
10 1 9 1 UPPPPPPPP
12 2 6 1 UUUUUULPP
13 2 8 2 UUUUUPPPP
14 1 22 2 DDDDDDDDR
14 2 14 2 PPPPPPPPP
15 1 18 2 DDDRPPPPP
15 2 15 2 PPPPPPPPP
16 1 21 1 DDDDDPPPP
17 1 26 1 DDDDD...

result:

ok answer 9

Test #86:

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

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
1 1 2 1 DPPPPPPP
1 3 1 3 PPPPPPPP
3 2 2 2 UPPPPPPP
3 3 3 3 PPPPPPPP
4 1 4 1 PPPPPPPP
4 2 2 3 UURPPPPP
4 3 4 3 PPPPPPPP
5 1 6 1 DPPPPPPP
5 2 7 1 DLDPPPPP
7 3 6 3 UPPPPPPP
8 3 7 2 ULPPPPPP
9 1 8 1 UPPPPPPP
9 2 10 2 DPPPPPPP
9 3 10 3 DPPPPPPP
11 3 11 3 PPPPPPPP
12 1 11 1 UPPPPPPP
14 1 14 1 PPPPPPPP
1...

result:

ok answer 8

Test #87:

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

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
1 2 1 1 LPPP
2 3 4 3 DDPP
3 1 4 2 DRPP
3 4 3 4 PPPP
5 1 6 1 DPPP
5 2 5 2 PPPP
5 3 5 3 PPPP
5 4 8 4 DDDP
6 2 6 3 RPPP
7 2 9 1 DDLP
7 3 9 4 DDRP
8 1 12 1 DDDD
8 2 9 2 DPPP
8 3 9 3 DPPP
8 4 10 4 SDDP
9 1 10 1 DPPP
9 4 12 4 DDDP
11 1 14 1 DDDP
12 4 15 4 SDDD
13 4 15 2 DDLL
14 4 15 1 DLLL
15 3 16 1 LDL...

result:

ok answer 4

Test #88:

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

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
1 2 1 1 LP
1 4 2 4 DP
2 2 2 2 PP
2 3 1 3 UP
2 5 2 5 PP
3 4 3 2 LL
4 2 4 2 PP
4 3 4 4 RP
4 5 3 5 UP
5 3 7 3 DD
6 2 6 2 PP
6 3 6 1 LL
6 5 6 5 PP
7 2 7 2 PP
7 4 6 4 UP
8 3 9 2 DL
8 4 8 4 PP
9 1 8 1 UP
9 2 10 2 DP
9 3 9 1 LL
9 4 9 4 PP
10 1 10 1 PP
10 5 9 5 UP
11 2 12 2 DP
11 3 11 3 PP
12 2 14 2 DD
12...

result:

ok answer 2

Test #89:

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

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
1 2 1 2 PPP
1 3 4 3 DDD
1 4 1 4 PPP
1 6 1 3 LLL
2 1 2 1 PPP
2 2 3 2 DPP
2 4 5 4 DDD
2 5 2 4 LPP
4 2 4 1 LPP
4 5 6 5 DDP
4 6 3 6 UPP
5 1 7 1 DDP
5 2 7 2 DDP
5 4 8 4 DDD
6 3 6 3 PPP
6 5 8 6 DDR
7 2 9 1 LDD
7 3 8 3 DPP
7 4 9 5 DDR
7 5 8 5 DPP
8 1 11 1 DDD
8 4 9 4 DPP
9 1 12 1 DDD
9 3 12 3 DDD
9 4 11 ...

result:

ok answer 3

Test #90:

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

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
1 2 1 2 PPP
1 3 2 2 DLP
2 6 2 7 RPP
3 1 3 1 PPP
3 3 3 3 PPP
3 6 3 6 PPP
4 2 2 1 ULU
4 4 2 4 UUP
4 5 2 6 UUR
4 6 1 6 UUU
4 7 3 7 UPP
5 1 5 1 PPP
5 2 5 2 PPP
5 6 6 7 RDP
6 2 6 1 LPP
6 4 5 4 UPP
6 5 6 4 RLL
7 2 7 2 PPP
7 4 7 4 PPP
7 5 7 5 PPP
8 3 8 3 PPP
8 4 7 3 ULP
8 6 6 6 UUP
9 1 9 1 PPP
9 2 7 1 UU...

result:

ok answer 3

Test #91:

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

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
1 1 1 1 PP
1 7 1 6 LP
2 3 2 3 PP
2 4 3 4 DP
2 7 2 7 PP
3 1 2 1 UP
3 2 2 2 UP
3 5 3 5 PP
3 6 2 6 UP
3 7 4 8 DR
4 1 4 3 RR
4 3 4 4 RP
4 4 4 6 RR
4 5 6 5 DD
4 7 4 7 PP
5 1 5 1 PP
5 2 5 4 RR
5 3 3 3 UU
5 5 5 6 RP
6 2 7 3 DR
6 5 8 5 DD
6 6 7 6 SD
6 8 7 8 DP
7 1 8 1 DP
7 3 9 3 DD
7 4 7 4 PP
8 4 9 5 DR
8...

result:

ok answer 2

Test #92:

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

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
1 2 4 2 DDD
1 6 2 6 DPP
1 8 1 9 RPP
2 1 2 1 PPP
2 2 5 2 DDD
2 4 1 4 UPP
2 5 3 4 DLP
2 7 4 6 DDL
2 8 4 8 DDP
2 9 2 9 PPP
3 2 3 1 LPP
3 4 4 3 DLP
3 5 3 3 LLP
3 7 3 6 LPP
3 8 3 8 PPP
4 2 7 2 DDD
4 4 4 4 PPP
4 5 6 5 DDP
4 6 7 6 DDD
4 7 7 7 DDD
4 8 7 8 DDD
5 4 7 4 DDP
5 5 5 5 PPP
5 6 5 6 PPP
5 7 8 7 DD...

result:

ok answer 3

Test #93:

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

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
1 1 4 1 DDD
1 3 3 4 DDR
1 4 2 4 DPP
1 9 1 6 LLL
1 10 2 8 DLL
2 1 2 1 PPP
2 2 3 2 DPP
2 7 4 7 DDP
2 9 3 8 LDP
2 10 4 9 DDL
3 5 4 4 DLP
3 6 3 5 UDL
3 10 4 8 LDL
4 1 7 1 DDD
4 9 7 9 DDD
4 10 5 9 DLP
5 1 7 2 DDR
5 3 5 2 LPP
5 5 6 5 DPP
5 8 5 7 SLP
6 4 7 4 DPP
6 6 5 6 UPP
6 8 7 7 DLP
6 10 6 10 PPP
7 1 ...

result:

ok answer 3

Test #94:

score: 0
Accepted
time: 12ms
memory: 10124kb

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 2 1 2 PPPPPPPPPP
1 5 1 5 PPPPPPPPPP
1 7 1 7 PPPPPPPPPP
1 8 1 4 LLLLPPPPPP
1 9 1 18 RRRRRRRRRP
1 10 1 20 RRRRRRRRRR
1 13 1 12 LPPPPPPPPP
1 14 1 22 RRRRRRRRPP
1 15 1 15 PPPPPPPPPP
1 16 1 19 RRRPPPPPPP
1 17 1 27 RRRRRRRRRR
1 22 1 21 SLPPPPPPPP
1 23 1 33 RRRRRRRRRR
1 25 1 28 RRRPPPPPPP
1 26 1 34 RR...

result:

ok answer 10

Test #95:

score: 0
Accepted
time: 9ms
memory: 8560kb

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
1 1 1 4 RRRPPP
1 5 1 11 RRRRRR
1 7 1 7 PPPPPP
1 9 1 9 PPPPPP
1 10 2 10 DPPPPP
1 12 2 12 DPPPPP
1 13 2 13 DPPPPP
1 15 2 15 DPPPPP
1 16 1 16 PPPPPP
1 19 2 17 DLLPPP
1 21 1 17 LLLLPP
1 23 1 23 PPPPPP
1 25 1 21 LLLLPP
1 26 1 20 LLLLLL
1 31 1 25 LLLLLL
1 33 1 27 LLLLLL
1 34 1 28 LLLLLL
1 35 1 30 SLLLLL...

result:

ok answer 6

Test #96:

score: 0
Accepted
time: 7ms
memory: 8540kb

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
1 1 2 1 DPPP
1 4 1 4 PPPP
1 6 1 6 PPPP
1 8 2 8 DPPP
1 9 1 9 PPPP
1 10 2 11 DRPP
1 11 1 11 PPPP
1 13 1 13 PPPP
1 14 1 14 PPPP
1 17 2 20 DRRR
1 18 3 18 DDPP
1 19 1 21 RRPP
1 20 1 24 RRRR
1 25 1 27 LRRR
1 30 1 32 RRPP
1 33 1 33 PPPP
2 2 1 2 UPPP
2 3 3 1 DLLP
2 4 3 7 DRRR
2 5 2 5 PPPP
2 6 1 7 URPP
2 9...

result:

ok answer 4

Test #97:

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

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
1 1 1 3 RRP
1 2 1 2 PPP
1 3 1 5 RRP
1 9 1 8 LPP
1 10 1 10 PPP
1 11 1 11 PPP
1 12 2 12 DPP
1 13 2 11 DLL
1 14 1 14 PPP
1 16 1 16 PPP
1 17 1 17 PPP
1 18 2 16 DLL
1 20 2 19 DLP
1 21 1 24 RRR
1 22 1 22 PPP
1 23 1 25 RRP
2 1 3 1 DPP
2 2 2 2 PPP
2 5 1 7 URR
2 9 2 9 PPP
2 10 2 10 PPP
2 14 1 15 URP
2 15 2...

result:

ok answer 3

Test #98:

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

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
1 1 1 1 PPP
1 2 1 2 PPP
1 4 1 3 LPP
1 5 1 5 PPP
1 8 1 11 RRR
1 9 2 10 DRP
1 18 1 18 PPP
1 19 1 17 LLP
1 20 3 20 DDP
2 1 3 1 DPP
2 3 2 3 PPP
2 5 2 8 RRR
2 6 1 6 UPP
2 9 4 9 DDP
2 12 1 12 UPP
2 14 1 14 UPP
2 16 2 16 PPP
2 18 2 19 RPP
2 20 2 20 PPP
3 2 3 2 PPP
3 3 4 5 DRR
3 4 3 7 RRR
3 7 3 8 RPP
3 8 ...

result:

ok answer 3

Test #99:

score: 0
Accepted
time: 6ms
memory: 8344kb

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
1 2 3 2 DDPP
1 4 1 4 PPPP
1 8 1 5 LLLP
1 10 1 10 PPPP
1 12 2 10 DLLP
1 14 1 13 LPPP
1 15 3 14 DDLP
1 16 2 13 DLLL
2 1 2 1 PPPP
2 2 2 2 PPPP
2 7 2 4 LLSL
2 8 2 6 LLPP
2 11 2 7 LLLL
2 13 3 10 DLLL
2 14 4 13 DDLP
2 15 2 11 LLLL
2 16 6 16 DDDD
3 1 3 1 PPPP
3 7 4 4 LLDL
3 9 2 9 UPPP
3 10 4 7 DLLL
3 11 ...

result:

ok answer 4

Test #100:

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

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
1 4 1 4 PP
1 5 2 6 DR
1 6 2 7 DR
1 7 1 7 PP
2 1 2 1 PP
2 2 2 2 PP
2 3 2 3 PP
2 4 2 4 PP
2 5 3 5 DP
2 9 2 11 RR
2 10 1 11 UR
2 12 1 13 UR
2 13 2 14 RP
3 1 3 1 PP
3 3 3 3 PP
3 6 3 6 PP
3 7 3 7 PP
3 8 3 9 RP
3 10 3 12 RR
3 11 2 12 UR
4 1 4 1 PP
4 2 5 2 DP
4 3 4 5 RR
4 4 3 4 UP
4 8 4 6 LL
4 9 4 9 PP
4...

result:

ok answer 2

Test #101:

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

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
1 2 2 2 DPP
1 3 2 3 DPP
1 4 1 4 PPP
1 5 1 5 PPP
1 6 1 6 PPP
1 7 1 7 PPP
1 10 2 10 DPP
1 11 1 11 PPP
2 4 2 4 PPP
2 6 2 6 PPP
2 8 2 8 PPP
2 9 1 8 ULP
2 11 2 11 PPP
2 12 1 12 UPP
3 1 3 1 PPP
3 2 6 2 DDD
3 4 5 3 DDL
3 5 2 5 UPP
4 1 5 1 DPP
4 2 4 2 PPP
4 7 2 7 UUP
4 9 1 9 UUU
4 10 3 10 UPP
4 11 4 8 LLL...

result:

ok answer 3

Test #102:

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

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
1 1 1 1 PP
1 2 2 2 DP
1 3 1 3 PP
1 5 1 5 PP
1 6 1 6 PP
1 7 1 7 PP
1 9 1 9 PP
2 3 3 3 DP
2 4 2 4 PP
2 5 1 4 UL
2 6 2 6 PP
2 7 1 8 UR
2 8 2 8 PP
2 10 1 10 UP
2 11 4 11 DD
3 1 3 1 PP
3 4 3 4 PP
3 9 3 9 PP
3 11 5 11 DD
4 7 2 7 UU
4 8 3 8 UP
4 9 3 10 UR
5 1 5 2 RP
5 5 5 3 LL
5 6 4 5 UL
5 7 6 8 DR
5 8 5...

result:

ok answer 2

Test #103:

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

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
1 3 2 2 DL
1 4 2 3 DL
1 8 1 7 LP
1 10 1 10 PP
2 6 1 5 UL
2 7 1 6 LU
2 8 2 6 LL
2 9 4 9 DD
2 10 2 9 LP
3 5 2 4 UL
3 7 3 5 LL
3 9 4 8 DL
3 10 5 10 DD
4 10 5 9 DL
5 1 3 1 UU
5 2 4 1 UL
5 3 4 4 UR
5 4 5 4 PP
5 7 3 7 UU
6 1 6 1 PP
6 2 6 4 RR
6 5 6 6 RP
6 7 5 7 UP
7 1 7 1 PP
7 2 8 1 DL
7 3 7 4 RP
7 4 7 ...

result:

ok answer 2

Test #104:

score: 0
Accepted
time: 13ms
memory: 10212kb

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
1 1 1 1 PPPPPPPPPPPPPPPPPP
3 1 5 1 DDPPPPPPPPPPPPPPPP
4 1 4 1 PPPPPPPPPPPPPPPPPP
6 1 6 1 PPPPPPPPPPPPPPPPPP
9 1 9 1 PPPPPPPPPPPPPPPPPP
10 1 11 1 DPPPPPPPPPPPPPPPPP
12 1 12 1 PPPPPPPPPPPPPPPPPP
16 1 16 1 PPPPPPPPPPPPPPPPPP
18 1 7 1 UUUUUUUUUUUPPPPPPP
22 1 22 1 PPPPPPPPPPPPPPPPPP
24 1 14 1 UUUUUUUU...

result:

ok answer 18

Test #105:

score: 0
Accepted
time: 9ms
memory: 10220kb

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
1 1 4 1 DSDDP
1 2 5 2 DDDDP
2 1 2 1 PPPPP
2 2 3 1 DLPPP
3 2 3 2 PPPPP
4 2 4 2 PPPPP
6 1 5 1 UPPPP
6 2 6 2 PPPPP
7 1 7 1 PPPPP
7 2 7 2 PPPPP
8 1 8 1 PPPPP
10 2 9 1 LUPPP
11 2 11 2 PPPPP
12 1 12 1 PPPPP
12 2 8 2 UUUUP
13 1 11 1 UUPPP
14 2 10 1 UUUUL
15 1 15 1 PPPPP
15 2 15 2 PPPPP
17 2 14 2 UUUPP
19...

result:

ok answer 5

Test #106:

score: 0
Accepted
time: 7ms
memory: 8560kb

input:

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

output:

4
1 1 3 1 DDPP
2 1 2 1 PPPP
3 1 7 1 DDDD
3 3 3 2 LPPP
4 2 4 2 PPPP
5 2 5 2 PPPP
6 1 5 3 URRP
6 2 6 2 PPPP
6 3 6 3 PPPP
7 1 8 1 DPPP
7 3 7 3 PPPP
8 1 7 2 URPP
8 2 8 2 PPPP
9 1 12 1 DDDP
9 2 9 2 PPPP
9 3 10 3 DPPP
10 1 13 1 DDDP
11 1 15 1 DDDD
11 2 11 3 RPPP
12 1 14 2 DDRP
12 2 15 2 DDDP
12 3 16 3 DDD...

result:

ok answer 4

Test #107:

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

input:

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

output:

3
1 1 1 1 PPP
1 3 2 4 RDP
2 2 2 3 RPP
3 1 4 1 DPP
3 2 3 2 PPP
3 3 3 3 PPP
3 4 3 4 PPP
4 2 4 2 PPP
4 4 4 4 PPP
5 2 5 2 PPP
5 4 5 4 PPP
6 1 6 1 PPP
6 2 5 1 ULP
6 3 4 3 UUP
7 4 6 4 UPP
8 1 7 1 UPP
8 3 5 3 UUU
8 4 8 4 PPP
9 3 9 3 PPP
10 1 9 1 UPP
10 3 8 3 UUP
10 4 10 4 PPP
11 1 11 1 PPP
11 2 10 2 UPP
11...

result:

ok answer 3

Test #108:

score: 0
Accepted
time: 7ms
memory: 8364kb

input:

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

output:

4
1 1 1 2 RPPP
1 3 1 3 PPPP
2 1 2 1 PPPP
2 2 1 5 RURR
2 3 2 3 PPPP
2 4 1 4 UPPP
2 5 2 5 PPPP
3 1 4 1 DPPP
3 2 3 2 PPPP
3 3 3 3 PPPP
3 5 3 5 PPPP
4 2 5 2 DPPP
4 3 4 3 PPPP
4 4 4 4 PPPP
4 5 4 5 PPPP
5 1 6 1 SDPP
5 2 9 2 DDDD
6 2 6 2 PPPP
6 3 10 3 DDDD
6 4 5 4 UPPP
6 5 6 5 PPPP
7 2 7 2 PPPP
7 3 7 3 PPP...

result:

ok answer 4

Test #109:

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

input:

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

output:

3
1 3 1 2 LPP
1 4 3 4 DDP
1 5 1 5 PPP
1 6 1 3 LLL
2 1 2 1 PPP
2 2 5 2 DDD
2 4 2 3 LPP
2 5 2 5 PPP
2 6 2 6 PPP
3 1 4 1 DPP
3 2 6 2 DDD
3 4 3 3 LPP
3 5 5 6 DDR
3 6 4 6 DPP
4 1 7 1 DDD
4 2 5 1 DLP
4 3 4 3 PPP
4 4 6 4 DDP
5 3 5 3 PPP
5 5 5 5 PPP
5 6 8 6 DDD
6 1 9 1 DDD
6 3 6 3 PPP
6 4 7 2 LLD
6 5 7 5 DP...

result:

ok answer 3

Test #110:

score: 0
Accepted
time: 6ms
memory: 8408kb

input:

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

output:

3
1 4 1 4 PPP
1 6 2 6 DPP
2 1 2 1 PPP
2 2 2 2 PPP
2 4 3 4 DPP
2 5 2 5 PPP
3 1 3 1 PPP
3 3 2 3 UPP
3 5 1 5 UUP
3 6 3 6 PPP
4 1 1 1 UUU
4 2 1 2 UUU
4 3 1 3 UUU
4 5 4 5 PPP
4 7 2 7 UUP
5 4 3 5 URU
6 2 3 2 UUU
6 3 5 3 UPP
6 4 6 4 PPP
6 5 6 5 PPP
6 7 3 7 UUU
7 1 4 1 UUU
7 3 8 1 DLL
7 4 7 4 PPP
7 5 7 2 LL...

result:

ok answer 3

Test #111:

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

input:

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

output:

2
1 2 1 3 RP
1 6 1 4 LL
1 8 1 8 PP
2 1 1 1 UP
2 4 2 4 PP
2 5 3 4 DL
2 6 2 6 PP
2 7 2 7 PP
2 8 3 8 DP
3 1 2 2 UR
3 2 2 3 UR
3 6 3 6 PP
4 1 2 1 UU
4 2 4 2 PP
4 3 3 3 UP
4 4 4 4 PP
4 6 3 7 UR
4 7 4 7 PP
4 8 6 8 DD
5 1 4 1 UP
5 2 5 2 PP
5 6 5 6 PP
5 8 5 8 PP
6 1 7 2 DR
6 2 8 2 DD
6 4 5 4 UP
6 6 5 7 UR
6...

result:

ok answer 2

Test #112:

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

input:

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

output:

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

result:

ok answer 2

Test #113:

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

input:

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

output:

2
1 2 1 2 PP
1 3 1 3 PP
1 4 1 4 PP
1 5 1 5 PP
1 6 3 6 DD
1 10 1 8 LL
2 1 1 1 UP
2 2 2 4 RR
2 3 2 3 PP
2 6 2 6 PP
2 7 2 7 PP
2 8 2 8 PP
2 9 2 9 PP
2 10 1 9 LU
3 1 2 2 UR
3 3 3 3 PP
3 4 3 4 PP
3 5 3 5 PP
3 7 3 7 PP
3 8 4 7 DL
3 9 4 8 DL
3 10 5 10 DD
4 1 5 1 DP
4 3 5 2 DL
4 5 4 5 PP
4 9 5 8 DL
5 3 5 3 ...

result:

ok answer 2

Test #114:

score: 0
Accepted
time: 12ms
memory: 8892kb

input:

70 100 1
100 1
38 1
87 1
80 1
90 1
60 1
61 1
15 1
40 1
20 1
12 1
66 1
88 1
92 1
11 1
64 1
34 1
28 1
55 1
26 1
72 1
1 1
76 1
3 1
98 1
67 1
69 1
7 1
44 1
24 1
30 1
56 1
79 1
93 1
47 1
29 1
46 1
5 1
49 1
77 1
74 1
73 1
25 1
99 1
33 1
19 1
18 1
51 1
86 1
48 1
9 1
70 1
52 1
4 1
94 1
50 1
14 1
91 1
27 1
2...

output:

5
1 1 6 1 DDDDD
2 1 2 1 PPPPP
3 1 3 1 PPPPP
4 1 4 1 PPPPP
5 1 5 1 PPPPP
7 1 7 1 PPPPP
8 1 8 1 PPPPP
9 1 9 1 PPPPP
11 1 11 1 PPPPP
12 1 12 1 PPPPP
14 1 10 1 UUUUP
15 1 20 1 DDDDD
16 1 16 1 PPPPP
17 1 17 1 PPPPP
18 1 18 1 PPPPP
19 1 19 1 PPPPP
20 1 23 1 DDDPP
23 1 28 1 DDDDD
24 1 29 1 DDDDD
25 1 30 1 ...

result:

ok answer 5

Test #115:

score: 0
Accepted
time: 6ms
memory: 8528kb

input:

70 50 2
29 2
49 2
25 1
30 1
40 1
6 1
4 2
12 1
22 1
11 2
29 1
28 2
17 1
17 2
27 2
36 2
46 2
44 2
38 1
3 2
45 2
44 1
34 2
5 1
30 2
13 2
14 1
47 1
48 2
40 2
34 1
35 2
1 2
18 1
24 2
23 2
18 2
8 2
15 2
31 1
33 1
21 1
37 2
42 1
2 2
24 1
12 2
25 2
45 1
16 2
41 2
23 1
15 1
14 2
32 2
46 1
16 1
10 2
22 2
42 2...

output:

4
1 2 1 2 PPPP
2 2 2 2 PPPP
3 2 3 1 LPPP
4 2 1 1 UUUL
5 1 2 1 UUUP
6 1 6 1 PPPP
6 2 5 2 UPPP
8 1 5 1 UUUP
8 2 4 2 UUUU
10 1 7 1 UUUP
10 2 8 2 UUPP
11 2 8 1 UUUL
12 1 9 1 UUUP
12 2 12 2 PPPP
13 2 9 2 UUUU
14 1 10 1 UUUU
14 2 10 2 UUUU
15 1 11 1 UUUU
15 2 11 2 UUUU
16 1 12 1 UUUU
16 2 16 2 PPPP
17 1 1...

result:

ok answer 4

Test #116:

score: 0
Accepted
time: 7ms
memory: 10132kb

input:

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

output:

2
1 1 1 2 RP
1 2 2 2 DP
1 3 1 3 PP
2 1 3 2 DR
2 3 3 3 DP
3 1 3 1 PP
3 3 5 3 DD
4 1 6 1 DD
5 1 6 2 DR
5 2 5 2 PP
5 3 6 3 DP
6 1 8 1 DD
6 2 7 3 DR
6 3 8 3 DD
7 1 9 1 DD
8 1 10 1 DD
8 3 9 2 DL
11 3 11 3 PP
12 1 11 1 UP
12 2 10 2 UU
12 3 10 3 UU
13 1 13 1 PP
13 2 11 2 UU
13 3 13 3 PP
14 1 14 1 PP
14 2 1...

result:

ok answer 2

Test #117:

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

input:

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

output:

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

result:

ok answer 2

Test #118:

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

input:

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

output:

2
1 1 1 1 PP
1 2 2 1 DL
1 4 1 2 LL
2 1 4 1 DD
2 2 4 2 DD
2 3 3 3 SD
2 5 1 5 UP
3 1 3 1 PP
3 2 5 2 DD
3 4 4 3 LD
3 5 5 5 DD
4 2 6 2 DD
4 3 5 3 DP
4 5 4 4 LP
5 1 5 1 PP
5 2 7 2 DD
5 4 5 4 PP
5 5 6 5 DP
6 1 6 1 PP
6 3 6 3 PP
6 4 6 4 PP
7 1 7 1 PP
7 2 8 2 DP
7 3 7 3 PP
7 4 7 4 PP
7 5 7 5 PP
8 1 8 1 PP
8...

result:

ok answer 2

Test #119:

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

input:

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

output:

2
1 2 1 2 PP
1 3 1 3 PP
1 4 1 4 PP
1 5 1 5 PP
1 6 1 6 PP
2 2 2 1 LP
2 3 2 3 PP
2 4 2 4 PP
2 6 2 5 LP
3 2 3 2 PP
3 3 3 3 PP
3 4 3 4 PP
3 6 5 6 DD
4 1 3 1 UP
4 2 2 2 UU
4 3 5 3 DP
4 4 4 4 PP
4 5 4 5 PP
5 1 5 1 PP
5 3 6 3 DP
5 5 5 5 PP
6 1 6 1 PP
6 2 5 2 UP
6 4 5 4 UP
6 5 6 5 PP
6 6 6 6 PP
7 1 7 1 PP
7...

result:

ok answer 2

Test #120:

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

input:

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

output:

2
1 2 1 2 PP
1 3 1 3 PP
1 4 1 4 PP
1 5 3 5 DD
1 6 1 6 PP
1 7 1 7 PP
2 1 2 3 RR
2 2 4 2 DD
2 3 3 4 DR
2 4 2 4 PP
2 5 2 5 PP
2 6 3 6 DP
2 7 2 7 PP
3 1 3 1 PP
3 2 5 2 DD
3 3 3 3 PP
3 4 4 4 DP
3 7 4 7 DP
4 1 4 1 PP
4 2 6 2 DD
4 4 4 5 RP
5 1 7 1 DD
5 2 5 4 RR
5 5 5 5 DU
5 7 5 6 LP
6 1 6 1 PP
6 2 6 3 RP
6...

result:

ok answer 2

Test #121:

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

input:

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

output:

2
1 1 1 1 PP
1 3 1 5 RR
1 4 3 4 DD
1 5 3 5 DD
1 6 2 5 DL
1 7 3 7 DD
1 8 1 8 PP
2 1 3 1 DP
2 2 4 2 DD
2 3 3 3 DP
2 4 4 4 DD
2 6 2 6 PP
2 7 4 7 DD
2 8 2 8 PP
3 1 5 1 DD
3 2 4 3 DR
3 3 5 3 DD
3 5 4 5 DP
3 7 5 7 DD
3 8 3 8 PP
4 1 5 2 DR
4 2 6 2 DD
4 4 5 5 DR
4 6 5 6 DP
4 7 5 8 DR
4 8 4 8 PP
5 1 7 1 DD
5...

result:

ok answer 2

Test #122:

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

input:

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

output:

2
1 1 1 1 PP
1 2 1 2 PP
1 3 1 3 PP
1 5 1 4 LP
1 6 2 7 DR
1 7 1 8 RP
1 9 1 9 PP
2 1 2 2 RP
2 3 3 4 RD
2 7 4 7 DD
2 8 2 8 PP
2 9 2 9 PP
3 1 3 1 PP
3 2 3 3 RP
3 5 2 5 UP
3 6 5 6 DD
3 8 3 8 PP
3 9 3 9 PP
4 1 5 2 DR
4 2 4 2 PP
4 3 4 3 PP
4 5 4 6 SR
4 6 4 8 RR
4 8 4 9 RP
5 1 5 1 PP
5 2 5 4 RR
5 7 5 7 PP
5...

result:

ok answer 2

Test #123:

score: 0
Accepted
time: 6ms
memory: 8304kb

input:

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

output:

2
1 2 1 2 PP
1 3 1 1 LL
1 4 1 4 PP
1 5 1 3 LL
1 6 1 6 PP
1 7 1 7 PP
1 8 1 8 PP
1 9 1 9 PP
1 10 1 10 PP
2 4 2 3 LP
2 5 2 5 PP
2 6 2 4 LL
2 7 2 6 LP
2 9 2 9 PP
3 1 3 1 PP
3 2 2 1 UL
3 4 3 3 LP
3 6 3 4 LL
3 7 3 5 LL
3 8 2 7 UL
3 9 2 10 UR
3 10 3 10 PP
4 2 4 1 LP
4 3 3 2 LU
4 4 4 2 LL
4 8 2 8 UU
5 4 4 3...

result:

ok answer 2

Test #124:

score: 0
Accepted
time: 15ms
memory: 9020kb

input:

80 1 100
1 41
1 75
1 13
1 62
1 25
1 89
1 45
1 40
1 10
1 81
1 100
1 26
1 97
1 30
1 42
1 96
1 19
1 80
1 38
1 61
1 11
1 68
1 44
1 84
1 98
1 49
1 20
1 83
1 27
1 37
1 93
1 52
1 23
1 14
1 86
1 67
1 43
1 99
1 56
1 53
1 88
1 28
1 87
1 95
1 74
1 50
1 79
1 64
1 18
1 54
1 12
1 36
1 94
1 31
1 82
1 63
1 91
1 51
...

output:

9
1 2 1 2 PPPPPPPPP
1 4 1 4 PPPPPPPPP
1 7 1 1 LLLLLLPPP
1 10 1 5 LLLLLPPPP
1 11 1 3 LLLLLLLLP
1 12 1 12 PPPPPPPPP
1 13 1 13 PPPPPPPPP
1 14 1 6 LLLLLLLLP
1 16 1 7 LLLLLLLLL
1 18 1 9 LLLLLLLLL
1 19 1 10 LLLLLLLLL
1 20 1 20 PPPPPPPPP
1 21 1 15 LLLLLLPPP
1 23 1 14 LLLLLLLLL
1 25 1 16 LLLLLLLLL
1 26 1 17...

result:

ok answer 9

Test #125:

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

input:

80 2 50
1 34
2 37
2 2
2 19
1 37
2 3
2 31
1 45
2 44
1 22
1 44
2 17
2 6
2 21
2 29
2 36
1 48
1 30
1 13
1 43
1 18
1 50
1 23
2 8
1 2
1 28
2 15
1 20
2 23
1 11
1 8
2 48
1 31
1 17
1 21
1 9
1 35
1 16
2 47
2 12
2 42
2 11
2 26
2 49
2 18
2 9
1 33
2 35
2 30
2 40
1 49
2 38
1 42
1 41
1 25
2 50
2 24
1 5
2 28
2 20
1...

output:

2
1 1 1 1 PP
1 2 1 3 RP
1 5 1 5 PP
1 7 1 6 LP
1 8 1 7 LP
1 9 1 9 PP
1 11 1 11 PP
1 12 1 12 PP
1 13 2 13 DP
1 14 1 14 PP
1 16 1 15 LP
1 17 1 16 LP
1 18 1 18 PP
1 19 1 19 PP
1 20 1 20 PP
1 21 1 21 PP
1 22 1 22 PP
1 23 1 23 PP
1 24 1 26 RR
1 25 1 25 PP
1 26 1 28 RR
1 27 1 27 PP
1 28 1 29 RP
1 30 1 31 R...

result:

ok answer 2

Test #126:

score: 0
Accepted
time: 7ms
memory: 8444kb

input:

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

output:

2
1 2 1 2 PP
1 5 1 4 LP
1 6 1 6 PP
1 7 1 5 LL
1 8 1 8 PP
1 9 1 7 LL
1 10 1 9 LP
1 11 1 11 PP
1 12 2 13 DR
1 14 1 16 RR
1 15 1 15 PP
1 16 1 18 RR
1 17 1 17 PP
1 18 1 19 RP
1 19 1 21 RR
1 20 1 22 RR
1 21 1 23 RR
1 22 1 24 RR
1 23 1 25 RR
1 24 1 26 RR
1 25 1 27 RR
1 27 1 29 RR
1 31 1 31 PP
1 32 1 32 PP...

result:

ok answer 2

Test #127:

score: 0
Accepted
time: 6ms
memory: 8412kb

input:

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

output:

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

result:

ok answer 2

Test #128:

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

input:

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

output:

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

result:

ok answer 1

Test #129:

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

input:

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

output:

1
1 2 1 1 L
1 3 1 3 P
1 4 1 4 P
1 5 1 5 P
1 6 2 6 D
1 7 1 6 L
1 8 1 7 L
1 9 1 9 S
1 10 1 11 R
1 11 1 12 R
1 12 1 13 R
1 14 1 15 R
1 15 1 16 R
2 1 2 1 P
2 2 2 2 P
2 3 2 3 P
2 4 2 4 P
2 5 2 5 P
2 8 1 8 U
2 9 2 9 P
2 10 2 10 P
2 11 2 11 P
2 12 3 12 D
2 13 2 13 P
2 14 1 14 U
2 15 2 15 P
2 16 3 16 D
3 1 ...

result:

ok answer 1

Test #130:

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

input:

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

output:

1
1 1 1 1 P
1 2 1 3 R
1 3 2 3 D
1 4 1 4 P
1 5 1 5 P
1 6 1 6 P
1 7 1 7 P
1 8 1 8 P
1 9 2 9 D
1 10 1 10 P
1 11 1 11 P
1 12 1 12 P
1 13 1 13 P
2 1 2 2 R
2 3 3 3 D
2 4 2 4 P
2 5 2 5 P
2 6 3 6 D
2 7 2 7 P
2 8 2 8 P
2 9 3 9 D
2 10 2 10 P
2 11 3 11 D
2 12 2 12 P
2 13 2 13 P
2 14 1 14 U
3 1 4 1 D
3 2 3 2 P
...

result:

ok answer 1

Test #131:

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

input:

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

output:

1
1 1 1 2 R
1 2 1 3 R
1 5 1 5 P
1 6 1 6 P
1 7 1 8 R
1 8 1 9 R
1 10 1 10 P
1 11 1 11 P
1 12 1 12 P
2 1 1 1 U
2 2 2 3 R
2 3 2 4 R
2 4 1 4 U
2 5 2 5 P
2 7 2 6 L
2 8 2 9 R
2 9 2 10 R
2 10 2 11 R
2 11 2 12 R
3 1 3 1 P
3 2 2 2 U
3 3 3 3 P
3 4 4 4 D
3 5 3 6 R
3 7 3 7 P
3 8 2 8 U
3 9 3 9 P
3 10 3 10 P
3 11 ...

result:

ok answer 1

Test #132:

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

input:

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

output:

1
1 1 1 1 P
1 2 1 2 P
1 4 1 5 R
1 7 1 7 P
1 8 1 8 P
1 9 1 9 P
1 10 1 10 P
1 11 1 11 P
2 2 2 3 R
2 3 2 4 R
2 4 1 4 U
2 5 2 5 P
2 6 2 6 P
2 7 2 7 P
2 8 2 8 P
2 9 3 9 D
2 10 2 10 P
2 11 2 11 P
3 1 2 1 U
3 2 2 2 U
3 3 3 3 P
3 4 3 4 P
3 5 3 5 P
3 7 3 6 L
3 8 3 8 P
3 9 4 9 D
3 10 3 10 P
3 11 3 11 P
4 1 3 ...

result:

ok answer 1

Test #133:

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

input:

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

output:

1
1 1 1 2 R
1 4 2 4 D
1 5 1 4 L
1 6 1 5 L
1 7 1 7 P
1 8 1 8 P
1 9 1 9 P
1 10 2 10 D
2 1 2 2 R
2 2 2 3 R
2 6 2 5 L
2 7 2 6 L
2 8 2 8 P
2 9 2 9 P
2 10 3 10 D
3 1 2 1 U
3 2 3 2 P
3 4 3 4 P
3 5 3 5 P
3 6 3 6 P
3 7 3 7 P
3 8 3 8 P
3 9 3 9 P
3 10 4 10 D
4 1 3 1 U
4 3 4 3 P
4 4 4 4 P
4 5 4 5 P
4 7 4 7 P
4 ...

result:

ok answer 1

Test #134:

score: 0
Accepted
time: 7ms
memory: 9156kb

input:

90 100 1
89 1
74 1
85 1
59 1
91 1
88 1
93 1
78 1
63 1
52 1
37 1
28 1
51 1
42 1
79 1
4 1
81 1
31 1
25 1
60 1
2 1
40 1
99 1
48 1
54 1
72 1
68 1
29 1
87 1
6 1
9 1
71 1
47 1
46 1
12 1
15 1
65 1
36 1
50 1
64 1
5 1
69 1
11 1
35 1
21 1
73 1
95 1
83 1
44 1
26 1
97 1
57 1
39 1
70 1
67 1
77 1
96 1
100 1
66 1
...

output:

4
1 1 5 1 DDDD
2 1 2 1 PPPP
3 1 3 1 PPPP
4 1 4 1 PPPP
5 1 7 1 DDPP
6 1 6 1 PPPP
8 1 8 1 PPPP
9 1 9 1 PPPP
11 1 11 1 PPPP
12 1 13 1 DPPP
15 1 15 1 PPPP
16 1 14 1 UUPP
17 1 17 1 PPPP
18 1 18 1 PPPP
20 1 16 1 UUUU
21 1 19 1 UUPP
22 1 22 1 PPPP
23 1 23 1 PPPP
24 1 20 1 UUUU
25 1 21 1 UUUU
26 1 26 1 PPPP...

result:

ok answer 4

Test #135:

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

input:

90 50 2
30 2
22 1
22 2
31 2
29 2
39 2
11 2
2 1
26 2
1 2
44 1
17 2
41 1
35 1
44 2
14 1
25 1
3 1
15 1
45 2
35 2
23 2
36 2
19 1
26 1
49 2
6 1
29 1
40 2
19 2
2 2
27 1
34 2
16 2
32 2
49 1
9 2
43 1
11 1
13 2
28 1
37 1
10 2
5 1
8 2
20 1
34 1
12 1
36 1
32 1
30 1
18 2
21 1
21 2
24 2
5 2
33 1
39 1
18 1
7 2
15...

output:

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

result:

ok answer 1

Test #136:

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

input:

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

output:

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

result:

ok answer 1

Test #137:

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

input:

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

output:

1
1 1 1 2 R
1 3 1 3 P
1 4 1 4 P
2 1 1 1 U
2 2 2 2 P
2 3 2 3 P
2 4 2 4 P
3 1 3 1 P
3 2 3 2 P
3 3 3 3 P
3 4 3 4 P
4 1 4 1 P
4 3 4 2 L
4 4 4 3 L
5 2 5 1 L
5 3 5 3 P
5 4 4 4 U
6 2 5 2 U
6 4 5 4 U
7 1 6 1 U
7 2 6 2 U
7 3 6 3 U
7 4 6 4 U
8 1 7 1 U
8 2 7 2 U
8 3 8 2 L
8 4 7 4 U
9 1 8 1 U
9 3 8 3 U
9 4 8 4 ...

result:

ok answer 1

Test #138:

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

input:

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

output:

1
1 1 2 1 D
1 2 1 2 P
1 3 1 3 P
1 4 1 4 P
1 5 2 5 D
2 1 3 1 D
2 2 3 2 D
2 3 2 3 P
2 4 3 4 D
2 5 2 4 L
3 1 4 1 D
3 4 3 3 L
3 5 4 5 D
4 2 4 2 P
4 4 4 3 L
4 5 4 4 L
5 1 5 1 P
5 2 5 2 P
5 4 5 4 P
5 5 5 5 P
6 1 6 1 P
6 2 6 2 P
6 3 5 3 U
6 5 6 5 P
7 1 7 1 P
7 2 7 2 P
7 3 6 3 U
7 4 6 4 U
7 5 7 5 P
8 1 9 1 ...

result:

ok answer 1

Test #139:

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

input:

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

output:

1
1 1 1 1 P
1 2 1 2 P
1 3 1 3 P
1 4 1 4 P
1 5 1 5 P
1 6 1 6 P
2 1 2 1 P
2 2 2 2 P
2 3 3 3 D
2 4 2 4 P
2 5 2 5 P
2 6 2 6 P
3 1 3 1 P
3 2 4 2 D
3 3 4 3 D
3 4 3 4 P
3 5 3 5 P
3 6 3 6 P
4 1 4 1 P
4 2 5 2 D
4 3 5 3 D
4 4 4 4 P
4 5 4 5 P
4 6 4 6 P
5 1 5 1 P
5 2 6 2 D
5 3 5 4 R
5 4 6 4 D
5 5 5 5 P
5 6 5 6 ...

result:

ok answer 1

Test #140:

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

input:

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

output:

1
1 1 1 1 P
1 2 1 2 P
1 3 1 4 R
1 5 1 5 P
1 6 1 6 P
1 7 1 7 P
2 1 2 1 P
2 2 2 2 P
2 3 1 3 U
2 4 2 4 P
2 5 2 5 P
2 6 2 6 P
2 7 2 7 P
3 1 3 1 P
3 2 3 2 P
3 3 3 3 P
3 4 3 4 P
3 5 3 5 P
3 6 3 6 P
3 7 3 7 P
4 1 4 1 P
4 3 4 2 L
4 4 4 4 P
4 5 4 5 P
4 6 4 6 P
4 7 4 7 P
5 1 5 1 P
5 2 5 2 P
5 3 5 3 P
5 4 5 4 ...

result:

ok answer 1

Test #141:

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

input:

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

output:

1
1 2 1 2 P
1 3 1 3 P
1 4 1 4 P
1 5 1 5 P
1 6 1 6 P
1 7 1 7 P
1 8 1 8 P
2 1 1 1 U
2 2 2 2 P
2 3 2 3 P
2 4 2 4 P
2 5 2 5 P
2 6 2 6 P
2 7 2 7 P
2 8 2 8 P
3 1 2 1 U
3 2 3 2 P
3 3 4 3 D
3 4 3 4 P
3 5 3 5 P
3 7 3 6 L
3 8 3 8 P
4 1 3 1 U
4 2 4 2 P
4 3 4 4 R
4 4 4 5 R
4 6 4 6 P
4 7 3 7 U
4 8 4 8 P
5 1 4 1 ...

result:

ok answer 1

Test #142:

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

input:

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

output:

1
1 1 1 1 P
1 2 1 2 P
1 3 1 3 P
1 4 2 4 D
1 5 1 5 P
1 6 1 6 P
1 7 1 8 R
1 9 1 9 P
2 1 2 1 P
2 2 2 2 P
2 3 2 3 P
2 4 3 4 D
2 5 2 5 P
2 6 3 6 D
2 7 2 7 P
2 8 2 8 P
2 9 2 9 P
3 1 3 1 P
3 2 3 2 P
3 3 3 3 P
3 4 4 4 D
3 5 3 5 P
3 6 3 7 R
3 7 3 8 R
3 9 3 9 P
4 1 4 1 P
4 2 4 2 P
4 3 4 3 P
4 4 4 5 R
4 5 4 6 ...

result:

ok answer 1

Test #143:

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

input:

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

output:

1
1 1 1 1 P
1 3 1 2 L
1 4 1 4 P
1 5 1 5 P
1 6 2 6 D
1 7 1 8 R
1 8 1 9 R
1 10 1 10 P
2 1 2 1 P
2 2 2 2 P
2 3 1 3 U
2 5 2 5 P
2 7 2 7 P
2 8 2 8 P
2 9 2 9 P
2 10 2 10 P
3 1 3 1 P
3 2 3 2 P
3 3 2 3 U
3 4 3 4 P
3 5 3 5 P
3 6 3 6 P
3 7 3 7 P
3 8 3 8 P
3 9 3 9 P
3 10 3 10 P
4 1 4 1 P
4 2 4 2 P
4 3 3 3 U
4 ...

result:

ok answer 1

Test #144:

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

input:

99 1 100
1 62
1 15
1 97
1 31
1 78
1 51
1 48
1 89
1 4
1 16
1 47
1 33
1 88
1 87
1 55
1 22
1 11
1 44
1 43
1 73
1 7
1 74
1 1
1 36
1 20
1 92
1 95
1 64
1 85
1 61
1 42
1 75
1 3
1 49
1 82
1 72
1 70
1 77
1 17
1 28
1 30
1 90
1 9
1 57
1 58
1 98
1 25
1 76
1 13
1 19
1 14
1 23
1 40
1 71
1 96
1 27
1 50
1 94
1 32
1...

output:

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

result:

ok answer 1

Test #145:

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

input:

99 2 50
2 18
1 20
2 6
2 9
1 3
2 30
2 4
1 33
2 43
2 21
1 31
2 24
1 10
1 42
1 4
1 45
2 28
1 27
1 24
2 47
1 47
1 13
2 40
1 18
1 22
1 36
2 5
2 16
1 37
1 49
1 50
2 31
2 32
1 17
1 14
1 19
2 35
1 44
2 29
2 23
1 12
1 6
2 17
1 9
2 8
1 7
2 11
2 38
2 10
2 26
2 44
1 8
1 40
1 34
1 26
2 36
2 22
1 32
2 48
2 27
2 4...

output:

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

result:

ok answer 1

Test #146:

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

input:

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

output:

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

result:

ok answer 1

Test #147:

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

input:

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

output:

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

result:

ok answer 1

Test #148:

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

input:

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

output:

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

result:

ok answer 1

Test #149:

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

input:

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

output:

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

result:

ok answer 1

Test #150:

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

input:

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

output:

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

result:

ok answer 1

Test #151:

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

input:

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

output:

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

result:

ok answer 1

Test #152:

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

input:

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

output:

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

result:

ok answer 1

Test #153:

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

input:

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

output:

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

result:

ok answer 1