//#define NDEBUG

#pragma GCC optimize ("O3") // 最適化レベルの変更 O0〜O3 などを指定
#pragma GCC optimize("-O3,inline,omit-frame-pointer,unroll-loops")
#pragma warning(1:4456) // 多重forループ内での変数の２重定義を警告にする

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#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 <string>
#include <sstream>
#include <fstream>
#include <cmath>
#include <bitset>

#include <memory>
#include <cassert>

#include <functional>
#include <chrono>

using namespace std;

namespace ValLib {

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

	constexpr ull V_MOD = 1000000007ull;
	constexpr int V_INT_MAX = 2147483647;
	constexpr ll V_LL_MAX = 9223372036854775807ll;
	constexpr ull V_ULL_MAX = 18446744073709551615ull;

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

	template<typename T>void fill(vector<T>&vec,const T&value){std::fill(vec.begin(),vec.end(),value);}
	template<typename T>void fill(vector<vector<T>>&vec,const T&value){for(vector<T>&t:vec)std::fill(t.begin(),t.end(),value);}
	template<typename T>void resize(vector<T>&vec,int size1){vec.resize(size1);}
	template<typename T>void resize(vector<T>&vec,int size1,const T& value){vec.resize(size1,value);}
	template<typename T>void resize(vector<vector<T>>&vec,int size1,int size2){vec.resize(size1);for(vector<T>&t:vec)t.resize(size2);}
	template<typename T>void resize(vector<vector<T>>&vec,int size1,int size2,const T& value){vec.resize(size1);for(vector<T>&t:vec)t.resize(size2,value);}
	template<typename T>void assign(vector<T>&vec,int size1,const T& value){vec.assign(size1,value);}
	template<typename T>void assign(vector<vector<T>>&vec,int size1,int size2,const T& value){vec.resize(size1);for(vector<T>&t:vec)t.assign(size2,value);}
	template<typename T>const typename vector<T>::const_iterator max_element(const vector<T>&vec){assert(!vec.empty());return std::max_element(vec.begin(),vec.end());}
	template<typename T,typename _Pr>const typename vector<T>::const_iterator max_element(const vector<T>&vec,_Pr lessThan){assert(!vec.empty());return std::max_element(vec.begin(),vec.end(),lessThan);}
	template<typename T>typename vector<T>::iterator min_element(vector<T>&vec){assert(!vec.empty());return std::min_element(vec.begin(),vec.end());}
	template<typename T>const typename vector<T>::const_iterator min_element(const vector<T>&vec){assert(!vec.empty());return std::min_element(vec.begin(),vec.end());}
	template<typename T,typename _Pr>const typename vector<T>::const_iterator min_element(const vector<T>&vec,_Pr lessThan){assert(!vec.empty());return std::min_element(vec.begin(),vec.end(),lessThan);}
	int accumulate(const vector<int>&vec){return std::accumulate(vec.begin(),vec.end(),0);}
	template<typename _Pr>int accumulate(const vector<int>&vec,_Pr func){return std::accumulate(vec.begin(),vec.end(),0,func);}
	double accumulate(const vector<double>&vec){return std::accumulate(vec.begin(),vec.end(),0.0);}
	template<typename _Pr>double accumulate(const vector<double>&vec,_Pr func){return std::accumulate(vec.begin(),vec.end(),0.0,func);}
	float accumulate(const vector<float>&vec){return std::accumulate(vec.begin(),vec.end(),0.f);}
	template<typename _Pr>float accumulate(const vector<float>&vec,_Pr func){return std::accumulate(vec.begin(),vec.end(),0.f,func);}
	template<typename T,typename _Pr>bool all_of(const vector<T>&vec,_Pr pred){return std::all_of(vec.begin(),vec.end(),pred);	}
	template<typename T,typename _Pr>bool any_of(const vector<T>&vec,_Pr pred){return std::any_of(vec.begin(),vec.end(),pred);}
	template<typename T,typename _Pr>bool none_of(const vector<T>&vec,_Pr pred){return std::none_of(vec.begin(),vec.end(),pred);}
	template<typename T>const typename vector<T>::const_iterator find(const vector<T>&vec,const T& val){return std::find(vec.begin(),vec.end(),val);}
	template<typename T,typename _Pr>const typename vector<T>::const_iterator find_if(const vector<T>&vec,_Pr pred){return std::find_if(vec.begin(),vec.end(),pred);}
	template<typename T>bool contains(const vector<T>&vec,const T& val){return std::find(vec.begin(),vec.end(),val) != vec.end();}
	template<typename T,typename _Pr>bool contains_if(const vector<T>&vec,_Pr pred){return std::find_if(vec.begin(),vec.end(),pred)!=vec.end();}
	template<typename T,typename _Pr>typename iterator_traits<const typename vector<T>::const_iterator>::difference_type count_if(const vector<T>&vec,_Pr pred){return std::count_if(vec.begin(),vec.end(),pred);}
	template<typename T>void sort(vector<T>&vec){std::sort(vec.begin(),vec.end());}
	template<typename T,typename _Pr>void sort(vector<T>&vec,_Pr pred){std::sort(vec.begin(),vec.end(),pred);}
	template<typename T>void stable_sort(vector<T>&vec){std::stable_sort(vec.begin(),vec.end());}
	template<typename T,typename _Pr>void stable_sort(vector<T>&vec,_Pr pred){std::stable_sort(vec.begin(),vec.end(),pred);}

	template<typename T,size_t N>void fill(array<T,N>&ary,const T& value){std::fill(ary.begin(),ary.end(),value);}
	template<typename T,size_t N,size_t M>void fill(array<array<T,M>,N>&ary,const T& value){ for(array<T,M>& t : ary) std::fill(t.begin(),t.end(),value);}
	template<typename T,size_t N,typename _Pr>const typename array<T,N>::const_iterator max_element(const array<T,N>&ary){assert(!ary.empty());return std::max_element(ary.begin(),ary.end());}
	template<typename T,size_t N,typename _Pr>const typename vector<T>::const_iterator max_element(const array<T,N>&ary){assert(!ary.empty());return std::max_element(ary.begin(),ary.end());}
	template<typename T,size_t N,typename _Pr>const typename array<T,N>::const_iterator max_element(const array<T,N>&ary,_Pr lessThan){assert(!ary.empty());return std::max_element(ary.begin(),ary.end(),lessThan);}
	template<typename T,size_t N,typename _Pr>const typename array<T,N>::const_iterator min_element(const array<T,N>&ary){assert(!ary.empty());return std::min_element(ary.begin(),ary.end());}
	template<typename T,size_t N,typename _Pr>const typename array<T,N>::const_iterator min_element(const array<T,N>&ary,_Pr lessThan){assert(!ary.empty());return std::min_element(ary.begin(),ary.end(),lessThan);}
	template<size_t N>int accumulate(const array<int,N>&ary){return std::accumulate(ary.begin(),ary.end(),0);}
	template<size_t N,typename _Pr>int accumulate(const array<int,N>&ary,_Pr func){return std::accumulate(ary.begin(),ary.end(),0,func);}
	template<size_t N>double accumulate(const array<double,N>&ary){return std::accumulate(ary.begin(),ary.end(),0.0);}
	template<size_t N,typename _Pr>double accumulate(const array<double,N>&ary,_Pr func){return std::accumulate(ary.begin(),ary.end(),0.0,func);}
	template<size_t N> float accumulate(const array<float,N>&ary){return std::accumulate(ary.begin(),ary.end(),0.f);}
	template<size_t N,typename _Pr>float accumulate(const array<float,N>&ary,_Pr func){return std::accumulate(ary.begin(),ary.end(),0.f,func);}
	template<typename T,size_t N,typename _Pr>bool all_of(const array<T,N>&ary,_Pr pred){return std::all_of(ary.begin(),ary.end(),pred);}
	template<typename T,size_t N,typename _Pr>bool any_of(const array<T,N>&ary,_Pr pred){return std::any_of(ary.begin(),ary.end(),pred);}
	template<typename T,size_t N,typename _Pr>bool none_of(const array<T,N>&ary,_Pr pred){return std::none_of(ary.begin(),ary.end(),pred);}
	template<typename T,size_t N>const typename array<T,N>::const_iterator find(const array<T,N>&ary,const T& val){return std::find(ary.begin(),ary.end(),val);}
	template<typename T,size_t N,typename _Pr>const typename array<T,N>::const_iterator find_if(const array<T,N>&ary,_Pr pred){return std::find_if(ary.begin(),ary.end(),pred);}
	template<typename T,size_t N>bool contains(const array<T,N>&ary,const T& val){return std::find(ary.begin(),ary.end(),val)!=ary.end();}
	template<typename T,size_t N,typename _Pr>bool contains_if(const array<T,N>&ary,_Pr pred){return std::find_if(ary.begin(),ary.end(),pred) != ary.end();}
	template<typename T,size_t N,typename _Pr>typename iterator_traits<const typename array<T,N>::const_iterator>::difference_type count_if(const array<T,N>&ary,_Pr pred){return std::count_if(ary.begin(),ary.end(),pred);}
	template<typename T,size_t N>void sort(array<T,N>&ary){std::sort(ary.begin(),ary.end());}
	template<typename T,size_t N,typename _Pr>void sort(array<T,N>&ary,_Pr pred){std::sort(ary.begin(),ary.end(),pred);}
	template<typename T,size_t N>void stable_sort(array<T,N>&ary){std::stable_sort(ary.begin(),ary.end());}
	template<typename T,size_t N,typename _Pr>void stable_sort(array<T,N>&ary,_Pr pred){std::stable_sort(ary.begin(),ary.end(),pred);}

	template<typename Key, typename Value>
	bool containsKey(const umap<Key, Value>& m, const Key& key) {
		return m.find(key) != m.end();
	}
	template<typename Key, typename Value>
	bool containsValue(const umap<Key, Value>& m, const Value& val) {
		for (auto it = m.begin(); it != m.end(); ++it)
			if (it->second == val)
				return true;
		return false;
	}
	template<typename T>
	const typename uset<T>::const_iterator find(const uset<T>& s, const T& key) {
		return s.find(key);
	}
	template<typename T>
	bool contains(const uset<T>& s, const T& key) {
		return s.find(key) != s.end();
	}

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

	class Point {
	public:

		constexpr inline Point() : Point(-1, -1) {}
		constexpr inline Point(int x, int y) : x(x), y(y)	{}

		static Point getManhattanDist(const Point& p1, const Point& p2) {
			return move(Point(abs(p1.x - p2.x), abs(p1.y - p2.y))); 
		}

		void setPos(const Point& pos) { x = pos.x; y = pos.y; }
		void setPos(int x, int y) { this->x = x; this->y = y; }

		Point operator+ (int val) const { return move(Point(x + val, y + val)); }
		Point operator- (int val) const { return move(Point(x - val, y - val)); }
		Point operator* (int val) const { return move(Point(x * val, y * val)); }
		Point operator/ (int val) const { return move(Point(x / val, y / val)); }
		Point operator+ (const Point &p) const { return move(Point(x + p.x, y + p.y)); }
		Point operator- (const Point &p) const { return move(Point(x - p.x, y - p.y)); }
		Point operator* (const Point &p) const { return move(Point(x * p.x, y * p.y)); }
		Point operator/ (const Point &p) const { return move(Point(x / p.x, y / p.y)); }
		void operator+= (int val) { x += val; y += val; }
		void operator-= (int val) { x -= val; y -= val; }
		void operator*= (int val) { x *= val; y *= val; }
		void operator/= (int val) { x /= val; y /= val; }
		void operator+= (const Point &p) { x += p.x; y += p.y; }
		void operator-= (const Point &p) { x -= p.x; y -= p.y; }
		void operator*= (const Point &p) { x *= p.x; y *= p.y; }
		void operator/= (const Point &p) { x /= p.x; y /= p.y; }
		bool operator== (const Point &p) const { return x == p.x && y == p.y; }
		bool operator!= (const Point &p) const { return x != p.x || y != p.y; }
		//bool operator<(const Point &p) const {return x * x + y * y < p.x * p.x + p.y * p.y;}
		const Point& getPos() const { return *this; }

		string to_string() const { return "(" + std::to_string(x) + ", " + std::to_string(y) + ")"; }

		int x, y;
	};

	constexpr Point DP4[] = {Point(DX4[0], DY4[0]), Point(DX4[1], DY4[1]), Point(DX4[2], DY4[2]), Point(DX4[3], DY4[3])};
	constexpr Point DP5[] = {Point(DX5[0], DY5[0]), Point(DX5[1], DY5[1]), Point(DX5[2], DY5[2]), Point(DX5[3], DY5[3]), Point(DX5[4], DY5[4])};
	constexpr Point DP8[] = {Point(DX8[0], DY8[0]), Point(DX8[1], DY8[1]), Point(DX8[2], DY8[2]), Point(DX8[3], DY8[3]), Point(DX8[4], DY8[4]), Point(DX8[5], DY8[5]), Point(DX8[6], DY8[6]), Point(DX8[7], DY8[7])};
	constexpr Point DP9[] = {Point(DX9[0], DY9[0]), Point(DX9[1], DY9[1]), Point(DX9[2], DY9[2]), Point(DX9[3], DY9[3]), Point(DX9[4], DY9[4]), Point(DX9[5], DY9[5]), Point(DX9[6], DY9[6]), Point(DX9[7], DY9[7])};

	// 文字列の先頭の0を削除する
	string cutZeroLeft(const string& str) {
		for (int i = 0; i < (int)str.length(); ++i) {
			if (str[i] != '0') {
				return str.substr(i);
			}
		}
		return "";
	}

	// 0以上の整数を0埋めで表記する
	string fillZero(ull number, int digit) {
		int zeroNum = max(0, (int)(digit - to_string(number).length()));
		return move(move(string(zeroNum, '0')) + move(to_string(number)));
	}

	// 0以上の10進数を2進数に変換する
	string toBinString(ull x) {
		return move(cutZeroLeft(bitset<20>(x).to_string()));
	}

	// 0以上の10進数を8進数に変換する
	string toOctString(ull x) {
		stringstream ss;
		ss << std::oct << x;
		return move(ss.str());
	}

	// 0以上の整数を16進数に変換する(a～fは小文字)
	string toHexString(ull x) {
		stringstream ss;
		ss << std::hex << x;
		return move(ss.str());
	}

	// 0以上の整数を任意の基数に変換する(最大36進数)(a～zは小文字)
	string toBaseString(ull x, int base) {
		const string table = "0123456789abcdefghijklmnopqrstuvwxyz";

		assert(base >= 2 && base <= 36);

		string result = "";
		ull y = x;
		do {
			ull div = y / (ull)base;
			int mod = y % (ull)base;

			result = table[mod] + result;
			y = div;
		}
		while (y != 0ull);

		return move(result);
	}

	// 任意の基数の0以上の整数を10進数に変換する
	// base: 変換元の基数
	ull toDecimal(string numberString, int base) {
		assert(numberString.length() < 20);
		assert(!numberString.empty());
		return stoull(numberString, nullptr, base);
	}

	// double型の値を任意の少数桁数で表示する
	// 指定の桁数まで0で埋める。指数表記にはならない
	// precision=0を指定したときは小数点は表示しない
	// 表示桁数＋１桁目を四捨五入する
	string sprintDoublePlane(double value, int precision) {
		assert(precision >= 0);
		stringstream ss;
		ss << fixed << setprecision(precision) << value;
		return move(ss.str());
	}

	template<typename A>void in(A&a){cin>>a;cin.ignore();}
	template<typename A,typename B>void in(A&a,B&b){cin>>a>>b;cin.ignore();}
	template<typename A,typename B,typename C>void in(A&a,B&b,C&c){cin>>a>>b>>c;cin.ignore();}
	template<typename A,typename B,typename C,typename D>void in(A&a,B&b,C&c,D&d){cin>>a>>b>>c>>d;cin.ignore();}
	template<typename A,typename B,typename C,typename D,typename E>void in(A&a,B&b,C&c,D&d,E&e){cin>>a>>b>>c>>d>>e;cin.ignore();}
	template<typename A,typename B,typename C,typename D,typename E,typename F>void in(A&a,B&b,C&c,D&d,E&e,F&f){cin>>a>>b>>c>>d>>e>>f;cin.ignore();}
	template<typename A,typename B,typename C,typename D,typename E,typename F,typename G>void in(A&a,B&b,C&c,D&d,E&e,F&f,G&g){cin>>a>>b>>c>>d>>e>>f>>g;cin.ignore();}

	template<typename A>
	void inr(vector<A>& a, int size) {
		resize(a, size);
		for (int i = 0; i < size; ++i) {
			cin >> a[i]; cin.ignore();
		}
	}
	template<typename A, typename B>
	void inr(vector<A>& a, vector<B>& b, int size) {
		resize(a, size); resize(b, size);
		for (int i = 0; i < size; ++i) {
			cin >> a[i] >> b[i]; cin.ignore();
		}
	}
	template<typename A, typename B, typename C>
	void inr(vector<A>& a, vector<B>& b, vector<C>& c, int size) {
		resize(a, size); resize(b, size); resize(c, size);
		for (int i = 0; i < size; ++i) {
			cin >> a[i] >> b[i] >> c[i]; cin.ignore();
		}
	}
	template<typename A, typename B, typename C, typename D>
	void inr(vector<A>& a, vector<B>& b, vector<C>& c, vector<D>& d, int size) {
		resize(a, size); resize(b, size); resize(c, size); resize(d, size);
		for (int i = 0; i < size; ++i) {
			cin >> a[i] >> b[i] >> c[i] >> d[i]; cin.ignore();
		}
	}
	template<typename A, typename B, typename C, typename D, typename E>
	void inr(vector<A>& a, vector<B>& b, vector<C>& c, vector<D>& d, vector<E>& e, int size) {
		resize(a, size); resize(b, size); resize(c, size); resize(d, size); resize(e, size);
		for (int i = 0; i < size; ++i) {
			cin >> a[i] >> b[i] >> c[i] >> d[i] >> e[i]; cin.ignore();
		}
	}

	template<typename A>
	void inr(vector<vector<A>>& a, int h, int wa) {
		resize(a, h, wa);
		for (int i = 0; i < h; ++i) {
			for (int j = 0; j < wa; ++j) {
				cin >> a[i][j];
			}
			cin.ignore();
		}
	}
	template<typename A,typename B>
	void inr(vector<vector<A>>& a, vector<vector<B>>& b, int h, int wa, int wb) {
		resize(a, h, wa); resize(b, h, wb);
		for (int i = 0; i < h; ++i) {
			for (int j = 0; j < wa; ++j) {
				cin >> a[i][j];
			}
			for (int j = 0; j < wb; ++j) {
				cin >> b[i][j];
			}
			cin.ignore();
		}
	}
	template<typename A,typename B,typename C>
	void inr(vector<vector<A>>& a, vector<vector<B>>& b, vector<vector<C>>& c, int h, int wa, int wb, int wc) {
		resize(a, h, wa); resize(b, h, wb); resize(c, h, wc);
		for (int i = 0; i < h; ++i) {
			for (int j = 0; j < wa; ++j) {
				cin >> a[i][j];
			}
			for (int j = 0; j < wb; ++j) {
				cin >> b[i][j];
			}
			for (int j = 0; j < wc; ++j) {
				cin >> c[i][j];
			}
			cin.ignore();
		}
	}

	template<typename T>
	void out(const T& val) { cout << val << endl; }
}

using namespace ValLib;

class vegde {
public:
	vegde() : vegde(-1) {

	}

	vegde(int cost) :
		mCost(cost) {

	}

	int getCost() const { return mCost; }

private:
	int mCost;
};

class vnode {
public:
	vnode() : vnode(-1) {

	}

	vnode(int id) :
		mID(id) {

	}

	void addEgde(const vegde& egde, const vnode* node) {
		mEgdeList.emplace_back(egde, node);
	}
	void removeEgde(int nodeID) {
		auto itrNewEnd = std::remove_if(mEgdeList.begin(), mEgdeList.end(), [=](const pair<vegde, const vnode*>& p)->bool {
			return (p.second->getID() == nodeID);
		});
		mEgdeList.erase(itrNewEnd, mEgdeList.end());
	}

	int getID() const { return mID; }
	const list<pair<vegde, const vnode*>>& getEgde() const { return mEgdeList; }
private:
	list<pair<vegde, const vnode*>> mEgdeList;
	int mID;
};

class AdjacencyMatrix {
public:

	AdjacencyMatrix() = default;

	AdjacencyMatrix(int nodeNum) {
		resize(mConnectionMap, nodeNum, nodeNum);
		resize(mCostMap, nodeNum, nodeNum);
		resize(mMinimumDistMap, nodeNum, nodeNum);
	}

	//virtual void addEdge(int nodeID1, int nodeID2, int cost) = 0;
	//virtual void removeEgde(int nodeID1, int nodeID2) = 0;

	void warshallFloyd(int nodeNum) {
		for (int k = 0; k < nodeNum; ++k) {
			for (int i = 0; i < nodeNum; ++i) {
				for (int j = 0; j < nodeNum; ++j) {
					if (mConnectionMap[i][j]) {
						mMinimumDistMap[i][j] = mCostMap[i][j];
					} else {
						mMinimumDistMap[i][j] = 99999999;
					}
				}
			}
		}
		for (int k = 0; k < nodeNum; ++k) {
			for (int i = 0; i < nodeNum; ++i) {
				for (int j = 0; j < nodeNum; ++j) {
					mMinimumDistMap[i][j] = min(mMinimumDistMap[i][j], mMinimumDistMap[i][k] + mMinimumDistMap[k][j]);
				}
			}
		}
		//for (int i = 0; i < mNodeNum; ++i) {
		//	for (int j = 0; j < mNodeNum; ++j) {
		//		cerr << mMinimumDistMap[i][j] << ", ";
		//	}
		//	cerr << endl;
		//}
	}

	const vector<vector<bool>>& getConnectionMap() const { return mConnectionMap; }
	const vector<vector<int>>& getCostMap() const { return mCostMap; }

	const vector<vector<int>>& getMinimumDistMap() const { return mMinimumDistMap; }

protected:
	vector<vector<bool>> mConnectionMap;
	vector<vector<int>> mCostMap;

	vector<vector<int>> mMinimumDistMap;
};

class DirectedAdjacencyMatrix : public AdjacencyMatrix  {
public:

	DirectedAdjacencyMatrix() = default;

	DirectedAdjacencyMatrix(int nodeNum) :
		AdjacencyMatrix(nodeNum) {
	}

	void addEgde(int nodeID1, int nodeID2, int cost) {
		mConnectionMap[nodeID1][nodeID2] = true;
		mCostMap[nodeID1][nodeID2] = cost;
	}

	void removeEgde(int nodeID1, int nodeID2) {
		mConnectionMap[nodeID1][nodeID2] = false;
		mCostMap[nodeID1][nodeID2] = 0;
	}
};

class UndirectedAdjacencyMatrix : public AdjacencyMatrix {
public:

	UndirectedAdjacencyMatrix() = default;

	UndirectedAdjacencyMatrix(int nodeNum) :
		AdjacencyMatrix(nodeNum) {
	}

	void addEgde(int nodeID1, int nodeID2, int cost) {
		mConnectionMap[nodeID1][nodeID2] = true;
		mConnectionMap[nodeID2][nodeID1] = true;
		mCostMap[nodeID1][nodeID2] = cost;
		mCostMap[nodeID2][nodeID1] = cost;
	}

	void removeEgde(int nodeID1, int nodeID2) {
		mConnectionMap[nodeID1][nodeID2] = false;
		mConnectionMap[nodeID2][nodeID1] = false;
		mCostMap[nodeID1][nodeID2] = 0;
		mCostMap[nodeID2][nodeID1] = 0;
	}

};

// グラフ
class vgraph {
public:

	const int INF = 1000000;

	vgraph(int nodeNum) {
		mNodeNum = nodeNum;
		mNodes.resize(nodeNum);
		for (int i = 0; i < nodeNum; ++i) {
			mNodes[i] = move(vnode(i));
		}
		mMinimumDists.resize(mNodeNum);
		mPrevNodes.resize(mNodeNum);
	}

	void addEgde(int nodeID1, int nodeID2) {
		addEgde(nodeID1, nodeID2, 1);
	}

	virtual void addEgde(int nodeID1, int nodeID2, int cost) = 0;
	virtual void removeEgde(int nodeID1, int nodeID2) = 0;

	int dfs(int start) {
		vector<bool> check(mNodes.size());
		fill(check, false);
		int MAX_DEPTH = INF; // 探索の深さ制限があれば定義する
		return dfsSub(start, check, MAX_DEPTH, 0);
	}

	void bfs(int start) {
		vector<bool> check(mNodes.size());
		fill(check, false);
		int MAX_DEPTH = INF; // 探索の深さ制限があれば定義する
		return bfsSub(start, check, MAX_DEPTH);
	}

	// ベルマンフォード法を使ってある頂点から全ての頂点への最短距離を求める
	// startからたどり着ける場所に負のループが存在する場合はfalseを返す
	// ダイクストラ法と違い、負のコストの辺があっても最短距離を計算できる
	// O(V*E)
	bool bellmanFord(int start) {

		vector<int>& dist = mMinimumDists;

		fill(dist, INF);
		dist[start] = 0;

		for (int i = 0; i < mNodeNum; ++i) {
			bool update = false;
			for (vnode node : mNodes) {
				for (const pair<vegde, const vnode*> egde : node.getEgde()) {
					int from = node.getID();
					int to = egde.second->getID();
					if (dist[from] == INF) {
						continue;
					}
					if (dist[from] + egde.first.getCost() < dist[to]) {
						dist[to] = dist[from] + egde.first.getCost();
						update = true;

						if (i == mNodeNum - 1) {
							//return false;
						}
					}
				}
			}
			if (!update) {
				break;
			}
		}
		return true;
	}

	// ダイクストラ法を使ってある頂点から全ての頂点への最短距離を求める
	// 負のコストの辺があると最短距離を計算できない点に注意する
	// O(E*logV)
	void dijkstraSearch(int start) {

		// Minimum distances for each nodes
		vector<int>& dpMinDists = mMinimumDists;
		fill(dpMinDists, INF);

		// Result of the previous visited node
		vector<int>& resultPrev = mPrevNodes;
		fill(resultPrev, -1);

		// Create a priority_queue for search.
		typedef pair<int, int> P; // key: その頂点までの最短距離, value: 頂点の番号
		priority_queue<P, vector<P>, greater<P>> pq_node;

		// Mark the current node as visited and enqueue it
		pq_node.push(P(0, start));

		dpMinDists[start] = 0;

		while (!pq_node.empty()) {
			P p = pq_node.top();
			pq_node.pop();
			int nowDist = p.first;
			int nowNodeID = p.second;

			if (dpMinDists[nowNodeID] < nowDist) {
				continue;
			}

			for (const pair<vegde, const vnode*>& egde : mNodes[nowNodeID].getEgde()) {
				const vnode* nextNode = egde.second;
				int nextNodeID = nextNode->getID();

				int nextNodeDist = nowDist + egde.first.getCost();
				if (nextNodeDist < dpMinDists[nextNodeID]) {
					dpMinDists[nextNodeID] = nextNodeDist;
					resultPrev[nextNodeID] = nowNodeID;

					pq_node.push(P(nextNodeDist, nextNodeID));
				}
			}
		}
	}

	int calcMaxDepth() const {
		pair<int, int> farestNodeData = getFarestNodeID(0);
		pair<int, int> farestNodeData2 = getFarestNodeID(farestNodeData.first);
		return farestNodeData2.second;
	}

	int getNodeNum() const { return mNodeNum; }
	const vector<vnode>& getNodes() const { return mNodes; }

	const vector<int>& getMinimumDists() const { return mMinimumDists; }
	const vector<int>& getPrevNodes() const { return mPrevNodes; }
protected:

	int dfsSub(int nodeIndex, vector<bool>& check, int MAX_DEPTH, int depth) {
		check[nodeIndex] = true;
		int result = 0;

		// 隣接する辺を探索
		if (depth < MAX_DEPTH) {
			for (const auto& t : mNodes[nodeIndex].getEgde()) {
				if (check[t.second->getID()]) {
					// 巡回済みの辺は見ない
					continue;
				}
				result += dfsSub(t.second->getID(), check, MAX_DEPTH, depth + 1);
			}
		}

		// 末端での処理
		result += 1; // この巡回順で末端に辿り着いた時、目的の条件を満たすなら+1する


		check[nodeIndex] = false;

		return result;
	}

	void bfsSub(int start, vector<bool>& check, int MAX_DEPTH) {

		queue<pair<int, int>> target;
		target.push(pair<int, int>(start, 0));
		while (!target.empty()) {
			pair<int, int> now = target.front();
			target.pop();

			// ノードに対して何かやることがあればここでやる
			//mNodes[now.first].something = someData;

			check[now.first] = true;
			int egdeCount = 0;
			if (now.second < MAX_DEPTH) {
				for (const pair<vegde, const vnode*>& egde : mNodes[now.first].getEgde()) {
					if (check[egde.second->getID()]) {
						// このノードはもっと少ない手順で巡回可能なので行かない
						continue;
					}
					++egdeCount;
					target.push(pair<int, int>(egde.second->getID(), now.second + 1));
				}
			}
			if (now.second == MAX_DEPTH || egdeCount == 0) {
				// 探索深さ制限またはこのノードから繋がる辺が全て巡回済み

				// doSomething.

			}
		}
	}

	// 引数で受け取ったノードから最も遠いノードのidと距離を返す
	// グラフにループがあると無限ループになるので注意する(つまり木専用)
	pair<int, int> getFarestNodeID(int start) const {
		queue<pair<int, int>> q; // nodeID, このノードまでの距離
		q.push(make_pair(start, 0));
		pair<int, int> finalNodeData;
		vector<bool> opened(mNodeNum);
		fill(opened, false);
		while (!q.empty()) {
			pair<int, int> nodeData = q.front();
			int nodeID = nodeData.first;
			int dist = nodeData.second;
			if (dist > finalNodeData.second) {
				finalNodeData.second = dist;
				finalNodeData.first = nodeID;
			}
			q.pop();
			for (const pair<vegde, const vnode*> egde : mNodes[nodeID].getEgde()) {
				int id = egde.second->getID();
				if (opened[id]) {
					continue;
				}
				opened[id] = true;
				q.push(make_pair(id, dist + egde.first.getCost()));
			}
		}
		return finalNodeData;
	}

	int mNodeNum;
	bool mUseMaps;
	vector<vnode> mNodes;

	vector<int> mMinimumDists;
	vector<int> mPrevNodes;
};

// 無向グラフ UnDirected Val Graph.
class udvgraph : public vgraph {
public:
	udvgraph(int nodeNum) :
		vgraph(nodeNum) {
	}

	void addEgde(int nodeID1, int nodeID2, int cost) {
		mNodes[nodeID1].addEgde(move(vegde(cost)), &mNodes[nodeID2]);
		mNodes[nodeID2].addEgde(move(vegde(cost)), &mNodes[nodeID1]);
	}

	void removeEgde(int nodeID1, int nodeID2) {
		mNodes[nodeID1].removeEgde(nodeID2);
		mNodes[nodeID2].removeEgde(nodeID1);
	}
};

// 隣接行列付きの無向グラフ。ワーシャルフロイドが使える。 UnDirected Val Graph Matrix
class udvgraph_m : public udvgraph {
public:

	udvgraph_m(int nodeNum) :
		udvgraph(nodeNum) {
		mAdjacencyMatrix = UndirectedAdjacencyMatrix(nodeNum);
	}
	void addEgde(int nodeID1, int nodeID2, int cost) {
		udvgraph::addEgde(nodeID1, nodeID2, cost);
		mAdjacencyMatrix.addEgde(nodeID1, nodeID2, cost);
	}

	void removeEgde(int nodeID1, int nodeID2) {
		udvgraph::removeEgde(nodeID1, nodeID2);
		mAdjacencyMatrix.removeEgde(nodeID1, nodeID2);
	}

	void warshallFloyd() {
		mAdjacencyMatrix.warshallFloyd(mNodeNum);
	}

	const vector<vector<bool>>& getConnectionMap() const { return mAdjacencyMatrix.getConnectionMap(); }
	const vector<vector<int>>& getCostMap() const { return mAdjacencyMatrix.getCostMap(); }

	const vector<vector<int>>& getMinimumDistMap() const { return mAdjacencyMatrix.getMinimumDistMap(); }
private:
	UndirectedAdjacencyMatrix mAdjacencyMatrix;
};


// 有向グラフ Directed Val Graph.
class dvgraph : public vgraph {
public:
	dvgraph(int nodeNum) :
		vgraph(nodeNum) {
	}

	void addEgde(int nodeID1, int nodeID2, int cost) {
		mNodes[nodeID1].addEgde(move(vegde(cost)),&mNodes[nodeID2]);
	}

	void removeEgde(int nodeID1, int nodeID2) {
		mNodes[nodeID1].removeEgde(nodeID2);
	}

	// 入力のないノードのリストを返す
	list<int> searchStartNodes() const {
		list<int> startNodes;
		unordered_map<int, int> nodesInputs; // key:ノード番号, value:インプット数
		for (auto node : mNodes) {
			for (auto edge : node.getEgde()) {
				++nodesInputs[edge.second->getID()];
			}
		}
		for (int i = 0; i < mNodeNum; ++i) {
			if (nodesInputs.find(i) == nodesInputs.end()) {
				startNodes.push_back(i);
			}
		}
		return move(startNodes);
	}
};

// 隣接行列付きの有向グラフ。ワーシャルフロイドが使える。 Directed Val Graph Matrix
class dvgraph_m : public dvgraph {
public:

	dvgraph_m(int nodeNum) :
		dvgraph(nodeNum) {
		mAdjacencyMatrix = DirectedAdjacencyMatrix(nodeNum);
	}
	void addEgde(int nodeID1, int nodeID2, int cost) {
		dvgraph::addEgde(nodeID1, nodeID2, cost);
		mAdjacencyMatrix.addEgde(nodeID1, nodeID2, cost);
	}

	void removeEgde(int nodeID1, int nodeID2) {
		dvgraph::removeEgde(nodeID1, nodeID2);
		mAdjacencyMatrix.removeEgde(nodeID1, nodeID2);
	}

	void warshallFloyd() {
		mAdjacencyMatrix.warshallFloyd(mNodeNum);
	}

	const vector<vector<bool>>& getConnectionMap() const { return mAdjacencyMatrix.getConnectionMap(); }
	const vector<vector<int>>& getCostMap() const { return mAdjacencyMatrix.getCostMap(); }

	const vector<vector<int>>& getMinimumDistMap() const { return mAdjacencyMatrix.getMinimumDistMap(); }
private:
	DirectedAdjacencyMatrix mAdjacencyMatrix;
};

int N;
vector<ull> a;

int main() {

	in(N);
	inr(a, N);

	for (int i = 0; i < N; ++i) {
		if (a[i] == 0ull) {
			out(0);
			return 0;
		}
	}

	constexpr ull pow10_18 = 1000000000000000000ull;

	ull mul = a[0];
	for (int i = 1; i < N; ++i) {
		ull maxNum = pow10_18 / mul;
		if (a[i] > maxNum) {
			out(-1);
			return 0;
		}
		mul *= a[i];
	}

	out(mul);
}


Measured memory_bytes: 4072