QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410202#6615. Cross the MazeSiilhouetteAC ✓23ms9448kbC++234.2kb2024-05-13 18:18:272024-05-13 18:18:28

Judging History

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

  • [2024-05-13 18:18:28]
  • 评测
  • 测评结果:AC
  • 用时:23ms
  • 内存:9448kb
  • [2024-05-13 18:18:27]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<set>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;

const int N=200010;
const int M=200010;
const int inf=1000000000;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,-1,1};
int n,m,q,st,ed,tot=1,head[N],d[N],cur[N];
vector<pair<int,int> >stx,edx;
vector<int>c[110];
struct Edge{
	int ver,suiv,edge;
	char dir;
}e[M<<1];

inline void _lnk(int x,int y,int z,char ch)
{
	e[++tot].ver=y;
	e[tot].edge=z;
	e[tot].suiv=head[x];
	head[x]=tot;
	e[tot].dir=ch;
}

inline void lnk(int x,int y,int z,char ch)
{
	_lnk(x,y,z,ch),_lnk(y,x,0,ch);
}

inline int dfs(int x,int flow)
{
	if(x==ed)return flow;
	int minflow,resflow=0;
	for(int &i=cur[x];i;i=e[i].suiv)
	//for(int i=head[x];i;i=e[i].suiv)
	{
		int y=e[i].ver;
		if(d[y]!=d[x]+1||!e[i].edge)continue;
		minflow=dfs(y,min(flow,e[i].edge));
		flow-=minflow;
		e[i].edge-=minflow;
		resflow+=minflow;
		e[i^1].edge+=minflow;
		if(!flow)break;
	}
	if(!resflow)d[x]=-1;
	return resflow;
}


inline bool bfs()
{
	memset(d,-1,sizeof(d));
	queue<int>q;
	q.push(st);
	d[st]=0;
	while(q.size())
	{
		int x=q.front();q.pop();
		for(int i=head[x];i;i=e[i].suiv)
		{
			int y=e[i].ver;
			if(~d[y]||!e[i].edge)continue;
			d[y]=d[x]+1;
			q.push(y);
		}
	}
	return ~d[ed];
}


inline ll dinic()
{
	ll res=0;
	while(bfs())
	{
		memcpy(cur,head,sizeof(head));
		res+=1ll*dfs(st,inf);
	}
	return res;
}

inline int _(int dep,int op,int x,int y)
{
	return ((dep-1)*2+op)*n*m+(x-1)*m+y;
}

inline void dfs1(int x,int id)
{
	//cout<<"dfs1 "<<x<<" "<<id<<endl;
	if(x==ed)return;
	for(int i=head[x];i;i=e[i].suiv)
	{
		int y=e[i].ver,z=e[i].edge;
		if((i&1)||z)continue;
		if(e[i].dir!=0)c[id].push_back(e[i].dir)
			//,cout<<"id "<<id<<" "<<char(e[i].dir)<<endl
			;
		dfs1(y,id);
	}
}

inline bool valid(int mid)
{
	tot=1;
	memset(head,0,sizeof(head));
	st=0,ed=N-1;
	for(auto pos:stx)
		lnk(st,_(1,0,pos.first,pos.second),1,0);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			lnk(_(1,0,i,j),_(1,1,i,j),1,0);
	for(int i=1;i<=q;i++)
		lnk(N-1-i,ed,1,0);
	for(int i=1;i<=q;i++)
		lnk(_(1,1,edx[i-1].first,edx[i-1].second),N-1-i,1,0);
	for(int i=1;i<=mid;i++)
	{
		for(int j=1;j<=n;j++)
			for(int k=1;k<=m;k++)
			{
				for(int l=0;l<4;l++)
				{
					int posx=j+dx[l],posy=k+dy[l];
					if(posx<1||posx>n||posy<1||posy>m)continue;
					char ch;
					if(dx[l]==0&&dy[l]==1)ch='R';
					else if(dx[l]==0&&dy[l]==-1)ch='L';
					else if(dx[l]==-1&&dy[l]==0)ch='U';
					else ch='D';
					//cout<<"lnk "<<ch<<endl;
					lnk(_(i,1,j,k),_(i+1,0,posx,posy),1,ch);
				}
				lnk(_(i,1,j,k),_(i+1,0,j,k),1,'S');
				lnk(_(i+1,0,j,k),_(i+1,1,j,k),1,0);
			}
		for(int j=1;j<=q;j++)
			lnk(_(i+1,1,edx[j-1].first,edx[j-1].second),N-1-j,1,0);
	}
	return dinic()>=q;
}


signed main()
{
	scanf("%d%d%d",&q,&n,&m);
	//swap(n,m);
	for(int i=1,x,y;i<=q;i++)
		scanf("%d%d",&x,&y)
		//,swap(x,y)
		,stx.push_back(make_pair(x,y));
	for(int i=1,x,y;i<=q;i++)
		scanf("%d%d",&x,&y)
		//,swap(x,y)
		,edx.push_back(make_pair(x,y));
	
	//dinic();
	//cout<<maxflow<<endl;
	//ans=3;
	//cout<<valid(25)<<endl;
	int l=1,r=n*m,ans=-1;
	while(l<=r)
	{
		int mid=l+r>>1;
		//cout<<"valid "<<mid<<endl;
		if(valid(mid))r=mid-1,ans=mid
			//,cout<<"ok"<<endl
			;
		else l=mid+1
			//,cout<<"no"<<endl
			;
	}
	valid(ans);
	printf("%d\n",ans);
	for(int i=1;i<=q;i++)
		dfs1(_(1,0,stx[i-1].first,stx[i-1].second),i);
	for(int i=1;i<=q;i++)
	{
		//for(int j=1,lim=c[i].size();j<=lim;j++)
		//	printf("%c",c[i][j-1]);
		//putchar('\n');


		printf("%d %d ",stx[i-1].first,stx[i-1].second);
		int posx=stx[i-1].first,posy=stx[i-1].second;
		for(int j=1;j<=ans;j++)
		{
			if(j>c[i].size())break;
			if(c[i][j-1]=='S')continue;
			if(c[i][j-1]=='R')posy+=1;
			if(c[i][j-1]=='L')posy-=1;
			if(c[i][j-1]=='U')posx-=1;
			if(c[i][j-1]=='D')posx+=1;
		}
		printf("%d %d ",posx,posy);
		for(int j=1,lim=c[i].size();j<=ans;j++)
			printf("%c",j<=lim?c[i][j-1]:'P');
		putchar('\n');
	}
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 6196kb

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 LD
4 4 2 4 UU

result:

ok answer 2

Test #2:

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

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

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

input:

2 10 10
2 9
3 8
10 5
10 10

output:

10
2 9 10 10 DRDDDDDDDP
3 8 10 5 LLLDDDDDDD

result:

ok answer 10

Test #5:

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

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 6 8 RDLLD
4 2 3 2 UPPPP
3 6 2 9 RRRUP
10 1 5 1 UUUUU
10 10 5 10 UUUUU
4 1 6 3 DRRDP

result:

ok answer 5

Test #6:

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

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 LDPP
4 1 1 2 RUUU

result:

ok answer 4

Test #7:

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

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

input:

1 10 10
10 1
6 6

output:

9
10 1 6 6 RRRRRUUUU

result:

ok answer 9

Test #9:

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

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 2 10 RRUUUUU
4 6 3 10 RRRRUPP
10 9 10 2 LLLLLLL
4 7 3 8 RUPPPPP
4 3 3 7 RDRRRUU
10 6 6 4 LLUUUUP
3 3 6 1 LLDDDPP
2 7 1 9 DURRUPP

result:

ok answer 7

Test #10:

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

input:

1 10 10
10 3
2 6

output:

11
10 3 2 6 RRRUUUUUUUU

result:

ok answer 11

Test #11:

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

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 RRRUP

result:

ok answer 5

Test #12:

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

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 LULUU
1 7 2 8 RDPPP
2 1 1 1 RLUPP
5 6 5 3 LLLPP
10 8 7 8 UUUPP
3 5 2 2 LLLUP
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: 5ms
memory: 7052kb

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: 9ms
memory: 7080kb

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 LLDD
10 8 8 10 RRUU
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: 4ms
memory: 8864kb

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: 10ms
memory: 8568kb

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
5 10 4 10 UPPPPP
3 8 8 9 RDDDDD
2 8 3 6 LLDPPP
3 5 6 5 RLDDDP
4 2 10 2 DDDDDD
8 2 10 6 DDRRRR
7 9 9 6 DLLLDP
3 4 5 5 RDDPPP

result:

ok answer 6

Test #17:

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

input:

1 10 10
8 6
1 8

output:

9
8 6 1 8 RRUUUUUUU

result:

ok answer 9

Test #18:

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

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 LLLUP
9 10 10 8 LLDPP
5 7 1 6 LUUUU
10 7 5 7 UUUUU
4 1 4 2 RPPPP
1 5 1 9 RRRRP
6 7 2 6 ULUUU
6 4 8 3 LDDPP
5 3 5 1 LLPPP

result:

ok answer 5

Test #19:

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

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
4 5 6 2 LLLDDP
1 5 2 7 RRDPPP
6 5 6 3 LLPPPP
9 6 10 6 DPPPPP
5 5 5 1 LLLLPP
9 3 8 1 LLUPPP
1 10 7 10 DDDDDD

result:

ok answer 6

Test #20:

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

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 RRRUUUUU
4 1 4 1 PPPPPPPP
9 1 3 1 UUUUUUPP
7 9 2 10 RUUUUUPP
2 6 1 7 RUPPPPPP
9 5 5 1 LLLLUUUU

result:

ok answer 8

Test #21:

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

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 6 1 LPPPP
10 8 8 10 RRUUP
1 10 3 9 LDDPP
9 5 6 4 LUUUP
1 2 3 5 RDDRR
8 3 4 3 UUUUP
10 9 8 9 UUPPP

result:

ok answer 5

Test #22:

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

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 10 2 LDDDDDDD
9 2 9 1 LPPPPPPP
2 4 2 5 RPPPPPPP
5 8 5 8 PPPPPPPP
1 6 3 6 DDPPPPPP
4 9 4 2 LLLLLLLP

result:

ok answer 8

Test #23:

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

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 RUPP
9 2 9 1 LPPP
7 7 7 7 PPPP
7 3 5 1 LLUU
6 8 7 6 LLDP
5 4 3 2 LLUU
2 10 6 10 DDDD
1 1 3 1 DDPP
5 9 9 9 DDDD
4 6 4 8 RRPP

result:

ok answer 4

Test #24:

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

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

result:

ok answer 13

Test #25:

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

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

result:

ok answer 25

Test #26:

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

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 88 1 82 LLLLLLPPPPPPPPPPPPPPPPP
1 38 1 15 LLLLLLLLLLLLLLLLLLLLLLL
1 43 1 51 RRRRRRRRPPPPPPPPPPPPPPP
1 99 1 97 LLPPPPPPPPPPPPPPPPPPPPP
1 63 1 74 LLLLLRRRRRRRRRRRRRRRRPP
1 24 1 6 LLLLLLLLLLLLLLLLLLPPPPP
1 44 1 57 RRRRRRRRRRRRRPPPPPPPPPP
1 31 1 14 LLLLLLLLLLLLLLLLLPPPPPP
1 47 1 55 RRRRRRRRPPPPPPPP...

result:

ok answer 23

Test #27:

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

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
96 1 68 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUPPPPPPP
41 1 31 1 UUUUUUUUUUPPPPPPPPPPPPPPPPPPPPPPPPP
76 1 41 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
97 1 77 1 UUUUUUUUUUUUUUUUUUUUPPPPPPPPPPPPPPP
72 1 39 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUPP
94 1 84 1 UUUUUUUUUUPPP...

result:

ok answer 35

Test #28:

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

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 UDDDDDDDDDDDDDDDDDDDDDDDDDDP
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: 18ms
memory: 7112kb

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
42 1 72 1 DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDPPPP
4 1 17 1 DDDDDDDDDDDDDPPPPPPPPPPPPPPPPPPPPP
64 1 70 1 DDDDDDPPPPPPPPPPPPPPPPPPPPPPPPPPPP
31 1 56 1 DDDDDDDDDDDDDDDDDDDDDDDDDPPPPPPPPP
92 1 88 1 UUUUPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
45 1 51 1 DDDDDDPPPPPPPPPPPPPPPPPPPPPPPPPPPP
60 1 87 1 UUUDDDDDDDDDDDDDDD...

result:

ok answer 34

Test #30:

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

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

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

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

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

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

input:

2 2 50
1 21
1 41
2 36
1 11

output:

10
1 21 1 11 LLLLLLLLLL
1 41 2 36 LLLLLDPPPP

result:

ok answer 10

Test #36:

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

input:

2 3 33
3 17
2 13
1 23
1 24

output:

11
3 17 1 24 RRRRRRUURPP
2 13 1 23 RRRRRRRRRRU

result:

ok answer 11

Test #37:

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

input:

2 4 25
3 15
2 22
1 22
1 11

output:

6
3 15 1 11 LLLLUU
2 22 1 22 UPPPPP

result:

ok answer 6

Test #38:

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

input:

2 5 20
2 18
5 2
5 7
3 8

output:

11
2 18 3 8 LLLLLLLLLLD
5 2 5 7 RRRRRPPPPPP

result:

ok answer 11

Test #39:

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

input:

2 6 16
5 12
6 4
1 11
5 15

output:

12
5 12 5 15 RRRPPPPPPPPP
6 4 1 11 RRRRRRRUUUUU

result:

ok answer 12

Test #40:

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

input:

2 7 14
3 14
7 1
1 12
6 4

output:

4
3 14 1 12 LLUU
7 1 6 4 RRRU

result:

ok answer 4

Test #41:

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

input:

2 8 12
8 4
1 4
5 12
2 6

output:

11
8 4 5 12 RRRRRRRRUUU
1 4 2 6 RRDPPPPPPPP

result:

ok answer 11

Test #42:

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

input:

2 9 11
1 7
3 4
4 3
7 6

output:

7
1 7 7 6 LDDDDDD
3 4 4 3 LDPPPPP

result:

ok answer 7

Test #43:

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

input:

2 10 10
4 5
10 7
4 2
2 10

output:

11
4 5 4 2 LLLPPPPPPPP
10 7 2 10 RRRUUUUUUUU

result:

ok answer 11

Test #44:

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

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

result:

ok answer 11

Test #45:

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

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 RUPPPPPPPP
12 2 6 1 UUULUUUPPP
39 1 41 2 RDDPPPPPPP
36 1 34 2 RUUPPPPPPP
19 2 9 2 UUUUUUUUUU

result:

ok answer 10

Test #46:

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

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 LUPP
4 1 4 1 PPPP
23 1 20 2 RUUU
23 3 21 3 UUPP
27 1 28 1 DPPP

result:

ok answer 4

Test #47:

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

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 LUUUUU
1 3 7 3 DDDDDD

result:

ok answer 6

Test #48:

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

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 LLLUUUPPP
15 3 20 2 LDDDDDPPP
16 5 15 5 UPPPPPPPP
12 2 3 2 UUUUUUUUU
15 2 19 1 LDDDDPPPP

result:

ok answer 9

Test #49:

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

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 3 4 RRUUUUUUUUUU
5 2 1 2 UUUUPPPPPPPP
2 6 2 3 LLLPPPPPPPPP
16 2 14 2 UUPPPPPPPPPP
3 4 1 4 UUPPPPPPPPPP

result:

ok answer 12

Test #50:

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

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 RURR
13 7 12 7 UPPP

result:

ok answer 4

Test #51:

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

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 LLLUUPP
11 8 7 6 LLUUUUP
1 7 2 1 LLLLLLD
4 8 5 8 DPPPPPP
11 4 6 3 ULUUUUP

result:

ok answer 7

Test #52:

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

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 RUUUU
1 4 2 6 RRDPP
10 4 7 3 LUUUP

result:

ok answer 5

Test #53:

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

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 LLLDPPP
7 4 9 5 RDDPPPP
6 5 6 5 PPPPPPP

result:

ok answer 7

Test #54:

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

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

result:

ok answer 19

Test #55:

score: 0
Accepted
time: 11ms
memory: 8724kb

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 SLLLLLPPPPPPPPP
1 48 2 48 DPPPPPPPPPPPPPP
1 33 2 29 LLLLDPPPPPPPPPP
1 22 1 23 RPPPPPPPPPPPPPP
1 10 2 23 RRRRRRRRRRRRRDP
2 5 1 6 RUPPPPPPPPPPPPP
1 49 1 48 LPPPPPPPPPPPPPP
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: 12ms
memory: 8904kb

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 16 1 18 RRPPPPPPP
1 4 2 6 RRDPPPPPP
1 30 3 31 RDDPPPPPP
2 8 2 2 RLLLLLLLP
1 8 3 9 RDDPPPPPP
2 16 2 11 LLLLLPPPP
3 33 3 33 PPPPPPPPP
2 12 2 10 LLPPPPPPP
2 20 3 28 RRRRRRRRD
1 15 3 10 LLLLLDDPP

result:

ok answer 9

Test #57:

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

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
4 13 2 13 UUPPPP
2 1 3 3 RRDPPP
1 6 2 6 DPPPPP
2 2 2 4 RRPPPP
2 15 4 15 DDPPPP
3 12 3 7 LLLLLP
3 19 1 22 RRRUUP
4 18 2 18 UUPPPP
4 23 1 24 RUUUPP
4 10 4 4 LLLLLL

result:

ok answer 6

Test #58:

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

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 3 7 RRRPPP
2 18 1 20 RRUPPP
4 11 1 9 UULLUP
3 16 2 11 LLLLLU
5 13 5 8 LLLLLP
5 20 3 17 LLLUUP
1 7 2 6 RRLLLD
5 4 4 2 LLUPPP
3 14 1 12 LLUUPP
2 1 3 1 DPPPPP

result:

ok answer 6

Test #59:

score: 0
Accepted
time: 11ms
memory: 8368kb

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 2 14 LUUUUPP
6 10 6 3 LLLLLLL
4 13 4 14 RPPPPPP
5 10 2 9 LUUUPPP
2 7 4 2 LLLLLDD
2 16 2 16 PPPPPPP
1 11 2 11 DPPPPPP
5 9 4 6 LLLUPPP
2 1 2 2 RPPPPPP
1 1 2 4 RRRDPPP

result:

ok answer 7

Test #60:

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

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 LUP
4 8 3 7 LUP
6 12 6 11 LPP
2 13 3 12 LDP
1 5 2 4 LDP
4 1 7 1 DDD
2 9 2 7 LLP
5 4 4 5 RUP
6 14 6 13 LPP

result:

ok answer 3

Test #61:

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

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 RRRU
8 10 7 11 RUPP
3 11 4 11 DPPP
5 10 5 8 LLPP
1 11 2 8 LLLD
7 4 7 7 RRRP
8 2 8 4 RRPP

result:

ok answer 4

Test #62:

score: 0
Accepted
time: 11ms
memory: 8792kb

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 5 9 RRRRR
4 4 4 7 RRRPP
9 10 7 7 LLLUU
5 6 6 8 RRDPP
8 11 8 8 LLLPP
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: 11ms
memory: 7068kb

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

result:

ok answer 7

Test #64:

score: 0
Accepted
time: 22ms
memory: 6896kb

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
77 1 93 1 DDDDDDDDDDDDDDDDP
38 1 42 1 DDDDPPPPPPPPPPPPP
67 1 84 1 DDDDDDDDDDDDDDDDD
91 1 95 1 UDDDDDPPPPPPPPPPP
60 1 70 1 DDDDDDDDDDPPPPPPP
34 1 19 1 UUUUUUUUUUUUUUUPP
32 1 32 1 PPPPPPPPPPPPPPPPP
56 1 47 1 UUUUUUUUUPPPPPPPP
76 1 90 1 DDDDDDDDDDDDDDPPP
57 1 58 1 DPPPPPPPPPPPPPPPP
22 1 8 1 UUUUUUUU...

result:

ok answer 17

Test #65:

score: 0
Accepted
time: 11ms
memory: 8708kb

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
23 2 22 2 UPPPPPPPPPPPPPPPP
17 2 8 2 UUUUUUUUUPPPPPPPP
46 1 38 1 UUUUUUUUPPPPPPPPP
38 1 27 2 RUUUUUUUUUUUPPPPP
47 1 47 2 RPPPPPPPPPPPPPPPP
33 1 19 2 RUUUUUUUUUUUUUUPP
45 2 29 2 SUUUUUUUUUUUUUUUU
24 1 21 2 RUUUPPPPPPPPPPPPP
16 1 5 1 UUUUUUUUUUUPPPPPP
18 1 19 1 DPPPPPPPPPP...

result:

ok answer 17

Test #66:

score: 0
Accepted
time: 11ms
memory: 7104kb

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
32 1 33 1 DPPPPPP
20 2 13 2 UUUUUUU
18 2 12 1 LUUUUUU
32 2 31 3 RUPPPPP
3 2 4 2 DPPPPPP
23 3 17 3 UUUUUUP
2 2 4 1 LDDPPPP
8 3 9 3 DPPPPPP
8 1 8 2 RPPPPPP
28 2 25 2 SUUUPPP
23 1 19 1 UUUUPPP
17 1 10 1 UUUUUUU
7 3 10 3 DDDPPPP
16 1 15 3 RRUPPPP
27 1 22 2 RUUUUUP
1 2 5 1 LDDDDPP
24 1 19 2 RUUUUUP
19 ...

result:

ok answer 7

Test #67:

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

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
23 2 22 2 UPPPPPP
8 2 9 2 SDPPPPP
24 3 24 4 RPPPPPP
12 2 19 2 DDDDDDD
11 4 16 3 LDDDDDP
13 3 19 3 DDDDDDP
13 1 20 1 DDDDDDD
23 3 23 4 RPPPPPP
2 2 3 2 DPPPPPP
20 2 20 4 LRRRPPP
10 4 10 3 LPPPPPP
17 1 21 4 RRRDDDD
24 2 21 1 LUUUPPP
25 2 25 1 LPPPPPP
2 1 8 2 RDDDDDD
6 1 12 2 RDDDDDD
3 4 2 4 UPPPPPP
5...

result:

ok answer 7

Test #68:

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

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
16 1 19 2 RDDD
5 2 5 4 RRPP
7 4 5 5 RUUP
12 5 14 4 LDDP
10 5 14 5 DDDD
16 5 17 5 DPPP
9 1 9 1 PPPP
1 3 3 5 RRDD
11 5 11 5 PPPP
12 1 13 1 DPPP
15 5 18 4 LDDD
15 3 18 3 SDDD
6 3 6 2 LPPP
8 1 8 1 PPPP
14 1 15 3 RRDP
3 3 3 4 RPPP
11 3 13 3 DDPP
7 1 7 4 RRRP
4 2 2 1 LUUP
10 4 8 4 UUPP

result:

ok answer 4

Test #69:

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

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
6 5 10 3 LLDDDD
5 6 4 4 LLUPPP
1 2 3 3 RDDPPP
3 6 3 4 LLPPPP
8 5 10 4 LDDPPP
14 3 13 3 UPPPPP
1 1 1 1 PPPPPP
4 1 10 1 DDDDDD
5 2 7 2 RULDDD
10 1 12 1 DDPPPP
13 1 16 1 DDDPPP
6 3 12 3 DDDDDD
13 5 11 3 LLUUPP
1 4 1 6 RRPPPP
2 5 2 5 PPPPPP
8 2 13 1 LDDDDD
2 1 3 2 RDPPPP
16 2 16 3 RPPPPP
12 2 15 2 DDD...

result:

ok answer 6

Test #70:

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

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
3 6 7 6 DDDD
3 1 5 1 DDPP
12 6 14 5 LDDP
10 6 11 6 DPPP
6 1 6 2 RPPP
13 2 13 4 RRPP
8 2 8 4 RRPP
12 3 11 5 RRUP
1 2 4 1 LDDD
11 5 9 5 UUPP
5 4 6 5 RUDD
7 4 7 4 PPPP
4 1 4 5 RRRR
11 4 11 4 PPPP
5 3 6 3 DPPP
1 3 1 1 LLPP
6 6 9 7 RDDD
12 1 12 2 RPPP
11 7 11 7 PPPP
11 2 11 1 LPPP

result:

ok answer 4

Test #71:

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

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
6 6 3 4 LLUUU
12 1 12 1 PPPPP
3 6 2 4 RULLL
7 6 7 6 PPPPP
8 4 8 4 PPPPP
4 5 1 3 LULUU
5 1 3 1 UUPPP
5 5 2 3 LUUUL
10 3 7 3 SUUUP
9 4 12 4 DDDPP
8 2 5 1 LUUUP
5 8 5 8 PPPPP
7 4 3 3 LUUUU
5 3 1 2 UULUU
12 2 11 2 UPPPP
8 5 7 1 LLLLU
10 7 9 7 UPPPP
6 4 3 2 LLUUU
6 7 2 7 UUUUP
8 6 9 8 RRDPP

result:

ok answer 5

Test #72:

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

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 3 1 1 LLUUU
8 7 8 7 PPPPP
5 9 5 6 LLLPP
7 1 3 1 UUUUP
4 8 4 3 LLLLL
10 4 10 4 PPPPP
6 6 6 1 LLLLL
8 6 4 5 LUUUU
9 9 10 9 DPPPP
11 2 11 2 PPPPP
11 5 11 6 RPPPP
4 5 2 4 LUUPP
9 6 9 7 RPPPP
11 8 11 8 PPPPP
10 3 7 3 UUUPP
4 7 1 6 LUUUP
7 8 11 9 RDDDD
5 5 4 2 LLLUP
8 5 6 4 LUUPP
1 8 1 9 RPPPP

result:

ok answer 5

Test #73:

score: 0
Accepted
time: 11ms
memory: 7324kb

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 DRR
1 7 1 6 LPP
9 9 9 6 LLL
8 4 7 6 RUR
2 5 2 6 RPP
4 2 4 2 PPP
4 4 4 3 LPP
2 4 2 4 PPP
8 3 7 5 URR
8 2 5 2 UUU
4 6 6 5 LDD
6 10 6 9 LPP
8 1 7 2 RUP
3 6 2 8 RRU
9 2 10 2 DPP
5 2 5 3 RDU
9 3 7 3 SUU
10 8 10 5 LLL

result:

ok answer 3

Test #74:

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

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 85 1 83 LLPPPPPP
1 59 1 51 LLLLLLLL
1 11 1 14 RRRPPPPP
1 17 1 24 RRRRRRRP
1 95 1 87 LLLLLLLL
1 98 1 93 LLLLLPPP
1 38 1 39 RPPPPPPP
1 47 1 43 LLLLPPPP
1 5 1 8 RRRPPPPP
1 92 1 84 LLLLLLLL
1 33 1 34 RPPPPPPP
1 30 1 31 RPPPPPPP
1 26 1 26 PPPPPPPP
1 50 1 45 RLLLLLLP
1 8 1 16 RRRRRRRR
1 86 1 86 PPPPPP...

result:

ok answer 8

Test #75:

score: 0
Accepted
time: 11ms
memory: 9036kb

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 40 2 39 LPPPPP
2 29 2 29 PPPPPP
2 44 1 40 LLLLUP
1 23 1 27 RRRRPP
2 48 2 46 LLPPPP
1 31 2 31 DPPPPP
1 15 1 17 RRPPPP
1 38 1 38 PPPPPP
1 9 1 14 RRRRRP
2 3 2 2 LPPPPP
1 30 1 28 LLPPPP
2 7 2 5 LLPPPP
2 13 2 13 PPPPPP
2 19 2 19 PPPPPP
1 7 1 2 LLLLLP
2 20 1 21 RUPPPP
1 46 2 41 DLLLLL
1 50 2 50 DPPPPP...

result:

ok answer 6

Test #76:

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

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 14 1 13 LPPPP
2 12 3 8 LLLLD
3 24 3 24 PPPPP
2 29 3 29 DPPPP
1 30 1 31 RPPPP
1 22 2 20 LLDPP
1 29 1 33 RRRRP
1 9 1 4 LLLLL
3 28 3 26 LLPPP
3 7 3 4 LLLPP
3 11 3 6 LLLLL
1 17 3 15 LLDDP
1 23 3 25 RDDRP
2 21 2 21 PPPPP
2 6 2 2 LLLLP
3 6 3 3 LLLPP
1 21 1 17 LLLLP
1 20 1 20 PPPPP
3 15 2 14 LUPPP
1 8 ...

result:

ok answer 5

Test #77:

score: 0
Accepted
time: 11ms
memory: 7340kb

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

result:

ok answer 3

Test #78:

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

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 9 2 7 LLDP
4 18 5 18 DPPP
5 11 5 9 LLPP
4 11 4 9 RLLL
3 10 3 10 PPPP
4 5 4 2 LLLP
3 9 4 6 DLLL
1 15 2 14 LDRL
2 12 2 10 LLPP
5 3 5 1 RLLL
1 18 1 15 LLLP
3 17 3 17 PPPP
5 20 5 19 LPPP
1 20 2 20 DPPP
5 17 5 14 LLLP
1 7 2 4 LLLD
3 6 4 4 LLDP
2 8 2 5 LLLP
1 3 1 1 RLLL
2 13 2 11 RLLL
5 6 5 5 LPPP
2 1...

result:

ok answer 4

Test #79:

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

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
5 13 5 10 LLL
5 2 5 2 PPP
1 5 2 7 RRD
2 11 3 9 LLD
6 5 6 8 RRR
4 9 4 10 RPP
2 1 2 4 RRR
1 12 1 12 PPP
1 8 1 7 LPP
1 13 2 13 DPP
5 5 6 4 LDP
3 15 1 16 RUU
6 13 6 13 PPP
5 1 5 3 RRP
5 12 6 10 LLD
1 3 1 5 RRP
1 4 3 4 DDP
4 11 4 11 PPP
5 4 5 4 PPP
6 16 6 16 PPP
6 2 6 3 RPP
1 11 1 11 PPP
4 14 6 14 DDP
...

result:

ok answer 3

Test #80:

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

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
7 2 7 2 PPP
7 11 6 11 UPP
1 6 1 6 PPP
5 4 5 4 PPP
2 10 2 11 RPP
3 11 3 11 PPP
7 9 5 10 URU
5 2 7 1 LDD
5 14 3 14 UUP
5 13 5 12 LPP
2 3 4 2 LDD
3 10 2 9 ULP
7 8 6 9 RUP
2 2 3 1 LDP
4 9 2 8 ULU
5 10 3 9 LUU
2 6 3 6 DPP
6 8 5 8 UPP
2 7 3 5 LLD
3 12 2 14 RUR
7 4 7 4 PPP
1 1 1 1 PPP
6 13 4 13 UUP
6 5 7...

result:

ok answer 3

Test #81:

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

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

result:

ok answer 3

Test #82:

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

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 4 1 DPP
2 10 3 8 LLD
8 8 6 7 ULU
9 6 8 4 LLU
2 1 1 2 URP
9 11 8 10 LUP
5 10 4 8 LLU
2 8 2 5 LLL
1 7 1 4 LLL
7 6 7 3 LLL
3 9 5 10 RDD
9 1 9 1 PPP
3 6 1 6 UUP
4 2 4 3 RPP
3 8 3 6 LLP
9 8 6 8 UUU
1 10 2 8 LLD
9 3 9 3 PPP
7 11 6 11 UPP
4 4 5 3 DLP
4 5 1 5 UUU
5 8 4 7 ULP
9 7 8 7 UPP
5 2 8 2 DDD
6 ...

result:

ok answer 3

Test #83:

score: 0
Accepted
time: 11ms
memory: 7396kb

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 LDP
1 8 1 5 LLL
5 8 4 9 RUP
8 4 7 3 ULP
8 3 8 3 PPP
10 2 10 1 RLL
4 1 5 1 DPP
5 2 3 2 UUP
9 7 10 6 LDP
4 5 3 4 LUP
8 9 7 7 LLU
7 7 7 4 LLL
8 10 5 10 UUU
7 5 5 4 ULU
2 8 3 6 LLD
6 3 4 3 UUP
8 5 9 3 LLD
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: 16ms
memory: 6864kb

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
11 1 10 1 UPPPPPPPPP
51 1 56 1 DDDDDPPPPP
65 1 65 1 PPPPPPPPPP
63 1 73 1 DDDDDDDDDD
1 1 1 1 PPPPPPPPPP
31 1 33 1 DDPPPPPPPP
4 1 3 1 UPPPPPPPPP
66 1 76 1 DDDDDDDDDD
7 1 2 1 UUUUUPPPPP
43 1 53 1 DDDDDDDDDD
42 1 49 1 DDDDDDDPPP
59 1 66 1 UDDDDDDDDP
83 1 93 1 DDDDDDDDDD
40 1 40 1 PPPPPPPPPP
85 1 95 1...

result:

ok answer 10

Test #85:

score: 0
Accepted
time: 22ms
memory: 9300kb

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
28 1 36 2 RDDDDDDDD
32 2 40 2 DDDDDDDDP
20 2 26 2 DDDDDDPPP
49 2 45 1 LUUUUPPPP
43 2 43 1 LPPPPPPPP
1 1 1 2 RPPPPPPPP
49 1 48 1 UPPPPPPPP
28 2 36 1 DDDDDDDLD
48 2 48 2 PPPPPPPPP
40 1 44 2 RDDDDPPPP
30 2 38 1 LDDDDDDDD
47 2 47 2 PPPPPPPPP
25 1 25 1 PPPPPPPPP
5 2 5 2 PPPPPPPPP
33 1 41 1 DDDDDDDDP
46...

result:

ok answer 9

Test #86:

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

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
23 3 15 3 UUUUUUUU
14 1 14 1 PPPPPPPP
32 2 32 2 PPPPPPPP
28 2 24 2 SUUUUPPP
21 3 20 3 UPPPPPPP
26 1 23 1 UUUPPPPP
9 2 10 2 DPPPPPPP
9 1 8 1 UPPPPPPP
7 3 7 2 LPPPPPPP
19 3 12 3 UUUUUUUP
14 3 11 1 LLUUUPPP
12 1 12 2 RPPPPPPP
3 3 3 3 PPPPPPPP
4 2 2 3 RUUPPPPP
16 3 10 1 UUUUUULL
33 1 32 1 UPPPPPPP
29 ...

result:

ok answer 8

Test #87:

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

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 10 1 DPPP
5 4 8 4 DDDP
25 1 25 1 PPPP
1 2 1 1 LPPP
2 3 4 3 DDPP
24 3 20 3 UUUU
19 1 19 1 PPPP
8 2 9 2 DPPP
19 3 16 2 LUUU
5 3 5 3 PPPP
8 1 12 1 DDDD
8 4 10 4 SDDP
8 3 9 3 DPPP
15 3 16 1 LLDP
7 3 9 4 RDDP
18 4 18 4 PPPP
5 1 6 1 DPPP
25 4 24 3 LUPP
12 4 15 4 SDDD
24 2 21 1 ULUU
23 3 21 3 UUPP
3 ...

result:

ok answer 4

Test #88:

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

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
2 2 2 2 PP
13 3 13 3 PP
6 2 6 1 LP
15 1 16 2 RD
2 3 3 2 LD
12 2 14 2 DD
9 1 9 1 PP
13 1 12 1 UP
10 5 9 5 UP
4 5 3 5 UP
14 1 15 2 RD
17 1 17 3 RR
10 1 10 1 PP
2 5 2 5 PP
8 3 8 1 LL
16 5 17 5 DP
6 5 6 5 PP
5 3 6 2 LD
4 2 4 2 PP
11 2 12 2 DP
9 3 9 2 LP
7 2 7 2 PP
18 5 19 4 LD
4 3 4 4 RP
6 3 6 4 RP
7 ...

result:

ok answer 2

Test #89:

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

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 9 6 UPP
7 5 8 5 DPP
5 1 7 1 DDP
8 1 11 1 DDD
7 3 8 3 DPP
16 3 16 3 PPP
9 1 12 1 DDD
15 6 16 5 LDP
16 2 16 2 PPP
7 2 9 1 LDD
12 5 15 5 DDD
4 5 6 5 DDP
11 3 14 3 DDD
4 2 4 1 LPP
9 3 12 3 DDD
9 4 11 3 DDL
10 2 13 2 DDD
15 5 16 4 LSD
2 1 2 1 PPP
5 4 8 4 DDD
2 4 4 3 LDD
1 6 3 6 DDP
2 2 3 2 DPP
6 3...

result:

ok answer 3

Test #90:

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

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
6 4 5 4 UPP
3 6 3 6 PPP
6 2 6 1 LPP
5 6 6 7 RDP
7 4 6 4 UPP
7 5 7 5 PPP
3 3 3 3 PPP
13 4 14 3 LDP
9 5 9 5 PPP
12 3 14 2 LDD
9 6 9 7 RPP
8 6 7 4 LLU
10 6 10 5 LPP
9 2 7 1 LUU
4 2 2 2 UUP
14 5 14 4 LPP
11 6 10 4 LLU
11 3 11 3 PPP
5 2 5 2 PPP
5 1 5 1 PPP
2 6 1 6 UPP
4 4 2 4 UUP
4 6 2 7 RUU
9 1 9 1 PP...

result:

ok answer 3

Test #91:

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

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
2 3 2 3 PP
10 7 10 8 RP
4 5 6 5 DD
10 1 9 2 RU
11 6 11 5 LP
2 7 2 7 PP
8 5 9 6 RD
8 4 9 5 RD
4 7 4 7 PP
12 2 12 4 RR
3 6 2 6 UP
5 5 5 6 RP
4 4 4 6 RR
7 4 7 4 PP
8 7 9 8 RD
4 1 2 1 UU
3 7 4 8 RD
9 4 10 5 RD
10 3 10 4 RP
5 2 5 4 RR
3 1 2 2 UR
6 6 7 6 DP
5 3 4 4 RU
2 4 3 4 DP
1 1 1 1 PP
11 1 12 2 RD
...

result:

ok answer 2

Test #92:

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

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
3 4 3 3 LPP
5 7 8 7 DDD
6 3 6 3 PPP
4 8 7 8 DDD
7 8 8 9 RDP
4 4 7 4 DDD
2 7 4 6 DLD
7 1 8 2 RDP
8 5 8 4 LPP
1 8 1 9 RPP
5 4 6 5 RDP
10 3 9 5 RRU
2 8 3 8 DPP
3 2 5 2 DDP
11 6 11 6 PPP
4 7 7 7 DDD
7 5 7 5 PPP
1 6 2 6 DPP
10 2 9 2 UPP
5 6 5 6 PPP
11 8 11 7 LPP
2 4 1 4 UPP
9 8 10 9 RDP
8 6 8 6 PPP
4 5...

result:

ok answer 3

Test #93:

score: 0
Accepted
time: 17ms
memory: 9000kb

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 LDD
7 1 9 1 DDP
4 1 7 1 DDD
4 9 5 9 DPP
5 5 5 6 RPP
1 10 2 8 LLD
8 5 8 2 LLL
5 1 5 2 RPP
6 10 7 9 LDP
10 7 10 7 PPP
8 4 10 3 LDD
1 9 1 6 LLL
8 10 8 10 PPP
8 7 7 7 USP
2 1 2 1 PPP
2 9 3 8 LDP
4 10 4 8 LLP
1 3 3 4 RDD
9 8 9 8 PPP
10 5 10 5 PPP
2 2 3 2 DPP
8 2 10 1 ...

result:

ok answer 3

Test #94:

score: 0
Accepted
time: 20ms
memory: 8752kb

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 86 1 76 LLLLLLLLLL
1 2 1 2 PPPPPPPPPP
1 25 1 28 RRRPPPPPPP
1 77 1 69 LLLLLLLLPP
1 98 1 93 LLLLLPPPPP
1 59 1 52 LLLLLLLPPP
1 57 1 56 LPPPPPPPPP
1 76 1 67 LLLLLLLLLP
1 38 1 37 LPPPPPPPPP
1 55 1 51 SLLLLLRPPP
1 43 1 43 PPPPPPPPPP
1 64 1 64 PPPPPPPPPP
1 54 1 46 LLLLLLLLPP
1 91 1 87 LLLLPPPPPP
1 16 ...

result:

ok answer 10

Test #95:

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

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 29 1 24 LLLLLU
2 27 1 22 LULLLL
1 19 1 17 LLPPPP
2 24 2 19 LLLLLP
2 38 2 36 LLPPPP
1 41 1 41 PPPPPP
1 44 1 43 LPPPPP
1 47 1 46 LPPPPP
1 35 1 30 LLLLLP
2 8 2 9 RPPPPP
1 45 1 45 PPPPPP
2 20 2 20 PPPPPP
1 7 1 8 SRPPPP
1 13 2 13 DPPPPP
2 48 2 43 LLLLLP
2 36 2 31 LLLLLP
2 11 2 11 PPPPPP
2 7 2 10 RRRP...

result:

ok answer 6

Test #96:

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

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 20 2 22 RRPP
1 33 1 33 PPPP
1 14 1 14 PPPP
2 25 2 28 RRRP
3 6 3 7 RPPP
2 5 2 5 PPPP
1 18 1 21 RRRP
3 24 2 27 RRRU
2 26 2 30 RRRR
1 13 1 13 PPPP
3 9 3 9 PPPP
2 22 2 25 RRRP
2 30 2 33 RRRP
3 30 2 31 RUPP
1 10 2 11 RDPP
1 6 1 6 PPPP
3 19 3 20 RPPP
3 31 3 31 PPPP
2 15 2 14 LPPP
3 4 3 5 RPPP
1 4 1 4 ...

result:

ok answer 4

Test #97:

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

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 2 2 RPP
3 15 3 13 LLP
4 15 4 13 LLP
3 20 4 21 RDP
2 14 2 11 LLL
3 13 3 10 LLL
1 11 1 11 PPP
4 19 4 19 PPP
1 21 2 19 LLD
2 9 2 9 PPP
1 14 1 14 PPP
2 24 2 24 PPP
3 18 3 19 RPP
3 3 3 5 RRP
1 20 2 18 LDL
2 10 3 8 DLL
4 25 1 25 UUU
1 10 2 10 DPP
2 20 2 20 PPP
2 18 2 16 LLP
4 22 4 22 P...

result:

ok answer 3

Test #98:

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

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
4 11 4 11 PPP
1 18 2 16 LLD
3 13 3 13 PPP
3 17 2 17 UPP
2 14 1 14 UPP
4 17 4 17 PPP
1 8 2 8 DPP
2 5 3 7 RRD
2 12 1 12 RLU
2 20 2 20 PPP
1 2 1 2 PPP
1 5 1 5 PPP
4 6 4 9 RRR
3 3 4 5 RRD
3 4 5 5 RDD
3 2 3 2 PPP
2 3 2 3 PPP
1 20 1 18 LLP
2 6 1 6 UPP
1 19 1 17 LLP
3 7 3 10 RRR
5 20 5 20 PPP
3 11 3 12 R...

result:

ok answer 3

Test #99:

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

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 4 1 4 PPPP
3 11 5 9 LLDD
4 3 6 1 LLDD
5 5 6 2 LLLD
2 13 2 10 LLLP
4 14 5 13 LDPP
2 14 3 11 LLLD
3 10 4 7 LLLD
2 8 2 4 LLLL
5 10 6 10 DPPP
4 9 5 6 LLLD
2 16 6 16 DDDD
1 8 1 5 LLLP
3 1 3 1 PPPP
1 14 1 13 LPPP
3 13 3 9 LLLL
6 6 6 5 LPPP
3 9 2 6 ULLL
6 4 6 4 PPPP
2 11 2 7 LLLL
2 2 2 2 PPPP
3 7 4 4 L...

result:

ok answer 4

Test #100:

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

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 3 5 DD
2 13 1 13 UP
1 4 1 4 PP
3 11 2 12 RU
2 12 2 14 RR
5 14 6 14 DP
4 4 4 5 RP
4 3 3 4 RU
4 13 2 13 UU
3 3 3 3 PP
4 11 4 13 RR
7 14 7 14 PP
6 12 6 12 PP
6 13 7 13 DP
5 10 5 10 PP
3 1 3 1 PP
4 9 3 9 UP
2 4 2 4 PP
6 8 6 10 RR
3 8 3 6 L...

result:

ok answer 2

Test #101:

score: 0
Accepted
time: 11ms
memory: 7072kb

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
6 7 4 7 SUU
5 5 6 5 DPP
3 2 5 3 RDD
4 9 2 8 LUU
6 10 4 9 ULU
8 10 5 10 UUU
8 9 8 6 LLL
1 5 1 5 PPP
5 2 5 2 PPP
7 12 7 12 PPP
5 7 5 7 PPP
2 9 2 10 RPP
4 10 3 10 UPP
2 8 1 8 UPP
1 2 2 2 DPP
7 5 7 5 PPP
6 1 6 2 RPP
2 11 2 11 PPP
3 5 2 5 UPP
4 1 5 1 DPP
5 6 4 8 RRU
2 12 1 12 UPP
2 6 2 6 PPP
7 4 7 3 LP...

result:

ok answer 3

Test #102:

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

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
3 11 3 10 LP
7 6 7 6 PP
4 8 3 8 UP
3 9 3 9 PP
9 6 9 6 PP
2 10 1 10 UP
8 1 9 1 DP
4 7 2 7 UU
9 9 9 9 PP
3 1 3 1 PP
7 10 7 10 PP
1 7 1 7 PP
5 8 6 9 RD
2 11 4 11 DD
7 4 7 4 PP
9 5 9 5 PP
9 3 8 3 UP
6 10 8 10 DD
9 11 9 10 LP
2 6 2 6 PP
2 7 1 8 RU
8 3 6 3 UU
1 1 1 1 PP
9 7 9 7 PP
2 8 2 8 PP
7 5 6 5 UP
...

result:

ok answer 2

Test #103:

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

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

result:

ok answer 2

Test #104:

score: 0
Accepted
time: 23ms
memory: 7200kb

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
65 1 48 1 UUUUUUUUUUUUUUUUUP
1 1 1 1 PPPPPPPPPPPPPPPPPP
55 1 37 1 UUUUUUUUUUUUUUUUUU
98 1 81 1 UUUUUUUUUUUUUUUUUP
4 1 4 1 PPPPPPPPPPPPPPPPPP
96 1 96 1 PPPPPPPPPPPPPPPPPP
91 1 91 1 PPPPPPPPPPPPPPPPPP
64 1 64 1 PPPPPPPPPPPPPPPPPP
88 1 88 1 PPPPPPPPPPPPPPPPPP
62 1 46 1 UUUUUUUUUUUUUUUUPP
99 1 99 1 P...

result:

ok answer 18

Test #105:

score: 0
Accepted
time: 19ms
memory: 7004kb

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
6 1 5 1 UPPPP
2 2 4 1 DDLPP
1 2 5 2 DDDDP
41 2 39 2 UUPPP
20 1 15 1 UUUUU
2 1 2 1 PPPPP
4 2 4 2 PPPPP
48 1 48 1 PPPPP
37 1 32 1 UUUUU
43 2 43 2 PPPPP
40 1 35 1 UUUUU
42 1 37 1 UUUUU
6 2 6 2 PPPPP
36 1 31 1 UUUUU
48 2 50 2 DDPPP
32 1 29 1 UUUPP
7 1 7 1 PPPPP
33 1 28 1 UUUUU
30 2 26 2 UUUUP
27 2 22 ...

result:

ok answer 5

Test #106:

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

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
11 2 11 3 RPPP
19 3 19 3 PPPP
30 1 30 1 PPPP
33 3 33 2 LPPP
31 3 31 2 LPPP
1 1 3 1 DDPP
2 1 2 1 PPPP
28 2 28 2 PPPP
15 3 15 3 PPPP
23 2 23 2 PPPP
10 1 13 1 DDDP
12 2 15 2 DDDP
30 2 30 2 PPPP
25 2 27 2 SDDP
25 3 25 3 PPPP
15 2 19 2 DDDD
12 1 12 1 PPPP
9 3 10 3 DPPP
8 1 8 1 PPPP
7 1 7 1 PPPP
16 3 17...

result:

ok answer 4

Test #107:

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

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
22 4 19 4 UUU
10 3 9 1 ULL
22 1 22 1 PPP
4 2 4 2 PPP
16 4 13 4 UUU
24 2 24 2 PPP
22 3 20 2 LUU
17 1 17 1 PPP
5 4 5 4 PPP
15 2 12 2 UUU
16 3 16 3 PPP
21 3 18 3 UUU
10 1 7 1 UUU
25 1 25 2 RPP
9 3 9 3 PPP
1 1 1 1 PPP
20 3 20 3 PPP
8 1 5 1 UUU
19 1 18 1 UPP
18 4 15 4 UUU
20 4 17 4 UUU
21 4 21 4 PPP
10...

result:

ok answer 3

Test #108:

score: 0
Accepted
time: 17ms
memory: 7136kb

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
6 2 6 2 PPPP
15 5 17 5 DDPP
3 1 4 1 DPPP
2 5 2 5 PPPP
15 2 15 2 PPPP
3 2 3 2 PPPP
10 2 12 3 SRDD
6 5 6 5 PPPP
1 3 1 3 PPPP
9 1 11 3 RRDD
15 3 19 3 DDDD
13 4 13 4 PPPP
11 4 13 3 LDDP
5 1 6 1 DPPP
9 2 9 2 PPPP
17 3 19 2 LDDP
18 1 19 1 DPPP
9 5 11 5 DDPP
3 3 3 3 PPPP
20 2 20 2 PPPP
4 2 4 4 RRPP
4 3 4...

result:

ok answer 4

Test #109:

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

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
7 1 10 1 DDD
13 3 14 3 UDD
10 5 11 5 DPP
4 2 5 2 DPP
14 3 15 3 DPP
6 4 6 4 PPP
1 4 3 4 DDP
8 3 11 3 DDD
12 2 12 2 PPP
10 3 12 3 DDP
5 6 8 6 DDD
2 4 2 3 LPP
7 3 7 2 LPP
11 1 14 1 DDD
6 1 9 1 DDD
13 2 15 1 LDD
16 3 16 3 PPP
5 3 5 3 PPP
13 5 14 6 RDP
3 1 5 1 DDP
2 1 2 1 PPP
2 5 2 5 PPP
15...

result:

ok answer 3

Test #110:

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

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
14 1 14 2 RPP
3 5 3 5 PPP
8 5 6 5 UUP
7 7 4 7 UUU
2 4 1 3 LUP
9 4 9 4 PPP
14 3 11 3 UUU
11 7 11 7 PPP
6 2 5 2 SUP
1 4 1 4 PPP
9 6 8 6 UPP
3 6 3 6 PPP
12 3 12 3 PPP
7 4 7 4 PPP
12 2 9 2 UUU
13 6 12 7 RUP
14 4 14 4 PPP
13 1 10 1 UUU
2 1 2 1 PPP
1 6 1 5 LPP
11 3 8 3 UUU
12 6 10 6 UUP
4 2 3 2 UPP
11 2...

result:

ok answer 3

Test #111:

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

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

result:

ok answer 2

Test #112:

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

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 5 1 4 LP
1 1 2 1 DP
6 1 7 1 DP
5 7 5 7 PP
10 8 10 8 PP
3 2 3 2 PP
5 4 4 4 UP
5 5 4 5 UP
10 6 11 5 LD
1 9 1 9 PP
11 8 11 8 PP
6 8 8 8 DD
8 3 10 3 DD
7 6 8 5 LD
9 9 11 9 DD
2 8 1 7 LU
1 7 1 6 LP
8 7 8 7 PP
10 1 10 1 PP
3 6 3 6 PP
5 6 6 5 LD
4 1 4 1 PP
2 7 3 7 DP
3 4 3 3 LP
8 6 8 6 PP
5 9 5 9 PP
10...

result:

ok answer 2

Test #113:

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

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

result:

ok answer 2

Test #114:

score: 0
Accepted
time: 20ms
memory: 8432kb

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
100 1 97 1 UUUPP
38 1 38 1 PPPPP
87 1 85 1 UUPPP
80 1 76 1 UUUUP
90 1 90 1 PPPPP
60 1 60 1 PPPPP
61 1 58 1 UUUPP
15 1 20 1 DDDDD
40 1 37 1 UUUPP
20 1 23 1 DDDPP
12 1 12 1 PPPPP
66 1 63 1 UUUPP
88 1 84 1 UUUUP
92 1 92 1 PPPPP
11 1 11 1 PPPPP
64 1 61 1 UUUPP
34 1 34 1 PPPPP
28 1 33 1 DDDDD
55 1 55 1...

result:

ok answer 5

Test #115:

score: 0
Accepted
time: 19ms
memory: 8768kb

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
29 2 31 2 DDPP
49 2 49 1 LPPP
25 1 25 1 PPPP
30 1 32 1 DDPP
40 1 40 1 PPPP
6 1 6 1 PPPP
4 2 1 1 UUUL
12 1 9 1 UUUP
22 1 22 1 PPPP
11 2 8 1 UUUL
29 1 33 1 DDDD
28 2 29 2 DPPP
17 1 13 1 UUUU
17 2 15 1 LUUP
27 2 27 2 PPPP
36 2 36 2 PPPP
46 2 50 2 DDDD
44 2 40 2 UUUU
38 1 38 1 PPPP
3 2 3 1 LPPP
45 2 4...

result:

ok answer 4

Test #116:

score: 0
Accepted
time: 18ms
memory: 7152kb

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
16 3 14 3 UU
31 1 31 1 PP
5 2 5 2 PP
23 2 23 2 PP
4 1 6 1 DD
28 2 28 2 PP
19 3 19 3 PP
29 3 29 3 PP
22 2 24 2 DD
1 3 1 3 PP
20 2 19 2 UP
25 2 26 2 DP
12 3 10 3 UU
3 3 5 3 DD
31 2 32 1 LD
19 1 19 1 PP
16 1 16 1 PP
17 2 17 2 PP
8 1 10 1 DD
5 1 6 2 RD
28 1 30 1 DD
14 2 14 2 PP
32 2 32 2 PP
6 2 7 3 DR...

result:

ok answer 2

Test #117:

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

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
14 1 14 1 PP
4 1 2 1 UU
2 1 2 2 RP
22 1 22 1 PP
17 4 17 4 PP
24 2 24 2 PP
5 4 5 4 PP
19 2 19 2 PP
15 3 15 3 PP
17 1 17 1 PP
21 2 21 2 PP
5 1 5 1 PP
10 4 9 3 UL
14 3 15 4 DR
8 1 8 1 PP
6 1 7 2 RD
10 2 9 2 UP
24 3 24 3 PP
3 1 3 1 PP
22 3 22 3 PP
3 2 3 4 RR
7 4 7 4 PP
21 4 21 4 PP
25 2 25 2 PP
16 2 1...

result:

ok answer 2

Test #118:

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

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
20 2 20 2 PP
9 3 11 3 DD
1 1 1 1 PP
2 1 4 1 DD
2 2 4 2 DD
5 2 7 2 DD
12 2 12 2 PP
14 4 14 4 PP
6 1 6 1 PP
20 5 20 5 PP
3 1 3 1 PP
3 2 5 2 DD
11 4 11 4 PP
1 4 1 2 LL
3 5 5 5 DD
14 1 14 1 PP
17 1 19 1 DD
7 1 7 1 PP
7 5 7 5 PP
18 4 19 4 DP
7 4 7 4 PP
1 2 2 1 LD
17 5 19 5 DD
6 3 6 3 PP
13 4 13 4 PP
16...

result:

ok answer 2

Test #119:

score: 0
Accepted
time: 18ms
memory: 8936kb

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
3 6 5 6 DD
3 4 3 4 PP
1 2 1 2 PP
16 4 16 2 LL
8 1 10 1 DD
11 4 13 4 DD
9 4 10 3 LD
10 4 11 3 LD
8 2 10 2 DD
13 6 13 6 PP
6 4 5 4 UP
7 4 7 4 PP
9 5 11 5 DD
4 1 3 1 UP
1 6 1 6 PP
5 1 5 1 PP
16 6 16 6 PP
8 3 8 2 LP
12 4 14 4 DD
10 3 12 3 DD
14 5 14 5 PP
6 5 6 5 PP
13 5 15 5 DD
4 4 4 4 PP
11 6 9 6 UU
...

result:

ok answer 2

Test #120:

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

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

result:

ok answer 2

Test #121:

score: 0
Accepted
time: 19ms
memory: 7104kb

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
4 6 5 5 DL
2 7 4 7 DD
12 6 12 6 PP
8 4 9 4 DP
10 8 10 8 PP
6 6 7 6 DP
3 3 5 3 DD
4 1 4 3 RR
12 5 12 5 PP
9 6 9 6 PP
2 1 3 1 DP
6 1 6 1 PP
6 8 7 8 DP
11 4 11 4 PP
11 5 11 5 PP
6 2 8 2 DD
9 3 10 4 DR
3 7 3 7 PP
5 6 5 6 PP
5 2 5 2 PP
3 1 5 1 DD
11 2 11 2 PP
4 4 5 4 DP
1 5 3 5 DD
7 1 8 1 DP
10 2 10 2 ...

result:

ok answer 2

Test #122:

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

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 7 1 8 RP
9 5 9 5 PP
4 1 4 3 RR
1 5 1 4 LP
11 2 10 1 LU
3 8 3 8 PP
4 8 4 8 PP
11 4 11 4 PP
3 6 4 7 RD
1 9 1 9 PP
9 4 9 4 PP
8 8 9 8 DP
1 1 1 1 PP
2 8 2 8 PP
1 6 2 7 RD
3 9 3 9 PP
8 3 8 4 RP
4 5 5 6 RD
10 8 10 8 PP
7 2 7 2 PP
9 2 9 2 PP
6 8 6 8 PP
8 7 8 7 PP
11 8 11 8 PP
6 5 5 5 UP
10 5 10 5 PP
7 ...

result:

ok answer 2

Test #123:

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

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

result:

ok answer 2

Test #124:

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

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 41 1 41 PPPPPPPPP
1 75 1 71 LLLLPPPPP
1 13 1 13 PPPPPPPPP
1 62 1 62 PPPPPPPPP
1 25 1 16 LLLLLLLLL
1 89 1 89 PPPPPPPPP
1 45 1 38 LLLLLLLPP
1 40 1 33 LLLLLLLPP
1 10 1 5 LLLLLPPPP
1 81 1 81 PPPPPPPPP
1 100 1 100 PPPPPPPPP
1 26 1 17 LLLLLLLLL
1 97 1 88 LLLLLLLLL
1 30 1 22 LLLLLLLLP
1 42 1 42 PPPPPPP...

result:

ok answer 9

Test #125:

score: 0
Accepted
time: 11ms
memory: 7380kb

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 34 1 34 PP
2 37 2 37 PP
2 2 2 2 PP
2 19 2 19 PP
1 37 1 39 RR
2 3 1 3 UP
2 31 2 33 RR
1 45 1 47 RR
2 44 2 45 RP
1 22 1 22 PP
1 44 2 44 DP
2 17 2 16 LP
2 6 2 5 LP
2 21 2 22 RP
2 29 2 31 RR
2 36 2 36 PP
1 48 1 48 PP
1 30 1 31 RP
1 13 2 13 DP
1 43 1 45 RR
1 18 1 18 PP
1 50 1 50 PP
1 23 1 23 PP
2 8 2...

result:

ok answer 2

Test #126:

score: 0
Accepted
time: 18ms
memory: 7080kb

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 16 1 18 RR
2 8 2 6 LL
2 30 1 30 UP
3 33 3 33 PP
2 21 2 23 RR
2 11 2 11 PP
1 5 1 4 LP
2 6 2 4 LL
2 7 2 7 PP
3 24 3 26 RR
1 14 1 16 RR
3 5 3 5 PP
2 23 2 25 RR
2 10 2 10 PP
2 9 2 9 PP
1 6 1 5 LP
2 28 2 30 RR
1 7 1 7 PP
2 3 2 3 PP
3 26 3 28 RR
1 27 1 28 RP
2 29 1 29 UP
3 25 3 25 PP
2 19 2 21 RR
1 31...

result:

ok answer 2

Test #127:

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

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 2 1 4 RR
1 3 1 3 PP
1 13 2 12 LD
2 11 3 11 DP
4 21 4 22 RP
1 7 1 7 PP
4 15 4 13 LL
2 9 2 8 LP
2 21 3 21 DP
2 13 2 11 LL
4 4 2 4 UU
3 2 3 2 PP
2 20 2 20 PP
4 8 4 6 LL
4 3 4 2 LP
4 14 4 12 LL
2 12 2 10 LL
3 25 3 25 PP
3 19 3 17 LL
1 25 1 25 PP
1 21 1 21 PP
4 5 4 3 LL
3 3 2 3 UP
2 6 2 6 PP
2 14 2 1...

result:

ok answer 2

Test #128:

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

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 17 2 17 D
3 8 3 7 L
4 12 5 12 D
2 19 2 19 P
1 10 1 10 P
2 14 2 14 P
4 7 4 7 P
4 3 4 3 P
2 8 2 9 R
3 14 3 14 P
5 20 5 19 L
1 20 1 20 P
3 18 3 18 P
5 18 5 18 P
1 2 1 3 R
4 10 5 10 D
5 3 5 3 P
4 19 4 19 P
5 13 5 14 R
4 2 4 2 P
1 3 1 4 R
1 8 1 8 P
3 13 4 13 D
5 9 5 9 P
3 16 4 16 D
2 9 1 9 U
4 8 5 8 ...

result:

ok answer 1

Test #129:

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

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
5 14 6 14 D
4 10 3 10 U
5 6 4 6 U
4 7 3 7 U
2 2 2 2 P
2 8 1 8 U
6 5 6 4 L
3 15 3 16 R
5 12 5 13 R
4 3 4 3 P
3 7 2 7 U
1 14 1 14 P
2 4 2 4 P
3 14 3 14 P
1 8 1 7 L
2 14 2 15 R
3 8 2 8 U
1 2 1 1 L
1 12 1 13 R
6 12 6 12 P
4 5 4 5 P
4 9 3 9 U
2 16 1 16 U
6 16 6 16 P
6 4 6 3 L
4 11 4 11 P
4 8 3 8 U
5 2 ...

result:

ok answer 1

Test #130:

score: 0
Accepted
time: 11ms
memory: 8708kb

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
7 13 6 13 U
3 14 2 14 U
4 1 4 1 P
4 9 4 9 P
2 8 2 8 P
3 10 3 10 P
7 7 7 6 L
6 8 6 7 L
6 12 6 11 L
5 3 5 3 P
2 1 2 2 R
4 5 4 5 P
7 8 7 7 L
3 1 3 2 R
7 3 7 3 P
4 12 4 12 S
4 14 4 14 P
6 14 6 14 P
7 1 7 1 P
1 3 1 4 R
2 5 2 5 P
1 8 1 8 P
5 2 6 2 D
2 11 2 12 R
7 10 7 9 L
5 12 5 12 P
3 3 3 3 P
3 8 4 8 D...

result:

ok answer 1

Test #131:

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

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
2 9 2 9 P
3 2 3 3 R
4 6 4 7 R
8 5 8 5 P
4 5 4 6 R
1 6 1 6 P
7 7 7 8 R
6 9 6 10 R
8 11 8 11 P
4 2 4 2 P
8 10 8 10 P
3 12 2 12 U
8 12 8 12 P
6 4 6 5 R
2 4 1 4 U
1 7 1 8 R
6 3 5 3 U
6 8 6 9 R
7 10 7 10 P
7 6 7 6 P
8 9 8 9 P
5 8 6 8 D
7 3 7 4 R
5 4 5 5 R
4 4 4 5 R
8 8 8 8 P
6 11 7 11 D
7 5 7 5 P
7 4 8...

result:

ok answer 1

Test #132:

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

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
7 2 7 3 R
1 4 1 4 P
8 8 7 8 U
6 9 6 8 L
1 2 1 2 P
8 3 8 3 P
1 11 1 11 P
8 6 8 6 P
1 8 1 8 P
7 8 7 7 L
4 7 4 7 P
3 2 3 3 R
2 9 2 10 R
6 3 6 4 R
9 10 9 9 L
4 8 4 8 P
8 10 8 10 P
3 9 3 9 P
9 2 9 3 R
2 3 2 3 P
8 2 8 2 P
9 5 9 5 P
6 11 6 11 P
2 11 2 11 P
6 4 5 4 U
7 3 6 3 U
3 8 3 8 P
7 1 7 1 P
5 8 5 8 ...

result:

ok answer 1

Test #133:

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

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
4 5 4 5 P
10 2 10 3 R
4 1 3 1 U
1 10 1 9 L
2 1 2 1 P
7 5 7 4 L
1 9 1 8 L
5 9 5 9 P
9 1 9 1 P
5 6 4 6 U
5 10 5 10 P
8 2 8 3 R
5 4 5 4 P
7 8 7 8 P
7 1 6 1 U
9 2 9 2 P
10 4 10 5 R
2 9 2 9 P
4 7 4 7 P
6 10 6 10 P
8 7 8 7 P
6 6 6 6 P
5 7 5 7 P
7 7 7 7 P
3 4 3 4 P
4 4 4 4 P
5 5 5 5 P
4 10 4 10 P
7 4 6 4...

result:

ok answer 1

Test #134:

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

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
89 1 89 1 PPPP
74 1 70 1 UUUU
85 1 85 1 PPPP
59 1 59 1 PPPP
91 1 91 1 PPPP
88 1 88 1 PPPP
93 1 93 1 PPPP
78 1 74 1 UUUU
63 1 63 1 PPPP
52 1 52 1 UUDD
37 1 33 1 UUUU
28 1 24 1 UUUU
51 1 51 1 PPPP
42 1 42 1 PPPP
79 1 79 1 PPPP
4 1 4 1 PPPP
81 1 81 1 PPPP
31 1 27 1 UUUU
25 1 21 1 UUUU
60 1 60 1 PPPP
...

result:

ok answer 4

Test #135:

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

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
30 2 30 2 P
22 1 22 1 P
22 2 21 2 U
31 2 31 2 P
29 2 29 2 P
39 2 39 1 L
11 2 11 2 P
2 1 1 1 U
26 2 25 2 U
1 2 1 2 P
44 1 45 1 D
17 2 17 2 P
41 1 42 1 D
35 1 35 1 P
44 2 44 2 P
14 1 13 1 U
25 1 24 1 U
3 1 3 1 P
15 1 14 1 U
45 2 45 2 P
35 2 35 2 P
23 2 22 2 U
36 2 37 2 D
19 1 19 1 P
26 1 25 1 U
49 2...

result:

ok answer 1

Test #136:

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

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
5 3 4 3 U
5 2 4 2 U
3 1 3 1 P
25 1 24 1 U
10 1 10 1 P
7 3 7 3 P
1 2 1 2 P
32 3 31 3 U
9 3 8 3 U
18 1 19 1 D
22 3 22 3 P
16 3 15 3 U
4 2 3 2 U
26 3 25 3 U
19 3 19 3 P
19 1 18 1 U
7 2 6 2 U
23 2 22 2 U
13 2 13 2 P
8 1 8 1 P
20 3 20 3 P
14 1 13 1 U
6 2 5 2 U
26 2 26 2 P
23 3 23 3 P
29 3 28 3 U
29 2 2...

result:

ok answer 1

Test #137:

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

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
13 1 12 1 U
2 4 2 4 P
17 1 17 1 P
22 4 22 4 P
16 1 16 2 R
21 3 20 3 U
8 1 7 1 U
9 3 8 3 U
13 3 13 4 R
18 4 17 4 U
23 4 23 4 P
22 1 22 1 P
20 2 20 2 P
8 2 7 2 U
17 4 16 4 U
1 3 1 3 P
9 1 8 1 U
22 3 21 3 U
13 4 12 4 U
12 3 11 3 U
14 1 14 1 P
1 1 1 1 P
9 4 8 4 U
22 2 22 2 P
7 1 6 1 U
11 1 10 1 U
16 2...

result:

ok answer 1

Test #138:

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

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
2 5 2 5 P
8 4 7 4 U
16 4 16 4 P
7 3 6 3 U
6 2 6 2 P
8 3 8 4 R
12 4 12 4 P
10 2 9 2 U
12 5 12 5 P
18 2 18 2 P
12 3 11 3 U
16 1 16 1 P
2 1 3 1 D
19 5 18 5 U
19 3 19 3 P
14 4 14 4 P
13 2 12 2 U
15 2 14 2 U
17 1 18 1 D
20 5 19 5 U
15 3 14 3 U
7 1 7 1 P
4 4 4 3 L
8 5 8 5 P
6 3 5 3 U
18 4 18 4 P
1 3 2 3...

result:

ok answer 1

Test #139:

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

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
14 5 14 5 P
1 1 1 1 P
4 6 4 6 P
9 2 10 2 D
11 2 12 2 D
14 2 15 2 D
5 6 5 6 P
5 5 5 5 P
7 1 8 1 D
2 6 2 6 P
13 2 14 2 D
8 4 8 4 P
1 4 1 4 P
15 5 15 5 P
16 6 15 6 U
7 3 8 3 D
11 3 11 3 P
13 3 13 3 P
3 3 4 3 D
2 1 2 1 P
1 6 1 6 P
16 2 16 1 L
13 1 14 1 D
12 6 12 6 P
2 2 2 2 P
8 3 9 3 D
14 6 13 6 U
14 ...

result:

ok answer 1

Test #140:

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

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
14 4 14 4 P
10 7 10 7 P
13 6 13 6 P
12 3 12 2 L
6 5 5 5 U
14 2 14 2 P
11 4 11 4 P
11 3 11 3 P
13 1 13 1 P
14 1 14 1 P
8 7 8 7 P
10 6 10 5 L
2 7 2 7 P
11 7 11 7 P
2 4 1 4 U
11 6 11 6 P
7 5 6 5 U
9 4 9 3 L
7 6 7 5 L
12 5 12 4 L
12 4 12 3 L
3 2 3 2 P
3 4 3 4 P
1 2 1 2 P
1 3 1 3 P
4 1 4 1 P
9 1 8 1 U
...

result:

ok answer 1

Test #141:

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

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
12 2 12 2 P
3 3 3 4 R
2 4 2 4 P
5 8 5 8 P
9 5 9 5 P
8 8 8 8 P
5 4 5 4 P
11 1 11 1 P
3 8 3 8 P
6 8 6 8 P
8 6 7 6 U
5 5 4 5 U
11 2 11 2 P
8 4 8 4 P
5 1 4 1 U
4 1 3 1 U
6 1 5 1 U
2 8 2 8 P
9 6 8 6 U
9 1 9 1 P
7 8 7 8 P
12 6 12 6 P
9 4 9 4 P
7 7 7 7 P
7 1 6 1 U
9 3 8 3 U
4 3 4 3 P
12 1 12 1 P
2 5 2 5 ...

result:

ok answer 1

Test #142:

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

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
2 8 3 8 D
5 4 5 4 P
7 3 7 3 P
7 8 7 8 P
1 5 2 5 D
5 2 5 2 P
2 6 2 7 R
8 8 8 9 R
9 4 8 4 U
6 4 6 4 P
9 7 9 8 R
1 6 1 6 P
3 2 3 2 P
1 7 1 8 R
4 7 4 8 R
6 6 6 6 P
2 1 2 1 P
8 2 8 2 P
11 2 11 2 P
11 5 10 5 U
9 2 9 2 P
6 7 6 7 P
10 9 9 9 U
2 9 2 9 P
4 9 4 9 P
1 1 1 1 P
4 4 4 4 P
6 1 6 1 P
10 3 10 4 R
6...

result:

ok answer 1

Test #143:

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

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
4 5 4 5 P
9 9 8 9 U
4 10 4 10 P
2 2 1 2 U
6 9 5 9 U
1 1 1 1 P
6 1 6 1 S
1 4 1 4 P
7 7 7 8 R
6 2 5 2 U
9 5 9 5 P
9 6 9 7 R
8 7 8 7 P
5 4 5 4 P
10 7 10 7 P
9 10 9 10 P
6 5 6 5 P
8 1 7 1 U
4 3 4 3 P
6 10 5 10 U
9 3 9 3 P
10 4 10 4 P
2 3 2 3 P
3 5 3 5 P
9 8 9 9 R
1 3 1 3 P
3 8 3 8 P
7 2 7 2 P
2 7 2 7 ...

result:

ok answer 1

Test #144:

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

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 62 1 61 L
1 15 1 14 L
1 97 1 97 P
1 31 1 30 L
1 78 1 78 P
1 51 1 50 L
1 48 1 47 L
1 89 1 89 P
1 4 1 4 P
1 16 1 15 L
1 47 1 46 L
1 33 1 32 L
1 88 1 88 P
1 87 1 87 P
1 55 1 54 L
1 22 1 21 L
1 11 1 11 P
1 44 1 43 L
1 43 1 42 L
1 73 1 73 P
1 7 1 7 P
1 74 1 74 P
1 1 1 1 P
1 36 1 35 L
1 20 1 19 L
1 92...

result:

ok answer 1

Test #145:

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

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
2 18 2 18 P
1 20 1 20 P
2 6 2 6 P
2 9 2 9 P
1 3 1 3 P
2 30 2 30 P
2 4 2 4 P
1 33 1 32 L
2 43 2 43 P
2 21 2 21 P
1 31 1 30 L
2 24 2 24 P
1 10 1 10 P
1 42 1 41 L
1 4 1 4 P
1 45 1 44 L
2 28 2 28 P
1 27 1 26 L
1 24 1 24 P
2 47 2 47 P
1 47 1 47 P
1 13 1 13 P
2 40 2 40 P
1 18 1 18 P
1 22 1 22 P
1 36 1 3...

result:

ok answer 1

Test #146:

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

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
2 19 2 19 P
3 20 3 21 R
3 10 3 11 R
1 33 1 33 P
1 17 1 17 P
1 7 1 7 P
3 8 3 9 R
1 3 1 3 P
3 6 3 7 R
3 7 3 8 R
3 18 3 19 R
1 22 1 22 P
2 3 2 3 P
3 30 3 30 P
3 31 3 31 P
3 3 3 3 P
1 26 1 26 P
1 21 1 21 P
1 27 1 27 P
1 31 1 31 P
3 17 3 18 R
2 12 2 12 P
3 13 3 14 R
2 26 2 26 P
2 28 2 28 P
3 15 3 16 R
...

result:

ok answer 1

Test #147:

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

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 25 1 25 P
3 11 3 11 P
1 2 1 2 P
4 1 4 1 P
4 19 4 19 P
3 5 3 5 P
4 5 4 5 P
1 12 1 12 P
2 1 1 1 U
3 4 3 4 P
1 23 1 23 P
2 18 2 17 L
4 15 4 15 P
4 13 4 13 P
4 11 4 11 P
2 23 2 22 L
3 1 3 1 P
2 7 2 6 L
4 6 4 6 P
4 20 4 20 P
2 16 2 15 L
1 17 1 17 P
2 10 2 9 L
4 18 4 18 P
3 3 3 3 P
2 22 2 21 L
2 6 2 5...

result:

ok answer 1

Test #148:

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

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
4 11 3 11 U
2 13 2 13 P
1 20 1 20 P
2 18 2 18 P
2 6 2 6 P
2 17 2 17 P
4 12 4 12 P
4 1 4 1 P
5 6 5 6 P
2 4 2 4 P
4 4 4 4 P
1 9 1 9 P
5 18 5 18 P
2 8 2 8 P
5 19 5 19 P
5 3 5 3 P
4 15 4 15 P
1 4 1 4 P
1 13 1 13 P
5 17 5 17 P
4 19 4 19 P
3 19 3 19 P
5 4 5 4 P
4 10 4 10 P
3 15 3 15 P
1 3 1 3 P
3 3 3 3 ...

result:

ok answer 1

Test #149:

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

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
2 8 2 8 P
1 4 1 4 P
6 7 6 7 P
1 10 1 10 P
5 3 5 3 P
5 13 5 13 P
2 15 2 15 P
6 12 6 12 P
4 12 4 12 P
1 13 1 13 P
2 6 2 6 P
4 2 4 2 P
2 2 2 2 P
4 6 4 6 P
2 10 2 10 P
2 11 2 11 P
5 2 5 2 P
5 14 5 14 P
3 14 3 14 P
3 9 3 9 P
5 8 5 8 P
6 1 6 1 P
1 12 1 12 P
1 11 1 11 P
6 13 6 13 P
6 5 6 5 P
4 9 4 9 P
5 ...

result:

ok answer 1

Test #150:

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

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
7 1 7 1 P
6 6 6 6 P
1 7 1 7 P
3 8 3 9 R
5 1 5 1 P
6 1 6 1 P
6 5 6 5 P
4 1 4 1 P
1 5 1 5 P
4 3 4 3 P
3 7 3 8 R
3 9 3 10 R
4 11 4 11 P
6 4 6 4 P
1 6 1 6 P
6 13 6 13 P
7 5 7 5 P
6 14 6 14 P
4 14 4 14 P
6 12 6 12 P
2 1 2 1 P
7 7 7 7 P
5 6 5 6 P
5 5 5 5 P
6 10 6 10 P
4 7 4 7 P
5 2 5 2 P
6 2 6 2 P
4 5 4...

result:

ok answer 1

Test #151:

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

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
3 4 3 4 P
7 8 7 8 P
6 7 6 7 P
2 7 2 7 P
7 10 7 9 L
3 12 3 12 P
8 10 8 10 P
4 1 4 1 P
8 1 8 1 P
5 10 5 10 P
7 9 6 9 U
2 12 2 12 P
3 11 3 11 P
6 12 6 12 P
5 3 5 3 P
5 8 5 8 P
8 9 8 9 P
7 4 7 4 P
6 8 6 8 P
1 12 1 12 P
7 6 7 6 P
4 2 4 2 P
6 5 6 5 P
4 10 4 10 P
5 5 5 5 P
1 1 1 1 P
2 5 2 5 P
1 2 1 2 P
6...

result:

ok answer 1

Test #152:

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

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
6 3 6 3 P
1 1 1 1 P
9 4 9 4 P
7 10 7 10 P
9 6 9 6 P
4 9 4 9 P
6 10 6 10 P
9 8 9 8 P
4 7 4 7 P
9 2 9 2 P
1 5 1 5 P
3 10 3 10 P
8 2 8 2 P
6 4 6 4 P
9 10 9 10 P
1 4 1 4 P
5 7 5 7 P
8 9 8 9 P
5 4 5 4 P
5 11 5 11 P
5 6 5 6 P
2 1 2 1 P
6 5 6 5 P
6 8 6 8 P
1 3 1 3 P
1 7 1 7 P
4 11 4 11 P
3 9 3 8 L
8 5 8 ...

result:

ok answer 1

Test #153:

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

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
9 10 9 10 P
9 2 9 2 P
6 5 6 5 P
7 2 7 2 P
10 7 10 7 P
5 5 5 5 P
1 9 1 9 P
5 10 5 10 P
1 7 1 7 P
1 10 1 10 P
7 6 7 6 P
9 8 9 8 P
10 10 10 10 P
2 2 2 2 P
7 9 7 9 P
5 4 5 4 P
3 4 3 4 P
5 9 5 9 P
9 9 9 9 P
5 3 5 3 P
10 2 10 2 P
3 3 3 3 P
8 7 8 7 P
6 3 6 3 P
6 10 6 10 P
10 9 10 9 P
10 5 10 5 P
7 4 7 4 ...

result:

ok answer 1