模板

//模板集合
/*class, struct, 函数的第1个花括号不断行, if, for, while等花括号单独一行*/
/*所有private首字母大写, 所有public接口全小写*/
/*变量多个单词不隔开, 函数用下划线隔开, 构造函数形参可用下划线*/
/*指针变量p做前缀, 指针类型typedef为ptr*/
#pragma GCC optimize(3, "inline")
//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double db;
typedef long double ldb;
typedef string str;
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define pre(i, a, b) for(int i = (a); i >= (b); --i)
#define il inline
#define mp make_pair
#define popb pop_back
#define popf pop_front
#define pushb push_back
#define pushf push_front
#define fir first
#define sec second
#define mem(a,b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << '=' << x << ' '
//#define int ll
//#define double ldb
//ifstream is(".in",ios::in);
//ofstream os(".out",ios::out);
//#define cin is
//#define cout os
int n, m;
const int N = 10, M = 10, MOD = 1e9 + 7;
const int base = 10, num_of_digit = 1;//进制
const int INF = 1e9;//极大值
const double eps = 1e-12;
template<typename T> T max(const T a, const T b, const T c) {
	return max(max(a, b), c);
}
template<typename T> T min(const T a, const T b, const T c) {
	return min(min(a, b), c);
}
template<typename T> T gcd(const T a, const T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T> T lcm(const T a, const T b) {
	return a / gcd(a, b) * b;
}
#define lowbit(x)  ((x) & (-(x)))
#define bin(i) (1 << (i))//生成只有第i位为1，其余位为0的数(2^i)
#define set_bit(x, i) ((x) | bin(i))//将第i位设置为1
#define clr_bit(x, i) ((x) & (~ bin(i)))//将第i位设置为0
#define flip_bit(x, i) ((x) ^ bin(i))//反转x的第i位
#define get_bit(x, i) (((x) >> (i)) & 1)//取出x的第i位
#define check_adjacent_1(x) ((x) & ((x) >> 1))//检查是否有相邻的1
int count_bit(int x) {
	int sum = 0;
	while(x != 0)
	{
		x &= (x - 1);//清除最低位的1
		++sum;
	}
	return sum;
}
namespace IO {//快速IO
	#ifndef LOCAL
		constexpr static size_t MAX_BUF_SIZE = 1 << 20;
		static char inbuf[MAX_BUF_SIZE], *inbufptr = inbuf, outbuf[MAX_BUF_SIZE], *outbufptr = outbuf;
		inline char get_char() {
			if(inbufptr == inbuf + MAX_BUF_SIZE)
			{
				size_t len = fread(inbuf, 1, MAX_BUF_SIZE, stdin);
				inbufptr = inbuf;
				if (len == 0) return EOF;
			}
			return *inbufptr++;
		}
		inline void flush() {
			fwrite(outbuf, 1, outbufptr - outbuf, stdout);
			outbufptr = outbuf;
		}
		inline void put_char(const char c) {
			if(outbufptr == outbuf + MAX_BUF_SIZE)
				flush();
			*outbufptr++ = c;
		}
		class Flush {
			public: inline ~Flush() {
				flush();
			}
		} _;
		#define gc() get_char()
		#define pc(x) put_char(x)
	#else
		#define gc() getchar()
		#define pc(x) putchar(x)
	#endif
	inline char read(char &ch) {
		do
			ch = gc(); 
		while(isspace(ch));
		return ch;
	}
	inline void write(const char ch) {
		pc(ch);
	}
	inline string read(string &s) {
		char ch;
		read(ch);
		while(!isspace(ch))
			s.push_back(ch), read(ch);
		return s;
	}
	inline void write(const string s) {
		for(char ch : s)
			pc(ch);
	}
	template<typename t1> inline t1 read(t1 &x) {
		x = 0;
		t1 f = 1;
		char ch = gc();
		while(ch < '0' || '9' < ch)
		{
			if(ch == '-') f = -1;
			ch = gc();
		}
		while('0' <= ch && ch <= '9')
			x = x * 10 + ch - '0', ch = gc();
		return x = x * f;
	}
	template<typename t1> inline void write(t1 x) {
		if(x < 0) x = -x, pc('-');
		short stk[25], top = 0;
		do
			stk[++top] = x % 10, x /= 10;
		while(x > 0);

		while(top)
			pc(stk[top--] + '0');
	}
	template<typename t1, typename ...t2> inline void read(t1 &x, t2 &...y) {
		read(x), read(y...);
	}
	template<typename t1, typename ...t2> inline void write(t1 x, t2 ...y) {
		write(x), pc(' '), write(y...), pc(' ');
	}
} using namespace IO;
class STL {
	int a;
	void Vector() {
		vector<int> v(N, -1);
		v.begin(), v.end(), v.front(), v.back();//首尾迭代器, 元素
		v.push_back(a), v.pop_back();//在末尾加入, 删除
		v.size();//当前长度
		v.empty();//true为空, false不空
		v.clear();//清空
		v.insert(v.begin() + 1, 1), v.erase(v.begin());//在指定位置插入, 删除
		sort(v.begin(), v.end());
	}
	void Queue() {
		queue<int> q;
		q.front(), q.back();//首尾元素
		q.push(a), q.pop();//从末尾加入, 删除
		q.size();//当前长度
		q.empty();//true为空, false不空
	}
	void Stack() {
		stack<int> st;
		st.top();//栈顶元素
		st.push(a), st.pop();//从栈顶加入, 弹出
		st.size();//当前长度
		st.empty();//true为空, false不空
	}
	void Priority_queue() {
		priority_queue<int> p;
		priority_queue<int, vector<int>, greater<int> > q;
		p.top();//优先级最大元素
		p.push(a), p.pop();//加入元素, 删除优先级最大元素
		p.size();//当前长度
		p.empty();//true为空, false不空
	}
	void Deque() {
		deque<int> de;
		de.begin(), de.end(), de.front(), de.back();//首尾迭代器, 元素
		de.push_front(a), de.pop_front();//从队头入队, 出队
		de.push_back(a), de.pop_back();//从队尾入队, 出队
		de.clear();//清空
	}
	void Set() {
		set<int> s;
		s.empty();//true为空, false不空
		s.size();//元素个数
		s.clear();//清空
		s.begin(), s.end();//首尾迭代器
		s.insert(a), s.erase(a);//加入, 删除a
		s.find(a);//返回指向a的迭代器, 不存在返回end()
		s.lower_bound(a), s.upper_bound(a);//返回集合中第1个 >= , > 关键字的元素
	}
	void Bitset() {
		bitset<100> b;
		b.count();//1的个数
		b.any(), b.none();//如果全都为0, any返回0, none返回1
		//如果有1个1, any返回1, none返回0
		b.set(), b.reset(), b.flip();//全部置为1, 0, 全部取反
		b.set(a, 1), b.reset(a), b.flip(a);//把a位置置为1, 0, 取反
	}
	void Map() {
		map<int, int> mapp, mapp1;
		mapp.begin(), mapp.end();//首尾迭代器
		mapp.insert(pair<int, int>(1, 1));//插入
		mapp.find(a);//返回键是a的映射的迭代器
		mapp.clear();//清空
		mapp.erase(a);//删除1个元素
		mapp.erase(mapp.begin(), mapp.end());//删区间
		mapp.size();//长度
		mapp.empty();//true为空, false不空
		swap(mapp, mapp1);//交换
	}
};
template<typename T = int> class chain_forward_star {//链式前向星
  public:
	struct edge {
		int v, nxt;//终点, 下一条边的编号
		T w;//权值
	} e[M << 1];
	int head[N], idx;
	chain_forward_star() {
		clear();
	}
	void clear() {
		idx = 0;
		memset(head, -1, sizeof head);
	}
	void add_edge(const int u, const int v, const T w = 1) {//加边
		e[++idx] = {v, head[u], w};
		head[u] = idx;
	}
};
class union_find {//并查集
  private:
	int fa[N], size[N];
  public:
	union_find() {
		clear();
	}
	void clear(const int n_ = N - 1) {//清空
		for(int i = 0; i <= n_; ++i)
			fa[i] = i, size[i] = 1;
	}
	int find(const int x) {//找最大祖先
		return x == fa[x] ? x : fa[x] = find(fa[x]);
	}
	bool merge(int x, int y) {//合并, true成功, false失败
		x = find(x), y = find(y);
		if(x == y) return false;
		if(size[x] < size[y]) swap(x, y);
		fa[y] = x;
		size[x] += size[y];
		size[y] = 0;
		return true;
	}
	bool query(const int x, const int y) {//查是否在同一集合
		return find(x) == find(y);
	}
	int get_size(const int x) {//查所在集合大小
		return size[find(x)];
	}
};
class binary_index_tree {//树状数组
  private:
	int t[N];
  public:
	binary_index_tree() {
		clear();
	}
	void clear() {
		memset(t, 0, sizeof t);
	}
	void add(int x, const int v) {//将x的位置加上v
		while(x <= n)
			t[x] += v, x += lowbit(x);
	}
	int sum(int x) const {//1 ~ x的和
		int res = 0;
		while(x != 0)
			res += t[x], x -= lowbit(x);
		return res;
	}
	int query(const int l, const int r) const {//查询l ~ r区间和
		return sum(r) - sum(l - 1);
	}
};
class Int {//高精度
  public:
	int d[N];
	Int(int x = 0) {
		clear();
		do d[++d[0]] = x % base, x /= base; while(x != 0);
	}
	Int(string s) {
		clear();
		d[0] = 1;
		int lens = s.size();
		for(int r = lens - 1, l = 0; r >= 0; r = l - 1)
		{
			l = r - num_of_digit + 1;
			if(l < 0) l = 0;
			for(int i = l; i <= r; ++i)
				d[d[0]] = (d[d[0]] * 10) + (s[i] - '0');
			++d[0];
		}
		--d[0];
	}
	void clear() {
		memset(d, 0, sizeof d);
	}
	Int operator + (const Int b) const {
		Int c;
		c.d[0] = max(d[0], b.d[0]);
		for(int i = 1; i <= c.d[0]; ++i)
		{
			c.d[i] += d[i] + b.d[i];
			c.d[i + 1] += c.d[i] / base;
			c.d[i] %= base;
		}
		if(c.d[c.d[0] + 1] != 0) ++c.d[0];
		return c;
	}
	Int operator - (const Int b) const {
		Int c;
		c.d[0] = max(d[0], b.d[0]);
		int num = 0;//借位
		for(int i = 1; i <= c.d[0]; ++i)
		{
			c.d[i] = d[i] - b.d[i] - num;
			if(c.d[i] < 0)
				c.d[i] += base, num = 1;
			else num = 0;
		}
		while(c.d[0] > 1 && c.d[c.d[0]] == 0)
			--c.d[0];
		return c;
	}
	Int operator * (const Int b) const {
		Int c;
		c.d[0] = d[0] + b.d[0];
		for(int i = 1; i <= d[0]; ++i)
			for(int j = 1; j <= b.d[0]; ++j)
			{
				c.d[i + j - 1] += d[i] * b.d[j];
				c.d[i + j] += c.d[i + j - 1] / base;
				c.d[i + j - 1] %= base;
			}
		while(c.d[0] > 1 && c.d[c.d[0]] == 0)
			--c.d[0];
		return c;
	}
	Int operator / (const int k) const {
		Int c;
		c.d[0] = d[0];
		int x = 0;
		for(int i = d[0]; i >= 1; --i)
		{
			x = x * base + d[i];
			c.d[i] = x / k;
			x %= k;
		}
		while(c.d[0] > 1 && c.d[c.d[0]] == 0)
			--c.d[0];
		return c;
	}
	int operator % (const int k) const {
		int x = 0;
		for(int i = d[0]; i >= 1; --i)
			x = (x * base + d[i]) % k;
		return x;
	}
	Int operator ^ (int b) const {
		Int res = 1, a = *this;
		while(b != 0)
		{
			if((b & 1) == 1)
				res = res * a;
			a = a * a;
			b >>= 1;
		}
		return res;
	}
	friend istream& operator >> (istream &in, Int &a) {
		string s;
		in >> s;
		a = s;
		return in;
	}
	friend ostream& operator << (ostream &out, Int &a) {
		while(a.d[0] > 1 && a.d[a.d[0]] == 0)
			--a.d[0];
		out << a.d[a.d[0]];
		for(int i = a.d[0] - 1; i >= 1; --i)
			out << setfill('0') << setw(num_of_digit) << a.d[i];
		return out;
	}
};
bool operator == (const Int a, const Int b) {
	if(a.d[0] != b.d[0]) return false;
	for(int i = a.d[0]; i >= 1; --i)
		if(a.d[i] != b.d[i]) return false;
	return true;
}
bool operator != (const Int a, const Int b) {
	return !(a == b);
}
bool operator < (const Int a, const Int b) {
	if(a.d[0] != b.d[0]) return a.d[0] < b.d[0];
	for(int i = a.d[0]; i >= 1; --i)
		if(a.d[i] != b.d[i]) return a.d[i] < b.d[i];
	return false;
}
bool operator > (const Int a, const Int b) {
	return b < a;
}
bool operator <= (const Int a, const Int b) {
	return !(a > b);
}
bool operator >= (const Int a, const Int b) {
	return !(a < b);
}
Int sqrt(Int a, int b) {//a的b次方根(取整)
	Int l = 0, r = a, ans;
	while(l <= r)
	{
		Int mid = (l + r) / 2;
		if(mid.d[0] * b - b + 1 <= a.d[0] && (mid ^ b) <= a)//mid最少的位数 <= a的位数
			l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	return ans;
}
Int gcd(Int a, Int b) {//高精gcd
	if(a < b) swap(a, b);
	int r = 0;//2的次数
	while(b > 0)
	{
		if(a.d[1] % 2 == 0 && b.d[1] % 2 == 0)
			a = a / 2, b = b / 2, ++r;
		else if(a.d[1] % 2 == 0 && b.d[1] % 2 != 0)
			a = a / 2;
		else if(a.d[1] % 2 != 0 && b.d[1] % 2 == 0)
			b = b / 2;
		else a = (a - b) / 2;
		if(a < b) swap(a, b);
	}
	for(int i = 1; i <= r; ++i)
		a = a * 2;
	return a;
}
class matrix {//矩阵
  public:
	ll a[N][N];
	ll n, m;//行数, 列数
	matrix(const int n_, const int m_): n(n_), m(m_) {
		clear();
	}
	void clear() {
		memset(a, 0, sizeof a);
	}
	matrix operator + (const matrix B) const {
		matrix res(n, m);
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= m; ++j)
				res.a[i][j] = a[i][j] + B.a[i][j];
		return res;
	}
	matrix operator - (const matrix B) const {
		matrix res(n, m);
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= m; ++j)
				res.a[i][j] = a[i][j] - B.a[i][j];
		return res;
	}
	matrix operator * (const int k) const {
		matrix res(n, m);
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= m; ++j)
				res.a[i][j] = a[i][j] * k;
		return res;
	}
	matrix operator * (const matrix B) const {
		matrix res(n, B.m);
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= B.m; ++j)
				for(int k = 1; k <= m; ++k)
					res.a[i][j] += a[i][k] * B.a[k][j];
		return res;
	}
	friend istream& operator >> (istream &in, matrix &A) {
		for(int i = 1; i <= A.n; ++i)
			for(int j = 1; j <= A.m; ++j)
				in >> A.a[i][j];
		return in;
	}
	friend ostream& operator << (ostream &out, matrix &A) {
		for(int i = 1; i <= A.n; ++i)
		{
			for(int j = 1; j <= A.m; ++j)
				out << A.a[i][j] << ' ';
			out << '\n';
		}
		return out;
	}
};
matrix qpow(const matrix A, ll b) {//矩阵快速幂
	matrix res = A, k = A;
	b--;
	while(b != 0)
	{
		if((b & 1) == 1)
			res = res * k;
		k = k * k;
		b >>= 1;
	}
	return res;
}
template<typename T> class sparse_table {//st表
  private:
	T st[N][32];//st[i][j]表示以i为起点, (2^j) - 1为长度的区间最大值
	int Log2[N];//卡常
  public:
	sparse_table(const int n_ = N - 1) {
		clear();
		Log2[0] = Log2[1] = 0;
		for(int i = 2; i <= n_; ++i)
			Log2[i] = Log2[i >> 1] + 1;
	}
	void clear() {
		memset(st, 0, sizeof st);
	}
	void build_st(const T *a) {
		for(int i = 1; i <= n; ++i)
			st[i][0] = a[i];

		for(int i = 1; i <= Log2[n]; ++i)//枚举区间长度
			for(int j = 1; j + ((1 << i) - 1) <= n; ++j)
				st[j][i] = max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
	}
	T query(const int l, const int r) {
		const int k = Log2[r - l + 1];
		return max(st[l][k], st[r - (1 << k) + 1][k]);
	}
};
template<typename T> class segment_tree {//线段树
  private:
	#define mid ((l + r) >> 1)
	#define ls (p << 1)
	#define rs (p << 1 | 1)
	struct node {
		T sum, maxval, minval, addtag, multag, covtag;
		T lmax, rmax, maxn;//最大子段和
		node(): sum(0), maxval(-INF), minval(INF), addtag(0), multag(1), covtag(-INF), lmax(0), rmax(0), maxn(0) {}
		node operator + (const node &b) const {
			node res;
			res.sum = sum + b.sum;
			res.maxval = max(maxval, b.maxval);
			res.minval = min(minval, b.minval);
			res.lmax = max(lmax, sum + b.lmax);
			res.rmax = max(rmax + b.sum, b.rmax);
			res.maxn = max(maxn, b.maxn, rmax + b.lmax);
			return res;
		}
	} t[N << 2];
  public:
	void build_tree(const int p, const int l, const int r, const T *a) const {//建树
		if(l == r)
		{
			t[p].sum = a[l];
			t[p].maxval = a[l];
			t[p].minval = a[l];
			t[p].lmax = a[l];
			t[p].rmax = a[l];
			t[p].maxn = a[l];
			return;
		}
		build_tree(ls, l, mid, a);
		build_tree(rs, mid + 1, r, a);
		t[p] = t[ls] + t[rs];
	}
	void modify(const int p, const int l, const int r, const int x, const int y, const T v, const int flag) const {//区间加, 乘, 覆盖(1, 2, 3)
		if(r < x || y < l) return;
		if(x <= l && r <= y)
		{
			if(flag == 1) Apply_add(p, l, r, v);
			if(flag == 2) Apply_mul(p, v);
			if(flag == 3) Apply_cov(p, l, r, v);
			return;
		}
		Push_down(p, l, r);
		if(x <= mid) modify(ls, l, mid, x, y, v, flag);
		if(y > mid) modify(rs, mid + 1, r, x, y, v, flag);
		t[p] = t[ls] + t[rs];
	}
	void modify_add(const int x, const int y, const T v) const {
		modify(1, 1, n, x, y, v, 1);
	}
	void modify_mul(const int x, const int y, const T v) const {
		modify(1, 1, n, x, y, v, 2);
	}
	void modify_cov(const int x, const int y, const T v) const {
		modify(1, 1, n, x, y, v, 3);
	}
	node query(const int p, const int l, const int r, const int x, const int y) const {
		if(x <= l && r <= y) return t[p];
		Push_down(p, l, r);
		if(y <= mid) return query(ls, l, mid, x, y);
		if(x > mid) return query(rs, mid + 1, r, x, y);
		return query(ls, l, mid, x, y) + query(rs, mid + 1, r, x, y);
	}
  private:
	void Apply_add(const int p, const int l, const int r, const T v) const {
		t[p].sum += (r - l + 1) * v;
		t[p].addtag += v;
		t[p].maxval += v;
		t[p].minval += v;
	}
	void Apply_mul(const int p, const T v) const {
		t[p].multag *= v;
		t[p].addtag *= v;
		t[p].sum *= v;
		t[p].maxval *= v;
		t[p].minval *= v;
	}
	void Apply_cov(const int p, const int l, const int r, const T v) const {
		t[p].covtag = v;
		t[p].sum = (r - l + 1) * v;
		t[p].maxval = v;
		t[p].minval = v;
		t[p].addtag = 0;
		t[p].multag = 1;
	}
	void Push_down(const int p, const int l, const int r) const {
		if(t[p].covtag != -INF)
		{
			Apply_cov(ls, l, mid, t[p].covtag);
			Apply_cov(rs, mid + 1, r, t[p].covtag);
			t[p].covtag = -INF;
		}
		if(t[p].multag != 1)
		{
			Apply_mul(ls, t[p].multag);
			Apply_mul(rs, t[p].multag);
			t[p].multag = 1;
		}
		if(t[p].addtag != 0)
		{
			Apply_add(ls, l, mid, t[p].addtag);
			Apply_add(rs, mid + 1, r, t[p].addtag);
			t[p].addtag = 0;
		}
	}
	#undef mid
	#undef ls
	#undef rs
};
template<typename T> class dynamic_segment_tree {//动态开点线段树
  private:
 	#define mid ((l + r) >> 1)
	#define ls t[p].lson
	#define rs t[p].rson
	int root, cnt;
	struct node {
		int lson, rson;
		T sum, maxval, minval, addtag, multag, covtag;
		T lmax, rmax, maxn;
		node(): sum(0), maxval(-INF), minval(INF), addtag(0), multag(1), covtag(-INF), lson(0), rson(0), lmax(0), rmax(0), maxn(0) {}
		node operator + (const node &b) const {
			node res;
			res.sum = sum + b.sum;
			res.maxval = max(maxval, b.maxval);
			res.minval = min(minval, b.minval);
			res.lmax = max(lmax, sum + b.lmax);
			res.rmax = max(rmax + b.sum, b.rmax);
			res.maxn = max(maxn, b.maxn, rmax + b.lmax);
			return res;
		}
	} t[N << 2];
  public:
	dynamic_segment_tree() {
		cnt = root = 1;
	}
	void modify(const int p, const int l, const int r, const int x, const int y, const T v, const int flag) const {
		if(r < x || y < l) return;
		if(x <= l && r <= y)
		{
			if(flag == 1) Apply_add(p, l, r, v);
			if(flag == 2) Apply_mul(p, v);
			if(flag == 3) Apply_cov(p, l, r, v);
			return;
		}
		Push_down(p, l, r);
		if(x <= mid) modify(ls, l, mid, x, y, v, flag);
		if(y > mid) modify(rs, mid + 1, r, x, y, v, flag);
		t[p] = t[ls] + t[rs];
	}
	void modify_add(const int x, const int y, const T v) const {
		modify(root, 1, n, x, y, v, 1);
	}
	void modify_mul(const int x, const int y, const T v) const {
		modify(root, 1, n, x, y, v, 2);
	}
	void modify_cov(const int x, const int y, const T v) const {
		modify(root, 1, n, x, y, v, 3);
	}
	node query(const int p, const int l, const int r, const int x, const int y) const {
		if(x <= l && r <= y) return t[p];
		Push_down(p, l, r);
		if(y <= mid) return query(ls, l, mid, x, y);
		if(x > mid) return query(rs, mid + 1, r, x, y);
		return query(ls, l, mid, x, y) + query(rs, mid + 1, r, x, y);
	}
  private:
	int New_node() {
		return ++cnt;
	}
	void Apply_add(const int p, const int l, const int r, const T v) const {
		t[p].sum += (r - l + 1) * v;
		t[p].addtag += v;
		t[p].maxval += v;
		t[p].minval += v;
	}
	void Apply_mul(const int p, const T v) const {
		t[p].multag *= v;
		t[p].addtag *= v;
		t[p].sum *= v;
		t[p].maxval *= v;
		t[p].minval *= v;
	}
	void Apply_cov(const int p, const int l, const int r, const T v) const {
		t[p].covtag = v;
		t[p].sum = (r - l + 1) * v;
		t[p].maxval = v;
		t[p].minval = v;
		t[p].addtag = 0;
		t[p].multag = 1;
	}
	void Push_down(const int p, const int l, const int r) const {
		if(ls == 0) ls = New_node();
		if(rs == 0) rs = New_node();
		if(t[p].covtag != -INF)
		{
			Apply_cov(ls, l, mid, t[p].covtag);
			Apply_cov(rs, mid + 1, r, t[p].covtag);
			t[p].covtag = -INF;
		}
		if(t[p].multag != 1)
		{
			Apply_mul(ls, t[p].multag);
			Apply_mul(rs, t[p].multag);
			t[p].multag = 1;
		}
		if(t[p].addtag != 0)
		{
			Apply_add(ls, l, mid, t[p].addtag);
			Apply_add(rs, mid + 1, r, t[p].addtag);
			t[p].addtag = 0;
		}
	}
	#undef mid
	#undef ls
	#undef rs
};
template<typename T> class persistent_segment_tree {//可持久化线段树
  private: 
	int root[N], cnt;
	struct node {
		int lson, rson, data;
	} t[N << 5];
	#define mid ((l + r) >> 1)
	#define ls t[p].lson
	#define rs t[p].rson
	int new_node() {
		return ++cnt;
	}
	int clone(int p) {
		t[new_node()] = t[p];//复制一个新节点
		return cnt;//返回节点编号
	}
  public:
	int build_tree(int l, int r, int *a) {//建树
		int p = new_node();//动态开点
		if(l == r)
		{
			t[p].data = a[l];
			return p;
		}
		ls = build_tree(l, mid, a);
		rs = build_tree(mid + 1, r, a);
		return p; //返回根节点
	}
	int modify(int p, int l, int r, int x, int v) {
		p = clone(p);
		if(l == r)
		{
			t[p].data = v;
			return p;
		}
		if(x <= mid) ls = modify(ls, l, mid, x, v);
		else rs = modify(rs, mid + 1, r, x, v);
		return p;
	}
	int query(int p, int l, int r, int x) {
		if(l == r) return t[p].data;
		if(x <= mid) return query(ls, l, mid, x);
		else return query(rs, mid + 1, r, x);
	}
	#undef mid
	#undef ls
	#undef rs
};
template<typename T> class rotate_treap {//旋转treap
  private:
	#define ls(p) t[p].lson
	#define rs(p) t[p].rson
	int root, cnt;
	struct node {
		int lson, rson;//左右儿子
		T val;//值
		int key, tot, size;//随机优先级, 值的个数, 子树大小
		node(): lson(0), rson(0), val(0), key(0), tot(0), size(0) {}
	} t[N];
  public:
	rotate_treap() {
		Build_treap();
	}
	void insert(int &p, const T val) const {//插入值为val的新节点
		if(p == 0)//子树为空, 新建
		{
			p = New_node(val);
			return;
		}
		if(val == t[p].val)//如果值和当前节点相同
		{
			++t[p].tot;//个数加1
			Push_up(p);//更新子树大小
			return;
		}
		if(val < t[p].val)
		{
			insert(ls(p), val);//要插到左边
			if(t[p].key < t[ls(p)].key)//不满足优先级
				Rotate_r(p);//右旋
		}
		else
		{
			insert(rs(p), val);//要插到右边
			if(t[p].key < t[rs(p)].key)//不满足优先级
				Rotate_l(p);//左旋
		}
		Push_up(p);//更新节点子树大小
	}
	void remove(int &p, const T val) const {//删除1个值为val的节点
		if(p == 0) return;//为空直接返回
		if(val == t[p].val)//找到值为val的节点
		{
			if(t[p].tot > 1)//个数超过一个
			{
				--t[p].tot;//个数减1
				Push_up(p);//更新子树大小
				return;
			}
			if(ls(p) != 0 || rs(p) != 0)//存在子树
			{
				if(rs(p) == 0 || t[ls(p)].key > t[rs(p)].key)
					Rotate_r(p), remove(rs(p), val);//右旋
				else Rotate_l(p), remove(ls(p), val);//左旋
				Push_up(p);//更新子树大小
			}
			else p = 0;//到叶子节点
			return;
		}
		val <= t[p].val ? remove(ls(p), val) : remove(rs(p), val);//递归查找要删除的数的位置
		Push_up(p);//更新节点子树大小
	}
	int get_rank(const int p, const T val) const {//查排名
		if(p == 0) return 0;//节点为空返回0
		if(val == t[p].val) return t[ls(p)].size + 1;//左子树个数 + 1就是排名
		if(val < t[p].val) return get_rank(ls(p), val);//去左子树里面查找
		return get_rank(rs(p), val) + t[ls(p)].size + t[p].tot;//同时左子树个数 + 当前节点个数 <= 他
	}
	T get_val(const int p, const int k) const {//查排名第k的值
		if(p == 0) return INF;//节点为空返回INF
		if(t[ls(p)].size >= k) return get_val(ls(p), k);//向左查找
		if(t[ls(p)].size + t[p].tot >= k) return t[p].val;//当前就是第k大的数
		return get_val(rs(p), k - t[ls(p)].size - t[p].tot);//在右子树里找剩下的
	}
	T get_prev(const T val) const {//查前驱
		T res = -INF;
		int p = root;
		while(p != 0)
		{
			if(val >= t[p].val)
				res = t[p].val, p = rs(p);
			else p = ls(p);
		}
		return res;
	}
	T get_next(const T val) const {//查后继
		T res = INF;
		int p = root;
		while(p != 0)
		{
			if(val <= t[p].val)
				res = t[p].val, p = ls(p);
			else p = rs(p);
		}
		return res;
	}
  private:
	int New_node(const T val) {//创建值为val的新节点
		t[++cnt].val = val;
		t[cnt].key = rand();//随机优先级
		t[cnt].tot = t[cnt].size = 1;
		return cnt;//返回节点编号
	}
	void Push_up(const int p) const {//更新节点子树大小
		t[p].size = t[ls(p)].size + t[ls(p)].size + t[p].tot;
		//节点子树的大小 = 左子树 + 右子树 + 当前节点值的个数
	}
	void Build_treap() const {
		New_node(-INF);
		New_node(INF);
		root = 1, rs(root) = 2;
		Push_up(root);
	}
	void Rotate_r(int &p) const {//右旋
		int q = ls(p);
		ls(p) = rs(q);
		rs(q) = p;
		p = q;
		Push_up(rs(q));
		Push_up(p);
	}
	void Rotate_l(int &p) const {//左旋
		int q = rs(p);
		rs(p) = ls(q);
		ls(q) = p;
		p = q;
		Push_up(ls(p));
		Push_up(p);
	}
	#undef ls
	#undef rs
};
template<typename T> class fhq_treap {//范浩强无旋treap
  private:
	#define ls(p) t[p].lson
	#define rs(p) t[p].rson
	int root, cnt;
	struct node {
		int lson, rson;//左右儿子
		T val;//值
		int key, size;//随机优先级, 子树大小
		node(): lson(0), rson(0), val(0), key(0), size(0) {}
	} t[N];
  public:
	fhq_treap() {
		Build_treap();
	}
	void insert(const T val) const {//插入值为val的节点
		int x, y;
		Split_by_val(root, val, x, y);
		root = Merge(Merge(x, New_node(val)), y);
	}
	void remove(const T val) const {//删除值为val的节点
		int x, y, z;
		Split_by_val(root, val, x, z);//把root树分为x, z两棵树, <= val的为x树, > val的为z树
		Split_by_val(x, val - 1, x, y);//把x树分为x, y两棵树, <= val - 1的为x树, == val的为y树
		y = Merge(ls(y), rs(y));//直接让y树的左右儿子进行合并, 忽略y节点(删除y点)
		root = Merge(Merge(x, y), z);//把x, y合并, 再与原来的z树合并
	}
	int get_rank(const T val) const {//查排名
		int x, y;
		Split_by_val(root, val - 1, x, y);//按val - 1分裂
		int res = t[x].size + 1;//x树大小 + 1就是排名
		root = Merge(x, y);//把x, y树合并, 还原root
		return res;
	}
	T get_val(const int p, const int k) const {//查排名第k
		int tmp = t[ls(p)].size + 1;//当前节点排名 = 左子树节点个数 + 1
		if(tmp == k) return t[p].val;//刚好等于k, 找到了
		if(tmp > k) return get_val(ls(p), k);//在左子树里寻找
		return get_val(rs(p), k - tmp);//已经找到tmp个比他小的, 再找k - tmp
	}
	T get_prev(const T val) const {//查前驱
		int x, y;
		Split_by_val(root, val - 1, x, y);
		T res = get_val(x, t[x].size);//前驱即在x树内排名为size的数值
		root = Merge(x, y);
		return res;
	}
	T get_next(const T val) const {//查后继
		int x, y;
		Split_by_val(root, val, x, y);
		T res = get_val(y, 1);//后继即在y树内排名为1的数值
		root = Merge(x, y);
		return res;
	}
  private:
	int New_node(const T val) {//创建值为val的新节点
		int x = ++cnt;
		ls(x) = rs(x) = 0;
		t[x].size = 1;
		t[x].val = val;
		t[x].key = rand();//随机优先级
		return x;//返回节点编号
	}
	void Build_treap() const {
		New_node(INF);
		New_node(-INF);
		root = 1, rs(root) = 2;
		Push_up(root);
	}
	void Push_up(const int p) const {//更新节点子树大小
		if(p == 0) return;
		t[p].size = t[ls(p)].size + t[rs(p)].size + 1;
	}
	void Split_by_val(const int p, const T k, int &x, int &y) const {//将p子树以按k拆成x和y子树, 其中x中的点 <= k, y中的点 > k
		if(p == 0)
		{
			x = y = 0;//分裂到头了
			return;
		}
		if(t[p].val <= k)//当前节点小, 放x上
		{
			x = p;//x上暂放p子树, 去看p的右子树
			Split_by_val(rs(p), k, rs(p), y);//去看p右子树, 如果有 < key的应保留在p右子树上(最后给x), 否则放在y上
		}
		else
		{
			y = p;
			Split_by_val(ls(p), k, x, ls(p));//去看p左子树, 如果有 >= key的应放在p左子树上(最后给y), 否则放在x上
		}
		Push_up(p);//防止更新0点
	}
	int Merge(const int x, const int y) const {//合并x, y为根的树, x子树的值 <= y子树的值, 返回根节点

		if(x == 0 || y == 0) return x | y;//有1个子树为空返回另一个子树
		if(t[x].key > t[y].key)//x在堆中是在y的上方,而值小于y, 故在y的左上方
		{
			rs(x) = Merge(rs(x), y);//x的右子树和y合并
			Push_up(x);
			return x;
		}
		else//x在y的左下方
		{
			ls(y) = Merge(x, ls(y));//x和y的左子树合并
			Push_up(y);
			return y;
		}
	}
	#undef ls
	#undef rs
};
template<typename T> class remove_heap{//可删堆
  private:
  	priority_queue<T> q1, q2;//q1存现在有的, q2存待删除的
	void update() {
		while(!q1.empty() && !q2.empty() && q1.top() == q2.top())
			q1.pop(), q2.pop();
	}
  public:
	void push(T v) {
		q1.push(v);
	}
	void remove(T v) {
		q2.push(v);
	}
	bool empty() {
		update();
		return q1.empty();
	}
	void clear() {
		while(!q1.empty())
			q1.pop();
		while(!q2.empty())
			q2.pop();
	}
	T top() {
		update();
		return q1.top();
	}
};
template<typename T> class my_list {//双向循环head链表
  private:
	struct node {
		T data;
		node* prev, next;
		node(): data(0), prev(nullptr), next(nullptr) {}
	};
	typedef node* nodeptr;
	nodeptr phead;
	int length;
	nodeptr New_node(const T x) const {
		nodeptr now = new node;
		now->data = x;
		return now;
	}
	void Build_list(nodeptr* pphead) const {
		*pphead = New_node(0);
		(*pphead)->next = *pphead;
		(*pphead)->prev = *pphead;
	}
  public:
	my_list() {
		phead = nullptr;
		Build_list(&phead);
		length = 0;
	}
	~my_list() {
		if(phead == nullptr) return;
		clear();
		delete phead;
		phead = nullptr;
	}
	void clear() const {
		if(phead == nullptr) return;
		nodeptr now = phead->next;
		while(now != phead)
		{
			nodeptr nxt = now->next;
			delete now;
			now = nullptr;
			now = nxt;
		}
	}
	void print() const {
		if(phead == nullptr) return;
		nodeptr now = phead->next;
		while(now != phead)
		{
			cout << now->data << ' ';
			now = now->next;
		}
		cout << '\n';
	}
	void unprint() const {
		if(phead == nullptr) return;
		nodeptr now = phead->prev;
		while(now != phead)
		{
			cout << now->data << ' ';
			now = now->prev;
		}
		cout << '\n';
	}
	void push_back(const T x) {
		if(phead == nullptr) return;
		nodeptr tail = phead->prev;
		nodeptr newnode = New_node(x);
		tail->next = newnode;
		newnode->prev = tail;
		newnode->next = phead;
		phead->prev = newnode;
		++length;
	}
	void pop_back() {
		if(phead == nullptr) return;
		if(phead->next == phead) return;
		nodeptr tail = phead->prev;
		phead->prev = tail->prev;
		phead->prev->next = phead;
		delete tail;
		tail = nullptr;
		--length;
	}
	void push_front(const T x) {
		nodeptr first = phead->next;
		nodeptr newnode = New_node(x);
		phead->next = newnode;
		newnode->prev = phead;
		newnode->next = first;
		first->prev = newnode;
		++length;
	}
	void pop_front() {
		if(phead == nullptr) return;
		if(phead->next == phead) return;
		nodeptr first = phead->next;
		nodeptr second = first->next;
		phead->next = second;
		second->prev = phead;
		delete first;
		first = nullptr;
		--length;
	}
	nodeptr find(const T x) const {
		if(phead == nullptr) return nullptr;
		nodeptr now = phead->next;
		while(now != phead)
		{
			if(now->data == x)
				return now;
			now = now->next;
		}
		return nullptr;
	}
	void insert_front(nodeptr pos, const T x) {//在pos前面插入x
		if(pos == nullptr) return;
		nodeptr posprev = pos->prev;
		nodeptr newnode = New_node(x);
		posprev->next = newnode;
		newnode->prev = posprev;
		newnode->next = pos;
		pos->prev = newnode;
		++length;
	}
	void insert_back(nodeptr pos, const T x) {//在pos后面插入x
		if(pos == nullptr) return;
		nodeptr newnode = new_node(x);
		newnode->prev = pos;
		newnode->next = pos->next;
		pos->next->prev = newnode;
		pos->next = newnode;
		++length;
	}
	void remove(nodeptr pos) {
		if(pos == nullptr) return;
		if(pos == phead) return;
		nodeptr posprev = pos->prev;
		nodeptr posnext = pos->next;
		delete pos;
		pos = nullptr;
		posprev->next = posnext;
		posnext->prev = posprev;
		--length;
	}
	int size() const {
		return length;
	}
	bool empty() const {
		return length > 0 ? true : false;
	}
	int front() const {
		if(phead == nullptr) return INT_MIN;
		return phead->next->data;
	}
	int back() const {
		if(phead == nullptr) return INT_MIN;
		return phead->prev->data;
	}
};
class treap_Pro_Max {//维护了许多信息的treap
	queue<int> trashcan;
	struct Node {
		int lson, rson, size, val, cov, key;
		int rev_tag, cov_tag;
		int sum, lmax, rmax, maxn;
	} t[N];
	int root, cnt;
	int new_node(int k) {
		int x;
		if(!trashcan.empty())//先垃圾篓里面找
			x = trashcan.front(), trashcan.pop();
		else x = ++cnt;
		t[x].lson = t[x].rson = t[x].cov = t[x].rev_tag = t[x].cov_tag = 0;
		t[x].size = 1;
		t[x].val = t[x].sum = t[x].maxn = k;
		t[x].lmax = t[x].rmax = max(0, k);
		t[x].key = rand();//随机优先级
		return x;
	}
	void push_up(int p) {
		if(p == 0) return;
		t[p].size = t[t[p].lson].size + t[t[p].rson].size + 1;
		t[p].sum = t[t[p].lson].sum + t[t[p].rson].sum + t[p].val;
		t[p].lmax = max(t[t[p].lson].lmax, t[t[p].lson].sum + t[p].val + t[t[p].rson].lmax, 0);//与0取最大
		t[p].rmax = max(t[t[p].rson].rmax, t[t[p].rson].sum + t[p].val + t[t[p].lson].rmax, 0);
		t[p].maxn = max(t[p].val, t[p].val + t[t[p].lson].rmax + t[t[p].rson].lmax);
		if(t[p].lson) t[p].maxn = max(t[p].maxn, t[t[p].lson].maxn);
		if(t[p].rson) t[p].maxn = max(t[p].maxn, t[t[p].rson].maxn);
	}
	void apply_rev(int p) {//对以p为根的树反转
		if(p == 0) return ;
		swap(t[p].lson, t[p].rson);
		swap(t[p].lmax, t[p].rmax);
		t[p].rev_tag ^= 1;
	}
	void apply_cov(int p, int c) {//对以p为根的树覆盖
		t[p].val = t[p].cov = c;
		t[p].sum = t[p].size * c;
		t[p].lmax = t[p].rmax = max(0, t[p].sum);
		t[p].maxn = max(c, t[p].sum);
		t[p].cov_tag = 1;
	}
	void push_down(int p) {//下传标记
		if(p == 0) return;
		if(t[p].rev_tag != 0)//有标记
		{
			if(t[p].lson != 0) apply_rev(t[p].lson);
			if(t[p].rson != 0) apply_rev(t[p].rson);
			t[p].rev_tag = 0;//清空
		}
		if(t[p].cov_tag != 0)//有标记
		{
			if(t[p].lson != 0) apply_cov(t[p].lson, t[p].cov);
			if(t[p].rson != 0) apply_cov(t[p].rson, t[p].cov);
			t[p].cov_tag = t[p].cov = 0;//清空
		}
	}
	void trash(int p) {//回收以p为根的子树
		if(p == 0) return;
		trashcan.push(p);
		if(t[p].lson != 0) trash(t[p].lson);//回收左儿子
		if(t[p].rson != 0) trash(t[p].rson);//回收右儿子
	}
	void split_by_rank(int p, int k, int &x, int &y) {//以第k为界限分裂
		if(p == 0)
		{
			x = y = 0;
			return;
		}
		push_down(p);
		if(t[t[p].lson].size + 1 <= k)//左边装不下
		{
			x = p;
			split_by_rank(t[p].rson, k - t[t[p].lson].size - 1, t[p].rson, y);
		}
		else
		{
			y = p;
			split_by_rank(t[p].lson, k, x, t[p].lson);
		}
		push_up(p);
	}
	int merge(int x, int y) {//合并
		if(x == 0 || y == 0) return x + y;
		if(t[x].key <= t[y].key)
		{
			push_down(x);
			t[x].rson = merge(t[x].rson, y);
			push_up(x);
			return x;
		}
		else
		{
			push_down(y);
			t[y].lson = merge(x, t[y].lson);
			push_up(y);
			return y;
		}
	}
	int a[N];
	int build(int l, int r) {//构造a数组的平衡树, 避免一个一个插入
		if(l == r) return new_node(a[l]);
		int mid = (l + r) >> 1;
		return merge(build(l, mid), build(mid + 1, r));
	}
	void insert() {//从pos处插入tot个
		int pos, tot;
		cin >> pos >> tot;
		int x, y;
		split_by_rank(root, pos, x, y);
		for(int i = 1; i <= tot; ++i)
			cin >> a[i];
		x = merge(x, build(1, tot));
		root = merge(x, y);
	}
	void delet() {//从pos处删除tot个
		int pos, tot;
		cin >> pos >> tot;
		int x, y, z;
		split_by_rank(root, pos - 1, x, y);
		split_by_rank(y, tot, y, z);
		trash(y);
		root = merge(x, z);
	}
	void make_same() {//从pos处覆盖tot个c
		int pos, tot, c;
		cin >> pos >> tot >> c;
		int x, y, z;
		split_by_rank(root, pos - 1, x, y);
		split_by_rank(y, tot, y, z);
		apply_cov(y, c);
		root = merge(merge(x, y), z);
	}
	void Reverse() {//从pos起翻转tot个
		int pos, tot;
		cin >> pos >> tot;
		int x, y, z;
		split_by_rank(root, pos - 1, x, y);
		split_by_rank(y, tot, y, z);
		apply_rev(y);
		root = merge(merge(x, y), z);
	}
	void get_sum() {//a到b区间和
		int a, b;
		cin >> a >> b;
		int x, y, z;
		split_by_rank(root, a - 1, x, y);
		split_by_rank(y, b, y, z);
		cout << t[y].sum << '\n';
		root = merge(merge(x, y), z);
	}
	void max_sum() {//最大子段和
		cout << t[root].maxn << '\n';
	}
};
struct Dijkstra {//最短路
	chain_forward_star<> C;
	int dis[N], dis1[N];//距离
	bool vis[N];//标记
	struct node {
		int name, dis;
		bool operator < (const node &x) const {
			return x.dis < dis;
		}
	};
	void dijkstra(int s) {//最短路
		memset(dis, 0x3f, sizeof dis);//初始化最大值
		dis[s] = 0;
		priority_queue<node> pq;
		pq.push({s, 0});
		while(!pq.empty())
		{
			node tmp = pq.top();
			pq.pop();
			int u = tmp.name;
			if(vis[u]) continue;
			vis[u] = true;
			for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
			{
				int v = C.e[i].v, w = C.e[i].w;
				if(dis[u] + w < dis[v])
				{
					dis[v] = dis[u] + w;
					if(!vis[v]) pq.push({v, dis[v]});
				}
			}
		}
	}
	void dijkstra1(int s) {//严格次短路
		memset(dis, 0x3f, sizeof dis);
		memset(dis1, 0x3f, sizeof dis1);
		dis[s] = 0;
		priority_queue<node> pq;
		pq.push({s, 0});
		while(!pq.empty())
		{
			node tmp = pq.top();
			pq.pop();
			int u = tmp.name;
			for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
			{
				int v = C.e[i].v, w = C.e[i].w;
				if(dis[u] + w < dis[v])
				{
					dis1[v] = dis[v];
					dis[v] = dis[u] + w;
					pq.push({v, dis[v]});
					pq.push({v, dis1[v]});
				}
				else
				{
					if(dis[u] + w < dis1[v] && dis[v] != dis[u] + w)
					{
						dis1[v] = dis[u] + w;
						pq.push({v, dis[v]});
						pq.push({v, dis1[v]});
					}
					else if(dis1[u] + w < dis1[v] && dis1[u] + w != dis[v])
					{
						dis1[v] = dis1[u] + w;
						pq.push({v, dis[v]});
						pq.push({v, dis1[v]});
					}
				}
			}
		}
	}
};
struct Math {//数学算法
	ll qpow(ll a, ll b, ll p) {//快速幂
		ll res = 1;
		a %= p;
		while(b != 0)
		{
			if((b & 1) == 1) res = res * a % p;
			a = a * a % p;
			b >>= 1;
		}
		return res;
	}
	ll qmul(ll a, ll b, ll p) {//龟速乘
		ll res = 0;
		a %= p, b %= p;
		while(b != 0)
		{
			if(b & 1) res = (res + a) % p;
			a =  a * 2 % p;
			b >>= 1;
		}
		return res;
	}
	int exgcd(int a, int b, int &x, int &y) {//返回gcd, x, y为ax + by = gcd(a, b)的一组可行解
		if(b == 0)
		{
			x = 1, y = 0;
			return a;
		}
		int gcd = exgcd(b, a % b, x, y);
		int t = x;
		x = y, y = t - a / b * y;
		return gcd;
	}
	void exgcd1(int a, int b, int &x, int &y) {
		if(b == 0) x = 1, y = 0;
		else exgcd1(b, a % b, y, x), y -= a / b * x;
	}
	int fac[N];//阶乘
	int inv[N];//逆元
	ll cata[N];//卡特兰数
	int C(int n, int m, int p) {
		if(m > n) return 0;
		return (fac[n] * inv[fac[m]] % p * inv[fac[n - m]] % p);
	}
	int lucas(int n, int m, int p) {
		if(m == 0) return 1;
		return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
	}
	void work(int p) {
		fac[0] = 1;
		for(int i = 1; i <= n; ++i)
			fac[i] = fac[i - 1] * i % p;
		inv[1] = 1;
		for(int i = 2; i <= n; ++i)
			inv[i] = (p - p / i) * inv[p % i] % p;
		cata[1] = 1;
		for(int i = 2; i <= n; ++i)
			cata[i] = cata[i - 1] * (4 * i - 2) / (i + 1);
	}
	bool notprime[N];
	int prime[N];
	int phi[N];//欧拉函数φ
	int factornum[N], g[N];//因数个数, 临时数组 
	void make() {//线性筛素数
		prime[0] = 0;
		phi[1] = 1;
		notprime[1] = true;
		factornum[1] = 1;
		for(int i = 2; i <= n; ++i)
		{
			if(!notprime[i])
				prime[++prime[0]] = i, phi[i] = i - 1, factornum[i] = 2, g[i] = 1; 
			for(int j = 1; j <= prime[0] && i * prime[j] <= n; ++j)
			{
				notprime[i * prime[j]] = true;
				if(i % prime[j] == 0)
				{
					phi[i * prime[j]] = phi[i] * prime[j];
					g[i * prime[j]] = g[i] + 1;
					factornum[i * prime[j]] = factornum[i] / (g[i] + 1) * (g[i] + 2);
					break;
				}
				phi[i * prime[j]] = phi[i] * phi[j];
				g[i * prime[j]] = 1;
				factornum[i * prime[j]] = factornum[i] * 2;
			}
		}
	}
	void sequence_partitioning() {//数列分块
		int k;
		for(int l = 1, r = 0; l <= n; l = r + 1)
		{
			r = k / l == 0 ? n : min(k / (k / l), n);
			//do other things
		}
	}
	int a[N][N], n, m;
	void gauss_elimination() {//高斯消元 
		m = n + 1;
		for(int i = 1; i <= n; ++i)
		{
			int max_row = i;
			for(int j = i + 1; j <= n; ++j)
				if(fabs(a[j][i]) > fabs(a[max_row][i]))
					max_row = j;
			for(int j = 1; j <= m; ++j)
				swap(a[max_row][j], a[i][j]);
			if(fabs(a[i][i]) < eps)//如果为0, 直接无解
			{
				cout << "No Solution";
				return;
			}
			for(int j = m; j >= 1; --j)//i行系数化1
				a[i][j] /= a[i][i];
			for(int j = 1; j <= n; ++j)
			{
				if(j == i) continue;
				double tmp = a[j][i] / a[i][i];
				for(int k = 1; k <= m; ++k)
					a[j][k] -= a[i][k] * tmp;
			}
		}
		for(int i = 1; i <= n; ++i)
			cout << fixed << setprecision(2) << a[i][m] << '\n';
	}
	ll bsgs(ll a, ll b, ll p) {// a^x === b mod p
		map<ll, ll> hash;//建立hash表
		hash.clear();
		b %= p;
		ll t = (int)sqrt(p) + 1;
		for(int i = 0; i < t; ++i)
			hash[1ll * b * qpow(a, i, p) % p] = i;
		a = qpow(a, t, p);
		if(a == 0) return b == 0 ? 1 : -1;
		for(int i = 0; i <= t; ++i)
		{
			ll val = qpow(a, i, p);
			int j = hash.find(val) == hash.end() ? -1 : hash[val];
			if(j >= 0 && i * t - j >= 0) return i * t - j;
		}
		return -1;
	}
};
struct Least_Common_Ancestors {//最近公共祖先
	chain_forward_star<> C;
	int depth[N];//深度
	int dis[N];//到根节点的距离
	int Log2[N];
	int fa[N][22];//fa[i][j]为i的第(2^j)父亲
	Least_Common_Ancestors(int n_ = N - 1) {
		Log2[0] = Log2[1] = 0;
		for(int i = 2; i <= n_; ++i)
			Log2[i] = Log2[i >> 1] + 1;
	}
	void dfs(int now, int f, int len) {//当前, 父亲, 边的长度
		depth[now] = depth[f] + 1;
		fa[now][0] = f;
		dis[now] = dis[f] + len;
		for(int i = 1; i <= 21; ++i)
			fa[now][i] = fa[fa[now][i - 1]][i - 1];
		for(int i = C.head[now]; i != -1; i = C.e[i].nxt)
		{
			int v = C.e[i].v, w = C.e[i].w;
			if(v == f) continue;
			dfs(v, now, w);
		}
	}
	int lca(int x, int y) {//最近公共祖先
		if(x == y) return x;
		if(depth[x] < depth[y]) swap(x, y);
		for(int s = Log2[depth[x] - depth[y]]; s >= 0; --s)//跳到同一层
			if(depth[fa[x][s]] >= depth[y])
				x = fa[x][s];
		if(x == y) return x;
		for(int s = Log2[depth[x]]; s >= 0; --s)//一起向上跳
			if(fa[x][s] != fa[y][s])
				x = fa[x][s], y = fa[y][s];
		return fa[x][0];
	}
	int query(int x, int y) {
		int k = lca(x, y);
		return dis[x] + dis[y] - (dis[k] << 1);
	}
};
struct Difference_Constraint {//差分约束
	chain_forward_star<> C;
	int dis[N];//距离
	int cnt[N];//入队次数
	bool in_queue[N];//是否在队列里
	bool spfa(int s) {//返回true则有负环
		memset(dis, 0x3f, sizeof dis);
		dis[s] = 0;
		queue<int> q;
		q.push(s);
		in_queue[s] = true;
		while(!q.empty())
		{
			int u = q.front();
			q.pop();
			in_queue[u] = false;
			for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
			{
				int v = C.e[i].v, w = C.e[i].w;
				if(dis[v] > dis[u] + w)
				{
					dis[v] = dis[u] + w;
					if(!in_queue[v])
					{
						++cnt[v];
						if(cnt[v] > n + 1) return true;
						q.push(v);
						in_queue[v] = true;
					}
				}
			}
		}
		return false;
	}
};
struct Kruskal {//最小生成树
	struct edge {
		int u, v, w;
		bool operator < (const edge &x) const {
			return w < x.w;
		}
	} e[M];
	union_find U;
	int kruskal() {//-1即失败, 否则返回生成树的权值
		int tot = 0;//已经选了多少条边
		int res = 0;
		sort(e + 1, e + m + 1);
		for(int i = 1; i <= m; ++i)
			if(U.merge(e[i].u, e[i].v))
			{
				res += e[i].w;
				++tot;
				if(tot == n - 1) break;
			}
		if(tot != n - 1) return -1;
		return res;
	}
};
struct Prim {//最小生成树
	chain_forward_star<> C;
	int dis[N];
	bool vis[N];
	struct node {
		int name, dis;
		bool operator < (const node &x) const {
			return x.dis < dis;
		}
	};
	int prim() {//-1即失败, 否则返回生成树大小
		priority_queue<node> pq;
		int res = 0, tot = 0;//生成树边数
		memset(dis, 0x3f, sizeof dis);
		dis[1] = 0;
		pq.push({1, 0});
		while(tot < n && !pq.empty())//边数 = 点数 - 1
		{
			node tmp = pq.top();
			pq.pop();
			int u = tmp.name;
			if(vis[u]) continue;
			vis[u] = true;
			++tot;
			res += tmp.dis;
			for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
			{
				int v = C.e[i].v, w = C.e[i].w;
				if(!vis[v] && dis[v] > w)
				{
					dis[v] = w;
					pq.push({v, w});
				}
			}
		}
		if(tot < n) return -1;//不连通
		return res;
	}
};
struct Hungarian_Algorithm {//二分图最大匹配匈牙利算法
	chain_forward_star<> C;
	int marry[N];
	bool vis[N];
	bool dfs(int u) {
		for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
		{
			int v = C.e[i].v;
			if(vis[v]) continue;
			vis[v] = true;
			if(marry[v] == 0 || dfs(marry[v]))
			{
				marry[v] = u;
				return true;
			}
		}
		return false;
	}
	int find_max_matching() {
		int matching = 0;
		for(int i = 1; i <= n; ++i)
		{
			memset(vis, false, sizeof vis);
			if(dfs(i)) ++matching;
		}
		return matching;
	}
};
struct Topological_Sorting {//拓扑排序
	int in[N];
	int res[N], cnt;
	chain_forward_star<> C;
	Topological_Sorting(): cnt(0) {}
	bool topo() {//返回true有环, 返回false无环
		queue<int> q;
		for(int i = 1; i <= n; ++i)
			if(in[i] == 0)
			{
				q.push(i);
				res[++cnt] = i;
			}
		while(!q.empty())
		{
			int u = q.front();
			q.pop();
			for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
			{
				int v = C.e[i].v;
				--in[v];
				if(in[v] == 0)
				{
					q.push(v);
					res[++cnt] = v;
				}
			}
		}
		if(cnt < n) return true;
		return false;
	}
};
struct Knuth_Morris_Pratt {//kmp字符串匹配
	int n, m;//n = lena, m = lenb
	int fail[N], f[N];
	int res;//a在b中出现的次数
	char a[N], b[N];
	Knuth_Morris_Pratt(): res(0) {}
	void kmp() {
		fail[1] = 0;
		for(int i = 2, j = 0; i <= n; ++i)
		{
			while(j > 0 && a[i] != a[j + 1])
				j = fail[j];
			if(a[i] == a[j + 1]) ++j;
			fail[i] = j;
		}
		for(int i = 1, j = 0; i <= m; ++i)
		{
			while(j > 0 && (j == n || b[i] != a[j + 1]))
				j = fail[j];
			if(b[i] == a[j + 1]) ++j;
			f[i] = j;
			if(f[i] == n) ++res;
		}
	}
};
struct Tarjan_Strong_Connectivity_Component {//强联通分量
	chain_forward_star<> C;
	int dfn[N], low[N], timestamp;
	stack<int> stk;
	bool in_stk[N];
	int scc[N], scc_cnt, scc_size[N];
	Tarjan_Strong_Connectivity_Component(): timestamp(0), scc_cnt(0) {}
	void tarjan(int u) {
		dfn[u] = low[u] = ++timestamp;
		stk.push(u);
		in_stk[u] = true;
		for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
		{
			int v = C.e[i].v;
			if(dfn[v] == 0)
			{
				tarjan(v);
				low[u] = min(low[u], low[v]);
			}
			else if(in_stk[v])
				low[u] = min(low[u], low[v]);
		}
		if(dfn[u] == low[u])
		{
			++scc_cnt;
			while(stk.top() != u)
			{
				scc[stk.top()] = scc_cnt;
				++scc_size[scc_cnt];
				in_stk[stk.top()] = false;
				stk.pop();
			}
			scc[stk.top()] = scc_cnt;
			++scc_size[scc_cnt];
			in_stk[stk.top()] = false;
			stk.pop();
		}
	}
};
struct Tarjan_Cutvtex {//割点
	chain_forward_star<> C;
	int dfn[N], low[N], timestamp;
	bool cutvertex[N];//是否是割点
	int res;//割点数
	Tarjan_Cutvtex(): timestamp(0), res(0) {}
	void tarjan(int u, int fa) {
		dfn[u] = low[u] = ++timestamp;
		int son = 0;
		for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
		{
			int v = C.e[i].v;
			if(dfn[v] == 0)
			{
				++son;
				tarjan(v, u);
				low[u] = min(low[u], low[v]);
				if(fa != u && low[v] >= dfn[u] && son != 0 && !cutvertex[u])
				{
					cutvertex[u] = true;
					++res;
				}
			}
			else if(v != fa)
				low[u] = min(low[u], dfn[v]);
		}
		if(fa == u && son >= 2 && !cutvertex[u])
		{
			cutvertex[u] = true;
			++res;
		}
	}
};
struct Longest_Common_Subsequence {//最长公共子序列
	int dp[N][N], a[N], b[N];
	int f[N], map[N], ans;
	void lcs1() {
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= m; ++j)
				if(a[i] == b[j])
					dp[i][j] = dp[i - 1][j - 1] + 1;
				else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		ans = dp[n][m];
	}
	void lcs2() {
		for(int i = 1; i <= n; ++i)
			map[a[i]] = i;
		for(int i = 1; i <= m; ++i)
			f[i] = 0x3f3f3f3f;
		for(int i = 1; i <= m; ++i)
		{
			int l = 0, r = ans, mid;
			if(map[b[i]] > f[ans])
				f[++ans] = map[b[i]];
			else
			{
				while(l < r)
				{
					mid = (l + r) / 2;
					if(f[mid] > map[b[i]])
						r = mid;
					else l = mid + 1;
				}
				f[l] = min(map[b[i]], f[l]);
			}
		}
	}
};
struct Longest_Increasing_Subsequence {//最长上升子序列
	int a[N], f[N], ans;
	void lis() {
		for(int i = 1; i <= n; ++i)
		{
			int j = lower_bound(f + 1, f + n + 1, a[i]) - f - 1;
			ans = max(ans, j + 1);
			f[j] = a[i];
		}
	}
};
struct Manacher {//马拉车求回文串
	string s, t;
	int ans, p[N];
	void manacher() {
		t = "$#";
		int n = s.size();
		for(int i = 0; i < n; ++i)
		{
			t += s[i];
			t += "#";
		}
		int mr = 0, mid = 0, m = t.size();
		for(int i = 1; i < m; ++i)
		{
			if(mr > i)
				p[i] = min(p[mid * 2 - i], mr - i);
			else p[i] = 1;
			while(t[i + p[i]] == t[i - p[i]])
				++p[i];
			if(mr < p[i] + i)
			{
				mr = p[i] + i;
				mid = i;
			}
			ans = max(ans, p[i]);
		}
		--ans;
	}
};
struct The_Diameter_Of_A_Tree {//树的直径
	chain_forward_star<> C;
	int dis[N];//到u点的距离
	int max_dis;
	int p;//最远点储存在p
	void dfs(int u, int f) {//当前点, 父亲
		for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
		{
			int v = C.e[i].v, w = C.e[i].w;
			if(v == f) continue;
			dis[v] = dis[u] + w;
			if(dis[v] > max_dis)
			{
				max_dis = dis[v];
				p = v;
			}
			dfs(v, u);
		}
	}
	void find_diameter() {//x, y是直径, max_dis为直径的长度
		dfs(1, 0);
		int x = p;
		max_dis = 0;
		dis[p] = 0;
		dfs(x, -1);
		int y = p;
	}
};
struct Divide_And_Conquer_Points {//点分治
	chain_forward_star<> C;
	int sum, root;//子树的大小, 子树的重心
	int dis[N];//某个节点到其子树中节点的距离
	int ask[1010], ans[1010];
	int dp[N], pd[100000010], size[N];
	//dp存储子树的最大不平衡度, pd标记某个距离是否被当前子树覆盖, size存储子树的大小
	int sta[N], top;
	int tmp[N];//临时存储距离值
	int vis[N];
	void get_focus(int u, int f) {//找到以u为根的子树的重心
		dp[u] = 0, size[u] = 1;
		for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
		{
			int v = C.e[i].v;
			if(v == f || vis[v]) continue;
			get_focus(v, u);
			size[u] += size[v];
			dp[u] = max(dp[u], size[v]);
		}
		dp[u] = max(dp[u], sum - size[u]);
		if(dp[u] < dp[root]) root = u;
	}
	void get_dis(int u, int f) {//递归计算u到其子树中所有节点的距离, 并将这些距离存储在sta栈中
		sta[++top] = dis[u];
		for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
		{
			int v = C.e[i].v, w = C.e[i].w;
			if(v == f || vis[v]) continue;
			dis[v] = dis[u] + w;
			get_dis(v, u);
		}
	}
	void calc(int u) {//遍历子树并计算距离, 检查是否存在满足条件的路径
		int c = 0;
		for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
		{
			int v = C.e[i].v, w = C.e[i].w;
			if(vis[v]) continue;
			top = 0, dis[v] = w, get_dis(v, u);
			for(int j = top ; j >= 1; --j)
				for(int k = 1; k <= m; ++k)
					if(ask[k] >= sta[j])
						ans[k] |= pd[ask[k] - sta[j]];
			for(int j = top ; j >= 1; --j)
				tmp[++c] = sta[j], pd[sta[j]] = 1;
		}
		for(int i = 1; i <= c; i++)
			pd[tmp[i]] = 0;
	}
	void solve(int u) {//以u为根的子树, 遍历所有未访问的子树
		vis[u] = pd[0] = 1;
		calc(u);
		for(int i = C.head[u]; i != -1; i = C.e[i].nxt)
		{
			int v = C.e[i].v;
			if(vis[v]) continue;
			dp[0] = INT_MAX, sum = size[v], root = 0;
			get_focus(v, 0), solve(root);
		}
	}
	void work() {
		cin >> n >> m;
		dp[0] = sum = n;
		for(int i = 1, u, v, w; i < n; ++i)
		{
			cin >> u >> v >> w;
			C.add_edge(u, v, w);
			C.add_edge(v, u, w);
		}
		for(int i = 1; i <= m; ++i)
			cin >> ask[i];
		get_focus(1, 0), solve(root);
		for(int i = 1; i <= m; ++i)
			cout << (ans[i] ? "yes\n" : "no\n");
	}
};
struct digitDP {//数位dp
	int a[30];//拆位数组
	int dp[60][60];//记忆化数组,dp[pos]定义为在没有限制没有前导零的情况, 从pos位开始填的答案
	//状态数随题目条件改变, 一般不止一维, 记得初始化为-1
	//pos表示还有几位要填
	//limit表示是否有最高位限制
	//lead表示是否填的数全是前导0, 这里0也会被判成前导0, 不过一般不影响结果
	//st是与题目相关的状态, 数量和名字都依据题目变化
	int dfs(int pos, int st, bool limit, bool lead) {
		if(pos == 0) return 1;//递归到底层, 满足要求就返回1
		if(!limit && !lead && dp[pos][st] != -1)
			return dp[pos][st];//如果发现没有限制, 不全是0且状态搜过则直接返回
		int up = limit ? a[pos] : base - 1;//当前位最高能填多少
		int res = 0;
		for(int i = 0; i <= up; ++i)//一些与题目要求去判断
			res += dfs(pos - 1, st, limit && (i == up), lead && (i == 0));
		return (!limit && !lead) ? dp[pos][st] = res : res;//如果发现没有限制, 不全是0, 则加入记忆化数组
	}
	int calc(int x) {
		if(x == 0) return 1;//特判0
		int len = 0;
		while(x) a[++len] = x % base, x /= base;
		return dfs(len, 0, true, true);
	}
};
class Monotonic_queue {//区间最小值单调队列
  public:
	int k;
	struct node {
		int id, val;
	};
  private:
	node q[N];
	int head, tail;
  public:
	Monotonic_queue(int k_): k(k_), head(1), tail(0) {}
	node front() {
		return q[head];
	}
	node back() {
		return q[tail];
	}
	void push_back(int id, int x) {
		while(head < tail && id - k > q[head].id)
			++head;
		while(head < tail && x <= q[tail].val)
			--tail;
		q[++tail] = {id, x};
	}
};
void merge_sort(int a[], int l, int r) {
	if(l >= r) return;
	int mid = (l + r) >> 1;
	merge_sort(a, l, mid);
	merge_sort(a, mid + 1, r);
	int i = l, j = mid + 1, k = l, tmp[N];
	while(i <= mid && j <= r)
		if(a[i] <= a[j]) tmp[k++] = a[i++];
		else tmp[k++] = a[j++];
	while(i <= mid)
		tmp[k++] = a[i++];
	while(j <= r)
		tmp[k++] = a[j++];
	for(int i = l; i <= r; ++i)
		a[i] = tmp[i]; 
}
//优化, 精简, 改进, 模板化, 改写为class
signed main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	system("taskkill /f /t /im studentmain.exe");
	return 0;
}