#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using lll = __int128;
using ld = long double;
using hash_t = unsigned long long;

namespace INT {constexpr int INF = 0x3FFF'FFFF;}
namespace LL {constexpr ll INF = 0x3FFF'FFFF'FFFF'FFFFll;}
namespace LD {constexpr ld INF = numeric_limits<ld>::infinity();}

namespace details {
	template<typename T = ll>
	bool isPrime(T x) {
		for (T i = 2; i*i <= x; i++) {
			if (x % i == 0) return false;
		}
		return x > 1;
	}
}

namespace Random {
	#ifdef SEED
		mt19937_64 rng(SEED);
	#else
		mt19937_64 rng(3141592653589793238ll);
	#endif
	template<typename T = ll>
	T integer(T l, T r) {
		return uniform_int_distribution<T>(l, r-1)(rng);
	}

	template<typename T = ll>
	T integer(T r) {
		return integer<T>(0, r);
	}

	template<typename T = ll>
	std::vector<T> integers(std::size_t n, T l, T r) {
		std::vector<T> res(n);
		for (T& x : res) x = integer<T>(l, r);
		return res;
	}

	template<typename T = ll>
	std::vector<T> integers(std::size_t n, T r) {
		return integers<T>(n, 0, r);
	}

	template<typename T = ll>
	std::vector<T> distinct(std::size_t n, T l, T r) {
		std::map<T, T> used;
		std::vector<T> res;
		for (std::size_t i = 0; i < n; i++) {
			T x = integer<T>(l, r - i);
			auto it = used.find(x);
			if (it != used.end()) res.emplace_back(it->second);
			else res.emplace_back(x);
			it = used.find(r - i - 1);
			if (it != used.end()) used[x] = it->second;
			else used[x] = r - i - 1;
		}
		return res;
	}

	template<typename T = ll>
	std::vector<T> distinct(std::size_t n, T r) {
		return distinct<T>(n, 0, r);
	}

	template<typename T = ld>
	T real(T l, T r) {
		return uniform_real_distribution<T>(l, r)(rng);
	}

	template<typename T = ld>
	T real(T r) {
		return real<T>(0, r);
	}

	template<typename T = ld>
	std::vector<T> reals(std::size_t n, T l, T r) {
		std::vector<T> res(n);
		for (T& x : res) x = real<T>(l, r);
		return res;
	}

	template<typename T = ld>
	std::vector<T> reals(std::size_t n, T r) {
		return reals<T>(n, 0, r);
	}

	template<typename T = ll>
	std::pair<T, T> pair(T l, T r) {
		T a = integer<T>(l, r);
		T b = integer<T>(l, r);
		if (a > b) swap(a, b);
		return {a, b};
	}

	template<typename T = ll>
	std::pair<T, T> pair(T r) {
		return pair<T>(0, r);
	}

	std::string string(std::size_t n, string_view chars) {
		std::string res(n, '*');
		for (char& c : res) c = chars[integer(ssize(chars))];
		return res;
	}

	template<typename T = ll>
	T prime(T l, T r) {
		T res = 0;
		do {
			res = integer<T>(l, r);
		} while (!details::isPrime<T>(res));
		return res;
	}

	template<typename T = ll>
	T prime(T r) {
		return prime<T>(2, r);
	}

	template<typename T = ll, typename std::enable_if<!std::is_floating_point<T>::value>::type* = nullptr>
	std::complex<T> point(T l, T r) {
		return {integer<T>(l, r), integer<T>(l, r)};
	}

	template<typename T = ld, typename std::enable_if<std::is_floating_point<T>::value>::type* = nullptr>
	std::complex<T> point(T l, T r) {
		return {real(l, r), real(l, r)};
	}

	template<typename T = ll>
	std::complex<T> point(T r) {
		return point<T>(0, r);
	}

	template<typename T = ll, typename std::enable_if<!std::is_floating_point<T>::value>::type* = nullptr>
	std::vector<std::complex<T>> points(std::size_t n, T l, T r) {
		std::vector<std::complex<T>> res(n);
		for (auto& x : res) x = point<T>(l, r);
		return res;
	}

	template<typename T = ld, typename std::enable_if<std::is_floating_point<T>::value>::type* = nullptr>
	std::vector<std::complex<T>> points(std::size_t n, T l, T r) {
		std::vector<std::complex<T>> res(n);
		for (auto& x : res) x = point<T>(l, r);
		return res;
	}

	template<typename T = ll>
	std::vector<std::complex<T>> points(std::size_t n, T r) {
		return points<T>(n, 0, r);
	}

}

[[noreturn]] ostream& FAIL(ostream& os) {
	os << endl;
	exit(1);
}

namespace detail {
	double benchmark() {
		mt19937 rng(734820734);
		vector<unsigned> a(10000000);
		for (unsigned &x: a) x = rng();
		chrono::steady_clock::time_point start = chrono::steady_clock::now();
		vector<unsigned> dp(ssize(a)+1, numeric_limits<unsigned>::max());
		int res = 0;
		for (unsigned x: a) {
			auto it = ranges::upper_bound(dp, x);
			res = max(res, (int)(it - begin(dp)));
			*it = x;
		}
		chrono::steady_clock::time_point end = chrono::steady_clock::now();
		assert(res == 6301);
		double t =
		  chrono::duration_cast<chrono::duration<double, milli>>(end - start)
		    .count();
		return 30/t;
	}

	double speed = benchmark();
}

struct timer {
	bool running = false;
	double time = 0;
	chrono::steady_clock::time_point begin;

	void start() {
		if (running) cerr << "timer already running!" << FAIL;
		running = true;
		begin = chrono::steady_clock::now();
	}

	void stop() {
		auto end = chrono::steady_clock::now();
		if (!running) cerr << "timer not running!" << FAIL;
		running = false;
		time += chrono::duration_cast<chrono::duration<double, milli>>(end - begin).count() * detail::speed;
	}

	void reset() {
		running = false;
		time = 0;
	}

	~timer() {
		if (running) cerr << "timer not stopped!" << FAIL;
	}

	friend std::ostream& operator<<(std::ostream& os, const timer& t) {
		if (t.running) cerr << "timer already running!" << FAIL;
		return os << t.time;
	}
};

namespace c20 {
	namespace detail {
		template<class T, std::size_t N, std::size_t... I>
		constexpr std::array<std::remove_cv_t<T>, N> to_array_impl(T (&a)[N], std::index_sequence<I...>) {
			return {{a[I]...}};
		}
	}

	template<class T, std::size_t N>
	constexpr std::array<std::remove_cv_t<T>, N> to_array(T (&a)[N]) {
		return c20::detail::to_array_impl(a, std::make_index_sequence<N>{});
	}
}

struct NoData {};

template<typename W = NoData>
struct Edge {
	int from, to;
	mutable W w;

	Edge(int from_, int to_, W w_ = {}) : from(from_), to(to_), w(w_) {}

	template<typename F>
	void forE(int x, F&& f) const {
		int y = from ^ to ^ x;
		if constexpr (is_same_v<W, NoData>) f(x, y);
		else f(x, y, w);
	}

	template<typename F>
	void forE(F&& f) const {
		forE(from, f);
	}

	friend std::ostream& operator<<(std::ostream& os, const Edge& e) {
		os << e.from << "->" << e.to;
		if constexpr (!is_same_v<W, NoData>) os << ": " << e.w;
		return os;
	}
};


template<typename W = NoData, bool DIR = false, bool MULTI = false, bool LOOPS = false>
class Graph {
	vector<multimap<int, int>> adj;
	vector<Edge<W>> edges;

	void _addAdj(int e) {
		adj[edges[e].from].emplace(edges[e].to, e);
		if (!DIR && edges[e].from != edges[e].to) adj[edges[e].to].emplace(edges[e].from, e);
	}
public:

	Graph(int n) : adj(n) {}

	int m() const {return ssize(edges);}
	int n() const {return ssize(adj);}
	int deg(int x) const {return ssize(adj[x]);}

	Graph& clear() {
		adj.assign(adj.size(), {});
		edges.clear();
		return *this;
	}

	bool addEdge(int from, int to, W w = {}) {
		if (!LOOPS && from == to) return false;
		if (!MULTI && adj[from].find(to) != adj[from].end()) return false;
		edges.emplace_back(from, to, w);
		_addAdj(ssize(edges) - 1);
		return true;
	}

	Graph& reverse() {
		for (auto& e : edges) swap(e.from, e.to);
		adj.assign(adj.size(), {});
		for (int i = 0; i < ssize(edges); i++) _addAdj(i);
		return *this;
	}

	Graph& shuffle() {
		ranges::shuffle(edges, Random::rng);
		if constexpr (!DIR) {
			for (auto& e : edges) {
				if (Random::integer(0, 2)) swap(e.from, e.to);
			}
		}
		adj.assign(adj.size(), {});
		for (int i = 0; i < ssize(edges); i++) _addAdj(i);
		return *this;
	}

	Graph& permutate() {
		vector<int> perm(n());
		iota(begin(perm), end(perm), 0);
		ranges::shuffle(perm, Random::rng);
		for (auto& e : edges) {
			e.from = perm[e.from];
			e.to = perm[e.to];
		}
		shuffle();
		return *this;
	}

	template<typename F>
	void forEdges(F&& f) {
		for (auto e : edges) e.forE(f);
	}

	template<typename F>
	void forOut(int x, F&& f) {
		for (auto [_, id] : adj[x]) edges[id].forE(x, f);
	}

	Graph& tree() {
		if (DIR) cerr << "randomTree must be undirected" << FAIL;
		if (n() <= 1) return *this;
		auto code = Random::integers<int>(n()-2, 0, n());
		vector<int> count(n());
		for (int x : code) count[x]++;
		int current = -1;
		int skip = -1;
		auto getNext = [&](){
			int oldSkip = skip;
			skip = -1;
			if (0 <= oldSkip and oldSkip <= current) return oldSkip;
			for (current++; count[current] > 0; current++) {}
			return current;
		};
		for (int x : code) {
			addEdge(x,  getNext());
			count[x]--;
			if (count[x] == 0) skip = x;
		}
		addEdge(getNext(), getNext());
		return *this;
	}

	Graph& star() {
		for (int i = 1; i < n; i++) addEdge(0, i);
		return *this;
	}

	Graph& path() {
		for (int i = 1; i < n; i++) addEdge(i-1, i);
		return *this;
	}

	Graph& erdosRenyi(int todo) {//this could be slow...
		if constexpr (!MULTI) {
			ll lim = (ll)n() * (n() - 1) / 2;
			if constexpr (DIR) lim *= 2;
			if constexpr (LOOPS) lim += n;
			lim -= m();
			if (todo > lim) cerr << "too many edges! n: " << n() << " " << todo << " > " << lim << FAIL;
			if (todo > lim / 2) {
				vector<pair<int, int>> tmp;
				if constexpr(LOOPS) {
					for (int i = 0; i < n(); i++) tmp.emplace_back(i, i);
				}
				for (int i = 0; i < n(); i++) {
					for (int j = 0; j < i; j++) {
						tmp.emplace_back(i, j);
						if constexpr (DIR) tmp.emplace_back(j, i);
					}
				}
				if constexpr (!DIR) {
					for (auto& [a, b] : tmp) {
						if (Random::integer<int>(0, 2) == 0) {
							swap(a, b);
						}
					}
				}
				ranges::shuffle(tmp, Random::rng);
				for (auto [a, b] : tmp) {
					if (todo <= 0) break;
					if (addEdge(a, b)) todo--;
				}
				if (todo > 0) cerr << "too many edges!" << FAIL;
				return *this;
			}
		}
		while (todo > 0) {
			int a = Random::integer(0, n());
			int b = Random::integer(0, n());
			if (addEdge(a, b)) todo--;
		}
		return *this;
	}

	friend std::ostream& operator<<(std::ostream& os, const Graph& g) {
		os << g.n() << " " << g.m();
		for (auto& e : g.edges) os << endl << e;
		return os;
	}
};

ld float_error(ld given, ld expected) {
	if (isfinite(given) && isfinite(expected)) {
		ld absDiff = abs(given-expected);
		ld relDiff = abs((given-expected)/expected);
		return min(absDiff, relDiff);
	}
	if (isnan(given) && isnan(expected)) {
		return 0;
	}
	if (isinf(given) && isinf(expected)) {
		return signbit(given) == signbit(expected) ? 0 : numeric_limits<ld>::infinity();
	}
	return numeric_limits<ld>::infinity();
}

#include <ext/pb_ds/assoc_container.hpp>
template<typename T>
using Tree = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>,
                              __gnu_pbds::rb_tree_tag,
                              __gnu_pbds::tree_order_statistics_node_update>;