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


#define TIME_LIMIT (2800)

#define NOT_SUBMIT 0
#define VALIDATION 0

#define IO_FILE 0

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

#define FIX_RESULT 0


#define TIME_LIMIT_US (TIME_LIMIT * 1000)

#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 CAP>
class CapArr {
private:
	friend class CapArr;

	static_assert(is_trivially_copyable<T>::value);

	T array_[CAP];
	int size_ = 0;

public:


	bool operator == (const CapArr<T, CAP>& r) const {
		if (size_ != r.size_) {
			return false;
		}
		REP(i, size_) {
			if (!(array_[i] == r.array_[i])) {
				return false;
			}
		}
		return true;
	}
	template <class U, int U_CAP>
	bool operator != (const CapArr<U, U_CAP>& r) const {
		return !(*this == r);
	}

	bool MemEqual(const CapArr<T, CAP>& r) const {
		if (size_ != r.size_) {
			return false;
		}
		return memcmp(data(), r.data(), sizeof(T) * size_) == 0;
	}

	constexpr int capacity() const {
		return CAP;
	}

	int size() const {
		return size_;
	}
	bool empty() const {
		return size_ == 0;
	}

	void clear() {
		size_ = 0;
	}

	void resize(int size) {
		size_ = size;
	}

	void assign(int size, const T& e) {
		size_ = size;
		if constexpr (sizeof(T) == 1) {
			if constexpr (is_enum<T>::value) {
				memset(data(), underlying_type<T>::type(e), size);
			}
			else {
				memset(data(), *reinterpret_cast<const unsigned char*>(&e), size);
			}
		}
		else {
			for (int i = 0; i < size; ++i) {
				array_[i] = e;
			}
		}
	}

	void AssignIota(int size) {
		resize(size);
		iota(begin(), end(), 0);
	}
	void Iota(int size) {
		resize(size);
		iota(begin(), end(), 0);
	}

	void MemAssign(int size, int byte) {
		size_ = size;
		memset(data(), byte, sizeof(T) * size);
	}

	void MemCopy(const CapArr<T, CAP>& from) {
		size_ = from.size_;
		memcpy(data(), from.data(), sizeof(T) * from.size_);
	}

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

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

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

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

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

	T* begin() {
		return &array_[0];
	}
	T* end() {
		return &array_[size_];
	}
	const T* begin() const {
		return &array_[0];
	}
	const T* end() const {
		return &array_[size_];
	}

	[[nodiscard]] T& push() {
		auto& ref = array_[size_];
		++size_;
		return ref;
	}
	void push(const T& e) {
		array_[size_] = e;
		++size_;
	}

	void pop() {
		--size_;
	}

	int find(const T& value) const {

		REP(i, size_) {
			if (array_[i] == value) {
				return i;
			}
		}
		return -1;
	}
	bool contains(const T& value) const {
		for (const auto& v : *this) {
			if (v == value) {
				return true;
			}
		}
		return false;
	}

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

	void insert(int index, const T* mem, int size) {
		if (index == size_) {
			memcpy(data() + index, mem, sizeof(T) * size);
			size_ += size;
		}
		else {
			memmove(data() + index + size, data() + index, sizeof(T) * (size_ - index));
			memcpy(data() + index, mem, sizeof(T) * size);
			size_ += size;
		}
	}

	template <int RCAP>
	void append(const CapArr<T, RCAP>& r) {
		insert(size(), r.data(), r.size());
	}

	void remove(int index) {
		remove(index, index + 1);
	}

	void remove(int start, int end) {
		int size = end - start;
		memmove(data() + start, data() + end, sizeof(T) * (size_ - end));
		size_ -= size;
	}

	void RemoveSwap(int index) {
		array_[index] = array_[size_ - 1];
		--size_;
	}

	void RemoveInsert(int start, int end, const T* p, int size) {
		int newEnd = start + size;
		if (size_ - end > 0 && newEnd != end) {
			memmove(data() + newEnd, data() + end, sizeof(T) * (size_ - end));
		}

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

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

	void stable_sort() {
		::stable_sort(begin(), end());
	}
	template <class LESS>
	void stable_sort(LESS&& less) {
		::stable_sort(begin(), end(), less);
	}

	void reverse() {
		::reverse(begin(), end());
	}
};




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 CAP>
struct CapacitySet {
private:
	CapArr<int, CAP> elemens;
	array<int, CAP> indexTable;

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

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

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

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

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

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

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

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

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

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

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

	auto begin() -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	auto end() -> decltype(elemens.begin()) {
		return elemens.end();
	}
	auto begin() const -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	auto end() const -> decltype(elemens.begin()) {
		return elemens.end();
	}
};
template <class T, int CAP>
using CapSet = CapacitySet<CAP>;





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 <class T, int CAP>
struct CapacityMap {
private:
	CapArr<pr<int, T>, CAP> elemens;
	CheckMapDataS<int, CAP> indexTable;

public:
	CapacityMap() {
		indexTable.Clear();
	}

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

	inline void Add(int i, const T& value) {
		indexTable.Set(i, elemens.size());
		elemens.push({ i, value });
	}

	inline void ForceAdd(int i, const T& value) {
		if (indexTable.IsChecked(i)) {
			return;
		}
		indexTable.Set(i, elemens.size());
		elemens.push({ i, value });
	}

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

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable[elemens[lastIndex].a] = removeIndex;
		}
		elemens.pop();
		indexTable.Reset(i);
	}

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

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable[elemens[lastIndex].a] = removeIndex;
		}
		elemens.pop();
		indexTable.Reset(i);
	}

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

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




	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, int CAPACITY>
using CapMap = struct CapacityMap<T, CAPACITY>;

template <class T, int CAP>
struct CapPriorityQueue {
    CapArr<T, CAP> buf_;

    void clear() {
        buf_.clear();
    }

    bool empty() const {
        return buf_.empty();
    }
    bool exist() const {
        return !buf_.empty();
    }

    const T& top() {
        return buf_.front();
    }

    template <class CMP>
    void push(const T& v, CMP&& cmp) {
        buf_.push(v);
        push_heap(ALL(buf_), cmp);
    }

    template <class CMP>
    T pop(CMP&& cmp) {
        pop_heap(ALL(buf_), cmp);
        T ret = buf_.back();
        buf_.pop();
        return ret;
    }

    void PushNoHeap(const T& v) {
        buf_.push(v);
    }
    void MakeHeap() {
        make_heap(ALL(buf_));
    }

};


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

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

	template <class T>
	inline T operator()(T r) {
		return (*this)() % r;
	}
	inline double GetDouble() {
		return (*this)() / (double)UINT64_MAX;
	}
	inline bool GetProb(double E) {
		return GetDouble() <= E;
	}
};




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} };
constexpr array<pint, 5> Around5 = { pint{-1, 0}, pint{0, -1}, pint{1, 0}, pint{0, 1}, pint{0, 0} };

inline Dir RotateRight(Dir d) {
	constexpr Dir nexts[4] = {
		Dir::U,
		Dir::R,
		Dir::D,
		Dir::L,
	};
	return nexts[(int8_t)d];
}
inline Dir RotateLeft(Dir d) {
	constexpr Dir nexts[4] = {
		Dir::D,
		Dir::L,
		Dir::U,
		Dir::R,
	};
	return nexts[(int8_t)d];
}

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 {
	pint toPos_[W*H];

	constexpr GridSystemS() : toPos_{} {
		REP(y, H) {
			REP(x, W) {
				int id = x + W * y;
				toPos_[id] = pint{ x, y };
			}
		}
	}

	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 const pint& ToPos(int id) const {
		return toPos_[id];
	}

	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 if (from == to) {
			return Dir::N;
		}
		else {
			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 void pop() {
        --s;
    }
    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 {
        VASSERT(i >= 0 && i < CAP);
        return ar[i];
    }
    inline constexpr const T& operator [](int i) const {
        VASSERT(i >= 0 && i < CAP);
        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 <int W, int H>
struct JointAroundMapS {
    using CA = CCA<int, 8>;
    CA table[W * H];

    constexpr JointAroundMapS() : table{} {
        REP(cellId, W * H) {
            pint p = { cellId % W, cellId / W };
            FOR(oy, -1, 2) {
                FOR(ox, -1, 2) {
                    if (oy == 0 && ox == 0) {
                        continue;
                    }
                    int x = p.a + ox;
                    int y = p.b + oy;
                    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];
    }
};


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


constexpr int N = 50;
constexpr int M = 20;
constexpr int NN = N*N;

constexpr int NNM = NN * M;			

constexpr int FireRange = 20;		
constexpr int TurnMax = 2000;


template <class T> using NArr = CapArr<T, N>;
template <class T> using NNArr = CapArr<T, NN>;
template <class T> using MArr = CapArr<T, M>;
template <class T> using NNMArr = CapArr<T, NNM>;

template <class T> using NQue = CapQue<T, N>;
template <class T> using NNQue = CapQue<T, NN>;
template <class T> using MQue = CapQue<T, M>;
template <class T> using NNMQue = CapQue<T, NNM>;

template <class T> using NSet = CapSet<T, N>;
template <class T> using NNSet = CapSet<T, NN>;
template <class T> using MSet = CapSet<T, M>;
template <class T> using NNMSet = CapSet<T, NNM>;

struct Bomb {
	int cost_;
	double invCost_;		
	double cosper_;			
	NNArr<int> ps_;			
	NNArr<bool> flags_;		
	CapArr<NNArr<bool>, 300> bombShop_;	

	bool CanBomb(const pint& p) const {
		int x = p.x + FireRange;
		int y = p.y + FireRange;
		if (gs.IsOut(x, y)) {
			return false;
		}
		return flags_[gs.ToId(x, y)];
	}

	bool CanBomb(int putPos, int targetPos) const {
		return CanBomb(gs.ToPos(targetPos) - gs.ToPos(putPos));
	}

	bool CanBombShop(int putPos, int si) const {
		return bombShop_[si][putPos];
	}
};

struct Input {
	NNArr<char> grid_;
	MArr<Bomb> bombs_;
	NNArr<int> shops_;
	int buildingCount_;		

	bool IsShop(int p) const {
		return grid_[p] == '@';
	}
	bool IsBuilding(int p) const {
		return grid_[p] == '#';
	}
	bool IsBlank(int p) const {
		return grid_[p] == '.';
	}
};
Input input_;

#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

#define PARAM_GROUP(NAME)
#define PARAM_GROUP_END


template <class T>
struct InputParam {
	T minValue_;
	T maxValue_;
	T value_;

	InputParam(T minValue, T maxValue) {
		minValue_ = minValue;
		maxValue_ = maxValue;
	}

	void SetValue(T value) {
		value_ = value;
	}

	double GetRate(double strong) const {
		double r = (value_ - minValue_) / (double)(maxValue_ - minValue_) * 2.0 - 1.0;		
		return r * strong;
	}
};

static double BlendDoubleParam(double baseValue, double minValue, double maxValue, initializer_list<double> rates) {
	double totalRate = 1;
	for (double rate : rates) {
		totalRate += rate;
	}

	double value = baseValue * totalRate;

	chmax(value, minValue);
	chmin(value, maxValue);

	return value;
}

static int BlendIntParam(double baseValue, int minValue, int maxValue, initializer_list<double> rates) {
	double totalRate = 1;
	for (double rate : rates) {
		totalRate += rate;
	}

	int value = (int)round(baseValue * totalRate);

	chmax(value, minValue);
	chmin(value, maxValue);

	return value;
}




constexpr
struct {





	START_TUNING;


	PARAM_DOUBLE(StartTemp, 28.472018965267413, 20.0, 30.0);PARAM_LOWER(0.0);
	PARAM_DOUBLE(EndTemp, 8.593583763956138, 6.0, 12.0);PARAM_LOWER(0.0);
	PARAM_INT(RemoveCountMin, 9, 7, 11);PARAM_LOWER(1);
	PARAM_INT(RemoveCountRange, 5, 3, 7);PARAM_LOWER(1);
	PARAM_DOUBLE(ShopDistRate, 0.1584479635782831, 0.1, 0.2);
	PARAM_DOUBLE(LastShopDistRate, 0.1227714408204275, 0.1, 0.15);
	PARAM_DOUBLE(CosperRate, 0.1337243085556696, -0.1, 0.5);



	END_TUNING;

} HP;


enum class CommandType : s8 {
	Empty = 0,
	Move = 1,
	Buy = 2,
	Fire = 3,
};

struct IOCommand {
	CommandType type_;
	s8 value_;			

	void SetMove(Dir dir) {
		type_ = CommandType::Move;
		value_ = (s8)dir;
	}
	void SetBuy(s8 bi) {
		type_ = CommandType::Buy;
		value_ = bi;
	}
	void SetFire(s8 bi) {
		type_ = CommandType::Fire;
		value_ = bi;
	}

	void SetEmpty() {
		type_ = CommandType::Empty;
		value_ = -1;
	}

	void Output(ostream& os) const {
		if (type_ == CommandType::Move) {
			os << (int)type_ << " " << DirToChar(Dir(value_)) << endl;
		}
		else {
			os << (int)type_ << " " << (int)value_ + 1 << endl;
		}
	}
};

struct IOResult {
	CapArr<IOCommand, TurnMax> commands_;

	IOCommand& push() {
		return commands_.push();
	}

	void Output(ostream& os) const {
		os << commands_.size() << endl;
		REP(i, commands_.size()) {
			commands_[i].Output(os);
		}
	}
};


struct PutPoint {
	int p_;			
	int bi_;		
};

struct TargetSystem {
	PutPoint putPoints_[NNM];

	constexpr TargetSystem() : putPoints_ {} {
		REP(p, NN) {
			REP(bi, M) {
				auto& pp = putPoints_[p * M + bi];
				pp.p_ = p;
				pp.bi_ = bi;
			}
		}
	}

	int ToId(int p, int bi) const {
		return p * M + bi;
	}
	int ToId(const PutPoint& pp) const {
		return pp.p_ * M + pp.bi_;
	}
	const PutPoint& ToPP(int tid) const {
		VASSERT(tid >= 0 && tid < NNM);
		return putPoints_[tid];
	}
};
constexpr TargetSystem ts;

struct FireMap {
    using CA = CapArr<u16, 31 * 31>;
    array<CA, NNM> table;

    void Init() {
        REP(p, NN) {
            REP(bi, M) {
                int tid = ts.ToId(p, bi);

                for (int op : input_.bombs_[bi].ps_) {
                    pint pos = gs.ToPos(op);
                    pos.x -= FireRange;
                    pos.y -= FireRange;
                    pos += gs.ToPos(p);
                    if (gs.IsOut(pos)) {
                        continue;
                    }
                    int id = gs.ToId(pos);
                    if (input_.IsBlank(id)) {
                        continue;
                    }
                    table[tid].push(id);
                }
            }
        }
    }

    inline const CA& operator [](int tid) const {
        return table[tid];
    }
};
constexpr int FireMapSize = sizeof(FireMap);

struct FromFireMap {
    using CA = CapArr<u16, 31 * 31 * M>;
    array<CA, NN> table;

    void Init() {
        REP(p, NN) {
            if (input_.IsBlank(p)) {
                continue;
            }
            REP(bi, M) {
                for (int op : input_.bombs_[bi].ps_) {
                    pint pos = gs.ToPos(op);
                    pos.x -= FireRange;
                    pos.y -= FireRange;
                    pos = -pos;         
                    pos += gs.ToPos(p);
                    if (gs.IsOut(pos)) {
                        continue;
                    }
                    int tid = ts.ToId(gs.ToId(pos), bi);
                    table[p].push(tid);
                }
            }
        }
    }

    inline const CA& operator [](int p) const {
        return table[p];
    }
};
constexpr int FromFireMapSize = sizeof(FromFireMap);
FireMap fireMap;
FromFireMap fromFireMap;



struct IOServer {

	void InitInput(ChronoTimer& timer) {
		istream& is = cin;

		int dummy;
		is >> dummy >> dummy;
		timer.Init();		

		input_.buildingCount_ = 0;

		auto& grid = input_.grid_;
		grid.resize(NN);
		REP(i, NN) {
			is >> grid[i];
			if (grid[i] == '@') {
				input_.shops_.push(i);
			}
			if (grid[i] == '#') {
				++input_.buildingCount_;
			}
		}
		auto& bombs = input_.bombs_;
		bombs.resize(M);
		REP(i, M) {
			auto& bomb = bombs[i];
			is >> bomb.cost_;
			bomb.invCost_ = 1.0 / (double)bomb.cost_;
			int L;
			is >> L;
			bomb.ps_.resize(L);
			bomb.flags_.assign(NN, false);
			REP(j, L) {
				int a, b;
				is >> a >> b;
				a += FireRange;
				b += FireRange;
				int id = gs.ToId(b, a);
				bomb.ps_[j] = id;
				bomb.flags_[id] = true;
			}

			bomb.bombShop_.resize(input_.shops_.size());
			for (auto& b : bomb.bombShop_) {
				b.assign(NN, false);
			}

			bomb.cosper_ = bomb.cost_ / (double)bomb.ps_.size();

		}


		fireMap.Init();
		fromFireMap.Init();

		REP(si, input_.shops_.size()) {
			for (int tid : fromFireMap[input_.shops_[si]]) {
				cauto& pp = ts.ToPP(tid);
				input_.bombs_[pp.bi_].bombShop_[si][pp.p_] = true;
			}
		}
	}

	void Output(const IOResult& result) {
		ostream& os = cout;
		result.Output(os);

	}

	void Finalize() {
	}
};
IOServer server;

#define USE_SA_POINT_FILTER 0
#define USE_SA_ROLLBACK 0
#define USE_ACCEPT_SCORE 1

constexpr int InitialStateCount = 1;



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



struct SAChecker {
	Xor64* rand_ = nullptr;
	double* totalMaxScore_ = nullptr;

	double temp = 0;		
	double divTemp = 0;

	double currentScore = 0;
	double maxScore = 0;

	int noMaxUpdateCount = 0;				
	int nextRollbackCheckCount = INT_MAX;	

	inline bool operator()(double newScore, bool forceUpdate = false) {
		++noMaxUpdateCount;

		if (newScore > currentScore) {
			currentScore = newScore;
			if (newScore > maxScore) {
				maxScore = newScore;
				noMaxUpdateCount = 0;

				if (newScore > *totalMaxScore_) {
					*totalMaxScore_ = newScore;
				}
			}

			return true;
		}

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

		else {
			if (forceUpdate || exp((newScore - currentScore) * divTemp) * UINT32_MAX > (*rand_)(UINT32_MAX)) {
				currentScore = newScore;
				return true;
			}
			else {
				return false;
			}
		}
	}

	double AcceptScore() {
		static_assert(numeric_limits<double>::is_iec559);
		return currentScore + temp * log(rand_->GetDouble());
	}

	void SetRevert() {
		++noMaxUpdateCount;

	}

};

template <class F>
struct SATransition {
	const char* name;
	F func;
	int weight;
};
template <class F>
auto MakeTransition(const char* name, F&& func, int weight) {
	return SATransition<F>{ name, func, weight };
}
#define MAKE_TRANS(func, weight) MakeTransition(#func, [&](SAChecker& sac, State& state) { func(sa, sac, state); }, weight)

struct SimulatedAnnealing {
	vector<SAChecker> checkers;

	double totalMaxScore = 0;				
	double timeRate = 0;				
	double temp = 0;					
	double divTemp = 0;					


	Xor64 rand_;

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

	double rollbackStartRate_ = 999.0;			
	int rollbackCount_ = INT_MAX;				
	double rollbackNextMulti_ = 1.1;			
	int minRollbackCount_ = 1;					


public:
	template <class STATE, class... TRANSITION>
	void Run2(ChronoTimer& timer, vector<STATE>& states, tuple<SATransition<TRANSITION>...>& transitions) {

		checkers.resize(states.size());
		totalMaxScore = states[0].EvalScore();
		REP(pi, checkers.size()) {
			auto& checker = checkers[pi];
			checker.rand_ = &rand_;
			checker.totalMaxScore_ = &totalMaxScore;

			checker.temp = 0;
			checker.divTemp = 0;
			checker.currentScore = states[pi].EvalScore();
			checker.maxScore = checker.currentScore;
			checker.noMaxUpdateCount = 0;
			checker.nextRollbackCheckCount = rollbackCount_;

			chmax(totalMaxScore, checker.maxScore);
		}

		RandomTable randTable;
		TupleLoop(transitions, [&](auto&& e, size_t i) {
			randTable.push((int)i, e.weight);
		});

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

		vector<int> pis(states.size());
		iota(ALL(pis), 0);

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


			for (int rp = 0; rp < stepLoopCount; ++rp) {
				int ti = (int)randTable(rand_);

				auto exec = [&](auto&& e, size_t i) {
					for (int pi : pis) {
						auto& checker = checkers[pi];
						e.func(checker, states[pi]);

					}
				};

				TupleAccess(transitions, ti, exec);
			}
			if (forceEnd) {
				break;
			}

		}

	}

	void ForceUpdate() {
	}

private:
	template <class Tuple, class Func>
	void TupleLoop(Tuple & t, Func && f) {
		TupleLoop2(t, forward<Func>(f), make_index_sequence<tuple_size<Tuple>::value>{});
	}
	template <class Tuple, class Func, size_t... Indics>
	void TupleLoop2(Tuple & t, Func && f, index_sequence<Indics...>) {
		using swallow = int[];
		(void)swallow {
			(TupleLoop3<Tuple, Func, Indics>(t, f), 0)...
		};
	}
	template <class Tuple, class Func, size_t Index>
	void TupleLoop3(Tuple & t, Func & f) {
		f(get<Index>(t), Index);
	}

	template <class Tuple, class Func>
	void TupleAccess(Tuple & t, int i, Func && f) {
		TupleAccess2(t, i, forward<Func>(f), make_index_sequence<tuple_size<Tuple>::value>{});
	}
	template <class Tuple, class Func, size_t... Indics>
	void TupleAccess2(Tuple & t, int i, Func && f, index_sequence<Indics...>) {
		using swallow = int[];
		(void)swallow {
			(TupleAccess3<Tuple, Func, Indics>(t, i, f), 0)...
		};
	}
	template <class Tuple, class Func, size_t Index>
	void TupleAccess3(Tuple & t, int i, Func & f) {
		if (i == Index) {
			f(get<Index>(t), Index);
		}
	}

};

Xor64 rand_;

struct ShopMap {
	NNArr<int> dist_;				
	NNArr<int> nearSi_;				

	void Init(const NNArr<int>& orderdSis) {
		dist_.resize(NN);
		nearSi_.resize(NN);
		REP(p, NN) {
			int nearD = INT_MAX;
			int nearSi = -1;
			RREP(sii, orderdSis.size()) {
				int si = orderdSis[sii];
				int shop = input_.shops_[si];

				int d = gs.CalcL1Dist(p, shop);
				if (d < nearD) {
					nearD = d;
					nearSi = si;
				}
			}

			dist_[p] = nearD;
			nearSi_[p] = nearSi;
		}
	}
};

struct Backup {
	NNMArr<int> breakableCount_;	
	NNMSet<int> breakableTids_;		
	NNMSet<int> tids_;				
	NNArr<int> firedCount_;			
};
static constexpr int BackupSize = sizeof(Backup);

struct PlanState {
	NNArr<int> orderdSis_;			
	ShopMap shopMap_;				
	NNMArr<int> breakableCount_;	
	NNMSet<int> breakableTids_;		
	NNMSet<int> tids_;				
	NNArr<int> firedCount_;			

	void Save(Backup& backup) {
		backup.breakableCount_ = breakableCount_;
		backup.breakableTids_ = breakableTids_;
		backup.tids_ = tids_;
		backup.firedCount_ = firedCount_;
	}
	void Restore(const Backup& backup) {
		breakableCount_ = backup.breakableCount_;
		breakableTids_ = backup.breakableTids_;
		tids_ = backup.tids_;
		firedCount_ = backup.firedCount_;
	}

	void Init() {
		orderdSis_.clear();
		orderdSis_.Iota(input_.shops_.size());

		breakableCount_.assign(NNM, 0);
		breakableTids_.Clear();

		REP(i, NN) {
			if (!input_.IsBlank(i)) {
				UpdateRefCountWithBuild(i);
			}
		}

		tids_.Clear();
		firedCount_.assign(NN, 0);
	}

	bool IsEnd() const {
		return breakableTids_.empty();
	}

	void Put(int tid) {
		tids_.Add(tid);

		for (int id : fireMap[tid]) {
			VASSERT(!input_.IsBlank(id));
			if (firedCount_[id] == 0) {
				UpdateRefCountWithBreak(id);
			}
			++firedCount_[id];
		}
	}

	void Remove(int tid) {
		for (int id : fireMap[tid]) {
			VASSERT(!input_.IsBlank(id));
			--firedCount_[id];
			if (firedCount_[id] == 0) {
				UpdateRefCountWithBuild(id);
			}
		}

		tids_.Remove(tid);
	}

	void UpdateRefCountWithBreak(int p) {
		VASSERT(!input_.IsBlank(p));

		for (int tid : fromFireMap[p]) {
			--breakableCount_[tid];
			VASSERT(breakableCount_[tid] >= 0);
			if (breakableCount_[tid] == 0) {
				breakableTids_.Remove(tid);
			}
		}
	}

	void UpdateRefCountWithBuild(int p) {
		VASSERT(!input_.IsBlank(p));

		for (int tid : fromFireMap[p]) {
			if (breakableCount_[tid] == 0) {
				breakableTids_.Add(tid);
			}
			++breakableCount_[tid];
		}
	}

	void RemoveUnnecessary() {
		auto IsRequire = [&](int tid) {
			cauto& pp = ts.ToPP(tid);

			for (int id : fireMap[tid]) {
				VASSERT(!input_.IsBlank(id));
				if (firedCount_[id] == 1) {
					return true;
				}
			}
			return false;
		};

		static NNMArr<int> notRequires;
		notRequires.clear();
		for (int tid : tids_) {
			if (!IsRequire(tid)) {
				notRequires.push(tid);
			}
		}
		Shuffle(ALL(notRequires), rand_);

		while (true) {
			bool updated = false;
			for (int tid : notRequires) {
				if (tids_.IsContain(tid)) {
					if (!IsRequire(tid)) {
						Remove(tid);
						updated = true;
					}
				}
			}
			if (!updated) {
				break;
			}
		}
	}

	void FillGreedy() {
		const int lastSi = orderdSis_.back();
		const int lastShop = input_.shops_[lastSi];
		bool brokenLastShop = firedCount_[lastShop] > 0;



		static NNMArr<bool> tidBreakLastShop;
		tidBreakLastShop.resize(NNM);
		for (int tid : breakableTids_) {
			cauto& pp = ts.ToPP(tid);
			tidBreakLastShop[tid] = input_.bombs_[pp.bi_].CanBombShop(pp.p_, lastSi);
		}


		while (!breakableTids_.empty()) {
			int bestTid = -1;
			bool bestBreakLastShop = false;
			double bestEval = -1e100;

			for (int tid : breakableTids_) {
				bool breakLastShop = tidBreakLastShop[tid];
				if (brokenLastShop && breakLastShop) {
					continue;
				}

				double eval = 0;
				cauto& pp = ts.ToPP(tid);

				{
					int count = breakableCount_[tid];
					eval += count;
					VASSERT(count > 0);
				}

				{
					int d = shopMap_.dist_[pp.p_];
					eval -= d * HP.ShopDistRate;
				}

				if (breakLastShop) {
					int d = gs.CalcL1Dist(lastShop, pp.p_);
					eval -= d * HP.LastShopDistRate;
				}

				cauto& bomb = input_.bombs_[pp.bi_];
				eval -= bomb.cosper_ * HP.CosperRate;

				eval *= bomb.invCost_;

				if (eval > bestEval) {
					bestEval = eval;
					bestTid = tid;
					bestBreakLastShop = breakLastShop;
				}
			}
			VASSERT(bestTid >= 0);

			Put(bestTid);

			if (bestBreakLastShop) {
				brokenLastShop = true;
			}
		}

		RemoveUnnecessary();
	}

};

int LocalSearch2opt(const NNArr<NNArr<int>>& sortedTbl, NNArr<int>& route, NNArr<int>& order) {
	cauto& shops = input_.shops_;

	auto Cost = [&](int a, int b) {
		return gs.CalcL1Dist(shops[a], shops[b]);
	};

	int totalCost = 0;
	REP(i, route.size() - 1) {
		totalCost += Cost(route[i], route[i + 1]);
	}

	auto Update = [&](int iA, int iC) {
		int iB = iA + 1;
		int iD = iC + 1;
		int A = route[iA];
		int B = route[iB];
		int C = route[iC];
		int D = route[iD];
		if (B == C || A == D || B == D) {
			return false;
		}
		if (Cost(A, B) + Cost(C, D) > Cost(A, C) + Cost(B, D)) {
			int newDist = totalCost - (Cost(A, B) + Cost(C, D)) + (Cost(A, C) + Cost(B, D));
			totalCost = newDist;
			if (iB > iD) {
				swap(iB, iD);
			}

			reverse(route.begin() + iB, route.begin() + iD);
			FOR(i, iB, iD) {
				order[route[i]] = i;
			}

			return true;
		}
		return false;
	};

	while (true) {
		bool update = false;

		REP(iA, shops.size() - 1) {
			int iB = iA + 1;
			for (u8 C : sortedTbl[route[iA]]) {
				int iC = order[C];
				if (iC == iB) {
					break;
				}
				if (iC == shops.size() - 1) {
					continue;
				}
				if (Update(iA, iC)) {
					update = true;
					break;
				}
			}
			if (update) {
				break;
			}
			for (u8 D : sortedTbl[route[iB]]) {
				int iD = order[D];
				if (iD == iA) {
					break;
				}
				if (iD == shops.size() - 1) {
					continue;
				}
				if (iD == 0) {
					continue;
				}
				int iC = iD - 1;
				if (Update(iA, iC)) {
					update = true;
					break;
				}
			}
			if (update) {
				break;
			}
		}
		if (!update) {
			break;
		}
	}

	return totalCost;
}

int CalcShopOrder(NNArr<int>& orderdSis, int firstSi, int lastSi) {
	orderdSis.clear();

	cauto& shops = input_.shops_;
	NNArr<bool> used;
	used.assign(shops.size(), false);
	int p = 0;
	orderdSis.push(firstSi);
	REP(loop, shops.size() - 2) {
		int bestD = INT_MAX;
		int bestI = -1;
		REP(i, shops.size()) {
			if (used[i]) {
				continue;
			}
			if (i == firstSi || i == lastSi) {
				continue;
			}
			int s = shops[i];
			int d = gs.CalcL1Dist(p, shops[i]);
			if (d < bestD) {
				bestD = d;
				bestI = i;
			}
		}
		VASSERT(bestI >= 0);
		p = shops[bestI];
		used[bestI] = true;
		orderdSis.push(bestI);
	}
	orderdSis.push(lastSi);

	static NNArr<NNArr<int>> aroundSortedSis;		
	aroundSortedSis.resize(shops.size());
	REP(siA, shops.size()) {
		auto& sis = aroundSortedSis[siA];
		sis.clear();
		REP(siB, shops.size()) {
			if (siA == siB) {
				continue;
			}
			sis.push(siB);
		}
		sis.stable_sort([&](int a, int b) {
			return gs.CalcL1Dist(shops[siA], shops[a]) < gs.CalcL1Dist(shops[siA], shops[b]);
			});
	}

	NNArr<int> order;
	order.resize(orderdSis.size());
	REP(i, orderdSis.size()) {
		order[orderdSis[i]] = i;
	}

	return LocalSearch2opt(aroundSortedSis, orderdSis, order);
}

struct MoveState {
	int p_;						
	NNArr<char> grid_;			
	int shopCount_;				
	int buildingCount_;			
	int bombCount_;				
	MArr<int> bombCounts_;		
	s64 cost_;					

	void Init() {
		p_ = 0;
		grid_ = input_.grid_;
		shopCount_ = input_.shops_.size();
		buildingCount_ = input_.buildingCount_;
		bombCount_ = 0;
		bombCounts_.assign(M, 0);
		cost_ = 0;
	}

	s64 Score() const {
		if (shopCount_ > 0 || buildingCount_ > 0) {
			return 1;
		}
		return max(10LL, 1000000000000LL / (10000LL + cost_));
	}

	bool IsEnd() const {
		return shopCount_ == 0 && buildingCount_ == 0;
	}





	void EasyMove(int p) {
		int d = gs.CalcL1Dist(p_, p);
		if (grid_[p] != '.') {
			++d;
		}
		cost_ += square(bombCount_ + 1) * d;
		p_ = p;
	}

	void SetPosAndCost(int p, s64 cost) {
		cost_ = cost;
		p_ = p;
	}

	void Buy(int bi) {
		VASSERT(grid_[p_] == '@');
		++bombCount_;
		++bombCounts_[bi];
		cost_ += input_.bombs_[bi].cost_;
	}
	void WarpBuy(int bi, int appendCost) {
		++bombCount_;
		++bombCounts_[bi];
		cost_ += input_.bombs_[bi].cost_;
		cost_ += appendCost;
	}

	void Fire(int bi) {
		VASSERT(bombCounts_[bi] > 0);
		--bombCount_;
		--bombCounts_[bi];

		WarpFire(p_, bi);
	}

	void WarpFire(int p, int bi) {
		for (int id : fireMap[ts.ToId(p, bi)]) {
			char c = grid_[id];
			if (c != '.') {
				if (c == '@') {
					--shopCount_;
				}
				else {
					VASSERT(c == '#');
					--buildingCount_;
				}
				grid_[id] = '.';
			}
		}
	}

};

void CalcRoute(const NNArr<char>& grid, int start, int end, NNArr<int>& route, int& costBlock) {
	route.clear();
	costBlock = -1;

	struct Node {
		int point;
		int totalCost;

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

	auto Compare = [&](const Node& a, const Node& b) {
		return a < b;
	};

	NNArr<int> costs;
	NNArr<int> froms;
	costs.assign(NN, INT_MAX);
	froms.resize(NN);
	CapPriorityQueue<Node, NN> que;

	costs[start] = 0;
	froms[start] = -1;
	que.push(Node{ start, 0 }, Compare);

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

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

		for (int n : aroundMap[node.point]) {
			int cost = node.totalCost + 1;
			if (grid[n] != '.') {
				cost += 1;
			}
			if (cost < costs[n]) {
				Node newNode;
				newNode.point = n;
				newNode.totalCost = cost;
				costs[n] = cost;
				froms[n] = node.point;
				que.push(newNode, Compare);
			}
		}
	}

	int p = end;
	while (p >= 0) {
		route.push(p);
		p = froms[p];
	}
	route.reverse();
	costBlock = costs[end];
}

bool MakeMove(const PlanState& plan, IOResult& result, s64& cost, s64 limitCost, bool easy) {
	result.commands_.clear();

	MoveState state;
	state.Init();

	int targetSii = 0;
	cauto& shops = input_.shops_;
	cauto& orderdSis = plan.orderdSis_;
	static NNMSet<int> planTids;
	planTids = plan.tids_;

	static NNArr<NNArr<int>> shopTids;		
	NNArr<int> posToSiDist;		
	{
		cauto& shopMap = plan.shopMap_;

		shopTids.resize(shops.size());
		REP(i, shops.size()) {
			shopTids[i].clear();
		}
		for (int tid : planTids) {
			cauto& pp = ts.ToPP(tid);
			int si = shopMap.nearSi_[pp.p_];
			shopTids[si].push(tid);
		}
		posToSiDist = shopMap.dist_;
	}

	auto UpdateNearShop = [&](int targetSii) {
		VASSERT(state.grid_[shops[orderdSis.back()]] != '.')

			REP(baseSii, orderdSis.size()) {
			int baseSi = orderdSis[baseSii];
			if (shopTids[baseSi].empty()) {
				continue;
			}

			if (baseSii < targetSii || state.grid_[shops[baseSi]] == '.') {
				for (int tid : shopTids[baseSi]) {
					if (!planTids.contains(tid)) {
						continue;
					}

					cauto& pp = ts.ToPP(tid);

					int nearD = INT_MAX;
					int nearSi = -1;
					RREP(sii, orderdSis.size()) {
						int si = orderdSis[sii];
						if (sii < targetSii || state.grid_[shops[si]] == '.') {
							continue;
						}

						int shop = input_.shops_[si];

						int d = gs.CalcL1Dist(pp.p_, shop);
						if (d < nearD) {
							nearD = d;
							nearSi = si;
						}
					}
					VASSERT(nearSi >= 0);
					shopTids[nearSi].push(tid);
					posToSiDist[pp.p_] = nearD;
				}
				shopTids[baseSi].clear();
			}
		}
	};

	struct Command {
		CommandType type_;
		int value_;			
	};
	struct MoveRecord {
		int bombCount;
		int costBlock;		
	};

	static CapArr<Command, TurnMax> commands;		
	static CapArr<CapArr<s8, 100>, 300> buys;
	commands.clear();
	buys.clear();

	int lastShop = -1;
	int lastBuyCi = -1;
	NNArr<MoveRecord> moveFromLastShop;		


	auto Move = [&](MoveState& state, int p) {
		state.EasyMove(p);
		auto& c = commands.push();
		c.type_ = CommandType::Move;
		c.value_ = p;
	};
	auto CalcMoveCostBlock = [&](int start, int end) {
		if (easy) {
			int d = gs.CalcL1Dist(start, end);
			if (state.grid_[end] != '.') {
				d += 1;
			}
			return d;
		}
		else {
			NNArr<int> route;
			int costBlock = 0;
			CalcRoute(state.grid_, start, end, route, costBlock);
			return costBlock;
		}
	};
	auto Buy = [&](MoveState& state, int bi) {
		state.Buy(bi);

		auto& buy = buys.push();
		buy.clear();
		buy.push(bi);

		auto& c = commands.push();
		c.type_ = CommandType::Buy;
		c.value_ = buys.size() - 1;

		lastShop = state.p_;
		lastBuyCi = commands.size() - 1;
		moveFromLastShop.clear();
	};
	auto UpdateBuy = [&](MoveState& state, int ci, int bi, int appendCost) {
		state.WarpBuy(bi, appendCost);

		cauto& c = commands[ci];
		auto& buy = buys[c.value_];
		buy.push(bi);
	};

	auto Fire = [&](MoveState& state, int bi) {
		state.Fire(bi);

		auto& c = commands.push();
		c.type_ = CommandType::Fire;
		c.value_ = bi;
	};

	auto CalcToShopCost = [&](int tid, int targetShop) {
		cauto& pp = ts.ToPP(tid);

		int cost = 0;

		{
			int cb = CalcMoveCostBlock(state.p_, targetShop);
			cost += cb * square(1);
		}
		{
			int cb = CalcMoveCostBlock(targetShop, pp.p_);
			cost += cb * square(1 + 1);
		}
		return cost;
	};

	auto CalcToNextCost = [&](int tid) {
		VASSERT(lastShop >= 0);
		cauto& pp = ts.ToPP(tid);

		int cost = 0;

		for (cauto& move : moveFromLastShop) {
			int oldCost = move.costBlock * square(move.bombCount + 1);
			int newCost = move.costBlock * square(move.bombCount + 1 + 1);
			cost += newCost - oldCost;
		}

		{
			int cb = CalcMoveCostBlock(state.p_, pp.p_);
			cost += cb * square(1 + 1);
		}
		return cost;
	};

	auto MoveFire = [&](int tid, int targetShop) {
		cauto& pp = ts.ToPP(tid);

		s64 beforeCost = state.cost_;

		VASSERT(state.bombCount_ == 0);

		int toShopCost = INT_MAX;
		int toNextCost = INT_MAX;
		toShopCost = CalcToShopCost(tid, targetShop);
		if (lastShop >= 0) {
			toNextCost = CalcToNextCost(tid);
		}

		if (toShopCost <= toNextCost) {
			Move(state, targetShop);

			Buy(state, pp.bi_);

			auto& move = moveFromLastShop.push();
			move.bombCount = 1;
			{
				int cb = CalcMoveCostBlock(targetShop, pp.p_);
				move.costBlock = cb;
			}
			Move(state, pp.p_);

			Fire(state, pp.bi_);

			if (easy) {
				VASSERT(state.cost_ == beforeCost + toShopCost + input_.bombs_[pp.bi_].cost_);
			}
		}
		else {
			int appendCost = 0;
			for (auto& move : moveFromLastShop) {
				int oldCost = move.costBlock * square(move.bombCount + 1);
				int newCost = move.costBlock * square(move.bombCount + 1 + 1);
				appendCost += newCost - oldCost;
				++move.bombCount;
			}
			UpdateBuy(state, lastBuyCi, pp.bi_, appendCost);

			auto& move = moveFromLastShop.push();
			move.bombCount = 1;
			{
				int cb = CalcMoveCostBlock(state.p_, pp.p_);
				move.costBlock = cb;
			}
			Move(state, pp.p_);

			Fire(state, pp.bi_);

			if (easy) {
				VASSERT(state.cost_ == beforeCost + toNextCost + input_.bombs_[pp.bi_].cost_);
			}
		}
	};

	while (targetSii < orderdSis.size()) {
		const int targetSi = orderdSis[targetSii];
		const int targetShop = shops[targetSi];
		if (state.grid_[targetShop] == '.') {
			++targetSii;
			continue;
		}

		UpdateNearShop(targetSii);

		NNArr<int> enableTids;		
		NNArr<int> finalTids;	
		for (int tid : shopTids[targetSi]) {
			if (!planTids.contains(tid)) {
				continue;
			}
			cauto& pp = ts.ToPP(tid);

			if (targetSii + 1 != orderdSis.size()) {
				int lastShop = shops[orderdSis.back()];
				if (input_.bombs_[pp.bi_].CanBomb(pp.p_, lastShop)) {
					continue;
				}
			}

			if (input_.bombs_[pp.bi_].CanBomb(pp.p_, targetShop)) {
				finalTids.push(tid);
			}
			else {
				enableTids.push(tid);
			}
		}


		if (!enableTids.empty()) {
			while (!enableTids.empty()) {
				int nearD = INT_MAX;
				int bestTi = -1;
				REP(ti, enableTids.size()) {
					int tid = enableTids[ti];
					cauto& pp = ts.ToPP(tid);

					int d = gs.CalcL1Dist(state.p_, pp.p_);
					if (d < nearD) {
						nearD = d;
						bestTi = ti;
					}
				}

				int tid = enableTids[bestTi];

				if (lastShop >= 0) {
					int toShopCost = INT_MAX;
					int toNextCost = INT_MAX;
					toShopCost = CalcToShopCost(tid, targetShop);
					toNextCost = CalcToNextCost(tid);
					if (toShopCost < toNextCost) {
						nearD = INT_MAX;
						REP(ti, enableTids.size()) {
							int tid = enableTids[ti];
							cauto& pp = ts.ToPP(tid);

							int d = gs.CalcL1Dist(targetShop, pp.p_);
							if (d < nearD) {
								nearD = d;
								bestTi = ti;
							}
						}
						tid = enableTids[bestTi];
					}
				}

				MoveFire(tid, targetShop);

				if (state.cost_ >= limitCost) {
					return false;
				}

				planTids.Remove(tid);
				enableTids.RemoveSwap(bestTi);
			}

			continue;
		}

		VASSERT(targetSii + 1 != orderdSis.size() || finalTids.size() == 1);

		finalTids.stable_sort([&](int a, int b) {
			return posToSiDist[ts.ToPP(a).p_] < posToSiDist[ts.ToPP(b).p_];
			});
		for (int tid : finalTids) {
			MoveFire(tid, targetShop);
			if (state.cost_ >= limitCost) {
				return false;
			}

			planTids.Remove(tid);

			break;
		}

		++targetSii;
	}

	VASSERT(state.IsEnd());

	if (!easy) {
		s64 cost = 0;
		state.Init();
		REP(ci, commands.size()) {
			cauto& c = commands[ci];
			if (c.type_ == CommandType::Move) {
				NNArr<int> route;
				int costBlock = 0;
				CalcRoute(state.grid_, state.p_, c.value_, route, costBlock);

				REP(i, route.size() - 1) {
					Dir dir = gs.CalcDir(route[i], route[i + 1]);
					VASSERT(dir != Dir::Invalid && dir != Dir::N);
					result.push().SetMove(dir);
				}

				int appendCost = costBlock * square(state.bombCount_ + 1);
				state.SetPosAndCost(c.value_, state.cost_ + appendCost);
			}

			else if (c.type_ == CommandType::Buy) {
				cauto& buy = buys[c.value_];
				for (int bi : buy) {
					state.Buy(bi);
					result.push().SetBuy(bi);
				}
			}
			else {
				VASSERT(c.type_ == CommandType::Fire);
				state.Fire(c.value_);
				result.push().SetFire(c.value_);
			}
		}
		if (state.cost_ >= limitCost) {
			return false;
		}
	}

	cost = state.cost_;

	return true;
}

void MakePlan(PlanState& plan, s64& cost) {
	int firstSi = 0;
	FOR(si, 1, input_.shops_.size()) {
		if (gs.CalcL1Dist(0, input_.shops_[si]) < gs.CalcL1Dist(0, input_.shops_[firstSi])) {
			firstSi = si;
		}
	}

	plan.Init();
	auto initedPlan = plan;

	s64 bestCost = INT64_MAX;
	int bestLastSi = -1;
	FOR(lastSi, 0, input_.shops_.size()) {
		if (lastSi == firstSi) {
			continue;
		}
		plan = initedPlan;
		CalcShopOrder(plan.orderdSis_, firstSi, lastSi);
		plan.shopMap_.Init(plan.orderdSis_);
		plan.FillGreedy();

		IOResult result;
		s64 cost = 0;
		if (MakeMove(plan, result, cost, bestCost, true)) {
			if (cost < bestCost) {
				bestCost = cost;
				bestLastSi = lastSi;
			}
		}
		else {
		}
	}

	plan = initedPlan;
	CalcShopOrder(plan.orderdSis_, firstSi, bestLastSi);
	plan.shopMap_.Init(plan.orderdSis_);
	plan.FillGreedy();
	cost = bestCost;

}

struct State {
	PlanState plan_;
	s64 rawScore_;

	void Init() {
		plan_.Init();
		MakePlan(plan_, rawScore_);
	}

	s64 RawScore() const {
		return -rawScore_;
	}
	double EvalScore() const {
		return (double)-rawScore_;
	}
};
static constexpr int StateSize = sizeof(State);


struct Solver {

	State maxState_;

	void CheckMaxScore(const State& state) {
		if (state.RawScore() > maxState_.RawScore()) {
			maxState_ = state;
		}
	}

	void Run(ChronoTimer& timer) {
		vector<State> states;
		InitState(states);
		maxState_ = states[0];


		SimulatedAnnealing sa;
		sa.startTemp_ = HP.StartTemp;
		sa.endTemp_ = HP.EndTemp;
		sa.stepLoopCount = 1;


		auto transitions = make_tuple(
			MAKE_TRANS(Transition_Update1, 10)
		);

		sa.Run2(timer, states, transitions);

		s64 cost = 0;
		IOResult result;
		MakeMove(maxState_.plan_, result, cost, INT64_MAX, false);

		server.Output(result);
	}

	void InitState(vector<State>& states) {
		states.resize(InitialStateCount);

		{
			State& state = states[0];
			state.Init();
		}

		FOR(i, 1, InitialStateCount) {
			states[i] = states[0];
		}
	}

	void Transition_Update1(SimulatedAnnealing& sa, SAChecker& checker, State& state) {
		static Backup backup;
		state.plan_.Save(backup);

		int removeCount = min(HP.RemoveCountMin + rand_((int)HP.RemoveCountRange), state.plan_.tids_.size());
		REP(i, removeCount) {
			int ti = rand_(state.plan_.tids_.size());
			int tid = state.plan_.tids_[ti];
			state.plan_.Remove(tid);
		}
		state.plan_.FillGreedy();

		double as = checker.AcceptScore();
		s64 limitCost = (s64)ceil(-as);

		s64 cost = 0;
		IOResult result;
		if (MakeMove(state.plan_, result, cost, limitCost, true)) {
			VASSERT(cost <= limitCost);
			double newEvalScore = (double)-cost;
			checker(newEvalScore, true);

			state.rawScore_ = cost;
			CheckMaxScore(state);
		}
		else {
			checker.SetRevert();
			state.plan_.Restore(backup);
		}
	}

};


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

        static Solver solver;
        timer.StartMs(TIME_LIMIT);

        solver.Run(timer);

        server.Finalize();

    }
};