結果

問題 No.5019 Hakai Project
ユーザー bowwowforeach
提出日時 2023-11-18 18:55:40
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,953 ms / 3,000 ms
コード長 53,855 bytes
コンパイル時間 6,143 ms
コンパイル使用メモリ 304,152 KB
実行使用メモリ 354,880 KB
スコア 2,434,147,186
最終ジャッジ日時 2023-11-18 18:58:22
合計ジャッジ時間 160,695 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:409:22: warning: class 'CapArr<T, CAP>' is implicitly friends with itself
  409 |         friend class CapArr;
      |                      ^~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#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 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 CapacitySet {
private:
    CapArr<T, CAP> elemens;
    CheckMapDataS<T, CAP> indexTable;
public:
    CapacitySet() {
    }
    bool operator == (const CapacitySet<T, CAP>& r) const {
        if (elemens.size() != r.elemens.size()) {
            return false;
        }
        for (int i : elemens) {
            if (!r.IsContain(i)) {
                return false;
            }
        }
        return true;
    }
    constexpr int capacity() {
        return CAP;
    }
    void Fill() {
        indexTable.Clear();
        elemens.resize(CAP);
        iota(ALL(elemens), 0);
        REP(i, CAP) {
            indexTable.Set(i, i);
        }
    }
    void Clear() {
        elemens.clear();
        indexTable.Clear();
    }
    void Add(T ai) {
        indexTable.Set(ai, elemens.size());
        elemens.push(ai);
    }
    void ForceAdd(T ai) {
        if (indexTable.IsChecked(ai)) {
            return;
        }
        indexTable.Set(ai, elemens.size());
        elemens.push(ai);
    }
    void Remove(int ai) {
        T removeIndex = indexTable[ai];
        T lastIndex = elemens.size() - 1;
        if (removeIndex != lastIndex) {
            elemens[removeIndex] = elemens[lastIndex];
            indexTable.Set(elemens[lastIndex], removeIndex);
        }
        elemens.pop();
        indexTable.Reset(ai);
    }
    void ForceRemove(T ai) {
        if (!indexTable.IsChecked(ai)) {
            return;
        }
        T removeIndex = indexTable[ai];
        T lastIndex = elemens.size() - 1;
        if (removeIndex != lastIndex) {
            elemens[removeIndex] = elemens[lastIndex];
            indexTable.Set(elemens[lastIndex], removeIndex);
        }
        elemens.pop();
        indexTable.Reset(ai);
    }
    bool contains(T i) const {
        return indexTable.IsChecked(i);
    }
    bool IsContain(T i) const {
        return contains(i);
    }
    int size() const {
        return elemens.size();
    }
    bool empty() const {
        return elemens.empty();
    }
    T At(int index) const {
        return elemens[index];
    }
    T 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<T, CAP>;
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 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 {
    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 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];
    }
};
template <int W, int H>
struct RandAroundMapS {
    using CA = CCA<int, 4>;
    CapArr<CA, 24> table[W * H];
    constexpr RandAroundMapS() : table{} {
        REP(cellId, W * H) {
            pint p = { cellId % W, cellId / W };
            CA tmp{};
            for (const pint& a : Around4) {
                int x = p.a + a.a;
                int y = p.b + a.b;
                if (x >= 0 && x < W &&
                    y >= 0 && y < H) {
                    tmp.push(x + y * W);
                }
            }
            CapArr<int, 4> idxs;
            REP(i, tmp.size()) {
                idxs.push(i);
            }
            do {
                auto& t = table[cellId].push();
                for (int i : idxs) {
                    t.push(tmp[i]);
                }
            } while (next_permutation(ALL(idxs)));
        }
    }
    template <class RAND>
    inline constexpr const CA& operator ()(int p, RAND& r) const {
        auto& tbl = table[p];
        return tbl[r(tbl.size())];
    }
};
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 = 100000;
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_;
    NNArr<int> ps_;         
    NNArr<bool> flags_;     
    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 {
        auto relPos = gs.ToPos(targetPos) - gs.ToPos(putPos);
        return CanBomb(relPos);
    }
};
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;
    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 {
    int ToId(int p, int bi) const {
        return p * M + bi;
    }
    int ToId(const PutPoint& pp) const {
        return pp.p_ * M + pp.bi_;
    }
    PutPoint ToPP(int id) const {
        return PutPoint{ id / M, id % M };
    }
};
constexpr TargetSystem ts;
struct FireMap {
    using CA = CapArr<int, 41 * 41>;
    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];
    }
};
struct FromFireMap {
    using CA = CapArr<int, 41 * 41 * 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];
    }
};
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_;
            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;
            }
        }
        fireMap.Init();
        fromFireMap.Init();
    }
    void Output(const IOResult& result) {
        ostream& os = cout;
        result.Output(os);
    }
    void Finalize() {
    }
};
IOServer server;
#define USE_SA_POINT_FILTER 1
#define USE_SA_ROLLBACK 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;   
#if USE_ACCEPT_SCORE
    inline bool operator()(double newScore, bool forceUpdate = false) {
#else
    inline bool operator()(double newScore) {
#endif
        ++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 USE_ACCEPT_SCORE
            if (forceUpdate || exp((newScore - currentScore) * divTemp) * UINT32_MAX > (*rand_)(UINT32_MAX)) {
#else
            if (exp((newScore - currentScore) * divTemp) * UINT32_MAX > (*rand_)(UINT32_MAX)) {
#endif
                currentScore = newScore;
                return true;
            }
            else {
                return false;
            }
        }
    }
#if USE_ACCEPT_SCORE
    double AcceptScore() {
        static_assert(numeric_limits<double>::is_iec559);
        return currentScore + temp * log(rand_->GetDouble());
    }
    void SetRevert() {
        ++noMaxUpdateCount;
    }
#endif
};
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) {
        vector<STATE> maxStates = states;
        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]);
                        if (states[pi].RawScore() > maxStates[pi].RawScore()) {
                            maxStates[pi] = states[pi];
                        }
                        else {
                            if (timeRate >= rollbackStartRate_) {
                                if (checker.noMaxUpdateCount >= checker.nextRollbackCheckCount) {
                                    states[pi] = maxStates[pi];
                                    checker.noMaxUpdateCount = 0;
                                    checker.nextRollbackCheckCount = (int)round(checker.nextRollbackCheckCount * rollbackNextMulti_);
                                    chmax(checker.nextRollbackCheckCount, minRollbackCount_);
                                }
                            }
                        }
                    }
                };
                TupleAccess(transitions, ti, exec);
            }
            if (forceEnd) {
                break;
            }
            {
                constexpr double start = 0.2;
                constexpr double end = 1.0;
                int targetPointCount = (int)states.size();
                if (timeRate >= end) {
                    targetPointCount = 1;
                }
                else if (timeRate >= start) {
                    double r = 1.0 - (timeRate - start) / (end - start);        
                    targetPointCount = 1 + (int)floor(states.size() * r);
                }
                if ((int)pis.size() > targetPointCount) {
                    sort(ALL(pis), [&](int a, int b) {
                        return checkers[a].maxScore > checkers[b].maxScore;
                    });
                    pis.resize(targetPointCount);
                }
            }
        }
    }
    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 Backup {
};
struct PlanState {
    NNArr<int> orderdSis_;          
    NNMArr<int> breakableCount_;    
    NNMSet<int> breakableTids_;     
    NNMSet<int> tids_;              
    NNArr<int> 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 p, int bi) {
        int tid = ts.ToId(p, bi);
        tids_.Add(tid);
        for (int id : fireMap[tid]) {
            VASSERT(!input_.IsBlank(id));
            ++firedCount_[id];
            if (firedCount_[id] == 1) {
                UpdateRefCountWithBreak(id);
            }
        }
    }
    void Remove(int tid) {
        auto pp = ts.ToPP(tid);
        for (int id : fireMap[tid]) {
            VASSERT(!input_.IsBlank(id));
            --firedCount_[id];
            if (firedCount_[id] == 0) {
                UpdateRefCountWithBuild(id);
            }
        }
        tids_.Remove(tid);
    }
    int GetBreakCount(int p, int bi) const {
        return breakableCount_[ts.ToId(p, bi)];
    }
    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]) {
            ++breakableCount_[tid];
            if (breakableCount_[tid] == 1) {
                breakableTids_.Add(tid);
            }
        }
    }
    void RemoveUnnecessary() {
        auto IsRequire = [&](int tid) {
            auto pp = ts.ToPP(tid);
            for (int id : fireMap[tid]) {
                VASSERT(!input_.IsBlank(id));
                if (firedCount_[id] == 1) {
                    return true;
                }
            }
            return false;
        };
        NNMArr<int> notRequires;
        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 lastShop = input_.shops_[orderdSis_.back()];
        bool brokenLastShop = firedCount_[lastShop] > 0;
        while (!breakableTids_.empty()) {
            int bestTo = -1;
            int bestBi = -1;
            bool bestBreakLastShop = false;
            double bestEval = -1e100;
            for (int tid : breakableTids_) {
                PutPoint pp = ts.ToPP(tid);
                int i = pp.p_;
                int bi = pp.bi_;
                bool breakLastShop = false;
                {
                    breakLastShop = input_.bombs_[bi].CanBomb(pp.p_, lastShop);
                    if (brokenLastShop && breakLastShop) {
                        continue;
                    }
                }
                int count = GetBreakCount(pp.p_, pp.bi_);
                VASSERT(count > 0);
                double eval = 0;
                eval += count;
                if (eval > bestEval) {
                    bestEval = eval;
                    bestTo = i;
                    bestBi = bi;
                    bestBreakLastShop = breakLastShop;
                }
            }
            VASSERT(bestTo >= 0);
            Put(bestTo, bestBi);
            if (bestBreakLastShop) {
                brokenLastShop = true;
            }
        }
        RemoveUnnecessary();
    }
    void FillRandom() {
        const int lastShop = input_.shops_[orderdSis_.back()];
        bool brokenLastShop = firedCount_[lastShop] > 0;
        while (!breakableTids_.empty()) {
            int bestTo = -1;
            int bestBi = -1;
            bool bestBreakLastShop = false;
            REP(loop, 1000) {
                int ti = rand_(breakableTids_.size());
                int tid = breakableTids_[ti];
                PutPoint pp = ts.ToPP(tid);
                bool breakLastShop = false;
                {
                    breakLastShop = input_.bombs_[pp.bi_].CanBomb(pp.p_, lastShop);
                    if (brokenLastShop && breakLastShop) {
                        continue;
                    }
                }
                VASSERT(GetBreakCount(pp.p_, pp.bi_) > 0);
                bestTo = pp.p_;
                bestBi = pp.bi_;
                bestBreakLastShop = breakLastShop;
                break;
            }
            Put(bestTo, bestBi);
            if (bestBreakLastShop) {
                brokenLastShop = true;
            }
        }
        RemoveUnnecessary();
    }
};
void 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;
        }
    }
}
void CalcShopOrder(NNArr<int>& orderdSis) {
    orderdSis.clear();
    cauto& shops = input_.shops_;
    NNArr<bool> used;
    used.assign(shops.size(), false);
    int p = 0;
    REP(loop, shops.size()) {
        int bestD = INT_MAX;
        int bestI = -1;
        REP(i, shops.size()) {
            if (used[i]) {
                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);
    }
    static NNArr<NNArr<int>> aroundSortedSis;       
    aroundSortedSis.resize(shops.size());
    REP(siA, shops.size()) {
        auto& sis = aroundSortedSis[siA];
        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;
    }
    LocalSearch2opt(aroundSortedSis, orderdSis, order);
}
void MakePlan(PlanState& plan) {
    plan.Init();
    CalcShopOrder(plan.orderdSis_);
    plan.FillGreedy();
}
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 Move(int p, IOResult& result) {
        pint cur = gs.ToPos(p_);
        pint to = gs.ToPos(p);
        int dx = to.x - cur.x;
        int dy = to.y - cur.y;
        Dir dirX = dx > 0 ? Dir::R : Dir::L;
        Dir dirY = dy > 0 ? Dir::D : Dir::U;
        if (dx > 0) {
            dx = 1;
        }
        else if (dx < 0) {
            dx = -1;
        }
        if (dy > 0) {
            dy = 1;
        }
        else if (dy < 0) {
            dy = -1;
        }
        while (cur.x != to.x) {
            cur.x += dx;
            result.push().SetMove(dirX);
            if (grid_[gs.ToId(cur)] == '.') {
                cost_ += square(bombCount_ + 1);
            } else {
                cost_ += 2 * square(bombCount_ + 1);
            }
        }
        while (cur.y != to.y) {
            cur.y += dy;
            result.push().SetMove(dirY);
            if (grid_[gs.ToId(cur)] == '.') {
                cost_ += square(bombCount_ + 1);
            }
            else {
                cost_ += 2 * square(bombCount_ + 1);
            }
        }
        p_ = p;
    }
    void Buy(int bi, IOResult& result) {
        VASSERT(grid_[p_] == '@');
        ++bombCount_;
        ++bombCounts_[bi];
        cost_ += input_.bombs_[bi].cost_;
        result.push().SetBuy(bi);
    }
    void Fire(int bi, IOResult& result) {
        VASSERT(bombCounts_[bi] > 0);
        --bombCount_;
        --bombCounts_[bi];
        WarpFire(p_, bi);
        result.push().SetFire(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 MakeMove(const PlanState& plan, IOResult& result, s64& cost) {
    MoveState state;
    state.Init();
    int targetSii = 0;
    cauto& shops = input_.shops_;
    cauto& orderdSis = plan.orderdSis_;
    auto planTids = plan.tids_;
    while (targetSii < orderdSis.size()) {
        const int targetSi = orderdSis[targetSii];
        const int targetShop = shops[targetSi];
        if (state.grid_[targetShop] == '.') {
            ++targetSii;
            continue;
        }
        NNArr<int> posToSi;
        NNArr<int> posToSiDist;
        NNArr<int> enableTids;      
        NNArr<int> finalTids;   
        posToSi.assign(NN, -1);
        posToSiDist.assign(NN, INT_MAX);
        for (int tid : planTids) {
            PutPoint pp = ts.ToPP(tid);
            if (posToSi[pp.p_] < 0) {
                int bestD = INT_MAX;
                int bestSi = -1;
                FOR(sii, targetSii, orderdSis.size()) {
                    int si = orderdSis[sii];
                    int sp = shops[si];
                    if (state.grid_[sp] == '.') {
                        continue;
                    }
                    int d = gs.CalcL1Dist(pp.p_, sp);
                    if (d < bestD) {
                        bestD = d;
                        bestSi = si;
                    }
                }
                VASSERT(bestSi >= 0);
                posToSi[pp.p_] = bestSi;
                posToSiDist[pp.p_] = bestD;
            }
            if (posToSi[pp.p_] == targetSi) {
                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.size()) {
            for (int tid : enableTids) {
                auto pp = ts.ToPP(tid);
                state.Move(targetShop, result);
                state.Buy(pp.bi_, result);
                state.Move(pp.p_, result);
                state.Fire(pp.bi_, result);
                planTids.Remove(tid);
            }
            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) {
            auto pp = ts.ToPP(tid);
            state.Move(targetShop, result);
            state.Buy(pp.bi_, result);
            state.Move(pp.p_, result);
            state.Fire(pp.bi_, result);
            planTids.Remove(tid);
            break;
        }
        ++targetSii;
    }
    VASSERT(state.IsEnd());
    cost = state.cost_;
}
struct State {
    PlanState plan_;
    s64 rawScore_;
    void Init() {
        plan_.Init();
        MakePlan(plan_);
        IOResult result;
        s64 cost;
        MakeMove(plan_, result, cost);
        rawScore_ = cost;
    }
    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_ = 100;
        sa.endTemp_ = 1;
        sa.stepLoopCount = 10;
        sa.rollbackStartRate_ = 0.1;
        sa.rollbackCount_ = 10000;      
        sa.rollbackNextMulti_ = 1.1;
        sa.minRollbackCount_ = 100;
        auto transitions = make_tuple(
            MAKE_TRANS(Transition_Update1, 10)
        );
        sa.Run2(timer, states, transitions);
        s64 cost = 0;
        IOResult result;
        MakeMove(maxState_.plan_, result, cost);
        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) {
        State backup = state;
        int removeCount = min(1 + rand_(8), 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();
        s64 cost = 0;
        IOResult result;
        MakeMove(state.plan_, result, cost);
        double newEvalScore = (double) - cost;
        if (checker(newEvalScore)) {
            state.rawScore_ = cost;
            CheckMaxScore(state);
        }
        else {
            state = 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();
    }
};
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0