#define CODETEST 0
#define OPTUNE 0
#define PERFORMANCE 0
#define EVAL 0

#define TIME_LIMIT (1950)

#define NOT_SUBMIT 0
#define VALIDATION 0

#define IO_FILE 0

#define OUTPUT_INFO 0
#define OUTPUT_FINAL_INFO 1
#define OUTPUT_LOG 0
#define OUTPUT_VISUAL 0

#define FIX_RESULT 0


#ifndef _MSC_VER 
#pragma GCC target ("avx2")
#pragma GCC optimize "O3,omit-frame-pointer,inline"
#pragma GCC optimize ("unroll-loops")



#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wunused-variable"

#endif

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


#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define RFOR(i, s, e) for (int i = int(e) - 1; i >= int(s); --i)
#define REP(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i)
#define RREP(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define ALL(x) (x).begin(),(x).end()

#define rep(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()

template <class T> inline void chmin(T& a, T b) { if (b < a) { a = b; } }
template <class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template <class T> inline constexpr T square(T v) { return v * v; }


using TimePoint = chrono::steady_clock::time_point;

struct Timer {
private:
	TimePoint startTime_;
	TimePoint endTime_;

public:
	inline void Init() {
		startTime_ = chrono::steady_clock::now();
	}

	inline void Start(int limit) {
		endTime_ = startTime_ + chrono::milliseconds(limit);
	}
	inline void StartMs(int limit) {
		endTime_ = startTime_ + chrono::milliseconds(limit);
	}
	inline void StartUs(int limit) {
		endTime_ = startTime_ + chrono::microseconds(limit);
	}

	inline void Join() {
	}

	inline bool IsOver() const {
		return chrono::steady_clock::now() >= endTime_;
	}

	inline int ElapseTimeMs() const {
		return (int)chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime_).count();
	}
	inline int ElapseTimeUs() const {
		return (int)chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - startTime_).count();
	}
	inline int LeftToUS(const TimePoint& limit) const {
		return (int)chrono::duration_cast<chrono::microseconds>(limit - chrono::steady_clock::now()).count();
	}

	inline double NowRate() const {
		return (chrono::steady_clock::now() - startTime_).count() / (double)(endTime_ - startTime_).count();
	}

	inline TimePoint Now() const {
		return chrono::steady_clock::now();
	}
	inline TimePoint EndTime() const {
		return endTime_;
	}

	TimePoint GetLimitTimePointUs(int limit) const {
		return startTime_ + chrono::microseconds(limit);
	}
};

Timer timer;

template <class T>
void InstanceRun(int argc, const char* argv[]) {
	timer.Init();
	T* m = new T;
	m->Run(argc, argv);
	quick_exit(0);
}

struct Main;

signed main(int argc, const char* argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(0);
	InstanceRun<Main>(argc, argv);
}

struct ValidateException {
	stringstream ss;
	ValidateException(const char* function, int line, const char* msg) {
		ss << "**** ABORT **** : " << function << " " << line << " " << msg;
	}
};
struct MemoryException {};


#define VALIDATE_ABORT()
#define VALIDATE_ASSERT(exp)


#define VABORT() VALIDATE_ABORT()
#define VASSERT(exp) VALIDATE_ASSERT(exp)



#include <cstdint>

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using s8 = int8_t;
using s16 = int16_t;
using s32 = int32_t;
using s64 = int64_t;


template <class A, class B>
struct pr {
	union {
		A a;
		A key;
		A first;
		A x;
	};
	union {
		B b;
		B value;
		B second;
		B y;
	};

	bool operator == (pr const& r) const { return a == r.a && b == r.b; }
	bool operator != (pr const& r) const { return !((*this) == r); }
	bool operator < (pr const& r) const {
		if (a == r.a) {
			return b < r.b;
		}
		return a < r.a;
	}

	pr& operator += (pr const& v) {
		a += v.a;
		b += v.b;
		return *this;
	}
	pr& operator -= (pr const& v) {
		a -= v.a;
		b -= v.b;
		return *this;
	}

	template <class C, class D>
	auto operator + (pr<C, D> const& v) const {
		return pr<decltype(a + v.a), decltype(b + v.b)>{ a + v.a, b + v.b };
	}

	template <class C, class D>
	auto operator - (pr<C, D> const& v) const {
		return pr<decltype(a - v.a), decltype(b - v.b)>{ a - v.a, b - v.b };
	}

	template <class C, class D>
	explicit operator pr<C, D>() const {
		return { C(a), D(b) };
	}

	template <class T>
	auto operator * (T const& v) const -> pr<decltype(x * v), decltype(y * v)> {
		return { x * v, y * v };
	}
	template <class T>
	auto operator / (T const& v) const -> pr<decltype(x / v), decltype(y / v)> {
		return { x / v, y / v };
	}

	template <class T>
	pr& operator *= (T const& v) {
		x *= v;
		y *= v;
		return *this;
	}
	template <class T>
	pr& operator /= (T const& v) {
		x /= v;
		y /= v;
		return *this;
	}

	pr operator -() const {
		return pr{ -x, -y };
	}

	void flip() { swap(x, y); }

	friend istream& operator>>(istream& is, pr& p) {
		is >> p.a >> p.b;
		return is;
	}
	friend ostream& operator<<(ostream& os, pr const& p) {
		os << p.a << " " << p.b;
		return os;
	}

	template <size_t I>
	auto get() const {
		if constexpr (I == 0) {
			return x;
		}
		else if constexpr (I == 1) {
			return y;
		}
	}
};
using pint = pr<int, int>;
using pdouble = pr<double, double>;

static_assert(is_pod<pint>::value, "not pod");

template <class A, class B>
struct tuple_size<pr<A, B>> : integral_constant<size_t, 2> {};

template <class A, class B>
struct tuple_element<0, pr<A, B>> { using type = A; };
template <class A, class B>
struct tuple_element<1, pr<A, B>> { using type = B; };

template <class A, class B, class C>
struct tr {
	union {
		A a;
		A first;
		A x;
	};
	union {
		B b;
		B second;
		B y;
	};
	union {
		C c;
		C third;
		C z;
	};

	bool operator == (tr const& r) const { return a == r.a && b == r.b && c == r.c; }
	bool operator != (tr const& r) const { return !((*this) == r); }
	bool operator < (tr const& r) const {
		if (a == r.a) {
			if (b == r.b) {
				return c < r.c;
			}
			return b < r.b;
		}
		return a < r.a;
	}

	tr operator + (tr v) const { return tr(x, y, z) += v; }
	tr operator - (tr v) const { return tr(x, y, z) -= v; }
	tr operator - () const { return tr{ -x, -y, -z }; }

	tr& operator += (tr v) {
		x += v.x;
		y += v.y;
		z += v.z;
		return *this;
	}
	tr& operator -= (tr v) {
		x -= v.x;
		y -= v.y;
		z -= v.z;
		return *this;
	}

	friend istream& operator>>(istream& is, tr& p) {
		is >> p.a >> p.b >> p.c;
		return is;
	}
	friend ostream& operator<<(ostream& os, tr const& p) {
		os << p.a << " " << p.b << " " << p.c;
		return os;
	}
};

using tint = tr<int, int, int>;
static_assert(is_pod<tint>::value, "not pod");

template <class T>
struct arr : public vector<T> {
	static arr<arr<T>> D2(int y, int x, T value) {
		return arr<arr<T>>(y, arr<T>(x, value));
	}
	static arr<arr<arr<T>>> D3(int z, int y, int x, T value) {
		return arr<arr<arr<T>>>(z, arr<arr<T>>(y, arr<T>(x, value)));
	}
	static arr<arr<arr<arr<T>>>> D4(int w, int z, int y, int x, T value) {
		return arr<arr<arr<arr<T>>>>(w, arr<arr<arr<T>>>(z, arr<arr<T>>(y, arr<T>(x, value))));
	}

	static arr<T> Iota(int N, int value = 0) {
		auto r = arr<T>(N);
		r.iota(value);
		return r;
	}
	arr() {}
	arr(initializer_list<T> il) : vector<T>(il) {}
	explicit arr(int n) : vector<T>(n) {}
	arr(int n, T v) : vector<T>(n, v) {}
	arr(const arr& r) : vector<T>(r) {}
	arr(arr&& r) : vector<T>(move(r)) {}

	arr& operator = (const arr& r) {
		vector<T>::operator = (r);
		return *this;
	}
	arr& operator = (arr&& r) {
		vector<T>::operator = (move(r));
		return *this;
	}


	T& operator()(int i) { return (*this)[i]; }
	T const& operator()(int i) const { return (*this)[i]; }
	void init(int n, T v = T()) {
		this->assign(n, v);
	}
	int sz() const { return (int)this->size(); }
	void pb(T v) { this->push_back(v); }
	void sort() { std::sort(this->begin(), this->end()); }
	template <class F> void sort(F&& f) { std::sort(this->begin(), this->end(), f); }
	void rsort() { std::sort(this->begin(), this->end(), greater<T>()); }
	void reverse() { std::reverse(this->begin(), this->end()); }
	void unique_erase() { this->erase(std::unique(this->begin(), this->end()), this->end()); }
	bool next_permutation() { return std::next_permutation(this->begin(), this->end()); }
	int lower_bound(T const& v, function<bool(T, T)> p) { return std::lower_bound(this->begin(), this->end(), v, p) - this->begin(); }
	int lower_bound(T const& v) { return std::lower_bound(this->begin(), this->end(), v) - this->begin(); }
	int upper_bound(T const& v, function<bool(T, T)> p) { return std::upper_bound(this->begin(), this->end(), v, p) - this->begin(); }
	int upper_bound(T const& v) { return std::upper_bound(this->begin(), this->end(), v) - this->begin(); }
	void iota(T startValue = 0) { ::iota(this->begin(), this->end(), startValue); }
	void fill(T v) { ::fill(this->begin(), this->end(), v); }

	int find_sorted_nearest(T const& v) {
		int i = this->lower_bound(v);
		if (i >= sz()) {
			--i;
		}
		else if ((*this)[i] != v) {
			int p = i - 1;
			if (p >= 0) {
				int id = abs((*this)[i] - v);
				int pd = abs((*this)[p] - v);
				if (pd < id) {
					i = p;
				}
			}
		}
		return i;
	}

	int find_sorted(T const& v) {
		int i = this->lower_bound(v);
		if (i >= sz()) {
			return -1;
		}
		if ((*this)[i] != v) {
			return -1;
		}
		return i;
	}

	int find(T const& v) const {
		auto it = std::find(this->begin(), this->end(), v);
		if (it == this->end()) {
			return -1;
		}
		return (int)(it - this->begin());
	}
	bool is_contains(T const& v) const {
		auto it = std::find(this->begin(), this->end(), v);
		if (it == this->end()) {
			return false;
		}
		return true;
	}

	template <class P>
	void remove_if_erase(P&& predicate) { this->erase(std::remove_if(this->begin(), this->end(), predicate), this->end()); }

	void slide_remove(int i) {
		(*this)[i] = (*this)[sz() - 1];
		this->pop_back();
	}
	void remove_idx(int i) {
		this->erase(this->begin() + i);
	}
	void insert_idx(int i, const T& v) {
		this->insert(this->begin() + i, v);
	}

	int findGE(const T& v) {
		return lower_bound(v);
	}
	int findG(const T& v) {
		return upper_bound(v);
	}
	int findLE(const T& v) {
		return upper_bound(v) - 1;
	}
	int findL(const T& v) {
		return lower_bound(v) - 1;
	}


	friend ostream& operator<<(ostream& os, const arr<T>& p) {
		if (p.empty()) {
			return os;
		}
		os << p[0];
		FOR(i, 1, p.size()) {
			os << " " << p[i];
		}
		return os;
	}
};
using ints = arr<int>;

template <class T, int CAPACITY>
struct CapacityQueue {
private:
	array<T, CAPACITY> ar = {};
	int start = 0;
	int end = 0;

public:
	inline void clear() {
		start = 0;
		end = 0;
	}

	inline void push(const T& v) {
		ar[end++] = v;
	}

	inline T* push() {
		T* ptr = &ar[end];
		++end;
		return ptr;
	}

	inline const T& get() const  {
		return ar[start];
	}

	inline T pop() {
		return ar[start++];
	}

	inline bool empty() const {
		return start == end;
	}

	inline bool exist() const {
		return start != end;
	}

	inline int size() const {
		return end - start;
	}

	inline int total_push_count() const {
		return end;
	}

	const T& operator[](int i) const{
		return ar[i];
	}
	int end_size() const {
		return end;
	}
};

template <class T, int CAPACITY>
using CapQue = CapacityQueue<T, CAPACITY>;


template <class T, int CAPACITY>
class CapacityArray {
	static_assert(is_trivially_copyable<T>::value);

private:
	array<T, CAPACITY> array_ = {};
	int count_ = 0;

public:
	CapacityArray() {
	}

	explicit CapacityArray(int count) {
		resize(count);
	}

	inline void clear() {
		count_ = 0;
	}
	inline void Clear() {
		clear();
	}

	inline void resize(int count) {
		count_ = count;
	}
	inline void Resize(int count) {
		resize(count);
	}

	inline void assign(int count, const T& e) {
		count_ = count;
		for (int i = 0; i < count; ++i) {
			array_[i] = e;
		}
	}

	inline T* PushBack() {
		return &array_[count_++];
	}

	inline void push_back(const T& e) {
		array_[count_++] = e;
	}
	inline void PushBack(const T& e) {
		push_back(e);
	}

	inline void pop_back() {
		--count_;
	}
	inline void PopBack() {
		pop_back();
	}


	inline void RemoveSlide(int i) {
		array_[i] = array_[count_ - 1];
		--count_;
	}

	inline int GetCount() const {
		return count_;
	}
	inline int size() const {
		return count_;
	}
	inline int sz() const {
		return count_;
	}

	inline bool empty() const {
		return count_ == 0;
	}

	inline T& operator[](int index) {
		return array_[index];
	}

	inline const T& operator[](int index) const {
		return array_[index];
	}

	inline auto begin() -> decltype(array_.begin()) {
		return array_.begin();
	}

	inline auto end() -> decltype(array_.begin()) {

		return array_.begin() + count_;
	}

	inline auto begin() const -> decltype(array_.begin()) {
		return array_.begin();
	}

	inline auto end() const -> decltype(array_.begin()) {

		return array_.begin() + count_;
	}

	inline bool IsContain(const T& value) const {
		for (const auto& v : *this) {
			if (v == value) {
				return true;
			}
		}
		return false;
	}

	inline void MemInsert(int index, const T* mem, int count) {
		if (index == count_) {
			memcpy(array_.data() + index, mem, sizeof(T) * count);
			count_ += count;
		}
		else {
			memmove(array_.data() + index + count, array_.data() + index, sizeof(T) * (count_ - index));
			memcpy(array_.data() + index, mem, sizeof(T) * count);
			count_ += count;
		}
	}

	void insert(int index, const T& value) {
		MemInsert(index, &value, 1);
	}

};

template <class T, int CAPACITY>
using CapArr = CapacityArray<T, CAPACITY>;





template <int CAPACITY>
struct CapacitySet {
private:
	CapacityArray<int, CAPACITY> elemens;
	array<int, CAPACITY> indexTable;

public:
	CapacitySet() {
		fill(indexTable.begin(), indexTable.end(), -1);
	}

	void Clear() {
		elemens.Clear();
		fill(indexTable.begin(), indexTable.end(), -1);
	}

	inline void Add(int ai) {
		indexTable[ai] = elemens.GetCount();
		elemens.PushBack(ai);
	}

	inline void ForceAdd(int ai) {
		if (indexTable[ai] >= 0) {
			return;
		}
		indexTable[ai] = elemens.GetCount();
		elemens.PushBack(ai);
	}

	inline void Remove(int ai) {
		int removeIndex = indexTable[ai];
		int lastIndex = elemens.GetCount() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable[elemens[lastIndex]] = removeIndex;
		}
		elemens.PopBack();
		indexTable[ai] = -1;
	}

	inline void ForceRemove(int ai) {
		if (indexTable[ai] < 0) {
			return;
		}
		int removeIndex = indexTable[ai];
		int lastIndex = elemens.GetCount() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable[elemens[lastIndex]] = removeIndex;
		}
		elemens.PopBack();
		indexTable[ai] = -1;
	}

	inline bool IsContain(int ai) const {
		return indexTable[ai] >= 0;
	}

	inline int GetCount() const {
		return elemens.GetCount();
	}
	inline int size() const {
		return elemens.GetCount();
	}

	inline int At(int index) const {
		return elemens[index];
	}

	inline int operator[](int index) const {
		return elemens[index];
	}

	inline auto begin() -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	inline auto end() -> decltype(elemens.begin()) {
		return elemens.end();
	}
	inline auto begin() const -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	inline auto end() const -> decltype(elemens.begin()) {
		return elemens.end();
	}
};


struct SizeSet {
private:
	vector<int> elemens;
	vector<int> indexTable;

public:
	void InitSize(int size) {
		elemens.clear();
		elemens.reserve(size);
		indexTable.assign(size, -1);
	}

	void Clear() {
		elemens.clear();
		indexTable.assign(indexTable.size(), -1);
	}

	inline void Add(int ai) {
		indexTable[ai] = (int)elemens.size();
		elemens.emplace_back(ai);
	}

	inline void ForceAdd(int ai) {
		if (indexTable[ai] >= 0) {
			return;
		}
		indexTable[ai] = (int)elemens.size();
		elemens.emplace_back(ai);
	}

	inline void Remove(int ai) {
		int removeIndex = indexTable[ai];
		int lastIndex = (int)elemens.size() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable[elemens[lastIndex]] = removeIndex;
		}
		elemens.pop_back();
		indexTable[ai] = -1;
	}

	inline void ForceRemove(int ai) {
		if (indexTable[ai] < 0) {
			return;
		}
		int removeIndex = indexTable[ai];
		int lastIndex = (int)elemens.size() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable[elemens[lastIndex]] = removeIndex;
		}
		elemens.pop_back();
		indexTable[ai] = -1;
	}

	inline bool IsContain(int ai) const {
		return indexTable[ai] >= 0;
	}

	inline int GetCount() const {
		return (int)elemens.size();
	}

	inline int At(int index) const {
		return elemens[index];
	}

	inline int operator[](int index) const {
		return elemens[index];
	}

	inline auto begin() -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	inline auto end() -> decltype(elemens.begin()) {
		return elemens.end();
	}
	inline auto begin() const -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	inline auto end() const -> decltype(elemens.begin()) {
		return elemens.end();
	}
};

template<class T, class COMPARERE>
struct PriorityQueue : public priority_queue<T, vector<T>, COMPARERE> {


	template <class D>
	void Cut(int size, D&& deleter) {
		if ((int)this->c.size() > size) {
			int orgSize = (int)this->c.size();
			for (int i = size; i < orgSize; ++i) {
				deleter(this->c[i]);
			}
			this->c.resize(size);
		}
	}

	vector<T>& Container() {
		return this->c;
	}

	void Cut(int size) {
		if ((int)this->c.size() > size) {
			this->c.resize(size);
		}
	}

	void Clear() {
		this->c.clear();
	}
};



template <int S>
struct CheckMapS {
private:
    array<u32, S> checked_ = {};
    u32 mark_ = 1;

public:
    void Clear() {
        ++mark_;

        if (mark_ == 0) {
            checked_ = {};
            ++mark_;
        }
    }
    bool IsChecked(int i) const {
        return checked_[i] == mark_;
    }
    void Check(int i) {
        checked_[i] = mark_;
    }
    void Reset(int i) {
        checked_[i] = mark_ - 1;
    }
    bool operator[](int i) const {
        return checked_[i] == mark_;
    }

    bool operator == (const CheckMapS<S>& r) const {
        REP(i, S) {
            if (this->IsChecked(i) != r.IsChecked(i)) {
                return false;
            }
        }
        return true;
    }
};

template <class T, int S>
struct CheckMapDataS {
private:
    array<T, S> data_;
    array<u32, S> checked_ = {};
    u32 mark_ = 1;

public:
    void Clear() {
        ++mark_;

        if (mark_ == 0) {
            checked_ = {};
            ++mark_;
        }
    }

    bool IsChecked(int i) const {
        return checked_[i] == mark_;
    }
    void Check(int i) {
        checked_[i] = mark_;
    }

    void Set(int i, const T& value) {
        checked_[i] = mark_;
        data_[i] = value;
    }

    void Reset(int i) {
        checked_[i] = mark_ - 1;
    }
    const T& Get(int i) const {
        VASSERT(checked_[i] == mark_);
        return data_[i];
    }
    T& Ref(int i) {
        VASSERT(checked_[i] == mark_);
        return data_[i];
    }
    const T& Ref(int i) const {
        VASSERT(checked_[i] == mark_);
        return data_[i];
    }
    const T& operator[](int i) const {
        VASSERT(checked_[i] == mark_);
        return data_[i];
    }

    T GetIf(int i, const T& defaultValue) const {
        if (checked_[i] == mark_) {
            return data_[i];
        }
        return defaultValue;
    }
};


struct CheckMapD {
private:
    vector<u32> checked_;
    u32 mark_ = 1;

public:
    void SetSize(int size) {
        checked_.resize(size, mark_);
    }
    void Clear() {
        ++mark_;

        if (mark_ == 0) {
            checked_.assign(checked_.size(), 0);
            ++mark_;
        }
    }
    bool IsChecked(int i) const {
        return checked_[i] == mark_;
    }
    void Check(int i) {
        checked_[i] = mark_;
    }
    void Reset(int i) {
        checked_[i] = mark_ - 1;
    }
};

template <class T>
struct CheckMapDataD {
private:
    vector<T> data_;
    vector<u32> checked_;
    u32 mark_ = 1;

public:
    void SetSize(int size) {
        checked_.resize(size, mark_);
        data_.resize(size);
    }

    void Clear() {
        ++mark_;

        if (mark_ == 0) {
            checked_.assign(checked_.size(), 0);
            ++mark_;
        }
    }

    bool IsChecked(int i) const {
        return checked_[i] == mark_;
    }
    void Check(int i) {
        checked_[i] = mark_;
    }

    void Set(int i, const T& value) {
        checked_[i] = mark_;
        data_[i] = value;
    }

    void Reset(int i) {
        checked_[i] = mark_ - 1;
    }
    const T& Get(int i) const {
        VASSERT(checked_[i] == mark_);
        return data_[i];
    }
    T& Ref(int i) {
        VASSERT(checked_[i] == mark_);
        return data_[i];
    }
};

enum class Dir : int8_t {
	L = 0,
	U,
	R,
	D,
	N,
	Invalid,
};

constexpr array<Dir, 4> Dir4 = {
	Dir::L,
	Dir::U,
	Dir::R,
	Dir::D,
};

constexpr array<pint, 4> Around4 = { pint{-1, 0}, pint{0, -1}, pint{1, 0}, pint{0, 1} };

inline Dir RotateRight(Dir d) {
	return Dir(((int)d + 1) % 4);
}
inline Dir RotateLeft(Dir d) {
	return Dir(((int)d + 3) % 4);
}

inline Dir Back(Dir d) {
	return Dir(s8(d) ^ 2);
}

bool IsHorizontal(Dir dir) {
	return dir == Dir::L || dir == Dir::R;
}
bool IsVertical(Dir dir) {
	return dir == Dir::U || dir == Dir::D;
}

inline Dir CalcDir(const pint& from, const pint& to) {
	if (from.x > to.x) {
		return Dir::L;
	}
	else if (from.y > to.y) {
		return Dir::U;
	}
	else if (from.x < to.x) {
		return Dir::R;
	}
	else if (from.y < to.y) {
		return Dir::D;
	}
	else {
		return Dir::N;
	}
}


inline const string& DirString(Dir dir) {
	static const string strs[6] = {
		"LEFT",
		"UP",
		"RIGHT",
		"DOWN",
		"WAIT",
		"INVALID",
	};
	return strs[(int)dir];
}

inline char DirToChar(Dir dir) {
	static const char chars[6] = {
		'L',
		'U',
		'R',
		'D',
		'N',
		'*',
	};
	return chars[(int)dir];
}

inline const Dir CharToDir(char c) {
	if (c == 'L') {
		return Dir::L;
	}
	else if (c == 'U') {
		return Dir::U;
	}
	else if (c == 'R') {
		return Dir::R;
	}
	else if (c == 'D') {
		return Dir::D;
	}
	else if (c == 'N') {
		return Dir::N;
	}
	VABORT();
	return Dir::Invalid;
}

template <class T, int CAP>
struct CCA {
    T ar[CAP];
    int s;
    inline constexpr void push(const T& v) {
        ar[s++] = v;
    }
    inline constexpr const T* begin() const {
        return &ar[0];
    }
    inline constexpr const T* end() const {
        return &ar[s];
    }

    inline constexpr const T& operator ()(int i) const {
        return ar[i];
    }
    inline constexpr const T& operator [](int i) const {
        return ar[i];
    }
};

template <int W, int H, int AROUND_COUNT>
struct AroundMapS {
    using CA = CCA<int, AROUND_COUNT>;
    CA table[W * H];

    constexpr AroundMapS(const array<pint, AROUND_COUNT>& aroundDirs) : table{} {
        REP(cellId, W * H) {
            pint p = { cellId % W, cellId / W };
            for (const pint& a : aroundDirs) {
                int x = p.a + a.a;
                int y = p.b + a.b;
                if (x >= 0 && x < W &&
                    y >= 0 && y < H) {
                    table[cellId].push(x + y * W);
                }
            }
        }
    }

    inline constexpr const CA& operator ()(int id) const {
        return table[id];
    }
    inline constexpr const CA& operator [](int id) const {
        return table[id];
    }
};

template <int AROUND_COUNT>
struct AroundMapD {
    using CA = CCA<int, AROUND_COUNT>;
    vector<CA> table_;
    int width_ = 1;

    void Init(int width, int height, const pint (&aroundDirs)[AROUND_COUNT]) {
        width_ = width;
        int count = width * height;
        table_.resize(count);

        REP(i, count) {
            pint p = { i % width, i / width };
            for (const pint& a : aroundDirs) {
                pint n = p + a;
                if (n.a >= 0 && n.a < width &&
                    n.b >= 0 && n.b < height) {
                    table_[i].push(n.a + n.b * width);
                }
            }
        }
    }

    inline const CA& operator[](int i) const {
        return table_[i];
    }
    inline const CA& operator[](const pint& p) const {
        return table_[p.x + p.y * width_];
    }
};

template <int W, int H, int AROUND_COUNT>
struct DirMapS {
    using CA = CCA<int, AROUND_COUNT>;
    CA table[W * H];

    constexpr DirMapS(const array<pint, AROUND_COUNT>& aroundDirs) : table{} {
        REP(cellId, W * H) {
            pint p = { cellId % W, cellId / W };
            for (const pint& a : aroundDirs) {
                int x = p.a + a.a;
                int y = p.b + a.b;
                int n = -1;
                if (x >= 0 && x < W &&
                    y >= 0 && y < H) {
                    n = x + y * W;
                }
                table[cellId].push(n);
            }
        }
    }

    inline constexpr const CA& operator ()(int id) const {
        return table[id];
    }
    inline constexpr const CA& operator [](int id) const {
        return table[id];
    }
};

#include <cstdint>

struct XorShift {
	uint32_t x;
	uint32_t y;
	uint32_t z;
	uint32_t w;

	inline XorShift(uint32_t seed = 0) {
		x = 123456789;
		y = 362436069;
		z = 521288629;
		w = 88675123 + seed;
	}

	inline uint32_t operator()() {
		uint32_t t = x ^ (x << 11);
		x = y;
		y = z;
		z = w;
		return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
	}

	inline uint32_t operator()(uint32_t l, uint32_t r) {
		return ((*this)() % (r - l)) + l;
	}

	inline uint32_t operator()(uint32_t r) {
		return (*this)() % r;
	}
};

struct Xor64 {
	using result_type = uint64_t;
	static constexpr result_type min() { return 0; }
	static constexpr result_type max() { return UINT64_MAX; }

	uint64_t x;
	inline Xor64(uint64_t seed = 0) {
		x = 88172645463325252ULL + seed;
	}

	inline uint64_t operator()() {
		x = x ^ (x << 7);
		return x = x ^ (x >> 9);
	}

	inline uint64_t operator()(uint64_t l, uint64_t r) {
		return ((*this)() % (r - l)) + l;
	}

	inline uint64_t operator()(uint64_t r) {
		return (*this)() % r;
	}
	inline double GetDouble() {
		return (*this)() / (double)UINT64_MAX;
	}
};

struct Xor32 {
	using result_type = uint32_t;
	static constexpr result_type min() { return 0; }
	static constexpr result_type max() { return UINT32_MAX; }

	uint32_t x;
	inline Xor32(uint32_t seed = 0) {
		x = 2463534242 + seed;
	}

	inline uint32_t operator ()(void) {
		x = x ^ (x << 13);
		x = x ^ (x >> 17);
		return x = x ^ (x << 5);
	}

	inline uint32_t operator()(uint32_t l, uint32_t r) {
		return ((*this)() % (r - l)) + l;
	}

	inline uint32_t operator()(uint32_t r) {
		return (*this)() % r;
	}
};

struct Random {
	static inline Xor32& Instnce() {
		static Xor32 x;
		return x;
	}

	static inline uint32_t Get() {
		return Instnce()();
	}
	static inline uint32_t Get(uint32_t l, uint32_t r) {
		return Instnce()(l, r);
	}
	static inline uint32_t Get(uint32_t r) {
		return Instnce()(r);
	}

	static inline void Get2(uint32_t N, uint32_t& a, uint32_t& b) {
		VASSERT(N >= 2);
		a = Get(N);
		b = Get(N - 1);
		if (b >= a) {
			++b;
		}
	}

	static inline double GetDouble() {
		return Get() / (double)UINT32_MAX;
	}

	static inline double GetDouble(double l, double r) {
		return l + GetDouble() * (r - l);
	}
};


#define REGIST_PARAM(name, type, defaultValue) type name = defaultValue;




constexpr
struct {

} HYPER_PARAM;
auto& HP = HYPER_PARAM;

double ParamValue(double x, double a, double e) {
	return a * pow(x, e);
}

constexpr int W = 20;
constexpr int H = 20;
constexpr int WH = W * H;

constexpr int L_MAX = 400;		
constexpr int T_MAX = 1000;		


AroundMapS<W, H, 4> AroundMap(Around4);
DirMapS<W, H, 4> DirMap(Around4);


template <int W, int H>
struct GridSystemS {
	inline constexpr int ToId(int x, int y) const {
		return x + W * y;
	}
	inline constexpr int ToId(const pint& p) const {
		return p.x + W * p.y;
	}
	inline constexpr pint ToPos(int id) const {
		return pint{ id % W, id / W };
	}

	inline int CalcL1Dist(const pint& a, const pint& b) const {
		return abs(a.x - b.x) + abs(a.y - b.y);
	}
	inline int CalcL1Dist(int a, int b) const {
		return CalcL1Dist(ToPos(a), ToPos(b));
	}

	inline int CalcL2Dist2(const pint& a, const pint& b) const {
		return square(a.x - b.x) + square(a.y - b.y);
	}
	inline int CalcL2Dist2(int a, int b) const {
		return CalcL2Dist2(ToPos(a), ToPos(b));
	}

	inline double CalcL2Dist(const pint& a, const pint& b) const {
		return sqrt(CalcL2Dist2(a, b));
	}
	inline double CalcL2Dist(int a, int b) const {
		return CalcL2Dist(ToPos(a), ToPos(b));
	}

	inline bool IsOut(int x, int y) const {
		if (x < 0 || x >= W ||
			y < 0 || y >= H) {
			return true;
		}
		return false;
	}
	inline bool IsOut(const pint& p) const {
		return IsOut(p.x, p.y);
	}
	inline bool IsIn(const pint& p) const {
		return !IsOut(p);
	}

	inline int RotateRight90(int id) const {
		pint p = ToPos(id);
		return ToId(W - 1 - p.y, p.x);
	}
};

template <class T>
using Grid = array<T, WH>;

GridSystemS<W, H> gs;

struct Action {
	CapArr<Dir, T_MAX> dirs;
};

struct Wall {
	int moveCount = 0;			
	int wallCount = 0;			
	double noWallRate = 0.5;	

	void CanMoved() {
		moveCount++;
	}

	void NotMoved(double failProb) {
		moveCount++;
		wallCount++;
		noWallRate *= failProb;
	}

	double CanMoveRate(double failProb) const {
		return noWallRate;
	}

	double WallRate(double failProb) const {
		if (moveCount > wallCount) {
			return 0;
		}
		return 1.0 - noWallRate;
	}
};

struct IOServer {
	array<array<Wall, W - 1>, H> wallsH = {};		
	array<array<Wall, H - 1>, W> wallsV = {};		
	double failProb = 0;

	bool CanMove(const pint& p, Dir dir, double& canMoveRate) const {
		pint nextP = p + Around4[(int)dir];
		if (nextP.x < 0 || nextP.x >= W || nextP.y < 0 || nextP.y >= H) {
			return false;
		}
		if (dir == Dir::L || dir == Dir::R) {
			int left = min(p.x, nextP.x);
			const auto& wall = wallsH[p.y][left];
			canMoveRate = wall.CanMoveRate(failProb);
		}
		else {
			int top = min(p.y, nextP.y);
			const auto& wall = wallsV[p.y][top];
			canMoveRate = wall.CanMoveRate(failProb);
		}
		return true;
	}

	void SetResult(const pint& p, Dir dir, bool successMove) {
		pint nextP = p + Around4[(int)dir];
		if (nextP.x < 0 || nextP.x >= W || nextP.y < 0 || nextP.y >= H) {
			VABORT();
		}
		if (dir == Dir::L || dir == Dir::R) {
			int left = min(p.x, nextP.x);
			auto& wall = wallsH[p.y][left];
			if (successMove) {
				wall.CanMoved();
			}
			else {
				wall.NotMoved(failProb);
			}
		}
		else {
			int top = min(p.y, nextP.y);
			auto& wall = wallsV[p.y][top];
			if (successMove) {
				wall.CanMoved();
			}
			else {
				wall.NotMoved(failProb);
			}
		}
	}


	void Input() {
		auto& is = cin;
		int dummy = 0;
		is >> dummy >> dummy;
		int ip = 0;
		is >> ip;
		failProb = ip / 100.0;

	}

	void Output(const CapArr<Dir, T_MAX>& dirs) {
        {
            auto& os = cout;
			static string str;
			str.clear();
			REP(i, dirs.size()) {
				auto dir = dirs[i];
				str += DirToChar(dir);
			}
			os << str << endl;

			auto& is = cin;
			int ret = 0;
			is >> ret;
			if (ret < 0) {
				quick_exit(0);
				return;
			}

			pint p = {};
			REP(i, ret) {
				Dir dir = dirs[i];
				SetResult(p, dir, true);
				p += Around4[(int)dir];
			}
			if (ret < dirs.size()) {
				Dir dir = dirs[ret];
				SetResult(p, dir, false);
			}
        }

	}

};
IOServer server;




const double D_MAX = sqrt(square(W - 1) + square(H - 1));

struct Solver {
    struct Node {
        pint p = {};
        double canMoveRate = 1;
        double score = 0;
        CapArr<Dir, T_MAX> dirs = {};

        Node() {};
        Node(const pint& p_, double canMoveRate_, const CapArr<Dir, T_MAX>& dirs_) {
            p = p_;
            canMoveRate = canMoveRate_;
            dirs = dirs_;

            double dist = sqrt(square(p.x - (W - 1)) + square(p.y - (H - 1)));
            double dr = 1.0 - (dist / D_MAX);
            score = dr * canMoveRate;
        }
    };
    struct Comparer {
        bool operator()(const Node& a, const Node& b) {
            return a.score < b.score;
        }
    };

    void Run() {
        PriorityQueue<Node, Comparer> que;
        array<array<bool, W>, H> checked;
        CapArr<Dir, T_MAX> bestDirs;
        double bestScore = 0;

        REP(t, T_MAX * 2) {
            que.Clear();
            checked.fill(array<bool, W>{});
            bestDirs.clear();

            que.push(Node(pint{}, 1, {}));
            checked[0][0] = true;

            while (!que.empty()) {
                Node node = que.top();
                que.pop();

                REP(di, 4) {
                    pint np = node.p + Around4[di];

                    Dir dir = Dir4[di];
                    double canMoveRate = 0;
                    if (server.CanMove(node.p, dir, canMoveRate))
                    {
                        if (checked[np.y][np.x]) {
                            continue;
                        }

                        CapArr<Dir, T_MAX> dirs = node.dirs;
                        dirs.push_back(dir);

                        double totalMoveRate = node.canMoveRate * canMoveRate;
                        Node newNode = Node(np, totalMoveRate, dirs);
                        if (np.y == H - 1 && np.x == W - 1) {
                            if (bestDirs.empty() || newNode.score > bestScore) {
                                bestScore = newNode.score;
                                bestDirs = newNode.dirs;
                            }
                        }
                        else {
                            que.push(newNode);
                            checked[np.y][np.x] = true;
                        }
                    }
                }
            }
            server.Output(bestDirs);
        }
    }

    double Score() {
        double score = 0;
        return score;
    }
};

struct Main {
	void Run(int argc, const char* argv[]) {
		try {
			timer.StartMs(TIME_LIMIT);
			server.Input();

			Solver* solver = new Solver;
			solver->Run();
		}
		catch (ValidateException& e) {
			(void)e;
		}

		cerr << "time " << timer.ElapseTimeMs() << endl;
	}
};