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

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

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

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

	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();
	}
	
	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 EndTime() const {
		return endTime_;
	}

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

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



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

static pint round(const pdouble& d) {
	return pint{ (int)round(d.x), (int)round(d.y) };
}

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

	bool operator == (const CapacityArray<T, CAPACITY>& r) const {
		return memcmp(array_.data(), r.array_.data(), sizeof(T) * count_) == 0;
	}

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

	
	const T* data() const {
		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_;
	}
	inline void PopBack() {
		pop_back();
	}

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

	
	
	
	
	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 <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 {
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];
    }
    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 AROUND_COUNT>
struct AroundMapD {
    using CA = CCA<int, AROUND_COUNT>;
    vector<CA> table_;
    int width_ = 1;

    void Init(int width, int height, const array<pint, AROUND_COUNT>& aroundDirs) {
        width_ = width;
        int count = width * height;
        table_.clear();
        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 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;
	}
};


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

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

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

	
	static inline double GetDouble() {
		return Get() / (double)UINT64_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);
}



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

};



struct Action {
	CapArr<pint, 8> Qs;
	CapArr<int, 1000> route;		
};

constexpr int N = 100;
constexpr int M = 8;
constexpr int alpha = 5;
CapArr<pint, 100> Ps;

struct IOServer {

	
	
	void Input(int argc, const char* argv[]) {
		auto& is = cin;
		int dummy;
		is >> dummy >> dummy;
		Ps.resize(N);
		REP(i, N) {
			is >> Ps[i].x >> Ps[i].y;
		}
	}

	
	
	void Output(const Action& action) {
		ostream& os = cout;
		REP(i, M) {
			os << action.Qs[i].x << " " << action.Qs[i].y << endl;
		}
		os << action.route.size() << endl;
		REP(i, action.route.size()) {
			int t = 1;
			int index = action.route[i];
			if (index >= N) {
				t = 2;
				index -= N;
			}
			os << t << " " << index + 1 << endl;
		}

	}

};
IOServer server;




constexpr int PROGRESS_COUNT = 10;			


struct SimulatedAnnealing {
	double currentScore = 0;
	double maxScore = 0;
	double timeRate = 0;				
	double temp = 1;					
	double divTemp = 1;					
	int noMaxUpdateCount = 0;			
	int resetCount = 0;					


	
	double startTemp_ = 200;					
	double endTemp_ = 1;						
	int stepLoopCount = 1000;					


	
	
	
	
	template <class CALC_NEXT_STATE>
	void Run(ChronoTimer& timer, double currentScore_, CALC_NEXT_STATE&& calcNextState) {
		currentScore = currentScore_;
		maxScore = currentScore_;

		const auto startTime = timer.Now();
		const auto endTime = timer.EndTime();
		const double subTimeCountDiv = 1.0 / (double)(endTime - startTime).count();


		
		bool forceEnd = false;
		while (!timer.IsOver()) {
			timeRate = (timer.Now() - startTime).count() * subTimeCountDiv;
			
			
			temp = startTemp_ * std::pow(endTemp_ / startTemp_, timeRate);		
			divTemp = 1.0 / temp;

			
			for (int rp = 0; rp < stepLoopCount; ++rp) {
				if (calcNextState(*this)) {
					forceEnd = true;
					break;
				}
			}
			if (forceEnd) {
				break;
			}

		}

	}

	
	
	
	inline pair<bool, bool> operator()(double newScore) {
		++noMaxUpdateCount;

		
		if (newScore > currentScore) {
			currentScore = newScore;

			if (newScore > maxScore) {
				maxScore = newScore;
				noMaxUpdateCount = 0;
				return { true, true };
			}

			return { true, false };
		}

		
		else if (newScore == currentScore) {
			return { true, false };
		}

		
		else {
			if (exp((newScore - currentScore) * divTemp) * UINT32_MAX > Random::Get(UINT32_MAX)) {
				currentScore = newScore;
				return { true, false };
			}
			else {
				return { false, false };
			}
		}
	}
};



struct RandomTable {
	vector<int> table_;

	
	void push(int value, int count) {
		table_.reserve(table_.size() + count);
		REP(i, count) {
			table_.emplace_back(value);
		}
	}

	template <class ENGINE>
	int operator()(ENGINE& engine) {
		return table_[engine() % table_.size()];
	}
};

template <int SIZE>
struct Mat {
	array<int, SIZE * SIZE> m_;

	const int& operator()(pint p) const {
		return m_[p.x + p.y * SIZE];
	}
	int& operator()(pint p) {
		return m_[p.x + p.y * SIZE];
	}
	const int& operator()(int x, int y) const {
		return m_[x + y * SIZE];
	}
	int& operator()(int x, int y) {
		return m_[x + y * SIZE];
	}
};

template <int SIZE>
void WarshallFloyd(Mat<SIZE>& mat) {
	REP(k, SIZE) {
		REP(i, SIZE) {
			REP(j, SIZE) {
				chmin(mat(i, j), mat(i, k) + mat(k, j));
			}
		}
	}
}
template <int SIZE>
void WarshallFloyd(Mat<SIZE>& mat, Mat<SIZE>& next) {
	REP(k, SIZE) {
		REP(i, SIZE) {
			REP(j, SIZE) {
				if (mat(i, j) > mat(i, k) + mat(k, j)) {
					mat(i, j) = mat(i, k) + mat(k, j);
					next(i, j) = next(i, k);
				}
			}
		}
	}
}

void Kmeans(array<pint, M>& centers) {
	array<int, N> labels = {};
	array<pdouble, M> cogs = {};

	
	labels.fill(-1);
	REP(label, M) {
		int pi = 0;
		while (true) {
			pi = (int)Random::Get(N);
			if (labels[pi] >= 0) {
				continue;
			}
			break;
		}
		labels[pi] = label;
		cogs[label] = (pdouble)Ps[pi];
	}

	array<pint, M> sums = {};
	array<int, M> counts = {};

	
	while (true) {
		bool update = false;

		sums = {};
		counts = {};
		REP(pi, N) {
			int bestLabel = 0;
			double nearD = INT_MAX;
			REP(label, M) {
				auto sub = cogs[label] - Ps[pi];
				double d = square(sub.x) + square(sub.y);
				if (d < nearD) {
					nearD = d;
					bestLabel = label;
				}
			}
			if (bestLabel != labels[pi]) {
				update = true;
			}
			labels[pi] = bestLabel;
			sums[bestLabel] += Ps[pi];
			counts[bestLabel] += 1;
		}
		if (!update) {
			break;
		}

		REP(label, M) {
			VASSERT(counts[label] > 0);
			cogs[label] = (pdouble)sums[label] / (double)counts[label];
		}
	}

	REP(label, M) {
		centers[label] = round(cogs[label]);
	}
}

struct Solver {
	
	using Stations = array<pint, M>;
	using Route = array<int, N - 1>;		

	struct State {
		double score;

		Stations stations;		
		Mat<M> stationMat;		
		
		Route route;			
		int S;					
	};

	
	Mat<N> planetMat_;		
	Xor64 rand_;

	
	
	
	void Run() {
		Random::Instnce().x += random_device()();

		
		{
			planetMat_.m_.fill(-1);

			REP(i, N) {
				FOR(j, i, N) {
					if (i == j) {
						planetMat_(i, j) = 0;
						planetMat_(j, i) = 0;
					}
					else {
						pint sub = Ps[i] - Ps[j];
						int cost = (square(sub.x) + square(sub.y)) * square(alpha);
						planetMat_(i, j) = cost;
						planetMat_(j, i) = cost;
					}
				}
			}
			WarshallFloyd(planetMat_);
		}

		State curState = {};
		InitState(curState);

		State maxState = curState;

		SimulatedAnnealing sim;
		sim.startTemp_ = 100.0;
		sim.endTemp_ = 1;
		sim.stepLoopCount = 1000;
		

		RandomTable randTable;
		randTable.push(0, 10);
		randTable.push(1, 10);
		randTable.push(2, 100);

		sim.Run(timer, curState.score, [&](SimulatedAnnealing& sa) {
			int p = randTable(rand_);
			if (p == 0) {
				UpdateStationJump(sa, curState, maxState);
			}
			else if (p == 1) {
				UpdateStationMove(sa, curState, maxState);
			}
			else {
				UpdatePlanet2opt(sa, curState, maxState);
			}
			return false;
		});


		
		Action action;
		{
			const auto& state = maxState;

			action.Qs.resize(M);
			REP(i, M) {
				action.Qs[i] = state.stations[i];
			}

			Mat<N + M> allMat;
			Mat<N + M> next;
			CalcAllMat(state.stations, allMat, next);

			
			auto AddRoute = [&](int start, int goal) {
				for (int cur = next(start, goal); cur != goal; cur = next(cur, goal)) {
					action.route.push_back(cur);
				}
				action.route.push_back(goal);
			};

			int S = 0;
			int now = 0;
			action.route.push_back(0);
			REP(i, state.route.size()) {
				int next = state.route[i];
				S += allMat(now, next);
				AddRoute(now, next);
				now = next;
			}
			{
				int next = 0;
				S += allMat(now, next);
				AddRoute(now, next);
				now = next;
			}

		}
		server.Output(action);
	}

	
	
	
	double RawScore(int S) {
		return 1000000000 / double(1000 + sqrt((double)S));
	}
	int RawScoreInt(int S) {
		return (int)round(RawScore(S));
	}

	
	
	
	void CalcAllMat(const Stations& stations, Mat<N+M>& allMat, Mat<N + M>& next) {
		constexpr int NM = N + M;
		allMat.m_.fill(-1);

		
		REP(i, N) {
			FOR(j, i, N) {
				if (i == j) {
					allMat(i, j) = 0;
					allMat(j, i) = 0;
				}
				else {
					pint sub = Ps[i] - Ps[j];
					int cost = (square(sub.x) + square(sub.y)) * square(alpha);
					allMat(i, j) = cost;
					allMat(j, i) = cost;
				}
			}
		}

		
		REP(i, N) {
			FOR(j, N, NM) {
				pint sub = Ps[i] - stations[j - N];
				int cost = (square(sub.x) + square(sub.y)) * alpha;
				allMat(i, j) = cost;
				allMat(j, i) = cost;
			}
		}

		
		FOR(i, N, NM) {
			FOR(j, i, NM) {
				if (i == j) {
					allMat(i, j) = 0;
					allMat(j, i) = 0;
				}
				else {
					pint sub = stations[i - N] - stations[j - N];
					int cost = (square(sub.x) + square(sub.y));
					allMat(i, j) = cost;
					allMat(j, i) = cost;
				}
			}
		}
		REP(i, NM) {
			REP(j, NM) {
				next(i, j) = j;
			}
		}
		WarshallFloyd(allMat, next);
	}

	
	
	
	void CalcStationMat(const Stations& stations, Mat<M>& stationMat) {
		REP(i, M) {
			FOR(j, i, M) {
				if (i == j) {
					stationMat(i, j) = 0;
					stationMat(j, i) = 0;
				}
				else {
					pint sub = stations[i] - stations[j];
					int cost = (square(sub.x) + square(sub.y));
					stationMat(i, j) = cost;
					stationMat(j, i) = cost;
				}
			}
		}
		WarshallFloyd(stationMat);
	}

	
	
	
	
	
	int MoveCost(int a, int b, const Stations& stations, const Mat<M>& stationMat) {
		VASSERT(a >= 0);
		VASSERT(b >= 0);

		
		int bestCost = planetMat_(a, b);

		
		
		auto PlanetStationCost = [&](int planet, int station) {
			pint sub = Ps[planet] - stations[station];
			int cost = (square(sub.x) + square(sub.y)) * alpha;
			return cost;
		};

		
		
		
		REP(im, M) {
			REP(om, M) {
				int cost = PlanetStationCost(a, im) + PlanetStationCost(b, om) + stationMat(im, om);
				chmin(bestCost, cost);
			}
		}

		return bestCost;
	}

	
	
	
	
	int RouteCost(const Route& route, const Stations& stations, const Mat<M>& stationMat) {
		int S = 0;
		int now = 0;
		REP(i, N - 1) {
			int next = route[i];
			S += MoveCost(now, next, stations, stationMat);
			now = next;
		}
		{
			int next = 0;
			S += MoveCost(now, next, stations, stationMat);
			now = next;
		}
		return S;
	}

	
	
	
	void InitState(State& state) {
		Kmeans(state.stations);
		CalcStationMat(state.stations, state.stationMat);

		
		Mat<N+M> allMat;
		Mat<N + M> dummy;
		CalcAllMat(state.stations, allMat, dummy);

		
		state.route.fill(-1);
		int S = 0;
		array<bool, N> used = {};
		int now = 0;
		REP(loop, N - 1) {
			int bestI = -1;
			int bestCost = INT_MAX;
			FOR(i, 1, N) {
				if (used[i]) {
					continue;
				}
				int cost = allMat(now, i);
				if (cost < bestCost) {
					bestCost = cost;
					bestI = i;
				}
			}
			now = bestI;
			used[bestI] = true;
			S += bestCost;
			state.route[loop] = bestI;
		}
		S += allMat(now, 0);

		
		S = RouteCost(state.route, state.stations, state.stationMat);

		state.S = S;
		state.score = RawScore(state.S);
	}

	
	
	
	void UpdateStationJump(SimulatedAnnealing& sa, State& state, State& maxState) {
		
		
		int qi = (int)Random::Get(M);
		auto backupP = state.stations[qi];
		pint newP;
		newP.x = (int)Random::Get(100, 901);
		newP.y = (int)Random::Get(100, 901);
		state.stations[qi] = newP;

		Mat<M> newStationMat;
		CalcStationMat(state.stations, newStationMat);
		int newS = RouteCost(state.route, state.stations, newStationMat);
		double newScore = RawScore(newS);

		
		auto r = sa(newScore);
		if (r.first) {
			
			state.score = newScore;
			state.S = newS;
			state.stationMat = newStationMat;

			if (r.second) {
				
				maxState = state;
			}
		}
		else {
			
			state.stations[qi] = backupP;
		}
	};

	
	
	
	void UpdateStationMove(SimulatedAnnealing& sa, State& state, State& maxState) {
		int qi = (int)Random::Get(M);
		auto backupP = state.stations[qi];
		pint newP = backupP;
		newP.x += (int)Random::Get(101) - 50;
		newP.y += (int)Random::Get(101) - 50;
		state.stations[qi] = newP;

		Mat<M> newStationMat;
		CalcStationMat(state.stations, newStationMat);
		int newS = RouteCost(state.route, state.stations, newStationMat);
		double newScore = RawScore(newS);

		
		auto r = sa(newScore);
		if (r.first) {
			
			state.score = newScore;
			state.S = newS;
			state.stationMat = newStationMat;

			if (r.second) {
				
				maxState = state;
			}
		}
		else {
			
			state.stations[qi] = backupP;
		}
	};

	
	
	
	void UpdatePlanet2opt(SimulatedAnnealing& sa, State& state, State& maxState) {
		int length = (int)Random::Get(2, 51);
		int start = (int)Random::Get(state.route.size() - length + 1);
		int end = start + length;

		
		int a = (start == 0) ? 0 : state.route[start - 1];
		int b = state.route[start];
		int c = state.route[end - 1];
		int d = (end == state.route.size()) ? 0 : state.route[end];

		
		
		
		int before = MoveCost(a, b, state.stations, state.stationMat) + MoveCost(c, d, state.stations, state.stationMat);
		int after  = MoveCost(a, c, state.stations, state.stationMat) + MoveCost(b, d, state.stations, state.stationMat);
		int newS = state.S - before + after;
		double newScore = RawScore(newS);

		
		auto r = sa(newScore);
		if (r.first) {
			
			state.score = newScore;
			reverse(state.route.begin() + start, state.route.begin() + end);
			state.S = newS;


			if (r.second) {
				
				maxState = state;
			}
		}
		else {
			
		}
	};

};

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

			Solver* solver = new Solver;
			solver->Run();

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