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

#define TIME_LIMIT (1950)
#define TIME_LIMIT_US (TIME_LIMIT * 1000)

#define NOT_SUBMIT 0
#define VALIDATION 0

#define IO_FILE 0

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

#define FIX_RESULT 0
#define FIX_LOOP_COUNT 3000



#ifdef __clang_version__
#pragma clang diagnostic ignored "-Wunknown-pragmas"
#pragma clang diagnostic ignored "-Wunknown-warning-option"
#pragma clang diagnostic ignored "-Wmissing-braces"
#endif


#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"
#pragma GCC diagnostic ignored "-Wunused-function"
#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
#endif

#define _USE_MATH_DEFINES
#ifdef __clang_version__

#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <cfenv>
#include <cinttypes>
#include <cstdint>
#include <cwchar>
#include <cwctype>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

#else
#include <bits/stdc++.h>
#endif

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()

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

template <class T, int SIZE>
constexpr int len(const T(&)[SIZE]) { return SIZE; }

#define cauto const auto

#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;



using TimePoint = chrono::high_resolution_clock::time_point;

struct ChronoTimer {
private:
	TimePoint startTime_;
	TimePoint endTime_;

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

	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::high_resolution_clock::now() >= endTime_;
	}

	inline int ElapseTimeMs() const {
		return (int)chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - startTime_).count();
	}
	inline int ElapseTimeUs() const {
		return (int)chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - startTime_).count();
	}

	void SetElapseTimeMs(int ms) {
		auto now = chrono::high_resolution_clock::now();
		auto limit = endTime_ - startTime_;
		startTime_ = now - chrono::milliseconds(ms);
		endTime_ = startTime_ + limit;
	}

	inline int LeftToUS(const TimePoint& limit) const {
		return (int)chrono::duration_cast<chrono::microseconds>(limit - chrono::high_resolution_clock::now()).count();
	}

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

	inline TimePoint Now() const {
		return chrono::high_resolution_clock::now();
	}
	inline TimePoint StartTime() const {
		return startTime_;
	}
	inline TimePoint EndTime() const {
		return endTime_;
	}

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

TimePoint Now() {
	return chrono::high_resolution_clock::now();
}


template <class T>
void InstanceRun(int argc, const char* argv[]) {
	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 MemoryException {};


#define VALIDATE_ABORT()
#define VALIDATE_ASSERT(exp)


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






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

	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;
	}
	bool operator > (pr const& r) const {
		return r < (*this);
	}


	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_trivially_copyable<pint>::value, "not trivially_copyable");

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; };

inline pdouble ToDouble(const pint& p) {
	return pdouble{ double(p.x), double(p.y) };
}
inline pint round(const pdouble& d) {
	return pint{ (int)round(d.x), (int)round(d.y) };
}
inline double norm(const pdouble& d) {
	return sqrt((d.x * d.x) + (d.y * d.y));
}
inline double norm(const pint& d) {
	return norm(ToDouble(d));
}
inline int norm2(const pint& d) {
	return square(d.x) + square(d.y);
}
inline pdouble normalized(const pdouble& d) {
	return d / norm(d);
}
inline double dot(const pdouble& a, const pdouble& b) {
	return a.x * b.x + a.y * b.y;
}
inline double cross(const pdouble& a, const pdouble& b) {
	return a.x * b.y - a.y * b.x;
}

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);
	}

	bool operator == (const CapacityArray<T, CAPACITY>& r) const {
		if (count_ != r.count_) {
			return false;
		}
		REP(i, count_) {
			if (!(array_[i] == r.array_[i])) {
				return false;
			}
		}
		return true;
	}
	bool operator != (const CapacityArray<T, CAPACITY>& r) const {
		return !(*this == r);
	}

	void CopyFrom(const CapacityArray<T, CAPACITY>& r) {
		memcpy(array_.data(), r.array_.data(), sizeof(T) * r.count_);
		count_ = r.count_;
	}

	constexpr int capacity() const {
		return CAPACITY;
	}

	inline void clear() {
		count_ = 0;
	}

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

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

	const T* data() const {
		return array_.data();
	}
	T* data() {
		return array_.data();
	}

	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_;
	}

	T& front() {
		return array_[0];
	}
	const T& front() const {
		return array_[0];
	}

	T& back() {
		return array_[count_ - 1];
	}
	const T& back() const {
		return array_[count_ - 1];
	}

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

	inline int size() 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 int Find(const T& value) const {
		REP(i, count_) {
			if (array_[i] == value) {
				return i;
			}
		}
		return -1;
	}
	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);
	}

	inline void Insert(int start, int end, const T* p, int size) {
		int newEnd = start + size;
		if (count_ - end > 0 && newEnd != end) {
			memmove(array_.data() + newEnd, array_.data() + end, sizeof(T) * (count_ - end));
		}

		memcpy(array_.data() + start, p, sizeof(T) * size);

		count_ -= end - start;
		count_ += size;
	}

	inline void Remove(int start, int end) {
		int size = end - start;
		memmove(array_.data() + start, array_.data() + end, sizeof(T) * (count_ - end));
		count_ -= size;
	}


};

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



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;
		++end_;
	}

	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_;
	}
	int direct_start() const {
		return start_;
	}
	int direct_end() const {
		return end_;
	}

	inline auto begin() -> decltype(ar_.begin()) {
		return ar_.begin() + start_;
	}
	inline auto end() -> decltype(ar_.begin()) {
		return ar_.begin() + end_;
	}
	inline auto begin() const -> decltype(ar_.begin()) {
		return ar_.begin() + start_;
	}
	inline auto end() const -> decltype(ar_.begin()) {
		return ar_.begin() + end_;
	}

	const T& front() const {
		return ar_[start_];
	}
	const T& back() const {
		return ar_[end_ - 1];
	}


};

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






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];
    }
    T& operator[](int i) {
        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;
    }
};

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

public:
	CapacitySet() {
	}

	constexpr int capacity() {
		return CAPACITY;
	}

	void Clear() {
		elemens.clear();
		indexTable.Clear();
	}

	inline void Add(int ai) {
		indexTable.Set(ai, elemens.size());
		elemens.PushBack(ai);
	}

	inline void ForceAdd(int ai) {
		if (indexTable.IsChecked(ai)) {
			return;
		}
		indexTable.Set(ai, elemens.size());
		elemens.PushBack(ai);
	}

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

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable.Set(elemens[lastIndex], removeIndex);
		}
		elemens.pop_back();
		indexTable.Reset(ai);
	}

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

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable.Set(elemens[lastIndex], removeIndex);
		}
		elemens.PopBack();
		indexTable.Reset(ai);
	}

	inline bool IsContain(int ai) const {
		return indexTable.IsChecked(ai);
	}

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

	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 <int CAPACITY>
using CapSet = CapacitySet<CAPACITY>;



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();
	}
};


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

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

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

        if (mark_ == 0) {
            checked_.assign(checked_.size(), 0);
            ++mark_;
        }
    }
    inline bool IsChecked(int i) const {
        return checked_[i] == mark_;
    }

    inline bool operator[](int i) const {
        return checked_[i] == mark_;
    }

    inline void Check(int i) {
        checked_[i] = mark_;
    }

    inline void Reset(int i) {
        checked_[i] = mark_ - 1;
    }
};

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 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 <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);
	}

	inline Dir CalcDir(int from, int to) const {
		if (from - 1 == to) {
			return Dir::L;
		}
		else if (from - W == to) {
			return Dir::U;
		}
		else if (from + 1 == to) {
			return Dir::R;
		}
		else if (from + W == to) {
			return Dir::D;
		}
		else {
			VABORT();
		}
		return Dir::Invalid;
	}

};

constexpr double LinearParam(double ax, double ay, double bx, double by, double cx) {
	double r = (cx - ax) / (bx - ax);
	double cy = ay + (by - ay) * r;
	return cy;
}

int LinearParamInt(double ax, double ay, double bx, double by, double cx) {
	return (int)round(LinearParam(ax, ay, bx, by, cx));
}


template <class IT, class RAND>
void Shuffle(IT&& begin, IT&& end, RAND&& rand) {
	int size = int(end - begin);
	if (size <= 1) {
		return;
	}
	REP(i, size - 1) {
		int j = i + rand() % (size - i);
		swap(*(begin + i), *(begin + j));
	}
}

template<class T, class COMPARERE = less<T>>
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();
	}
};


#include <cstdint>


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

private:
	Xor64(const Xor64& r) = delete;
	Xor64& operator =(const Xor64& r) = delete;
public:

	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;
	}
	inline bool GetProb(double E) {
		return (*this)() < ((double)UINT64_MAX + 1) * E;
	}
};



#define PARAM_CATEGORY(NAME, VALUE, ...) int NAME = VALUE;
#define PARAM_INT(NAME, VALUE, LOWER_VALUE, UPPER_VALUE) int NAME = VALUE;
#define PARAM_DOUBLE(NAME, VALUE, LOWER_VALUE, UPPER_VALUE) double NAME = VALUE;


#define PARAM_LOWER(v)
#define PARAM_UPPER(v)
#define START_TUNING
#define END_TUNING




constexpr
struct {
} HP;

constexpr int N = 3000;
constexpr int T = 400;
constexpr int H = 14;
constexpr int W = 14;
constexpr int WH = W * H;


constexpr int INF = 100100100;

template <class T, int CAP>
struct CCA {
private:
    T ar[CAP];
    int s;

public:
    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];
    }
    inline constexpr int size() const {
        return s;
    }
};

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 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];
    }
};

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

constexpr GridSystemS<W, H> gs;
constexpr AroundMapS<W, H, 4> aroundMap(Around4);
constexpr DirMapS<W, H, 4> dirMap(Around4);




struct IOServer {
	array<array<int, WH>, WH> fromToCounts_ = {};		
	array<array<bool, 4>, WH> builded_ = {};				
	int turn_ = -1;
	int money_ = 1000000;
	int persons_ = 1;
	int buildCost_ = 10000000;
	int income_ = 0;

	void InitInput(ChronoTimer& timer) {
		istream& is = cin;
		int dummy;
		is >> dummy >> dummy;
		timer.Init();

		int a, b, c, d;
		REP(i, N) {
			is >> a >> b >> c >> d;
			int from = gs.ToId(b - 1, a - 1);
			int to = gs.ToId(d - 1, c - 1);
			++fromToCounts_[from][to];
		}
	}

	void Input() {
		istream& is = cin;

		int money;
		int persons;
		is >> money >> persons;
		if (money != money_) {
			cerr << "money: " << money << " money_: " << money_ << endl;
		}
		if (persons != persons_) {
			cerr << "persons: " << persons << " persons_: " << persons_ << endl;
		}
		assert(money == money_);
		assert(persons == persons_);

	}


	void Build(int from, int to) {
		assert(money_ >= buildCost_);

		ostream& os = cout;
		pint f = gs.ToPos(from) + pint{ 1, 1 };
		pint t = gs.ToPos(to) + pint{ 1, 1 };
		os << 1 << " " << f.y << " " << f.x << " " << t.y << " " << t.x << endl;

		Dir dir = gs.CalcDir(from, to);
		builded_[from][(int)dir] = true;
		builded_[to][(int)Back(dir)] = true;

		money_ -= buildCost_;
		income_ = CalcIncome();
		money_ += income_;
	}
	void GetPerson() {
		ostream& os = cout;
		os << 2 << endl;

		++persons_;
		buildCost_ = (int)floor(10000000 / sqrt(persons_));
		money_ += income_;
	}
	void GetMoney() {
		ostream& os = cout;
		os << 3 << endl;

		money_ += 50000;
		money_ += income_;
	}


	void Finalize() {
	}


	void Dijkstra(int start, Grid<int>& costs, Grid<int>& moneys) const {
		struct Node {
			int point;
			int totalCost;
			int totalMoney;

			bool operator < (Node const& n) const {
				return totalCost > n.totalCost;
			}
		};

		costs.fill(INF);
		moneys.fill(0);
		priority_queue<Node> que;

		costs[start] = 0;
		moneys[start] = 0;
		que.push(Node{ start, 0 });

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

			if (costs[node.point] != node.totalCost) {
				continue;
			}

			REP(dir, 4) {
				int next = dirMap[node.point][dir];
				if (next < 0) {
					continue;
				}
				bool builded = builded_[node.point][dir];
				int cost = builded ? 223 : 1000;
				int nextTotalCost = node.totalCost + cost;

				if (nextTotalCost < costs[next]) {
					costs[next] = nextTotalCost;
					moneys[next] = moneys[node.point] + (builded ? 30 : 0);

					Node newNode;
					newNode.point = next;
					newNode.totalCost = nextTotalCost;
					que.push(newNode);
				}
			}
		}
	}

	int CalcIncome() const {
		int income = 0;
		REP(from, WH) {
			Grid<int> costs;
			Grid<int> moneys;
			Dijkstra(from, costs, moneys);
			REP(to, WH) {
				int money = moneys[to];
				income += fromToCounts_[from][to] * money * 2;		
			}
		}
		return income;
	}

};
IOServer server;


struct Solver {

	void Run(ChronoTimer& timer) {

		REP(turn, T) {
			server.Input();

			bool build = false;
			if (server.money_ >= server.buildCost_) {
				REP(ci, WH) {
					REP(dir, 4) {
						int ni = dirMap[ci][dir];
						if (ni < 0) {
							continue;
						}
						if (!server.builded_[ci][dir]) {
							server.Build(ci, ni);
							build = true;
							break;
						}
					}
					if (build) {
						break;
					}
				}
			}
			if (!build) {
				if (turn % 2) {
					server.GetPerson();
				}
				else {
					server.GetMoney();
				}
			}
		}

		cerr << "money: " << server.money_ << endl;
		cerr << "persons: " << server.persons_ << endl;
	}
};

struct Main {
    void Run(int argc, const char* argv[]) {
        ChronoTimer timer;
        server.InitInput(timer);
        cerr << "init input " << timer.ElapseTimeMs() << endl;

        static Solver solver;
        timer.StartMs(TIME_LIMIT);
        solver.Run(timer);

        server.Finalize();

    }
};