#define NDEBUG

#pragma GCC optimize("O3")
#pragma GCC optimize("-O3,inline,omit-frame-pointer,unroll-loops")
#pragma warning(1:4456)

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

//#define DEBUG_TIME 2

//#define INPUT_FROM_FILE
//#define OUTPUT_TO_FILE
//#define CERR_TO_FILE

#define ALL(a) (a).begin(),(a).end()
#define MEM2LOC(type, name) type name = (this->name);
#define MEM2LOC_V(type, name) type name = ((this->name).data());
#define LOC2MEM(name) (this->name) = (name);

#include <iostream>

#include <array>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <math.h>
#include <fstream>
#include <string>
#include <sstream>
#include <cmath>
#include <memory>
#include <cassert>
#include <functional>
#include <chrono>
#ifdef __linux
#include <sys/resource.h>
#endif

using namespace std;
using namespace chrono;

constexpr int DX4[]={0,-1,0,1};
constexpr int DY4[]={-1,0,1,0};
constexpr int DX8[]={0,-1,-1,-1,0,1,1,1};
constexpr int DY8[]={-1,-1,0,1,1,1,0,-1};

constexpr int DX5[]={DX4[0],DX4[1],DX4[2],DX4[3],0};
constexpr int DY5[]={DY4[0],DY4[1],DY4[2],DY4[3],0};
constexpr int DX9[]={DX8[0],DX8[1],DX8[2],DX8[3],DX8[4],DX8[5],DX8[6],DX8[7],0};
constexpr int DY9[]={DY8[0],DY8[1],DY8[2],DY8[3],DY8[4],DY8[5],DY8[6],DY8[7],0};

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

template<typename Key, typename Value>
using umap = std::unordered_map<Key, Value>;
template<typename T>
using uset = std::unordered_set<T>;
template <typename T>
using sptr = typename std::shared_ptr<T>;

template <class _Iter>
using iter_cat_type = typename std::iterator_traits<_Iter>::iterator_category;
//template <class _Ty, class = void>
//constexpr bool _is_iterator = false;
//template <class _Ty>
//constexpr bool _is_iterator<_Ty, std::void_t<iter_cat_type<_Ty>>> = true;

constexpr int DIST_INF = 99999999;

template<typename T>void fill(vector<T>&a,const T&v){std::fill(ALL(a),v);}
template<typename T>void fill(vector<vector<T>>&a,const T&v){for(vector<T>&t:a)std::fill(ALL(t),v);}
template<typename T>void resize(vector<T>&a,int sz1){a.resize(sz1);}
template<typename T>void resize(vector<T>&a,int sz1,const T&v){a.resize(sz1,v);}
template<typename T>void resize(vector<vector<T>>&a,int sz1,int sz2){a.resize(sz1);for(vector<T>&t:a)t.resize(sz2);}
template<typename T>void resize(vector<vector<T>>&a,int sz1,int sz2,const T&v){a.resize(sz1);for(vector<T>&t:a)t.resize(sz2,v);}
template<typename T>void assign(vector<T>&a,int sz1,const T&v){a.assign(sz1,v);}
template<typename T>void assign(vector<vector<T>>&a,int sz1,int sz2,const T&v){a.resize(sz1);for(vector<T>&t:a)t.assign(sz2,v);}

template<typename T,size_t SZ>void fill(array<T,SZ>&a,const T&v){std::fill(ALL(a),v);}
template<typename T,size_t SZ1,size_t SZ2>void fill(array<array<T,SZ2>,SZ1>&a,const T&v){for(array<T,SZ2>&t:a)std::fill(ALL(t),v);}


// pair出力
template<typename T, typename U>
ostream& operator << (ostream& os, const pair<T, U>& pr) {
	os << "{" << pr.first << "," << pr.second << "}";
	return os;
}
// vector出力
template<typename T>
std::ostream& operator<<(std::ostream& os, vector<T>& a) {
	os << "[";
	for (int i = 0; i < a.size(); i++) {
		if (i != 0) {
			os << ",";
		}
		os << a[i];
	}
	os << "]";
	return os;
}
// array出力
template<typename T, size_t SZ>
ostream& operator<<(ostream& os, const array<T, SZ>& a) {
	os << "[";
	for (int i = 0; i < SZ; i++) {
		if (i != 0) {
			os << ",";
		}
		os << a[i];
	}
	os << "]";
	return os;
}
// map出力
template<typename T,typename U>
ostream& operator<<(ostream& os, const map<T, U>& m) {
	os << "{";
	auto b = m.begin();
	auto e = m.end();
	for (auto p = b; p != e; ++p) {
		if (p != b) {
			os << ",";
		}
		os << p->first << ":" << p->second;
	}
	os << "}";
	return os;
}
// set出力
template<typename T>
ostream& operator << (ostream& os, const set<T>& s) {
	os << "{";
	auto b = s.begin();
	auto e = s.end();
	for (auto p = b; p != e; ++p) {
		if (p != b) {
			os << ",";
		}
		os << *p;
	}
	os << "}";
	return os;
}
// unordered_map出力
template<typename T,typename U>
ostream& operator<<(ostream& os, const unordered_map<T, U>& m) {
	os << "{";
	auto b = m.begin();
	auto e = m.end();
	for (auto p = b; p != e; ++p) {
		if (p != b) {
			os << ",";
		}
		os << p->first << ":" << p->second;
	}
	os << "}";
	return os;
}
// unordered_set出力
template<typename T>
ostream& operator << (ostream& os, const unordered_set<T>& s) {
	os << "{";
	auto b = s.begin();
	auto e = s.end();
	for (auto p = b; p != e; ++p) {
		if (p != b) {
			os << ",";
		}
		os << *p;
	}
	os << "}";
	return os;
}

bool same(double a,double b){return abs(a-b)<1e-5;}
bool same(int a,int b){return a==b;}
ull xor128(){static ull x=123456789,y=362436069,z=521288629,w=88675123;ull t=(x^(x<<11));x=y;y=z;z=w;return w=(w^(w>>19))^(t^(t>>8));}
string strConcat(const vector<int>& strList, const string& separator){stringstream s;for(int i=0;i<(int)strList.size();++i){if(i>0){s<<separator;}s<<strList[i];}return move(s.str());}

#ifdef __linux
void setStackSizeFull(){const rlim_t s=4294967295;struct rlimit l;int r;r=getrlimit(RLIMIT_STACK,&l);if(r==0){if(l.rlim_cur<s){l.rlim_cur=s;r=setrlimit(RLIMIT_STACK,&l);}}}
#endif

ll getTime() {
	auto now = std::chrono::system_clock::now();
	auto now_ms = std::chrono::time_point_cast<std::chrono::milliseconds>(now);
	auto epoch = now_ms.time_since_epoch();
	return epoch.count();
}

template <typename T, size_t CAPACITY>
class ArrayVector {
public:

	ArrayVector() : mSize(0) {}
	ArrayVector(size_t size) : mSize(0) {
		resize(size);
	}
	ArrayVector(size_t size, const T& initVal) : mSize(0) {
		resize(size, initVal);
	}
	ArrayVector(const ArrayVector<T, CAPACITY>& other) { copyInit(other); }
	ArrayVector& operator=(const ArrayVector<T, CAPACITY>& other) { return copyInit(other); }
	ArrayVector(ArrayVector<T, CAPACITY>&& other) { moveInit(std::move(other)); }
	ArrayVector& operator=(ArrayVector<T, CAPACITY>&& other) { return moveInit(std::move(other)); }

private:
	inline ArrayVector& copyInit(const ArrayVector<T, CAPACITY>& other) {
		T* p = begin();
		for (const T* op = other.begin(); op != other.end(); ++p, ++op) {
			*p = *op;
		}
		mSize = other.mSize;
		return *this;
	}
	inline ArrayVector& moveInit(ArrayVector<T, CAPACITY>&& other) {
		T* p = begin();
		for (const T* op = other.begin(); op != other.end(); ++p, ++op) {
			*p = std::move(*op);
		}
		mSize = other.mSize;
		return *this;
	}

public:
	inline void clear() {
		mSize = 0;
	}
	inline void resize(size_t size) {
		assert(size <= CAPACITY);
		mSize = size;
	}
	inline void resize(size_t size, const T& initVal) {
		assert(size <= CAPACITY);
		if (size > mSize) {
			T* e = &mData[size];
			for (T* p = &mData[mSize]; p != e; ++p) {
				*p = initVal;
			}
		}
		mSize = size;
	}
	inline void assign(size_t size, const T& initVal) {
		assert(size <= CAPACITY);
		std::fill_n(mData, size, initVal);
		mSize = size;
	}
	inline void add_size(size_t amount) {
		assert(mSize + amount <= CAPACITY && mSize + amount >= mSize);
		resize(mSize + amount);
	}
	inline void reduce_size(size_t amount) {
		assert(mSize >= amount);
		resize(mSize - amount);
	}
	constexpr size_t size() const noexcept { return mSize; }
	constexpr size_t capacity() const noexcept { return CAPACITY; }
	constexpr bool empty() const noexcept { return !mSize; }
	constexpr bool full() const noexcept { return mSize == CAPACITY; }
	template<typename... _Valty>
	T& emplace_back(_Valty&&... args) {
		assert(mSize != CAPACITY);
		T* target = &mData[mSize++];
		::new(target) T(std::forward<_Valty>(args)...);
		return *target;
	}
	inline void push_back(const T& val) {
		assert(mSize != CAPACITY);
		mData[mSize++] = val;
	}
	inline void push_back(T&& val) {
		assert(mSize != CAPACITY);
		mData[mSize++] = std::move(val);
	}
	inline void pop_back() {
		assert(mSize != 0);
		--mSize;
	}
	T* erase(T* _Where) {
		for (T* p = _Where + 1, *e = end(); p != e; ++p) {
			*(p - 1) = *p;
		}
		--mSize;
		return end();
	}
	T* erase(T* _First, T* _Last) {
		auto dist = _Last - _First;
		for (T* p = _Last, *e = end(); p != e; ++p) {
			*(p - dist) = *p;
		}
		mSize -= dist;
		return end();
	}
	inline T& operator[](size_t index) {
		assert(index < mSize);
		return mData[index];
	}
	constexpr const T& operator[](size_t index) const {
		assert(index < mSize);
		return mData[index];
	}
	inline T& at(size_t index) {
		if (index >= mSize) {
			throw out_of_range("ArrayVector: out of range.");
		}
		return mData[index];
	}
	constexpr const T& at(size_t index) const {
		if (index >= mSize) {
			throw out_of_range("ArrayVector: out of range.");
		}
		return mData[index];
	}
	inline T& front() {
		assert(mSize != 0);
		return mData[0];
	}
	constexpr const T& front() const {
		assert(mSize != 0);
		return mData[0];
	}
	inline T& back() {
		assert(mSize != 0);
		return mData[mSize - 1];
	}
	constexpr const T& back() const {
		assert(mSize != 0);
		return mData[mSize - 1];
	}
	inline T* data() noexcept { return mData; }
	constexpr const T* data() const noexcept { return mData; }
	inline T* begin() noexcept { return mData; }
	constexpr const T* begin() const noexcept { return mData; }
	inline T* end() noexcept { return &mData[mSize]; }
	constexpr const T* end() const noexcept { return &mData[mSize]; }
	template <typename... _Valty>
	inline T* emplace(const T* _Where, _Valty&&... args) {
		assert(mSize != CAPACITY);
		assert(_Where >= begin());
		assert(_Where <= end());
		++mSize;
		for (T* p = end() - 1; p != _Where; --p) {
			*p = *(p - 1);
		}
		::new(_Where) T(std::forward<_Valty>(args)...);
		return _Where;
	}
	inline T* insert(T* _Where, const T& _Val) {
		assert(mSize != CAPACITY);
		assert(_Where >= begin());
		assert(_Where <= end());
		++mSize;
		for (T* p = end() - 1; p != _Where; --p) {
			*p = *(p - 1);
		}
		*_Where = _Val;
		return _Where;
	}
	inline T* insert(T* _Where, T&& _Val) {
		assert(mSize != CAPACITY);
		assert(_Where >= begin());
		assert(_Where <= end());
		++mSize;
		for (T* p = end() - 1; p != _Where; --p) {
			*p = *(p - 1);
		}
		*_Where = std::move(_Val);
		return _Where;
	}
	inline T* insert(T* _Where, const size_t _Count, const T& _Val) {
		assert(mSize + _Count <= CAPACITY && mSize + _Count >= mSize);
		assert(_Where >= begin());
		assert(_Where <= end());
		mSize += _Count;
		for (T* p = end() - 1, *e = _Where + _Count - 1; p != e; --p) {
			*p = *(p - _Count);
		}
		for (T* p = _Where, *e = _Where + _Count; p != e; ++p) {
			*p = _Val;
		}
		return _Where;
	}

private:
	size_t mSize;
	T mData[CAPACITY];
};

template<typename T, size_t CAPACITY>
ostream& operator<<(ostream& os, ArrayVector<T, CAPACITY>& a) {
	os << "[";
	for (int i = 0; i < a.size(); i++) {
		if (i != 0) {
			os << ",";
		}
		os << a[i];
	}
	os << "]";
	return os;
}

template<typename T,size_t SZ>void fill(ArrayVector<T,SZ>&a,const T&v){std::fill(ALL(a),v);}
template<typename T,size_t SZ1,size_t SZ2>void fill(ArrayVector<ArrayVector<T,SZ2>,SZ1>&a,const T&v){for(ArrayVector<T,SZ2>&t:a)std::fill(ALL(t),v);}
template<typename T,size_t SZ>void resize(ArrayVector<T,SZ>&a,int sz1){a.resize(sz1);}
template<typename T,size_t SZ>void resize(ArrayVector<T,SZ>&a,int sz1,const T&v){a.resize(sz1,v);}
template<typename T,size_t SZ1,size_t SZ2>void resize(ArrayVector<ArrayVector<T,SZ2>,SZ1>&a,int sz1,int sz2){a.resize(sz1);for(ArrayVector<T,SZ2>&t:a)t.resize(sz2);}
template<typename T,size_t SZ1,size_t SZ2>void resize(ArrayVector<ArrayVector<T,SZ2>,SZ1>&a,int sz1,int sz2,const T&v){a.resize(sz1);for(ArrayVector<T,SZ2>&t:a)t.resize(sz2,v);}
template<typename T,size_t SZ>void assign(ArrayVector<T,SZ>&a,int sz1,const T&v){a.assign(sz1,v);}
template<typename T,size_t SZ1,size_t SZ2>void assign(ArrayVector<ArrayVector<T,SZ2>,SZ1>&a,int sz1,int sz2,const T&v){a.resize(sz1);for(ArrayVector<T,SZ2>&t:a)t.assign(sz2,v);}

//template<typename T,size_t CAPACITY>class ArrayVector{public:ArrayVector():mSize(0){}ArrayVector(size_t size){resize(size);}ArrayVector(size_t size,const T&initVal){resize(size,initVal);}ArrayVector(const ArrayVector<T,CAPACITY>&other){
//copyInit(other);}ArrayVector&operator=(const ArrayVector<T,CAPACITY>&other){return copyInit(other);}ArrayVector(ArrayVector<T,CAPACITY>&&other){moveInit(std::move(other));}ArrayVector&operator=(ArrayVector<T,CAPACITY>&&other){return moveInit(
//std::move(other));}private:inline ArrayVector&copyInit(const ArrayVector<T,CAPACITY>&a){T*p=begin();for(const T*q=a.begin();q!=a.end();++p,++q){*p=*q;}mSize=a.mSize;return*this;}inline ArrayVector&moveInit(ArrayVector<T,CAPACITY>&&a){T*p=
//begin();for(const T*q=a.begin();q!=a.end();++p,++q){*p=std::move(*q);}mSize=a.mSize;return*this;}public:inline void clear(){mSize=0;}inline void resize(size_t size){assert(size<=CAPACITY);mSize=size;}inline void resize(size_t size,const T&
//initVal){assert(size<=CAPACITY);if(size>mSize){T*e=&mData[size];for(T*p=&mData[mSize];p!=e;++p){*p=initVal;}}mSize=size;}inline void assign(size_t size,const T&initVal){assert(size<=CAPACITY);std::fill_n(mData,size,initVal);mSize=size;}inline
//void add_size(size_t amount){assert(mSize+amount<=CAPACITY&&mSize+amount>=mSize);resize(mSize+amount);}inline void reduce_size(size_t amount){assert(mSize>=amount);resize(mSize-amount);}constexpr size_t size()const noexcept{return mSize;}
//constexpr size_t capacity()const noexcept{return CAPACITY;}constexpr bool empty()const noexcept{return!mSize;}constexpr bool full()const noexcept{return mSize==CAPACITY;}template<typename..._Valty>T&emplace_back(_Valty&&...args){assert(mSize!=
//CAPACITY);T*t=&mData[mSize++];::new(t) T(std::forward<_Valty>(args)...);return*t;}inline void push_back(const T&val){assert(mSize!=CAPACITY);mData[mSize++]=val;}inline void push_back(T&&val){assert(mSize!=CAPACITY);mData[mSize++]=std::move(val
//);}inline void pop_back(){assert(mSize!=0);--mSize;}T*erase(T*_Where){for(T*p=_Where+1,*e=end();p!=e;++p){*(p-1)=*p;}--mSize;return end();}T*erase(T*_First,T*_Last){auto d=_Last-_First;for(T*p=_Last,*e=end();p!=e;++p){*(p-d)=*p;}mSize-=d;
//return end();}inline T&operator[](size_t index){assert(index<mSize);return mData[index];}constexpr const T&operator[](size_t index)const{assert(index<mSize);return mData[index];}inline T&at(size_t index){if(index>=mSize){throw out_of_range(
//"ArrayVector: out of range.");}return mData[index];}constexpr const T&at(size_t index)const{if(index>=mSize){throw out_of_range("ArrayVector: out of range.");}return mData[index];}inline T&front(){assert(mSize!=0);return mData[0];}constexpr
//const T&front()const{assert(mSize!=0);return mData[0];}inline T&back(){assert(mSize!=0);return mData[mSize-1];}constexpr const T&back()const{assert(mSize!=0);return mData[mSize-1];}inline T*data() noexcept{return mData;}constexpr const T*data()
//const noexcept{return mData;}inline T*begin() noexcept{return mData;}constexpr const T*begin()const noexcept{return mData;}inline T*end() noexcept{return&mData[mSize];}constexpr const T*end()const noexcept{return&mData[mSize];}template<
//typename..._Valty>inline T*emplace(const T*_Where,_Valty&&...args){assert(mSize!=CAPACITY);assert(_Where>=begin());assert(_Where<=end());++mSize;for(T*p=end()-1;p!=_Where;--p){*p=*(p-1);}::new(_Where) T(std::forward<_Valty>(args)...);return
//_Where;}inline T*insert(T*_Where,const T&_Val){assert(mSize!=CAPACITY);assert(_Where>=begin());assert(_Where<=end());++mSize;for(T*p=end()-1;p!=_Where;--p){*p=*(p-1);}*_Where=_Val;return _Where;}inline T*insert(T*_Where,T&&_Val){
//assert(mSize!=CAPACITY);assert(_Where>=begin());assert(_Where<=end());++mSize;for(T*p=end()-1;p!=_Where;--p){*p=*(p-1);}*_Where=std::move(_Val);return _Where;}inline T*insert(T*_Where,const size_t _Count,const T&_Val){assert(mSize+
//_Count<=CAPACITY&&mSize+_Count>=mSize);assert(_Where>=begin());assert(_Where<=end());mSize+=_Count;for(T*p=end()-1,*e=_Where+_Count-1;p!=e;--p){*p=*(p-_Count);}for(T*p=_Where,*e=_Where+_Count;p!=e;++p){*p=_Val;}return _Where;}private:size_t
//mSize;T mData[CAPACITY];};

template<typename _Ty,size_t CAPACITY>class ArrayQueue{public:ArrayQueue():mLeft(mData),mRight(mData),mSize(0){}ArrayQueue(const ArrayQueue&other){copyInit(other);}ArrayQueue&operator=(const ArrayQueue&other){return copyInit(other);}ArrayQueue
(ArrayQueue&&other){moveInit(std::move(other));}ArrayQueue&operator=(ArrayQueue&&other){return moveInit(std::move(other));}private:inline ArrayQueue&copyInit(const ArrayQueue&a){mLeft=mData;_Ty*p=mLeft;const _Ty*q=a.mLeft;size_t c=a.mSize;const
_Ty*b=a.mData+CAPACITY-1;for(;c;++p,((q==b)?q=mLeft:++q),--c){*p=*q;}mRight=(p==mData+CAPACITY)?mLeft:p;mSize=a.mSize;return*this;}inline ArrayQueue&moveInit(ArrayQueue&&a){mLeft=mData;_Ty*p=mLeft;const _Ty*q=a.mLeft;size_t c=a.mSize;const _Ty
*b=a.mData+CAPACITY-1;for(;c;++p,((q==b)?q=mLeft:++q),--c){*p=std::move(*q);}mRight=(p==mData+CAPACITY)?mLeft:p;mSize=a.mSize;return*this;}public:template<typename..._Valty>void emplace(_Valty&&...args){assert(mSize!=CAPACITY);::new(mRight)_Ty
(std::forward<_Valty>(args)...);if(++mRight==mData+CAPACITY){mRight=mData;}++mSize;}void push(const _Ty&_Val){assert(mSize!=CAPACITY);*mRight=_Val;if(++mRight==mData+CAPACITY){mRight=mData;}++mSize;}void pop(){assert(!this->empty());if(++mLeft
==mData+CAPACITY){mLeft=mData;}--mSize;}const _Ty&front()const{assert(!this->empty());return*mLeft;}const _Ty&back()const{assert(!this->empty());return(mRight==mData)?mData[CAPACITY-1]:*(mRight-1);}size_t capacity()const{return CAPACITY;}
size_t size()const{return mSize;}bool empty()const{return mSize==0;}void clear(){mLeft=mData;mRight=mData;mSize=0;}private:_Ty*mLeft;_Ty*mRight;_Ty mData[CAPACITY];
size_t mSize;};template <typename _Ty,size_t CAPACITY>using aqueue=ArrayQueue<_Ty,CAPACITY>;

constexpr int APQ_SMALL_THRESH=170;template <typename _Ty,int MAX_SIZE,class _Pr=less<_Ty>,bool SMALL=(sizeof(_Ty)<APQ_SMALL_THRESH)>class ArrayPriorityQueue{public:ArrayPriorityQueue():mSize(0){}ArrayPriorityQueue(const ArrayPriorityQueue&
other){copyInit(other);}ArrayPriorityQueue&operator=(const ArrayPriorityQueue&other){return copyInit(other);}ArrayPriorityQueue(ArrayPriorityQueue&&other){moveInit(std::move(other));}ArrayPriorityQueue&operator=(ArrayPriorityQueue&&other){
return moveInit(std::move(other));}private:inline ArrayPriorityQueue&copyInit(const ArrayPriorityQueue&other){_Ty*p=mHeap;const _Ty*q=other.mHeap;for(const _Ty*e=q+other.mSize;q!=e;++p,++q){*p=*q;}mSize=other.mSize;return*this;}inline
ArrayPriorityQueue&moveInit(ArrayPriorityQueue&&other){_Ty*p=mHeap;const _Ty*q=other.mHeap;for(const _Ty*e=q+other.mSize;q!=e;++p,++q){*p=std::move(*q);}mSize=other.mSize;return*this;}public:template<typename..._Valty>void emplace(_Valty&&...
args){assert(mSize!=MAX_SIZE);MEM2LOC(size_t,mSize);MEM2LOC(_Pr,mCompare);MEM2LOC(_Ty*,mHeap);_Ty o(std::forward<_Valty>(args)...);size_t i=mSize;size_t m=(i-1)>>1;while(i&&mCompare(mHeap[m],o)){mHeap[i]=mHeap[m];i=m;m=(i-1)>>1;}mHeap[i]=o;++
mSize;LOC2MEM(mSize);}void push(const _Ty&val){assert(mSize!=MAX_SIZE);MEM2LOC(size_t,mSize);MEM2LOC(_Pr,mCompare);MEM2LOC(_Ty*,mHeap);size_t i=mSize;size_t m=(i-1)>>1;while(i&&mCompare(mHeap[m],val)){mHeap[i]=mHeap[m];i=m;m=(i-1)>>1;}mHeap[i]=
val;++mSize;LOC2MEM(mSize);}void pop(){assert(!this->empty());MEM2LOC(size_t,mSize);MEM2LOC(_Pr,mCompare);MEM2LOC(_Ty*,mHeap);--mSize;if(1<mSize){size_t i=0;size_t l=1;size_t g=(l==mSize-1||mCompare(mHeap[l+1],mHeap[l]))?l:l+1;while(mCompare(
mHeap[mSize],mHeap[g])){mHeap[i]=mHeap[g];i=g;l=(i<<1)+1;if(l>=mSize)break;g=(l==mSize-1||mCompare(mHeap[l+1],mHeap[l]))?l:l+1;}mHeap[i]=mHeap[mSize];}else if(mSize==1){mHeap[0]=mHeap[1];}LOC2MEM(mSize);}const _Ty&top()const{assert(!this->
empty());return mHeap[0];}int capacity()const{return MAX_SIZE;}size_t size()const{return mSize;}bool empty()const{return!mSize;}void clear(){mSize=0;}_Ty*_unsafe_add_size(){assert(mSize!=MAX_SIZE);++mSize;return&mHeap[mSize-1];}_Ty*_unsafe_put(
const _Ty&val){assert(mSize!=MAX_SIZE);mHeap[mSize++]=val;return&mHeap[mSize-1];}template<typename..._Valty>_Ty*_unsafe_emplace_put(_Valty&&...args){assert(mSize!=MAX_SIZE);::new(&mHeap[mSize++])_Ty(std::forward<_Valty>(args)...);return&mHeap[
mSize-1];}void _unsafe_insert(_Ty*p=nullptr){assert(!this->empty());MEM2LOC(_Pr,mCompare);MEM2LOC(_Ty*,mHeap);_Ty v=mHeap[mSize-1];size_t i=mSize-1;size_t m=(i-1)>>1;while(i&&mCompare(mHeap[m],v)){mHeap[i]=mHeap[m];i=m;m=(i-1)>>1;}mHeap[i]=v;}
private:size_t mSize;_Ty mHeap[MAX_SIZE];_Pr mCompare;};

template<typename _Ty,int MAX_SIZE,class _Pr>class ArrayPriorityQueue<_Ty,MAX_SIZE,_Pr,false>{public:ArrayPriorityQueue():mSize(0),mBlankListSize(0){}ArrayPriorityQueue(const ArrayPriorityQueue&other){copyInit(other);}ArrayPriorityQueue&
operator=(const ArrayPriorityQueue&other){return copyInit(other);}ArrayPriorityQueue(ArrayPriorityQueue&&other){moveInit(std::move(other));}ArrayPriorityQueue&operator=(ArrayPriorityQueue&&other){return moveInit(std::move(other));}private:
inline ArrayPriorityQueue&copyInit(const ArrayPriorityQueue&a){_Ty*p=mHeap;size_t*r=mHeapRef;const size_t*s=a.mHeapRef;const _Ty*h=a.mHeap;size_t c=0;for(const size_t*e=s+a.mSize;s!=e;++p,++r,++s){*p=h[*s];*r=c++;}mSize=a.mSize;mBlankListSize=0
;return*this;}inline ArrayPriorityQueue&moveInit(ArrayPriorityQueue&&a){_Ty*p=mHeap;size_t*r=mHeapRef;const size_t*s=a.mHeapRef;const _Ty*h=a.mHeap;size_t c=0;for(const size_t*e=s+a.mSize;s!=e;++p,++r,++s){*p=std::move(h[*s]);*r=c++;}mSize=a.
mSize;mBlankListSize=0;return*this;}public:template<typename..._Valty>void emplace(_Valty&&...args){assert(mSize!=MAX_SIZE);MEM2LOC(size_t,mSize);MEM2LOC(_Pr,mCompare);MEM2LOC(_Ty*,mHeap);MEM2LOC(size_t*,mHeapRef);size_t h;if(mBlankListSize!=0)
{h=mBlankList[mBlankListSize-1];--mBlankListSize;}else{h=mSize;}::new(&mHeap[h])_Ty(std::forward<_Valty>(args)...);size_t i=mSize;size_t m=(i-1)>>1;while(i&&mCompare(mHeap[mHeapRef[m]],mHeap[h])){mHeapRef[i]=mHeapRef[m];i=m;m=(i-1)>>1;}mHeapRef
[i]=h;++mSize;LOC2MEM(mSize);}void push(const _Ty&val){assert(mSize!=MAX_SIZE);MEM2LOC(size_t,mSize);MEM2LOC(_Pr,mCompare);MEM2LOC(_Ty*,mHeap);MEM2LOC(size_t*,mHeapRef);size_t h;if(mBlankListSize!=0){h=mBlankList[mBlankListSize-1];--
mBlankListSize;}else{h=mSize;}mHeap[h]=val;size_t i=mSize;size_t m=(i-1)>>1;while(i&&mCompare(mHeap[mHeapRef[m]],val)){mHeapRef[i]=mHeapRef[m];i=m;m=(i-1)>>1;}mHeapRef[i]=h;++mSize;LOC2MEM(mSize);}void pop(){assert(!this->empty());MEM2LOC(
size_t,mSize);MEM2LOC(_Pr,mCompare);MEM2LOC(_Ty*,mHeap);MEM2LOC(size_t*,mHeapRef);mBlankList[mBlankListSize++]=mHeapRef[0];--mSize;if(1<mSize){size_t i=0;size_t l=1;size_t g=(l==mSize-1||mCompare(mHeap[mHeapRef[l+1]],mHeap[mHeapRef[l]]))?l:l+1;
while(mCompare(mHeap[mHeapRef[mSize]],mHeap[mHeapRef[g]])){mHeapRef[i]=mHeapRef[g];i=g;l=(i<<1)+1;if(l>=mSize)break;g=(l==mSize-1||mCompare(mHeap[mHeapRef[l+1]],mHeap[mHeapRef[l]]))?l:l+1;}mHeapRef[i]=mHeapRef[mSize];}else if(mSize==1){
mHeapRef[0]=mHeapRef[1];}LOC2MEM(mSize);}const _Ty&top()const{assert(!this->empty());return mHeap[mHeapRef[0]];}int capacity()const{return MAX_SIZE;}size_t size()const{return mSize;}bool empty()const{return!mSize;}void clear(){mSize=0;
mBlankListSize=0;}_Ty*_unsafe_add_size(){assert(mSize!=MAX_SIZE);size_t h;if(mBlankListSize!=0){h=mBlankList[mBlankListSize-1];--mBlankListSize;}else{h=mSize;}mHeapRef[mSize]=h;++mSize;return&mHeap[h];}_Ty*_unsafe_put(const _Ty&val){assert(
mSize!=MAX_SIZE);_Ty*p=_unsafe_add_size();*p=val;return p;}template<typename..._Valty>_Ty*_unsafe_emplace_put(_Valty&&...args){assert(mSize!=MAX_SIZE);_Ty*p=_unsafe_add_size();::new(p)_Ty(std::forward<_Valty>(args)...);return p;}void
_unsafe_insert(_Ty*p){assert(!this->empty());MEM2LOC(size_t,mSize);MEM2LOC(_Pr,mCompare);MEM2LOC(_Ty*,mHeap);MEM2LOC(size_t*,mHeapRef);size_t h=mHeapRef[mSize-1];size_t i=mSize-1;size_t m=(i-1)>>1;while(i&&mCompare(mHeap[mHeapRef[m]],*p)){
mHeapRef[i]=mHeapRef[m];i=m;m=(i-1)>>1;}mHeapRef[i]=h;}private:size_t mSize;_Ty mHeap[MAX_SIZE];size_t mHeapRef[MAX_SIZE];_Pr mCompare;size_t mBlankList[MAX_SIZE];size_t mBlankListSize;};
template<typename _Ty,int MAX_SIZE,class _Pr=less<_Ty>,bool SMALL=(sizeof(_Ty)<APQ_SMALL_THRESH)>using apq=ArrayPriorityQueue<_Ty,MAX_SIZE,_Pr,SMALL>;


constexpr int MAX_N = 400;
constexpr int MAX_E = 2 * MAX_N;
constexpr int T = 10000;

int N = -1;
int E = -1;

array<ArrayVector<int, MAX_N>, MAX_N> EDGES;
array<array<int, MAX_N>, MAX_N> DISTS;
array<int, T> ORDER;
array<int, MAX_N> gCompletedOrder;
array<int, MAX_N> gLatestOrder;

array<array<int, MAX_N>, MAX_N> CALC_DISTS;
array<array<ArrayVector<int, MAX_N>, MAX_N>, MAX_N> CALC_PATH;

constexpr int MAX_DELIVER = 16;
int gEvalNum = 0;

int gTurn = 0;
array<int, T> gResult;

void init() {
	fill(DISTS, DIST_INF);
	for (int i = 0; i < MAX_N; ++i) {
		DISTS[i][i] = 0;
	}

	fill(ORDER, -1);
	fill(gCompletedOrder, -1);
	fill(gLatestOrder, -1);
}

void input() {
	cin >> N >> E; cin.ignore();
	for (int i = 0; i < E; ++i) {
		int u, v, d;
		cin >> u >> v >> d; cin.ignore();
		--u;
		--v;
		EDGES[u].push_back(v);
		EDGES[v].push_back(u);
		DISTS[u][v] = d;
		DISTS[v][u] = d;
	}
	int t;
	cin >> t; cin.ignore();
	for (int i = 0; i < T; ++i) {
		int n;
		cin >> n; cin.ignore();
		if (n > 0) {
			int id;
			cin >> id >> ORDER[i]; cin.ignore();
			--ORDER[i];
		}
	}
}

void calcDists() {
	array<array<int, MAX_N>, MAX_N> next;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			next[i][j] = j;
			CALC_PATH[i][j].clear();
			CALC_DISTS[i][j] = DISTS[i][j];
		}
	}

	for (int k = 0; k < N; ++k) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (CALC_DISTS[i][j] > CALC_DISTS[i][k] + CALC_DISTS[k][j]) {
					CALC_DISTS[i][j] = CALC_DISTS[i][k] + CALC_DISTS[k][j];
					next[i][j] = next[i][k];
				}
			}
		}
	}
	for (int start = 0; start < N; ++start) {
		for (int goal = 0; goal < N; ++goal) {
			for (int cur = start; cur != goal; cur = next[cur][goal]) {
				CALC_PATH[start][goal].push_back(cur);
			}
			CALC_PATH[start][goal].push_back(goal);
		}
	}
}

#define State ArrayVector<int, MAX_DELIVER>

ll simulate(const State& state) {
	ll score = 0;
	int now = 0;
	int turn = gTurn;
	for (int i = 0; i < (int)state.size(); ++i) {
		turn += CALC_DISTS[now][ORDER[state[i]]];
		int watingTurn = turn - state[i];
		score -= ((ll)watingTurn * watingTurn);
		now = ORDER[state[i]];
	}
	// TODO:戻ってくる評価
	//dist += CALC_DISTS[now][0];
	return score;
}

State doSA(const State initState, const ll msec) {

	const ll m_startTime = getTime(); // 開始時刻

	State curState = initState;
	State bestState = initState;        // ベストの状態
	ll bestScore = simulate(initState);      // ベストスコア。getScoreは、状態からスコアを求める関数
	ll currentScore = bestScore;    // 現在のスコア

	const ll saTimeStart = getTime();            // 焼きなまし開始時刻。getTimeは、時間を返す関数
	const ll saTimeEnd = m_startTime + msec;     // 焼きなまし終了時刻。m_startTimeはこのプログラム自体の開始時間
	ll saTimeCurrent = saTimeStart;          // 現在の時刻

#if DEBUG_TIME == 2
	while ((saTimeCurrent = getTime()) || true)
#else
	while ((saTimeCurrent = getTime()) < saTimeEnd/* || gDebug*/) // 焼きなまし終了時刻までループ
#endif
	{
		// 次の状態
		int index1 = xor128() % (int)curState.size();
		int index2 = xor128() % ((int)curState.size() - 1);
		if (index2 == index1) {
			index2 = (int)curState.size() - 1;
		}
		if (index1 > index2) {
			std::swap(index1, index2);
		}
		std::reverse(curState.begin() + index1, curState.begin() + index2 + 1);
		const ll nextScore = simulate(curState);

		// 最初t=0のときは、スコアが良くなろうが悪くなろうが、常にnextを使用
		// 最後t=Tのときは、スコアが改善したときのみ、nextを使用
		const ll T = saTimeEnd - saTimeStart;         // 焼きなましにかける時間
		const ll t = saTimeCurrent - saTimeStart;     // 焼きなまし法開始からの時間
		const ll R = 10000;
		// スコアが悪くなったときでも、次の状態に移動する遷移する場合はtrue。１次関数を使用。
		//const bool FORCE_NEXT = R * (T - t) > T*(ll)(xor128() % R);

		double startTemp = 3.0;
		double endTemp = 0.01;
		double temp = startTemp + (endTemp - startTemp) * t / T;
		double probability = exp((nextScore - currentScore) / temp);  // 最大化なので、分子はnextScore - currentScoreで良い。
		bool FORCE_NEXT = probability > (double)(xor128() % R) / R;


		// スコアが良くなった or 悪くなっても強制遷移
		if (nextScore >= currentScore || FORCE_NEXT)
		{
			currentScore = nextScore;
			//fprintf(stderr, "current Score=%.8f time=%lld\n", currentScore, t);
		} else {
			std::reverse(curState.begin() + index1, curState.begin() + index2 + 1);
		}

		// ベストスコアは保存しておく。
		if (currentScore > bestScore)
		{
			bestScore = currentScore;
#ifndef NDEBUG
			fprintf(stderr, "New best Score=%lld time=%lld\n", bestScore, t);
#endif
			bestState = curState;
		}

		gEvalNum++;
	}

#ifndef NDEBUG
	cerr << "EvalNum:" << gEvalNum << endl;
#endif

	return bestState;
}

int dp[1<<MAX_DELIVER][MAX_DELIVER];
int gVSize = -1;
ArrayVector<int, MAX_DELIVER> gTempOrders;

int rec(int S, int v) {
	if (dp[S][v] >= 0) {
		return dp[S][v];
	}
	if (S == (1<<gVSize)-1 && v==0) {
		return dp[S][v] = 0;
	}
	int tmp = DIST_INF;
	for (int u = 0; u < gVSize; ++u) {
		if (!((S>>u) & 1)) {
			tmp = min(tmp, rec(S|(1<<u),u) + CALC_DISTS[gTempOrders[v]][gTempOrders[u]]);
		}
	}
	return dp[S][v] = tmp;
}

int deliver(const State& orders) {
	State result;
	if (orders.size() >= 2) {
		result = doSA(orders, 100);
	} else {
		result = State(1, orders[0]);
	}
	int currentTurn = gTurn;
	int nextTurn = currentTurn;
	int now = 0;
	for (int t : result) {
		for (int v : CALC_PATH[now][ORDER[t]]) {
			if (v == now) {
				continue;
			}
			assert(DISTS[now][v] > 0);
			assert(DISTS[now][v] < DIST_INF);
			nextTurn += DISTS[now][v];
			if (nextTurn >= T) {
				nextTurn = T;
			}
			for (int turn = currentTurn; turn < nextTurn; ++turn) {
				gResult[turn] = v;
			}
			gCompletedOrder[v] = gLatestOrder[v];
			currentTurn = nextTurn;
			if (currentTurn >= T) {
				return T;
			}
			now = v;
		}
	}
	for (int v : CALC_PATH[now][0]) {
		if (v == now) {
			continue;
		}
		assert(DISTS[now][v] > 0);
		assert(DISTS[now][v] < DIST_INF);
		nextTurn += DISTS[now][v];
		if (nextTurn >= T) {
			nextTurn = T;
		}
		for (int turn = currentTurn; turn < nextTurn; ++turn) {
			gResult[turn] = v;
		}
		gCompletedOrder[v] = gLatestOrder[v];
		currentTurn = nextTurn;
		if (currentTurn >= T) {
			return T;
		}
		now = v;
	}

	return currentTurn;

	//gTempOrders = orders;
	//fill((int *)dp, (int *)(dp+(1<<MAXN)), -1);
	//gVSize = orders.size();
	//rec(0,0);
}

template <int SZ>
int processOrders(aqueue<int, SZ>& orderQueue, bool doAll) {
	if (orderQueue.size() >= (doAll ? 1 : MAX_DELIVER)) {
		State orders;
		int num = min((int)orderQueue.size(), MAX_DELIVER);
		int count = 0;
		for (int i = 0; i < num; ++i) {
			int order = orderQueue.front();
			orderQueue.pop();
			orders.push_back(order);
		}
		int nextTurn = deliver(orders);
		aqueue<int, SZ> newQueue;
		while (!orderQueue.empty()) {
			int orderTurn = orderQueue.front();
			orderQueue.pop();
			if (orderTurn > gCompletedOrder[ORDER[orderTurn]]) {
				newQueue.push(orderTurn);
			}
		}
		orderQueue = newQueue;
		return nextTurn;
	}
	return gTurn;
}

void printAnswer() {
	for (int i = 0; i < T; ++i) {
		cout << (gResult[i] == -1 ? -1 : (gResult[i] + 1)) << endl;
	}
}

void solve() {
	fill(gResult, -1);
	int nextTurn = 0;
	aqueue<int, T> orderQueue;
	for (gTurn = 0; gTurn < T; ++gTurn) {
		if (ORDER[gTurn] == -1) {
			continue;
		}
		orderQueue.push(gTurn);
		gLatestOrder[ORDER[gTurn]] = gTurn;
		if (gTurn >= nextTurn) {
			nextTurn = processOrders<T>(orderQueue, false);
		}
	}
	processOrders<T>(orderQueue, true);
}

int main() {
	std::ios::sync_with_stdio(false);

#ifdef __linux
	//setStackSize();
#endif

#ifdef INPUT_FROM_FILE
	ifstream ifs("input/input00.txt");
	cin.rdbuf(ifs.rdbuf());
#endif
#ifdef OUTPUT_TO_FILE
	ofstream ofs("output/output00.txt");
	cout.rdbuf(ofs.rdbuf());
#endif
#ifdef CERR_TO_FILE
	ofstream ofserr("debug.txt");
	cerr.rdbuf(ofserr.rdbuf());
#endif

	init();
	input();
	calcDists();
	solve();
	printAnswer();

	return 0;
}


Measured memory_bytes: 254208