typedef long long ll;
const ll INF = 1e9;  //表示（值）正无穷，且两个正无穷相加不会溢出
const int NPOS = -1; //表示（下标）不存在

struct Ranker : vector<ll>
{
	void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
	int ask(ll x) const { return lower_bound(begin(), end(), x) - begin(); }
};

struct UnionfindSet : vector<int>
{
	UnionfindSet(int n) : vector<int>(n)
	{
		for (int i = 0; i < n; ++i)
			at(i) = i;
	}
	void merge(int u, int w)
	{
		if (w = ask(w), u = ask(u), w != u)
			at(w) = u;
	}
	int ask(int u) { return at(u) != u ? at(u) = ask(at(u)) : u; }
};

typedef pair<ll, int> pli;
struct Monotone : deque<pli>
{
	void push(const pli &p, int k)
	{
		while (!empty() && back().first >= p.first)
			pop_back();
		for (push_back(p); p.second - front().second >= k;)
			pop_front();
	}
};

/*
//可选优化
#define log2(n) LOG2[n]
struct Log : vector<ll>
{
	Log(int N, ll E) : vector<ll>(N, -1)
	{
		for (int i = 1; i < N; ++i)
			at(i) = at(i / E) + 1;
	}
} LOG2(N, 2);
*/
struct SparseTable
{
	vector<vector<ll>> f;
	SparseTable(const vector<ll> &a) : f(log2(a.size()) + 1, a)
	{
		for (int k = 0; k + 1 < f.size(); ++k)
			for (int i = 0; i + (1 << k) < a.size(); ++i)
				f[k + 1][i] = min(f[k][i], f[k][i + (1 << k)]);
	}
	ll ask(int l, int r)
	{
		int k = log2(r - l + 1);
		return min(f[k][l], f[k][r + 1 - (1 << k)]);
	}
};

struct Fenwick
{
	struct BaseFenwick
	{
		vector<ll> v;
		BaseFenwick(int n) : v(n, 0) {}
		void add(int x, ll w)
		{
			for (; x < v.size(); x += x & -x)
				v[x] += w;
		}
		ll ask(int x)
		{
			ll ans = 0;
			for (; x; x -= x & -x)
				ans += v[x];
			return ans;
		}
	};
	pair<BaseFenwick, BaseFenwick> p;
	Fenwick(int n) : p(n, n) {}
	void add(int x, ll w) { p.first.add(x, w), p.second.add(x, x * w); }
	void add(int l, int r, ll w) { add(l, w), add(r + 1, -w); }
	ll ask(int x) { return (x + 1) * p.first.ask(x) - p.second.ask(x); }
	ll ask(int l, int r) { return ask(r) - ask(l - 1); }
};

struct Fenwick2
{
	struct BaseFenwick2
	{
		vector<Fenwick> v;
		BaseFenwick2(int r, int c) : v(r, c) {}
		void add(int x, int b, int t, ll w)
		{
			for (; x < v.size(); x += x & -x)
				v[x].add(b, t, w);
		}
		ll ask(int x, int b, int t)
		{
			ll ans = 0;
			for (; x; x -= x & -x)
				ans += v[x].ask(b, t);
			return ans;
		}
	};
	pair<BaseFenwick2, BaseFenwick2> p;
	Fenwick2(int r, int c) : p(BaseFenwick2(r, c), BaseFenwick2(r, c)) {}
	void add(int x, int b, int t, ll w) { p.first.add(x, b, t, w), p.second.add(x, b, t, x * w); }
	void add(int l, int b, int r, int t, ll w) { add(l, b, t, w), add(r + 1, b, t, -w); } //(l,b)~(r,t)
	ll ask(int x, int b, int t) { return (x + 1) * p.first.ask(x, b, t) - p.second.ask(x, b, t); }
	ll ask(int l, int b, int r, int t) { return ask(r, b, t) - ask(l - 1, b, t); }
};

struct SegmentTree
{
	struct Seg
	{
		int l, r;
		ll min, max, sum;
		void upd(ll mul, ll add) { min = min * mul + add, max = max * mul + add, sum = sum * mul + add * (r - l + 1); }
		friend Seg operator+(const Seg &lc, const Seg &rc) { return {lc.l, rc.r, std::min(lc.min, rc.min), std::max(lc.max, rc.max), lc.sum + rc.sum}; }
	};
	struct Node : Seg
	{
		int lc, rc;
		ll mul, add;
	};
	vector<Node> v;
	SegmentTree(int l, int r) { build(l, r); }
	void build(int l, int r)
	{
		int rt = v.size();
		v.push_back({});
		v[rt].Seg::operator=({l, r, 0, 0, 0});
		v[rt].lc = v[rt].rc = NPOS;
		v[rt].mul = 1, v[rt].add = 0;
		//if (l < r) //动态开点的时候注释掉本行和下一行
		//down(rt), v[rt].Seg::operator=(v[v[rt].lc] + v[v[rt].rc]);
	}
	void down(int rt)
	{
		int m = v[rt].l + (v[rt].r - v[rt].l >> 1);
		if (v[rt].lc == NPOS)
			v[rt].lc = v.size(), build(v[rt].l, m);
		//else //非可持久化的时候注释掉本行和下一行
		//v.push_back(v[v[rt].lc]), v[rt].lc = v.size() - 1;
		if (v[rt].rc == NPOS)
			v[rt].rc = v.size(), build(m + 1, v[rt].r);
		//else //非可持久化的时候注释掉本行和下一行
		//v.push_back(v[v[rt].rc]), v[rt].rc = v.size() - 1;
		upd(v[v[rt].lc].l, v[v[rt].lc].r, v[rt].mul, v[rt].add, v[rt].lc);
		upd(v[v[rt].rc].l, v[v[rt].rc].r, v[rt].mul, v[rt].add, v[rt].rc);
		v[rt].mul = 1, v[rt].add = 0;
	}
	void upd(int l, int r, ll mul, ll add, int rt = 0)
	{
		if (l <= v[rt].l && v[rt].r <= r)
			return v[rt].mul *= mul, v[rt].add = v[rt].add * mul + add, v[rt].upd(mul, add);
		down(rt);
		if (r <= v[v[rt].lc].r)
			upd(l, r, mul, add, v[rt].lc);
		else if (l >= v[v[rt].rc].l)
			upd(l, r, mul, add, v[rt].rc);
		else
			upd(l, v[v[rt].lc].r, mul, add, v[rt].lc), upd(v[v[rt].rc].l, r, mul, add, v[rt].rc);
		v[rt].Seg::operator=(v[v[rt].lc] + v[v[rt].rc]);
	}
	Seg ask(int l, int r, int rt = 0)
	{
		if (l <= v[rt].l && v[rt].r <= r)
			return v[rt];
		down(rt);
		if (r <= v[v[rt].lc].r)
			return ask(l, r, v[rt].lc);
		if (l >= v[v[rt].rc].l)
			return ask(l, r, v[rt].rc);
		return ask(l, v[v[rt].lc].r, v[rt].lc) + ask(v[v[rt].rc].l, r, v[rt].rc);
	}
};

struct FhqTreap
{
	struct Node
	{
		int ch[2], siz, rev;
		ll key, val, min, add;
		void upd(ll v, int r)
		{
			val += v, min += v, add += v;
			if (r)
				rev ^= 1, swap(ch[0], ch[1]);
		}
	};
	vector<Node> v;
	int root;
	FhqTreap() : v(1), root(0) {}
	void down(int k)
	{
		if (!k)
			return;
		for (int i = 0, *ch = v[k].ch; i < 2; ++i)
			if (ch[i])
				v[ch[i]].upd(v[k].add, v[k].rev);
		v[k].add = v[k].rev = 0;
	}
	void up(int k)
	{
		if (!k)
			return;
		v[k].siz = 1, v[k].min = v[k].val;
		for (int i = 0, *ch = v[k].ch; i < 2; ++i)
			if (ch[i])
				v[k].siz += v[ch[i]].siz, v[k].min = min(v[k].min, v[ch[i]].min);
	}
	int merge(int a, int b)
	{
		if (!a || !b)
			return a + b;
		if (v[a].key < v[b].key)
			return down(a), v[a].ch[1] = merge(v[a].ch[1], b), up(a), a;
		return down(b), v[b].ch[0] = merge(a, v[b].ch[0]), up(b), b;
	}
	void split(int a, int s, int &l, int &r)
	{
		if (!s)
			l = 0, r = a;
		else if (v[v[a].ch[0]].siz < s)
			down(a), split(v[a].ch[1], s - v[v[a].ch[0]].siz - 1, v[a].ch[1], r), up(l = a);
		else
			down(a), split(v[a].ch[0], s, l, v[a].ch[0]), up(r = a);
	}
	void push_back(ll d) { v.push_back(Node{{0, 0}, 1, 0, rand(), d, d, d}), root = merge(root, v.size() - 1); }
	void insert(int x, ll d)
	{
		v.push_back(Node{{0, 0}, 1, 0, rand(), d, d, d});
		int a, b, c;
		split(root, x - 1, a, b), root = merge(merge(a, v.size() - 1), b);
	}
	void erase(int x)
	{
		int a, b, c;
		split(root, x, a, b), split(a, x - 1, a, c), root = merge(a, b);
	}
	Node ask(int l, int r)
	{
		int a, b, c;
		split(root, r, b, c), split(b, l - 1, a, b);
		Node ret = v[b];
		return root = merge(merge(a, b), c), ret;
	}
	void upd(int l, int r, ll add, int rev)
	{
		int a, b, c;
		split(root, r, b, c), split(b, l - 1, a, b), v[b].upd(add, rev), root = merge(merge(a, b), c);
	}
	void revolve(int l, int r, int d)
	{
		int a, b, c, e = r - l + 1;
		split(root, r, b, c), split(b, l - 1, a, b), split(b, (e - d % e) % e, b, e), root = merge(merge(a, merge(e, b)), c);
	}
};

struct FhqTreap
{
	struct Node
	{
		int ch[2], siz;
		ll key, val;
	};
	vector<Node> v;
	int root;
	FhqTreap() : v(1), root(0) {}
	void up(int k) { v[k].siz = v[v[k].ch[0]].siz + v[v[k].ch[1]].siz + 1; }
	int merge(int a, int b)
	{
		if (!a || !b)
			return a + b;
		if (v[a].key < v[b].key)
			return v[a].ch[1] = merge(v[a].ch[1], b), up(a), a;
		return v[b].ch[0] = merge(a, v[b].ch[0]), up(b), b;
	}
	void splitVal(int a, ll w, int &l, int &r) //按值将树划分，使得左子树上的值恰小于w
	{
		if (!a)
			l = r = 0;
		else if (v[a].val > w)
			splitVal(v[a].ch[0], w, l, v[a].ch[0]), up(r = a);
		else
			splitVal(v[a].ch[1], w, v[a].ch[1], r), up(l = a);
	}
	void insert(ll x)
	{
		int a, b;
		v.push_back(Node{{0, 0}, 1, rand(), x}), splitVal(root, x, a, b), root = merge(merge(a, v.size() - 1), b);
	}
	void erase(ll x)
	{
		int a, b, c;
		splitVal(root, x, a, b), splitVal(a, x - 1, a, c), root = merge(merge(a, merge(v[c].ch[0], v[c].ch[1])), b);
	}
	ll kth(int k)
	{
		for (int u = root, ls;;)
		{
			if (ls = v[v[u].ch[0]].siz, ls + 1 == k)
				return v[u].val;
			if (ls < k)
				k -= ls + 1, u = v[u].ch[1];
			else
				u = v[u].ch[0];
		}
	}
	int lower_bound(ll x) { return upper_bound(x - 1); }
	int upper_bound(ll x)
	{
		int a, b, ret;
		return splitVal(root, x, a, b), ret = v[a].siz + 1, root = merge(a, b), ret;
	}
};

struct Mo
{
	struct Query
	{
		int l, r, id;
		bool operator<(const Query &n) const
		{
			return l / BS != n.l / BS ? l < n.l : r < n.r;
		}
	};
	vector<Query> q;
	int L, R;
	void query(int l, int r) { q.push_back(Query{l, r, q.size()}); }
	void rev(int x) {}
	void cal(int id) {}
	void ask()
	{
		L = 0, R = -1;
		sort(q.begin(), q.end());
		for (int i = 0; i < q.size(); ++i)
		{
			while (L < q[i].l)
				rev(L++);
			while (L > q[i].l)
				rev(--L);
			while (R < q[i].r)
				rev(++R);
			while (R > q[i].r)
				rev(R--);
			cal(q[i].id);
		}
	}
};

struct Mo
{
	struct Update
	{
		int pos, NEW, OLD;
	};
	struct Query
	{
		int t, l, r, id;
		bool operator<(const Query &n) const
		{
			return l / BS != n.l / BS ? l < n.l : r / BS != n.r / BS ? r < n.r : t < n.t;
		}
	};
	vector<Update> cq;
	vector<Query> q;
	int T, L, R;
	Mo() : cq(1) {}
	void query(int x, int y) { q.push_back(Query{cq.size() - 1, x, y, q.size()}); }
	void update(int x, int y) { cq.push_back(Update{x, y, t[x]}), t[x] = y; }
	void set(int x, int d)
	{
		if (vis[x])
			return rev(x), a[x] = d, rev(x);
		a[x] = d;
	}
	void rev(int x) {}
	void cal(int id) {}
	void ask()
	{
		T = L = 0, R = -1;
		sort(q.begin(), q.end());
		for (int i = 0; i < q.size(); ++i)
		{
			while (T < q[i].t)
				++T, set(cq[T].pos, cq[T].NEW);
			while (T > q[i].t)
				set(cq[T].pos, cq[T].OLD), --T;
			while (L < q[i].l)
				rev(L++);
			while (L > q[i].l)
				rev(--L);
			while (R < q[i].r)
				rev(++R);
			while (R > q[i].r)
				rev(R--);
			cal(q[i].id);
		}
	}
};

struct TreeMo : Graph
{
	struct Query
	{
		int l, r, lca, id;
		bool operator<(const Query &b) const
		{
			return l / BS != b.l / BS ? l < b.l : r < b.r;
		}
	};
	vector<Query> q;
	vector<int> dfp, dfi, dfo;
	UnionFindSet ufs;
	Graph h;
	int L, R;
	TreeMo(int n) : Graph(n), h(n), dfp(n * 2 + 1), dfi(n), dfo(n), ufs(n) {}
	void query(int x, int y)
	{
		h.add(Edge{x, y}), h.add(Edge{y, x});
		q.push_back(Query{0, 0, 0, q.size()});
	}
	void rev(int x) {}
	void cal(int id) {}
	void dfs(int u, int &cnt)
	{
		dfp[dfi[u] = ++cnt] = u;
		for (int i = 0, k, to; i < v[u].a.size(); ++i)
			if (k = v[u].a[i], to = e[k].second, !dfi[to])
				dfs(to, cnt), ufs.merge(u, to);
		dfp[dfo[u] = ++cnt] = u;
		for (int i = 0, k, to, id; i < h.v[u].a.size(); ++i)
			if (k = h.v[u].a[i], id = k / 2, to = h.e[k].second, dfo[to])
			{
				q[id].lca = ufs.fa(to);
				q[id].l = q[id].lca != u ? dfo[u] : dfi[u];
				q[id].r = dfi[to];
			}
	}
	void ask(int root = 1)
	{
		dfs(root, BS = 0), BS = sqrt(BS);
		sort(q.begin(), q.end());
		L = 0, R = -1;
		for (int i = 0; i < q.size(); ++i)
		{
			while (L < q[i].l)
				rev(dfp[L++]);
			while (L > q[i].l)
				rev(dfp[--L]);
			while (R < q[i].r)
				rev(dfp[++R]);
			while (R > q[i].r)
				rev(dfp[R--]);
			if (q[i].lca != dfp[L])
				rev(q[i].lca);
			cal(q[i].id);
			if (q[i].lca != dfp[L])
				rev(q[i].lca);
		}
	}
};

struct CapitalTreeMo : Graph
{
	struct Update
	{
		int pos, NEW, OLD;
	};
	struct Query
	{
		int t, l, r, lca, id;
		bool operator<(const Query &b) const
		{
			return l / BS != b.l / BS ? l < b.l : r / BS != b.r / BS ? r < b.r : t < b.t; //在BZOJ4129上去掉r/BS还快100ms?
		}
	};
	vector<Update> cq;
	vector<Query> q;
	vector<int> dfp, dfi, dfo;
	UnionFindSet ufs;
	Graph h;
	int T, L, R;
	CapitalTreeMo(int n) : cq(1), Graph(n), h(n), dfp(n * 2 + 1), dfi(n), dfo(n), ufs(n) {}
	void query(int x, int y)
	{
		h.add(Edge{x, y}), h.add(Edge{y, x});
		q.push_back(Query{cq.size() - 1, 0, 0, 0, q.size()});
	}
	void update(int x, int y)
	{
		cq.push_back(Update{x, y, t[x]}), t[x] = y;
	}
	void dfs(int u, int &cnt)
	{
		dfp[dfi[u] = ++cnt] = u;
		for (int i = 0, k, to; i < v[u].a.size(); ++i)
			if (k = v[u].a[i], to = e[k].second, !dfi[to])
				dfs(to, cnt), ufs.merge(u, to);
		dfp[dfo[u] = ++cnt] = u;
		for (int i = 0, k, to, id; i < h.v[u].a.size(); ++i)
			if (k = h.v[u].a[i], id = k / 2, to = h.e[k].second, dfo[to])
			{
				q[id].lca = ufs.fa(to);
				q[id].l = q[id].lca != u ? dfo[u] : dfi[u];
				q[id].r = dfi[to];
			}
	}
	void set(int u, int d)
	{
		if (vis[u])
			return rev(u), a[u] = d, rev(u);
		a[u] = d;
	}
	void rev(int u) {}
	void cal(int id) {}
	void ask(int root = 1)
	{
		dfs(root, BS = 0), BS = sqrt(BS);
		sort(q.begin(), q.end());
		T = L = 0, R = -1;
		for (int i = 0; i < q.size(); ++i)
		{
			while (T < q[i].t)
				++T, set(cq[T].pos, cq[T].NEW);
			while (T > q[i].t)
				set(cq[T].pos, cq[T].OLD), --T;
			while (L < q[i].l)
				rev(dfp[L++]);
			while (L > q[i].l)
				rev(dfp[--L]);
			while (R < q[i].r)
				rev(dfp[++R]);
			while (R > q[i].r)
				rev(dfp[R--]);
			if (q[i].lca != dfp[L])
				rev(q[i].lca);
			cal(q[i].id);
			if (q[i].lca != dfp[L])
				rev(q[i].lca);
		}
	}
};

struct HashString : Mod
{
	vector<ll> f, p;
	HashString(const string &s, ll M = 1e9 + 7, ll P = 131) : Mod(M), f(s.size() + 1), p(s.size() + 1, 1)
	{
		for (int i = 0; i < s.size(); ++i)
		{
			f[i + 1] = add(mul(f[i], P), s[i]);
			p[i + 1] = mul(p[i], P);
		}
	}
	ll ask(int pos, int len) { return add(f[pos + len], -mul(f[pos], p[len])); } //从pos位置开始的长度为len的子串的hash值
};

struct KMP
{
	vector<int> next;
	string pattern;
	KMP(const string &pattern) : pattern(pattern), next(pattern.size() + 1, -1)
	{
		for (int i = 0, j = -1; i < pattern.size();)
		{
			if (j == -1 || pattern[i] == pattern[j])
				next[++i] = ++j;
			else
				j = next[j];
		}
	}
	int find_in(const string &text)
	{
		for (int i = 0, j = 0;;)
		{
			if (j == pattern.size())
				return i - j; //不return可得到所有匹配地址
			if (i == text.size())
				return -1;
			if (j == -1 || text[i] == pattern[j])
				++i, ++j;
			else
				j = next[j];
		}
	}
};

struct AhoCorasick
{
	struct Node
	{
		int ch[26], val, f, last;
		int &to(char c)
		{
			return ch[c - 'a'];
		} //如果不确定c的范围，使用map
	};
	vector<Node> v;
	AhoCorasick() : v(1) {}
	void getFail()
	{
		for (deque<int> q(1, v[0].last = v[0].f = 0); !q.empty(); q.pop_front())
			for (char c = 'a'; c <= 'z'; ++c)
			{
				int r = q.front(), u = v[r].to(c), w = v[r].f;
				if (!r && u)
				{
					q.push_back(u);
					v[u].f = v[u].last = 0;
					continue;
				}
				if (!u)
				{
					v[r].to(c) = v[w].to(c);
					continue;
				}
				q.push_back(u);
				while (w && !v[w].to(c))
					w = v[w].f;
				v[u].f = v[w].to(c);
				v[u].last = v[v[u].f].val ? v[u].f : v[v[u].f].last;
			}
	}
	void add(const string &s, int val, int u = 0)
	{
		for (int i = 0; i < s.size(); u = v[u].to(s[i++]))
			if (!v[u].to(s[i]))
			{
				v[u].to(s[i]) = v.size();
				v.push_back(Node());
			}
		v[u].val = val;
	}
	bool find_in(const string &s, int u = 0) //调用需要调用`getFail()`生成失配函数。
	{
		for (int i = 0; i < s.size(); ++i)
			if (u = v[u].to(s[i]),
				v[u].val || v[u].last)
				return 1;
		return 0;
	}
};

int palindrome(const char *s)
{
	int ans = 0;
	for (int i = 0, b, e; s[i]; ++i)
	{
		for (b = i; s[i] == s[i + 1];)
			++i;
		for (e = i + 1; b && s[b - 1] == s[e];)
			--b, ++e;
		if (ans < e - b)
			ans = e - b; //此时[b,e)为最大回文区间
	}
	return ans;
}

struct Manacher
{
	vector<int> t, f, g;
	Manacher(const string &s) : t(s.size() + 1 << 1, 0), f(t), g(t) //t初始值为s中没有出现过的值，g开始为0
	{
		for (int i = 0; i < s.size(); ++i)
			t[i + 1 << 1] = s[i];
		for (int i = 1, p = 0, m = 0; i < t.size(); ++i)
		{
			for (f[i] = i < m ? min(f[2 * p - i], m - i) : 1;
				 0 < i - f[i] && i + f[i] < t.size() &&
				 t[i - f[i]] == t[i + f[i]];)
				++f[i];
			if (m < i + f[i])
				m = i + f[p = i];
		}
		for (int i = 2; i < t.size(); ++i)
			if (g[i - f[i] + 1] < i + 1)
				g[i - f[i] + 1] = i + 1;
		for (int i = 1; i < t.size(); ++i)
			if (g[i] < g[i - 1])
				g[i] = g[i - 1];
	}
	int ask(int l, int r) //多次询问可做一个ST表
	{
		int ans = 0;
		for (int i = l + 1 << 1, e = r + 1 << 1; i <= e; i += 2)
			if (ans < g[i] - i)
				ans = g[i] - i;
		return ans;
	}
};

struct SufArr
{
	vector<int> sa, rk, h;
	SufArr(const vector<int> &s, int m) : sa(s.size(), 0), rk(s), h(s.size(), 0)
	{
		vector<int> cnt(s.size() + m, 0);
		for (int i = 0; i < s.size(); ++i)
			++cnt[rk[i]];
		for (int i = 1; i < m; ++i)
			cnt[i] += cnt[i - 1];
		for (int i = 0; i < s.size(); ++i)
			sa[--cnt[rk[i]]] = i;
		for (int k = 1, j = 0; k <= s.size() && j < s.size() - 1; k <<= 1)
		{
			for (int i = 0; i < s.size(); ++i)
			{
				if (j = sa[i] - k, j < 0)
					j += s.size();
				h[cnt[rk[j]]++] = j;
			}
			cnt[0] = sa[h[0]] = j = 0;
			for (int i = 1; i < s.size(); ++i)
			{
				if (rk[h[i]] != rk[h[i - 1]] || rk[h[i] + k] != rk[h[i - 1] + k])
					cnt[++j] = i;
				sa[h[i]] = j;
			}
			swap(rk, sa), swap(sa, h);
		}
		for (int i = 0, k = 0, j = rk[0]; i < s.size() - 1; ++i, ++k)
			for (; ~k && s[i] != s[sa[j - 1] + k]; j = rk[sa[j] + 1], --k)
				h[j] = k;
	}
};

struct Graph
{
	struct Vertex
	{
		vector<int> o, i;		//相关出边和入边编号
		int siz, dep, top, dfn; //树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
	};
	struct Edge : pair<int, int>
	{
		ll len, cap; //边长、容量，图论算法使用
	};
	vector<Vertex> v; //点集
	vector<Edge> e;   //边集
	Graph(int n) : v(n) {}
	void add(const Edge &ed)
	{
		if (ed.first == ed.second)
			return; //如果有需要请拆点
		v[ed.first].o.push_back(e.size());
		v[ed.second].i.push_back(e.size());
		e.push_back(ed);
	}
	int ch(int u, int i = 0) { return e[v[u].o[i]].second; } //u的第i个孩子节点
	int fa(int u, int i = 0) { return e[v[u].i[i]].first; } //u的第i个父节点
};

struct Dijkstra : Graph
{
	vector<ll> d;
	vector<int> p;
	Dijkstra(int n) : Graph(n) {}
	void ask(int s)
	{
		d.assign(v.size(), INF);
		p.assign(v.size(), e.size());
		priority_queue<pair<ll, int>> q;
		for (q.push(make_pair(d[s] = 0, s)); !q.empty();)
		{
			ll dis = -q.top().first;
			int u = q.top().second;
			if (q.pop(), d[u] < dis)
				continue;
			for (int i = 0, k, to; i != v[u].o.size(); ++i)
				if (k = v[u].o[i], to = e[k].second,
					d[to] > d[u] + e[k].len)
				{
					d[to] = d[u] + e[k].len, p[to] = k;
					q.push(make_pair(-d[to], to));
				}
		}
	}
};

struct BellmanFord : Graph
{
	vector<ll> d;
	vector<int> p;
	BellmanFord(int n) : Graph(n) {}
	bool ask(int s)
	{
		d.assign(v.size(), INF);
		p.assign(v.size(), e.size());
		vector<int> cnt(v.size(), 0), flag(v.size(), d[s] = 0);
		for (deque<int> q(cnt[s] = flag[s] = 1, s); !q.empty(); q.pop_front())
			for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].o.size(); ++i)
				if (k = v[u].o[i], to = e[k].second,
					d[to] > d[u] + e[k].len)
				{
					d[to] = d[u] + e[k].len, p[to] = k;
					if (!flag[to])
					{
						if (v.size() == ++cnt[to])
							return 0;
						flag[to] = 1, q.push_back(to);
					}
				}
		return 1;
	}
};

void floyed(Mat &a, int n) // 其实一般手打即可，没必要套这个鬼模板…
{
	for (int k = 0; k < n; ++k)
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				if (a[i][j] > a[i][k] + a[k][j])
					a[i][j] = a[i][k] + a[k][j];
}