QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#255947#7751. Palindrome Pathucup-team087#AC ✓28ms18520kbC++2013.4kb2023-11-18 17:34:382023-11-18 17:34:39

Judging History

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

  • [2023-11-18 17:34:39]
  • 评测
  • 测评结果:AC
  • 用时:28ms
  • 内存:18520kb
  • [2023-11-18 17:34:38]
  • 提交

answer

#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

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

using ll=long long;
//#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

template<class t>
void print_single(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
	print_single(p.a,2);
	print_single(p.b,suc);
}

template<class T>
void print_single(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print_single(v[i],i==int(v.size())-1?suc:2);
}

template<class T>
void print_offset(const vector<T>&v,ll off,int suc=1){
	rep(i,v.size())
		print_single(v[i]+off,i==int(v.size())-1?suc:2);
}

template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
	rep(i,N)
		print_single(v[i],i==int(N)-1?suc:2);
}

template<class T>
void print(const T&t){
	print_single(t);
}

template<class T,class ...Args>
void print(const T&t,const Args&...args){
	print_single(t,2);
	print(args...);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

void YES(bool ex=true){
	cout<<"YES\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void NO(bool ex=true){
	cout<<"NO\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void Yes(bool ex=true){
	cout<<"Yes\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void No(bool ex=true){
	cout<<"No\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}*/
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
int popcount(ull t){
	return __builtin_popcountll(t);
}
int bitparity(ll t){
	return __builtin_parityll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}
ull umask(int i){
	return (ull(1)<<i)-1;
}
ll minp2(ll n){
	if(n<=1)return 1;
	else return ll(1)<<(topbit(n-1)+1);
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	//#ifdef LOCAL
	static mt19937_64 gen;
	/*#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif*/
	return uniform_int_distribution<ll>(l, r)(gen);
}

ll rand_int(ll k){ //[0,k)
	return rand_int(0,k-1);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t,class u>
int lwb(const vc<t>&v,const u&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t,class u>
bool bis(const vc<t>&v,const u&a){
	return binary_search(all(v),a);
}

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> readTree(int n){
	return readGraph(n,n-1);
}

template<class t>
vc<t> presum(const vc<t>&a){
	vc<t> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
vc<ll> presum(const vi&a){
	vc<ll> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
	gnr(i,1,si(a))a[i]-=a[i-1];
	return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
	int n=si(a),m=si(a[0]);
	vvc<ll> b(n+1,vc<ll>(m+1));
	rep(i,n)rep(j,m)
		b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
	return b;
}

//verify してないや
void transvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[j][i]=a[i][j];
	}
	a.swap(b);
	transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[m-1-j][i]=a[i][j];
	}
	a.swap(b);
	rotvvc(n,m,args...);
}

//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
	int n=si(a);
	vi idx(n);iota(all(idx),0);
	sort(all(idx),[&](int i,int j){return a[i]<a[j];});
	return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
	int n=si(a);
	assert(si(idx)==n);
	vc<t> vs(n);
	rep(i,n)vs[i]=a[idx[i]];
	return vs;
}
//CF850C
vi invperm(const vi&p){
	int n=si(p);
	vi q(n);
	rep(i,n)q[p[i]]=i;
	return q;
}

template<class t,class s=t>
s SUM(const vc<t>&a){
	return accumulate(all(a),s(0));
}

template<class t>
t MAX(const vc<t>&a){
	return *max_element(all(a));
}

template<class t>
pair<t,int> MAXi(const vc<t>&a){
	auto itr=max_element(all(a));
	return mp(*itr,itr-a.bg);
}

template<class t>
t MIN(const vc<t>&a){
	return *min_element(all(a));
}

template<class t>
pair<t,int> MINi(const vc<t>&a){
	auto itr=min_element(all(a));
	return mp(*itr,itr-a.bg);
}

vi vid(int n){
	vi res(n);iota(all(res),0);
	return res;
}

template<class S>
void soin(S&s){
	sort(all(s));
}

template<class S>
S soout(S s){
	soin(s);
	return s;
}

template<class S>
void rein(S&s){
	reverse(all(s));
}

template<class S>
S reout(S s){
	rein(s);
	return s;
}

template<class t,class u>
pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){
	a.a+=b.a;a.b+=b.b;return a;}
template<class t,class u>
pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){
	a.a-=b.a;a.b-=b.b;return a;}
template<class t,class u>
pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(a.a-b.a,a.b-b.b);}

template<class t>
t gpp(vc<t>&vs){
	assert(si(vs));
	t res=move(vs.back());
	vs.pop_back();
	return res;
}

template<class t,class u>
void pb(vc<t>&a,const vc<u>&b){
	a.insert(a.ed,all(b));
}

template<class t,class...Args>
vc<t> cat(vc<t> a,Args&&...b){
	(pb(a,forward<Args>(b)),...);
	return a;
}

template<class t,class u>
vc<t>& operator+=(vc<t>&a,u x){
	for(auto&v:a)v+=x;
	return a;
}

template<class t,class u>
vc<t> operator+(vc<t> a,u x){
	return a+=x;
}

template<class t,class u>
vc<t>& operator-=(vc<t>&a,u x){
	for(auto&v:a)v-=x;
	return a;
}

template<class t,class u>
vc<t>& operator-(vc<t> a,u x){
	return a-=x;
}

template<class t,class u>
void remval(vc<t>&a,const u&v){
	a.erase(remove(all(a),v),a.ed);
}

template<class t,class u>
void fila(vc<t>&vs,const u&a){
	fill(all(vs),a);
}


//VERIFY: yosupo
//KUPC2017J
//AOJDSL1A
//without rank
struct unionfind{
	vi p,s;
	int c;
	unionfind(int n):p(n,-1),s(n,1),c(n){}
	void clear(){
		fill(all(p),-1);
		fill(all(s),1);
		c=si(p);
	}
	int find(int a){
		return p[a]==-1?a:(p[a]=find(p[a]));
	}
	//set b to a child of a
	bool unite(int a,int b){
		a=find(a);
		b=find(b);
		if(a==b)return false;
		p[b]=a;
		s[a]+=s[b];
		c--;
		return true;
	}
	bool same(int a,int b){
		return find(a)==find(b);
	}
	int sz(int a){
		return s[find(a)];
	}
};

//CF869B
//複数始点
template<class E>
tuple<vi,vi,vc<E>> bfs(const vvc<E>&g,vi rs){
	int n=si(g);
	vi dist(n,-1),from(n,-1);
	vc<E> use(n);
	vi q(n);
	int b=0,e=0;
	auto reach=[&](int v,int d,int f,E u){
		if(dist[v]!=-1)return;
		dist[v]=d;
		from[v]=f;
		use[v]=u;
		q[e++]=v;
	};
	for(auto r:rs)reach(r,0,-1,E());
	while(b<e){
		int v=q[b++];
		for(auto to:g[v])
			reach(to,dist[v]+1,v,to);
	}
	return mt(move(dist),move(from),move(use));
}


template<class E>
auto getpath(const vvc<E>&g,int s,int t){
	auto [dist,from,use]=bfs(g,{s});
	vi vs;
	vc<E> es;
	while(from[t]!=-1){
		vs.pb(t);
		es.pb(use[t]);
		t=from[t];
	}
	vs.pb(t);
	rein(vs);
	rein(es);
	return mp(move(vs),move(es));
}

bool dbg=false;

void slv(){
	int n,m;cin>>n>>m;
	vc<string> ss(n);
	rep(i,n)cin>>ss[i];
	int s=0;
	vvc<int> idx(n,vi(m,-1));
	rep(i,n)rep(j,m)if(ss[i][j]=='1')idx[i][j]=s++;
	using Arr=array<int,4>;
	vc<Arr> g(s);
	const int dyx[]{-1,0,1,0,-1};
	string URDL="URDL";
	rep(i,n)rep(j,m)if(idx[i][j]!=-1)rep(d,4){
		int y=i+dyx[d],x=j+dyx[d+1];
		if(inc(0,y,n-1)&&inc(0,x,m-1)&&idx[y][x]!=-1){
			g[idx[i][j]][d]=idx[y][x];
		}else{
			g[idx[i][j]][d]=idx[i][j];
		}
	}
	{
		unionfind uf(s);
		rep(i,s)for(auto j:g[i])uf.unite(i,j);
		if(uf.c>1){
			return print(-1);
		}
	}
	const int len=5*ten(5)-ten(4);
	auto endup=[&](int v,const vi&z){
		rep(i,len)v=g[v][z[i]];
		return v;
	};
	int srcorg,dstorg;
	{
		int r,c;cin>>r>>c;
		r--;c--;
		srcorg=idx[r][c];
	}
	{
		int r,c;cin>>r>>c;
		r--;c--;
		dstorg=idx[r][c];
	}
	
	while(1){
		int src=srcorg;
		int dst=dstorg;
		
		vi A(len);
		
		rep(i,len)A[i]=rand_int(4);
		/*while(1){
			vi z(tar);
			rep(i,tar)z[i]=rand_int(4);
			rep(i,s){
				int x=i;
				rep(_,tar)x=g[x][z[i]];
			}
			
		}*/
		
		{
			//k->dst
			struct E{
				int to,dir;
				operator int()const{return to;}
			};
			vvc<E> h(s);
			rep(i,s)rep(d,4)h[i].pb({g[i][d],d});
			
			auto [vs,es]=getpath(h,endup(rand_int(s),A),dst);
			for(auto [to,dir]:es)
				A.pb(dir);
		}
		
		vi B=reout(A);
		
		src=endup(src,B);
		vi C;
		
		{
			vc<bool> vis(s);
			auto dfs=[&](auto self,int v)->void{
				assert(!vis[v]);
				vis[v]=true;
				rep(dir,4){
					int to=g[v][dir];
					if(!vis[to]){
						C.pb(dir);
						self(self,to);
						C.pb(dir^2);
					}
				}
			};
			dfs(dfs,src);
		}
		
		vi D=reout(C);
		
		vi ans=cat(B,C,D,A);
		assert(si(ans)<=ten(6));
		
		assert(ans==reout(ans));
		
		bool ok=true;
		{//check
			int x=srcorg;
			vc<bool> vis(s);
			vis[x]=true;
			for(auto d:ans){
				x=g[x][d];
				vis[x]=true;
			}
			rep(i,s)if(!vis[i])ok=false;
			if(x!=dstorg)ok=false;
		}
		if(ok){
			for(auto d:ans)cout<<URDL[d];
			cout<<endl;
			break;
		}
	}
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	if(dbg){
		while(1)slv();
	}else{
		//int t;cin>>t;rep(_,t)
		slv();
	}
}

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

详细

Test #1:

score: 100
Accepted
time: 24ms
memory: 17016kb

input:

2 2
11
11
1 1 2 2

output:

RLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRRU...

result:

ok Valid Solution (Length = 980014).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:

LDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRRUU...

result:

ok Valid Solution (Length = 980000).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

RULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRR...

result:

ok Valid Solution (Length = 980080).

Test #5:

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

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

RRRRLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRD...

result:

ok Valid Solution (Length = 980088).

Test #6:

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

input:

5 3
111
100
111
001
111
4 3 3 2

output:

RLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRRU...

result:

ok Valid Solution (Length = 980042).

Test #7:

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

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

ULULULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDR...

result:

ok Valid Solution (Length = 980054).

Test #8:

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

input:

5 3
101
111
100
111
100
4 1 2 2

output:

RUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRD...

result:

ok Valid Solution (Length = 980044).

Test #9:

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

input:

5 5
01110
10110
11110
11011
11100
2 4 5 1

output:

LDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRRUU...

result:

ok Valid Solution (Length = 980064).

Test #10:

score: 0
Accepted
time: 27ms
memory: 16912kb

input:

5 3
011
111
110
111
011
3 1 2 1

output:

LUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRD...

result:

ok Valid Solution (Length = 980052).

Test #11:

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

input:

4 5
11111
11111
11111
11111
3 2 1 3

output:

RRUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDR...

result:

ok Valid Solution (Length = 980086).

Test #12:

score: 0
Accepted
time: 27ms
memory: 17076kb

input:

5 5
11111
10101
11111
10101
11111
2 5 1 1

output:

UUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRD...

result:

ok Valid Solution (Length = 980088).

Test #13:

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

input:

4 5
11111
10000
11111
00001
1 3 4 5

output:

DRRRRDDLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRUR...

result:

ok Valid Solution (Length = 980058).

Test #14:

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

input:

3 5
10100
00010
00111
1 3 1 1

output:

-1

result:

ok No Solution.

Test #15:

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

input:

4 5
10001
11111
11100
11111
4 5 3 1

output:

ULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRRU...

result:

ok Valid Solution (Length = 980058).

Test #16:

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

input:

3 5
11111
10100
11111
1 2 3 5

output:

RRRRDLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDR...

result:

ok Valid Solution (Length = 980054).

Test #17:

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

input:

4 5
01110
10101
11011
10111
1 3 2 3

output:

-1

result:

ok No Solution.

Test #18:

score: 0
Accepted
time: 24ms
memory: 18044kb

input:

5 5
11111
11111
11111
11111
11111
1 3 5 2

output:

RLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRRU...

result:

ok Valid Solution (Length = 980098).

Test #19:

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

input:

5 5
11111
10101
11111
10101
11111
5 1 2 3

output:

URRUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDR...

result:

ok Valid Solution (Length = 980090).

Test #20:

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

input:

5 5
11111
10000
11111
00001
11111
4 5 5 3

output:

LLDDRRRRDDLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLL...

result:

ok Valid Solution (Length = 980084).

Test #21:

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

input:

5 5
01010
10101
10101
11001
10011
4 1 5 4

output:

-1

result:

ok No Solution.

Test #22:

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

input:

5 5
10101
11111
10101
11111
11111
3 1 2 4

output:

RRRUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURD...

result:

ok Valid Solution (Length = 980092).

Test #23:

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

input:

5 5
00001
11111
01110
01111
01111
1 5 5 2

output:

LDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRRUU...

result:

ok Valid Solution (Length = 980064).

Test #24:

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

input:

5 5
01011
10111
11011
10101
01110
4 1 2 3

output:

-1

result:

ok No Solution.

Test #25:

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

input:

10 8
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
7 7 3 6

output:

RRRRUUUUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULL...

result:

ok Valid Solution (Length = 980338).

Test #26:

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

input:

10 6
111111
101010
111111
101010
111111
101010
111111
101010
111111
101010
1 6 2 3

output:

UUUUUUURLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRU...

result:

ok Valid Solution (Length = 980192).

Test #27:

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

input:

10 10
1111111111
1000000000
1111111111
0000000001
1111111111
1000000000
1111111111
0000000001
1111111111
1000000000
5 5 5 2

output:

LLLLLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRD...

result:

ok Valid Solution (Length = 980224).

Test #28:

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

input:

10 10
1010110101
0000011010
1001001001
0011111000
1000111100
1011101001
1100110011
0110001011
0011111000
0101011101
7 5 4 3

output:

-1

result:

ok No Solution.

Test #29:

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

input:

10 6
100100
111111
100001
111111
101111
111111
101010
111111
111100
111111
6 5 7 3

output:

URRUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDR...

result:

ok Valid Solution (Length = 980190).

Test #30:

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

input:

10 8
11111110
11110111
01111111
11111101
11011101
11111111
11111011
11011101
11001111
11111110
7 1 2 1

output:

LUURUUUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLL...

result:

ok Valid Solution (Length = 980288).

Test #31:

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

input:

10 10
1111011101
1110111110
1111011111
1011101111
0101010111
1110111111
0111010111
1011111011
0111010101
1011111110
2 6 7 4

output:

-1

result:

ok No Solution.

Test #32:

score: 0
Accepted
time: 27ms
memory: 15484kb

input:

8 10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
8 10 6 10

output:

RRRRRRUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRU...

result:

ok Valid Solution (Length = 980332).

Test #33:

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

input:

10 10
1111111111
1010101010
1111111111
1010101010
1111111111
1010101010
1111111111
1010101010
1111111111
1010101010
3 5 9 1

output:

LLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRRU...

result:

ok Valid Solution (Length = 980298).

Test #34:

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

input:

10 10
1111111111
1000000000
1111111111
0000000001
1111111111
1000000000
1111111111
0000000001
1111111111
1000000000
5 4 7 2

output:

RDDLLLLLLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRU...

result:

ok Valid Solution (Length = 980232).

Test #35:

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

input:

9 10
1111001000
1110010111
0001001000
0101000101
1101000001
0111100110
0010010000
0001001000
1011001101
2 8 5 2

output:

-1

result:

ok No Solution.

Test #36:

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

input:

5 10
1001011101
1111111111
1000011001
1111111111
1101110010
4 3 4 7

output:

DDRRRRLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURD...

result:

ok Valid Solution (Length = 980152).

Test #37:

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

input:

7 10
1111111001
1111101110
1111011111
1101011101
1111011111
1111001011
1111111011
7 10 7 2

output:

-1

result:

ok No Solution.

Test #38:

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

input:

9 10
0101011101
1111111111
0101111111
1111111111
1111110101
1011111111
1101111101
1111111011
1101011111
3 7 7 10

output:

URURRRLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURD...

result:

ok Valid Solution (Length = 980312).

Test #39:

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

input:

10 10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
9 5 3 2

output:

LLUUUUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLR...

result:

ok Valid Solution (Length = 980414).

Test #40:

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

input:

10 10
1111111111
1010101010
1111111111
1010101010
1111111111
1010101010
1111111111
1010101010
1111111111
1010101010
2 1 1 3

output:

UUUUUUUURLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLR...

result:

ok Valid Solution (Length = 980314).

Test #41:

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

input:

10 10
1111111111
1000000000
1111111111
0000000001
1111111111
1000000000
1111111111
0000000001
1111111111
1000000000
7 4 3 5

output:

LLLLLUURRRRLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULL...

result:

ok Valid Solution (Length = 980238).

Test #42:

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

input:

10 10
1110000101
1100110001
1011011001
0000000111
0010010111
0100111011
1110010011
1100111111
0110001110
0100000101
9 9 6 10

output:

-1

result:

ok No Solution.

Test #43:

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

input:

10 10
1110111011
1111111111
1110110000
1111111111
1010011100
1111111111
1111001110
1111111111
1001010011
1111111111
6 9 2 9

output:

RRRUULUUUURUURLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUD...

result:

ok Valid Solution (Length = 980344).

Test #44:

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

input:

10 10
1111110011
1011111110
0111011111
1101101101
1111111110
1110111101
1011011111
1111111101
1011111101
1111111011
7 3 5 5

output:

RRUULUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRU...

result:

ok Valid Solution (Length = 980340).

Test #45:

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

input:

10 10
1101011101
1110111011
0101110101
1111101011
1111111111
1010111010
0111111101
1111101011
0111111101
1011101111
3 8 2 2

output:

-1

result:

ok No Solution.

Test #46:

score: 0
Accepted
time: 27ms
memory: 15924kb

input:

20 12
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
111111111111
16 8 13 12

output:

RRRRRRUUUUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDU...

result:

ok Valid Solution (Length = 980982).

Test #47:

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

input:

20 17
11111111111111111
10101010101010101
11111111111111111
10101010101010101
11111111111111111
10101010101010101
11111111111111111
10101010101010101
11111111111111111
10101010101010101
11111111111111111
10101010101010101
11111111111111111
10101010101010101
11111111111111111
10101010101010101
111111...

output:

ULLUUUUUUUUUUUULLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUU...

result:

ok Valid Solution (Length = 981068).

Test #48:

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

input:

20 19
1111111111111111111
1000000000000000000
1111111111111111111
0000000000000000001
1111111111111111111
1000000000000000000
1111111111111111111
0000000000000000001
1111111111111111111
1000000000000000000
1111111111111111111
0000000000000000001
1111111111111111111
1000000000000000000
11111111111111...

output:

LLLLLLLUURRRRRRRRRRRRRRRRRRUULLLLLLLLLLLLLLLLLLUURRRRRRRRRRRRRLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDL...

result:

ok Valid Solution (Length = 980920).

Test #49:

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

input:

20 16
0101001111110001
0000111101001011
0000111100011001
1101110100110100
1011011110001101
1101000110111111
0111010111100101
1101101111011001
1101010100000101
1111001000110010
0001011000101000
0101111010110110
0001101111000111
1010100010000110
0100100011011100
0100100101011111
0001000001001110
10011...

output:

-1

result:

ok No Solution.

Test #50:

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

input:

20 18
100101011111011110
111111111111111111
101111101010000001
111111111111111111
110010011011001010
111111111111111111
110110111110000010
111111111111111111
100001000001111000
111111111111111111
100010100111111000
111111111111111111
111100011010110111
111111111111111111
111101010111011110
111111111...

output:

RRRRRRUURUURUURULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUU...

result:

ok Valid Solution (Length = 981140).

Test #51:

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

input:

20 16
1110111111111111
1111111001111111
1111110111111011
1111110011111111
1111111111011111
1111110111101111
1111011111111111
1101111111111111
1011111111111001
0111111011111111
1110111111111111
1111111111111111
1111011011111111
0101110111111111
1110111101111110
1111111111111111
1111111111011111
11111...

output:

RULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRR...

result:

ok Valid Solution (Length = 981160).

Test #52:

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

input:

20 18
110111110101110101
101010111110101010
110101111101111101
111011111011101111
010111110111111101
111011111011111011
011111110111010111
101110101010111010
010111110101110111
101010101011101110
011101110111011111
101010111011111010
010101111111110101
101011101110111011
110101011101010101
101010101...

output:

-1

result:

ok No Solution.

Test #53:

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

input:

14 20
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
...

output:

RRRRRRRLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRUR...

result:

ok Valid Solution (Length = 981130).

Test #54:

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

input:

19 20
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
...

output:

URRRRRRRRRRUUUUUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLUL...

result:

ok Valid Solution (Length = 981194).

Test #55:

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

input:

10 20
11111111111111111111
10000000000000000000
11111111111111111111
00000000000000000001
11111111111111111111
10000000000000000000
11111111111111111111
00000000000000000001
11111111111111111111
10000000000000000000
5 6 8 20

output:

DRRRRRRRRRRRRRRRRRRRDDLLLLLLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUU...

result:

ok Valid Solution (Length = 980470).

Test #56:

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

input:

18 20
11011110100011011100
01100010001011110000
11100110001011101110
10110111100011001111
10100011111011110011
00001010110000010010
01101101100110010001
10001000111110000100
11000011001000001001
10101011101010100110
01111011011010100001
00010110000101101011
10110101011011000011
00110010111011000100
...

output:

-1

result:

ok No Solution.

Test #57:

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

input:

20 20
10101101000110011011
11111111111111111111
10110101010011101111
11111111111111111111
11010000010101011110
11111111111111111111
10100110101011011011
11111111111111111111
10010101101010101001
11111111111111111111
11101001101101101010
11111111111111111111
11100110110111110111
11111111111111111111
...

output:

LLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRRU...

result:

ok Valid Solution (Length = 981278).

Test #58:

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

input:

18 20
11111111111110111111
01111111111011111111
01111111111110011111
11111111111101111111
11111011111110111111
11111111111110111110
11111111111111011111
11011111111111111110
11110111111111001111
10111111110110111111
11111011111111111111
11111111111011101111
11101111001111111111
11111111111111111111
...

output:

RRRRLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRD...

result:

ok Valid Solution (Length = 981308).

Test #59:

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

input:

13 20
11011101111111110111
11111110111010111111
11111111111101011101
10111010101111111010
01011101111111010111
10101011101110101110
01111101010101011111
11111011111110101011
11110111111111011111
11111010101011101011
01111111110101011111
10111010101011111110
11111111110111011101
12 16 1 20

output:

-1

result:

ok No Solution.

Test #60:

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

input:

20 20
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
11111111111111111111
...

output:

RRRRRRRRRRUUUUUUUUUUUUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUD...

result:

ok Valid Solution (Length = 981646).

Test #61:

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

input:

20 20
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
11111111111111111111
10101010101010101010
...

output:

RRRRRRRRRRRRUUUUUUUUUUUUUUUURLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRD...

result:

ok Valid Solution (Length = 981254).

Test #62:

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

input:

20 20
11111111111111111111
10000000000000000000
11111111111111111111
00000000000000000001
11111111111111111111
10000000000000000000
11111111111111111111
00000000000000000001
11111111111111111111
10000000000000000000
11111111111111111111
00000000000000000001
11111111111111111111
10000000000000000000
...

output:

LLLLLLLLLLLLLLLLLLUURRRRRRRRRRRRRRRRRRRUULLLLLLLLLLLLLLLLLLLUURRRRRRRRRRRRRRRRRRRUULLLLLLLLLLLLLLLLLLLUURRRRRRRRRRRRRRRRRRRUULLLLLLLLLLLLLLLLLLLUURRRRRRRRRRRRRRLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUUL...

result:

ok Valid Solution (Length = 981156).

Test #63:

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

input:

20 20
11110100001010101100
10110001101110101000
01011110111010110000
10111001001011011100
00110111011000010101
01001111110001010010
00101001010111010111
10110100100010001000
10101010001110000010
01111111010110101011
00100101001111000101
00110001001001111000
10101110010001000010
00000100010000110000
...

output:

-1

result:

ok No Solution.

Test #64:

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

input:

20 20
11010001010100101010
11111111111111111111
11000010111011001011
11111111111111111111
10010100111100111110
11111111111111111111
11101100001110000111
11111111111111111111
11010100111101000011
11111111111111111111
11010011111100110100
11111111111111111111
10001011110000111010
11111111111111111111
...

output:

DDDDRDDLLDLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLL...

result:

ok Valid Solution (Length = 981216).

Test #65:

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

input:

20 20
11111111111101111111
11111111111111111101
11111110111110111111
11111011110111111111
11010010110111111011
11111111111111101111
11111111111111111111
11111111111111111001
11111111011110111111
11111111111111111101
11101011111111111111
11111110111111101111
11111111111111111101
10111111111111100111
...

output:

LLLLUUUUUUUUUUUULLUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLU...

result:

ok Valid Solution (Length = 981480).

Test #66:

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

input:

20 20
11010111110101010101
10111010101111101010
11111101111101110111
10101011111010101110
11111111110101111101
10111111111010101111
11110101010111111101
10111110101011101111
01110111011101111101
10111011101010111010
11010111011111010111
11111011101011101111
01010111011111011111
11111010111110111011
...

output:

-1

result:

ok No Solution.

Test #67:

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

input:

30 25
1111111111111111111111111
1111111111111111111111111
1111111111111111111111111
1111111111111111111111111
1111111111111111111111111
1111111111111111111111111
1111111111111111111111111
1111111111111111111111111
1111111111111111111111111
1111111111111111111111111
1111111111111111111111111
11111111...

output:

LLLLUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRU...

result:

ok Valid Solution (Length = 983012).

Test #68:

score: 0
Accepted
time: 27ms
memory: 17520kb

input:

30 25
1111111111111111111111111
1010101010101010101010101
1111111111111111111111111
1010101010101010101010101
1111111111111111111111111
1010101010101010101010101
1111111111111111111111111
1010101010101010101010101
1111111111111111111111111
1010101010101010101010101
1111111111111111111111111
10101010...

output:

ULLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRURDRDRR...

result:

ok Valid Solution (Length = 982280).

Test #69:

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

input:

30 25
1111111111111111111111111
1000000000000000000000000
1111111111111111111111111
0000000000000000000000001
1111111111111111111111111
1000000000000000000000000
1111111111111111111111111
0000000000000000000000001
1111111111111111111111111
1000000000000000000000000
1111111111111111111111111
00000000...

output:

RRRRRRRRRRRRRRLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUD...

result:

ok Valid Solution (Length = 981584).

Test #70:

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

input:

30 30
011110110001111010011111110010
011101110110100110001101010100
100100100111010000000011100101
111110001011110110101000100000
100110011100000111100111100010
110011101000111000101110011101
011000001101110100001010011100
001101101010010100111111110011
100010111001110111010110100001
000101010010110...

output:

-1

result:

ok No Solution.

Test #71:

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

input:

30 30
101011111010110011011100010111
111111111111111111111111111111
101000010010011000101010010010
111111111111111111111111111111
101010011110010001011010010101
111111111111111111111111111111
111100010110101001000001000001
111111111111111111111111111111
111101000101101001001000100001
111111111111111...

output:

LLLLLLUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRU...

result:

ok Valid Solution (Length = 982724).

Test #72:

score: 0
Accepted
time: 27ms
memory: 16648kb

input:

30 30
111111111111111101111111011011
111111100111011111111111101010
111111111111111111111111011111
111111111101111111110111111110
111111111111111011111111111111
111110111111111111111111011111
111111111111111111111111111011
111101111111011111111111111111
111111111111111111111111111111
101110111110111...

output:

URRRRRRRRRRRRUUUUUUUUUUURUUUUUUUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLUR...

result:

ok Valid Solution (Length = 983434).

Test #73:

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

input:

30 30
110111011111110111011111110101
101110101010111010101011101010
011101111101011101011111010111
111110101110111111111011101110
010101110101011101010101111111
101111101011111111111110101011
111101110111010101011101010101
111011111010101010101010101111
011111011111110101011111111101
111010101111101...

output:

-1

result:

ok No Solution.

Test #74:

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

input:

21 30
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111...

output:

LUUUUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRU...

result:

ok Valid Solution (Length = 982532).

Test #75:

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

input:

21 30
111111111111111111111111111111
101010101010101010101010101010
111111111111111111111111111111
101010101010101010101010101010
111111111111111111111111111111
101010101010101010101010101010
111111111111111111111111111111
101010101010101010101010101010
111111111111111111111111111111
101010101010101...

output:

LLLLLLLLLLLLLLLULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUU...

result:

ok Valid Solution (Length = 981948).

Test #76:

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

input:

21 30
111111111111111111111111111111
100000000000000000000000000000
111111111111111111111111111111
000000000000000000000000000001
111111111111111111111111111111
100000000000000000000000000000
111111111111111111111111111111
000000000000000000000000000001
111111111111111111111111111111
100000000000000...

output:

RUULLLLLLLLLLLLLLLLLLLLLLLLLLLLLUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRUULLLLLLLLLLLLLLLLLLLLLLLLLLLLLUURRRRRRRRRRRRRRRRRRRRRRRRLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRD...

result:

ok Valid Solution (Length = 981596).

Test #77:

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

input:

25 30
011010010110010101001110110111
000011111001111101110011010001
011011100010011000110100110000
001111001100100010111111101001
000101111100111001000000001111
001010110011101110101000010000
001010011001010000011001001001
011111010111110110101001110000
011001010011100010100101011000
100011000011110...

output:

-1

result:

ok No Solution.

Test #78:

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

input:

25 30
101100000100000111111100110011
111111111111111111111111111111
100111110101001111010001110011
111111111111111111111111111111
101101100110111111011110101110
111111111111111111111111111111
111001000110101100010101000110
111111111111111111111111111111
100000001011110010001101011010
111111111111111...

output:

URRRRRRRRRRRRRRRRRUURUUUUUURUURRUURLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLUR...

result:

ok Valid Solution (Length = 982286).

Test #79:

score: 0
Accepted
time: 27ms
memory: 16804kb

input:

25 30
111111101111111111111111111111
111111111111111101111111110111
111111111111101111111111111111
111111111111111101101111111111
011101111111111111111111101111
111011100111111110111110111111
111111110111111111111111111111
111111111111110111111111111111
111111111111111101111111111111
111111111111111...

output:

RRRUUURLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULUUUUDULLLRUR...

result:

ok Valid Solution (Length = 982818).

Test #80:

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

input:

25 30
110101110101011111010101010111
101111101011111011111110101010
110111011101110111111101011101
101011111011101011111111111011
110111111101011111110111111111
111111111110101011111111101010
110101010101010101011111011101
101010111010101111111111101111
111101110111011101011111010111
101010101010111...

output:

-1

result:

ok No Solution.

Test #81:

score: 0
Accepted
time: 24ms
memory: 17224kb

input:

30 30
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111...

output:

RRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLL...

result:

ok Valid Solution (Length = 983670).

Test #82:

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

input:

30 30
111111111111111111111111111111
101010101010101010101010101010
111111111111111111111111111111
101010101010101010101010101010
111111111111111111111111111111
101010101010101010101010101010
111111111111111111111111111111
101010101010101010101010101010
111111111111111111111111111111
101010101010101...

output:

RRRRRRRRRRRRRRRRRRRRRRUUUURLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUU...

result:

ok Valid Solution (Length = 982750).

Test #83:

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

input:

30 30
111111111111111111111111111111
100000000000000000000000000000
111111111111111111111111111111
000000000000000000000000000001
111111111111111111111111111111
100000000000000000000000000000
111111111111111111111111111111
000000000000000000000000000001
111111111111111111111111111111
100000000000000...

output:

RRRRRRRRRRRRRRRRRRRRRRRRRRRRRUULLLLLLLLLLLLLLLLLLLLLLLLLLLLLUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRUULLLLLLLLLLLLLLLLLLLLLLLLLLLLLUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRUULLLLLLLLLLLLLLLLLLLLLLLLLLLLLUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRUULLLLLLLLLLLLLLLLLLLLLLLLLLLLLUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRUULLLLLLLLLLLLLLLLLLLLL...

result:

ok Valid Solution (Length = 982648).

Test #84:

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

input:

30 30
010110110101101010000010000110
101110000111000001001111100101
010100011111100110100001111101
101101100010111011011010001010
100101010100001011101100101100
101001111001111101101100001110
000111101010011110100001110100
111111001101000001011110000111
010000100010000100000011101000
100001010111010...

output:

-1

result:

ok No Solution.

Test #85:

score: 0
Accepted
time: 27ms
memory: 17180kb

input:

30 30
100110101011111011001000111100
111111111111111111111111111111
101001000111011110000110011110
111111111111111111111111111111
111001111110100011111000000010
111111111111111111111111111111
100111001001100000100010001101
111111111111111111111111111111
110001101000111011111010110110
111111111111111...

output:

DDRDDRRRDDRRRRRRRRRRRRRRRRRRRDLDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDR...

result:

ok Valid Solution (Length = 982760).

Test #86:

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

input:

30 30
111101111111111111111011111111
100111111111111111111111011111
111111011111111111011111111110
101111111101111111111111111111
111111111111111111111111111111
111111101111011111111110111111
111011111111111111111111111111
111111111111111111111101111111
111111111111111111111111111111
011111100111111...

output:

UUUUUUUUUUUULLUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDLRDRDUUUDDDLLULU...

result:

ok Valid Solution (Length = 983396).

Test #87:

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

input:

30 30
011111010101111111011101111101
111011101011111110111111101011
111111010101011101111101110101
111110101011101110111111101110
010111011101110101110101111101
101111101011101110101010111111
110101010101010111011101010101
101110101111101110101110111111
110111011101010111010111110101
101011111110111...

output:

-1

result:

ok No Solution.

Test #88:

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

input:

30 30
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111111111111111111
111111111111111...

output:

LLLLLUUUUUUUUUUUUUUUUUUUUUUUUUUUULDUDLDRLRLDLULRUURRLDRLRDRLULLLDLLRDRLUURLRDRDRRDLURLRRDRRLURDRDDRRUDLULLDLDUDDDDUDRLDLDDRLDRRULRULDULUDLURULLLDRDUUDLUDUURDLURLRDLLUUUDRUULLLDDLULUDURLURURDDLLULLLURLDDLRLLLRDLDRDUULUUDRULRUDDRUDLULLDLRURRRRDULDRRRRLLURRDDRDRULDRLDDDDUDLDLDDLDDDDDLDDRRRLDRULUDLLURDL...

result:

ok Valid Solution (Length = 983662).

Extra Test:

score: 0
Extra Test Passed