///////////        
//                   //      //
//              ////////////////////
//                   //      //
//                 
///////////

//          
//          
//           //     //    ////////     /\     /////////
//           //     //   //      //          //       //
//            ////////   //      //    //    //       //
//                  //   //      //    //    //       //
//////////   ////////    //      //    //     /////////////

#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <stack>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>
#include <numeric>
#include <functional>
//#include <Windows.h>

using namespace std;

#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define pb push_back
#define HashMap unordered_map
#define HashSet unordered_set
#define var auto
#define all(i) i.begin(), i.end()
#define all1(i) i.begin() + 1,i.end()
#define endl '\n'
#define px first
#define py second
#define DEBUG(a) cout<<a<<endl

using VI = vector<int>;
using VL = vector<long long>;
using ll = long long;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
	out << '(' << p.first << ", " << p.second << ')';
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& ve) {
	for (T i : ve)
		out << i << ' ';
	return out;
}

template<class T1, class T2>
ostream& operator<<(ostream& out, const map<T1, T2>& mp) {
	for (auto i : mp)
		out << i << '\n';
	return out;
}

const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int IINF = 0x7fffffff;
const int iinf = 0x80000000;
const ll LINF = 0x7FFFFFFFFFFFFFFF;
const ll linf = 0x8000000000000000;
int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };

//#include "Lynia.h"
namespace MyTools
{
	template <typename T>
	class Math
	{
	public:
		static T gcd(T a, T b)
		{
			return b ? gcd(b, a % b) : a;
		}
		static T lcm(T a, T b)
		{
			return a / gcd(a, b) * b;
		}
		static T exgcd(T a, T b, T& x, T& y)
		{
			if (b == 0)
			{
				x = 1;
				y = 0;
				return a;
			}
			T d = exgcd(b, a % b, x, y);
			T t = x;
			x = y;
			y = t - a / b * y;
			return d;
		}
		static T lowbit(T k)
		{
			return k & (-k);
		}
		static T fastPow(T a, T n, T mod = 1e9 + 7)
		{ // 快速幂
			T ans = 1;
			a %= mod;
			while (n)
			{
				if (n & 1)
					ans = (ans * a) % mod;
				a = (a * a) % mod;
				n >>= 1;
			}
			return ans;
		}
		static T inv(T x, T mod)
		{ // 快速幂求逆
			return fastPow(x, mod - 2, mod);
		}
		static vector<int> highPrecisionAdd(vector<int>& A, vector<int>& B)
		{ // AB倒序输入
			vector<int> C;
			int t = 0; // 进位
			for (int i = 0; i < A.size() || i < B.size(); i++)
			{
				if (i < A.size())
					t += A[i];
				if (i < B.size())
					t += B[i];
				C.push_back(t % 10);
				t /= 10;
			}
			if (t)
				C.push_back(1);
			return C; // 倒序
		}
		static vector<long long> factorCount(int n)
		{ // 计算1-n每个数的因子个数
			vector<long long> factorsCnts(n + 1);
			for (int i = 1; i <= n; i++)
				for (int j = i; j <= n; j += i)
					factorsCnts[j]++;
			return factorsCnts;
		}
		static set<int> factorNumbers(int n)
		{ // 统计n有哪些因子
			set<int> factors;
			for (int i = 1; i <= n / i; i++)
			{
				if (n % i == 0)
				{
					factors.insert(i);
					if (i != n / i)
						factors.insert(n / i);
				}
			}
			return factors;
		}
		static map<int, int> primeFactorsMAP(int n)
		{ // 分解质因数
			map<int, int> mp;
			int m = n;
			for (int i = 2; i <= n / i; i++)
			{
				while (m % i == 0)
				{
					m /= i;
					mp[i]++;
				}
			}
			if (m > 1)
				mp[m]++;
			return mp;
		}
		static set<int> primeFactorsSET(int n)
		{ // 分解质因数
			set<int> se;
			int m = n;
			for (int i = 2; i <= n / i; i++)
			{
				while (m % i == 0)
				{
					m /= i;
					se.insert(i);
				}
			}
			if (m > 1)
				se.insert(m);
			return se;
		}
		static long long C(long long a, long long b, long long mod)
		{
			long ans = 1;
			for (long long i = 1; i <= b; i++)
			{
				ans = ans * (a - i + 1) % mod * fastPow(i, mod - 2, mod) % mod;
			}
			return ans;
		}
		static string decimalToBinary(int n, bool flag = 0)
		{ // flag是否返回倒转 如4:100 4:001
			if (n == 0)
				return "0";
			string binaryNumber = "";
			while (n > 0)
			{
				binaryNumber = to_string(n % 2) + binaryNumber;
				n /= 2;
			}
			if (!flag)
				return binaryNumber;
			else
			{
				reverse(binaryNumber.begin(), binaryNumber.end());
				return binaryNumber;
			}
		}
	};

	class EulerPrime
	{
	public:
		int cnt = 0;
		vector<int> prime;

		EulerPrime(int n)
		{
			prime.assign(n + 1, 0);
			vis.assign(n + 1, 0);
			init(n);
		}

		bool isPrime(int n)
		{
			if (n == 1 || n == 0)
				return 0;
			return !vis[n];
		}

		map<int, int> primeFactorsMAP(int n)
		{ // 分解质因数
			map<int, int> mp;
			int m = n;
			for (int i : prime)
			{
				while (m % i == 0)
				{
					m /= i;
					mp[i]++;
				}
				if (isPrime(m) or m == 1) break;
			}
			if (m > 1)
				mp[m]++;
			return mp;
		}

		vector<int> primeFactorsVEC(int n)
		{ // 欧拉筛优化分解质因数 (防多测用)
			vector<int> se;
			int m = n;
			for (int i : prime)
			{
				if (m % i == 0)se.push_back(i);
				while (m % i == 0)m /= i;
				if (isPrime(m) or m == 1) break;
			}
			if (m > 1)
				se.push_back(m);
			return se;
		}

	private:
		vector<bool> vis;
		void init(int n) // 欧拉筛
		{
			for (int i = 2; i <= n; i++)
			{
				if (!vis[i])
					prime[cnt++] = i;
				for (int j = 0; j < cnt && i * prime[j] <= n; j++)
				{
					vis[i * prime[j]] = 1; // 用最小质因数筛去
					if (i % prime[j] == 0)
						break; // 不是最小质因数
				}
			}
		}
	};

	template <typename T>
	class Combinatorics
	{
	private:
		T mod;

		T inv(T x)
		{ // 快速幂求逆
			return Math<T>::fastPow(x, mod - 2, mod);
		}

		void init(T N)
		{ // 组合数计算初始化
			fac[0] = 1;
			for (T i = 1; i <= N; i++)
				fac[i] = fac[i - 1] * i % mod;
		}

	public:
		vector<T> fac; // 阶乘

		Combinatorics(T N, T mod = 1e9 + 7) : mod(mod)
		{
			fac.assign(N + 1, 0);
			init(N);
		}

		T C(T n, T m)
		{ // 朴素组合数计算
			if (m < 0 || n - m < 0)
				return 0;
			return fac[n] * inv(fac[m]) % mod * inv(fac[n - m]) % mod;
		}

		T lucas(T n, T m)
		{ // 卢卡斯定理
			return m == 0 ? 1 % mod : lucas(n / mod, m / mod) * C(n % mod, m % mod) % mod;
		}

		T Stirling2(ll n, ll m)
		{ // 第二类斯特灵数：将一个有 n 个元素的集合分成 m 个非空的集合，求方案数。
			if (m > n)
				return 0; // n大于m
			ll res = 0;
			for (int i = 0; i <= m; i++)
			{ // 通项公式
				ll p = Math<T>::fastPow(i, n) * inv(fac[i]) % mod * inv(fac[m - i]) % mod;
				if ((m - i) % 2)
					res = (res + mod - p) % mod;
				else
					res = (res + p) % mod;
			}
			return res % mod;
		}
	};

	template <class Info>
	class SegmentTree
	{ // 下标从 1 开始
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)
	protected:
		int n;
		vector<Info> info;

		void init(int _n)
		{
			vector<Info> _now(_n + 1, Info());
			init(_now);
		}
		void init(vector<Info>& _init)
		{
			n = _init.size() - 1;
			info.assign(n << 2, Info()); // 为info开辟大小
			auto build = [&](auto self, int p, int l, int r)
				{
					if (l == r)
					{
						info[p] = _init[l];
						return;
					}
					int mid = l + r >> 1;
					self(self, l(p), l, mid);
					self(self, r(p), mid + 1, r);
					pushup(p);
				};
			build(build, 1, 1, n);
		}
		void pushup(int p)
		{
			info[p] = info[l(p)] + info[r(p)];
		}

	public:
		// 该模板在单点替换的题目中，运算符重载可能会出现一定错误，比如出现了 空值替换有值 (不必要的替换)
		SegmentTree() : n(0) {};
		SegmentTree(int _n)
		{
			init(_n);
		}
		SegmentTree(vector<Info>& _init)
		{
			init(_init);
		}
		template<typename Args> // 万能引用
		void modify(int p, int pl, int pr, int x, Args&& v)
		{
			if (pl == pr)
			{
				// info[p] = v;
				info[p].apply(v);
				return;
			}
			int mid = pl + pr >> 1;
			if (x <= mid)
				modify(l(p), pl, mid, x, v);
			else
				modify(r(p), mid + 1, pr, x, v);
			pushup(p);
		}
		void modify(int p, Info&& v)
		{
			modify(1, 1, n, p, forward<Info>(v)); // 完美转发
		}
		void modify(int p, Info& v)
		{
			modify(1, 1, n, p, forward<Info>(v)); // 完美转发
		}
		Info query(int L, int R, int p, int pl, int pr)
		{
			if (pl > R || pr < L)
				return Info();
			if (L <= pl && pr <= R)
				return info[p];
			int mid = pl + pr >> 1;
			return query(L, R, l(p), pl, mid) + query(L, R, r(p), mid + 1, pr);
		}
		Info query(int L, int R)
		{
			return query(L, R, 1, 1, n);
		}
#undef l(p)
#undef r(p)
	};

	template<class Info, class T>
	class SegmentTree_BinarySearch : SegmentTree<Info> {
#define super SegmentTree<Info>
	public:
		SegmentTree_BinarySearch() : super::n(0) {};
		SegmentTree_BinarySearch(int _n)
		{
			super::init(_n);
		}
		SegmentTree_BinarySearch(vector<Info>& _init)
		{
			super::init(_init);
		}
		int bin_search(int L, int R, const T& v);
		void modify(int p, const Info& v = Info())
		{
			super::modify(p, v);
		}
		Info query(int L, int R)
		{
			return super::query(L, R);
		}
#undef super
	};

	template <class Info, class Tag>
	class LazySegmentTree
	{
		/* 该模板可能在直接相加的情况下比较好用，区间替换可能会出大大小小问题，这里写出区间替换模板
		*  区间替换并求区间和板子
			struct Tag {
				ll newValue = 0;
				bool f = 0;  // 是否进行替换
				Tag() {};
				Tag(ll newValue, bool f = 0) :newValue(newValue), f(f) {};
				void apply(Tag t) {
					if (t.f) { // 这里很重要，因为这个板子初始化的时候就会调用 tag，所以这里上个 f 作为保险
						f = 1;
						newValue = t.newValue;
					}
				}
			};
			struct Info {
				ll value = 0;
				Info() {};
				Info(ll value) :value(value) {};
				void apply(Tag t, int len) {
					if (t.f)
						value = t.newValue * len;
				}
			};
			Info operator+(Info a, Info b) {
				Info c;
				c.value = a.value + b.value;
				return c;
			}

			void solve(int CASE)
			{
				int n; cin >> n;
				auto a = vector<Info>(n + 1, Info());
				fa(i, 1, n) {
					ll now; cin >> now;
					a[i].now = now;
				}

				// 初始化的时候自动会调用所有 Tag
				MT::LazySegmentTree<Info, Tag> sg(a);

				// 查看每个值
				fa(i, 1, n) {
					cout << sg.query(i, i).value << ' ';
				}
				cout << endl;

				int q; cin >> q;
				while (q--) {
					ll l, r, x; cin >> l >> r >> x;
					sg.modifyRange(l, r, Tag(x, 1));

					// 查看更新后的每个值
					fa(i, 1, n)
						cout << sg.query(i, i).value << ' ';
					cout << endl;
				}
				return;
			}
		*/
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)
	protected:
		int n;
		vector<Info> info;
		vector<Tag> tag;

		void init(int _n)
		{
			vector<Info> _now(_n + 1);
			init(_now);
		}
		void init(vector<Info>& _init)
		{
			n = _init.size() - 1;
			info.assign(n << 2, Info()); // 为info开辟大小
			tag.assign(n << 2, Tag());     // 为tag开辟大小
			auto build = [&](auto self, int p, int l, int r)
				{
					if (l == r)
					{
						info[p] = _init[l];
						return;
					}
					int mid = l + r >> 1;
					self(self, l(p), l, mid);
					self(self, r(p), mid + 1, r);
					pushup(p);
				};
			build(build, 1, 1, n);
		}
		void pushup(int p)
		{
			info[p] = info[l(p)] + info[r(p)];
		}
		void apply(int p, const Tag& v, int len)
		{
			info[p].apply(v, len);
			tag[p].apply(v);
		}
		void pushdown(int p, int pl, int pr)
		{ // 传入pl, pr计算区间长度
			int mid = pl + pr >> 1;
			apply(l(p), tag[p], mid - pl + 1);
			apply(r(p), tag[p], pr - mid);
			tag[p] = Tag(); // 设空
		}

	public:
		LazySegmentTree() : n(0) {};
		LazySegmentTree(int _n)
		{
			init(_n);
		}
		LazySegmentTree(vector<Info>& _init)
		{
			init(_init);
		}
		void modify(int p, int pl, int pr, int x, const Info& v = Info())
		{ // 单点修改
			if (pl == pr)
			{
				info[p] = v;
				return;
			}
			int mid = pl + pr >> 1;
			pushdown(p, pl, pr); // 传入pl, pr计算区间长度
			if (x <= mid)
				modify(l(p), pl, mid, x, v);
			else
				modify(r(p), mid + 1, pr, x, v);
			pushup(p);
		}
		void modify(int p, const Info& v = Info())
		{
			modify(1, 1, n, p, v);
		}
		Info query(int L, int R, int p, int pl, int pr)
		{
			if (pl > R || pr < L)
				return Info();
			if (L <= pl && pr <= R)
				return info[p];
			int mid = pl + pr >> 1;
			pushdown(p, pl, pr); // 传入pl, pr计算区间长度
			return query(L, R, l(p), pl, mid) + query(L, R, r(p), mid + 1, pr);
		}
		Info query(int L, int R)
		{
			return query(L, R, 1, 1, n);
		}
		void modifyRange(int L, int R, int p, int pl, int pr, const Tag& v)
		{ // 区间修改
			if (pl > R || pr < L)
				return;
			if (L <= pl && pr <= R)
			{
				apply(p, v, pr - pl + 1); // 传入区间长度
				return;
			}
			int mid = pl + pr >> 1;
			pushdown(p, pl, pr); // 传入pl, pr计算区间长度
			modifyRange(L, R, l(p), pl, mid, v);
			modifyRange(L, R, r(p), mid + 1, pr, v);
			pushup(p);
		}
		void modifyRange(int L, int R, const Tag& v)
		{
			return modifyRange(L, R, 1, 1, n, v);
		}

#undef l(p)
#undef r(p)
	};


	template <class T>
	class List
	{
	private:
		vector<int> l, r;
		map<T, int> pos;
		int cnt = 1, tail = 0;

	public:
		vector<T> value;

		List(int n = 2e5 + 10)
		{ // 预留空间，默认2e6
			value.assign(n * 10, 0);
			l.assign(n * 10, 0);
			r.assign(n * 10, 0);
		}

		void remove(int idx)
		{
			try
			{
				if (tail == 0)
					throw runtime_error("list size is null");
				if (idx > tail)
					throw runtime_error("remove null pos");
			}
			catch (const std::exception& e)
			{
				cerr << e.what() << endl;
			}

			l[r[idx]] = l[idx];
			r[l[idx]] = r[idx];
			tail--;
		}

		void insert(int idx, T val)
		{
			value[cnt] = val;
			pos[val] = cnt;

			// 插入节点
			l[cnt] = idx;
			r[cnt] = r[idx];
			l[r[idx]] = cnt;
			r[idx] = cnt++;

			tail++;
		}

		void push_back(T val)
		{
			value[cnt] = val;
			pos[val] = cnt;

			// 插入节点
			l[cnt] = tail;
			r[cnt] = r[tail];
			l[r[tail]] = cnt;
			r[tail] = cnt++;

			tail++;
		}

		void print_all()
		{
			int k = tail;
			for (int i = r[0]; k; i = r[i])
			{
				cout << value[i] << ' ';
				k--;
			}
		}
	};

	template <typename T>
	class ST
	{
	public:
		static vector<T> Log2;
		/* 构造 st 表前，先在类外定义 Log2，防止多次计算
			template <typename T>
			vector<T> ST<T>::Log2;
		*/

		ST(vector<T>& arr, int MAXN = 1e6 + 10)
		{
			// arr 从 1 开始
			n = arr.size() - 1;
			Min.assign(n + 1, vector<T>(21));
			Max.assign(n + 1, vector<T>(21));
			if (Log2.size() == 0) {
				Log2.resize(MAXN);
				log2_pre(MAXN);
			}
			build(arr);
		}

		T queryMin(int l, int r)
		{ // 查询最小值
			T s = Log2[r - l + 1];
			return min(Min[l][s], Min[r - (1 << s) + 1][s]);
		}

		T queryMax(int l, int r)
		{ // 查询最大值
			T s = Log2[r - l + 1];
			return max(Max[l][s], Max[r - (1 << s) + 1][s]);
		}

	private:
		vector<vector<T>> Min, Max;
		int n;

		void log2_pre(int MAXN)
		{ // 预处理log2
			Log2[0] = -1;
			for (int i = 1; i < MAXN; i++)
			{
				Log2[i] = Log2[i / 2] + 1;
			}
		}

		void build(vector<T>& arr)
		{ // 构建ST表
			for (int i = 1; i <= n; i++)
			{
				Min[i][0] = Max[i][0] = arr[i];
			}
			for (int j = 1; j <= Log2[n]; j++)
			{
				for (int i = 1; i + (1 << j) - 1 <= n; i++)
				{
					Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
					Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
				}
			}
		}
	};

	template <typename T>
	class BitTree
	{ // 树状数组(优化的可操作前缀和)
	public:
		BitTree(int N)
		{
			n = N + 20;
			t.assign(n, 0);
		}

		void update(T idx, const T& k)
		{
			for (T i = idx + 1; i <= n; i += lowbit(i))
				t[i - 1] += k; // 运算符可改
		}

		T getsum(T idx)
		{
			T res = 0;
			for (T i = idx + 1; i > 0; i -= lowbit(i))
				res += t[i - 1]; // 运算符可改
			return res;
		}

		T queryRange(int l, int r)
		{
			return getsum(r) - getsum(l - 1);
		}

	private:
		vector<T> t; // 下标从0开始，实际上就是前缀和数组
		int n;

		T lowbit(T k) { return k & -k; }
	};

	class Manacher
	{
	public:
		vector<int> lengths; // 以每个字符为中心的最长长度回文串的半径
		int max_length = -1; // 最大回文长度

		Manacher(string str)
		{
			int n = str.size();
			init(str, n);
		};

	private:
		void init(string str, int n)
		{
			// build
			string s;
			s.assign(n * 2 + 100, ' ');
			str = ' ' + str;
			int cnt = 0;
			s[++cnt] = '~', s[++cnt] = '#';
			for (int i = 1; i <= n; i++)
				s[++cnt] = str[i], s[++cnt] = '#';
			s[++cnt] = '!';

			// solve
			int mr = 0, mid = 0;
			vector<int> p(n * 2 + 100);
			for (int i = 2; i <= cnt - 1; i++)
			{
				if (i <= mr)
					p[i] = min(p[mid * 2 - i], mr - i + 1);
				else
					p[i] = 1;
				while (s[i - p[i]] == s[i + p[i]])
					++p[i];
				if (i + p[i] > mr)
					mr = i + p[i] - 1, mid = i;

				// 更新最大回文长度
				max_length = max(max_length, p[i]);

				// 放最大回文长度
				if (s[i] != '#' && s[i] != '~' && s[i] != '!')
					lengths.push_back(p[i] - 1);
			}
			max_length--;
		}
	};

	class DoubleHashString
	{
	private:
#define ll long long
#define pll pair<long, long>

		vector<ll> hs1, bs1, hs2, bs2;

		// const int mod1 = 2147483647;
		// const int mod2 = 1000000007;
		// int generateRandomBase(int mod) {
		//      random_device rd;
		//      mt19937 gen(rd());
		//      uniform_int_distribution<> dis(1, mod - 1);
		//      return dis(gen);
		// }
		// const int base1 = generateRandomBase(mod1);
		// const int base2 = generateRandomBase(mod2);

		const int base1 = 233;       // 第一个质数基数
		const int base2 = 131;       // 第二个质数基数
		const ll mod1 = 1e9 + 13;  // 第一个模数
		const ll mod2 = 998244353; // 第二个模数

	public:
		// 初始化函数，预计算质数基数的幂次
		DoubleHashString(const string& s)
		{
			// s 下标从 0 开始，l r 查询下标从 1 开始
			int n = s.size();

			hs1.resize(n + 1);
			bs1.resize(n + 1);
			hs2.resize(n + 1);
			bs2.resize(n + 1);

			hs1[0] = hs2[0] = 0;
			bs1[0] = bs2[0] = 1;

			for (int i = 1; i <= n; i++)
			{
				bs1[i] = (bs1[i - 1] * base1) % mod1;
				bs2[i] = (bs2[i - 1] * base2) % mod2;
				hs1[i] = (hs1[i - 1] * base1 + s[i - 1] - 'a' + 1) % mod1;
				hs2[i] = (hs2[i - 1] * base2 + s[i - 1] - 'a' + 1) % mod2;
			}
		}

		// 获取子串的双哈希值
		pll get(int l, int r)
		{
			ll x = ((hs1[r] - hs1[l - 1] * bs1[r - l + 1]) % mod1 + mod1) % mod1;
			ll y = ((hs2[r] - hs2[l - 1] * bs2[r - l + 1]) % mod2 + mod2) % mod2;
			return make_pair(x, y);
		}
#undef ll
#undef pll
	};

	class SingleHashString
	{ // 自然溢出单哈希
	private:
#define ull unsigned long long
		vector<ull> hs, p;

		const int base = 131;

	public:
		SingleHashString(string s)
		{
			// s 下标从 0 开始，l r 查询下标从 1 开始
			hs.resize(s.size() + 10), p.resize(s.size() + 10);
			s = ' ' + s;
			p[0] = 1;
			for (int i = 1; i < s.size(); i++)
			{
				hs[i] = hs[i - 1] * base + s[i] - 'a' + 1;
				p[i] = p[i - 1] * base;
			}
		}

		ull get(int l, int r)
		{
			return hs[r] - hs[l - 1] * p[r - l + 1];
		}
#undef ull
	};

	template <class T>
	class LCA
	{
	public:
		vector<int> depth;
		// vector<int>w; 树上边差分没准能用上，w[to] 表示 to 到其 fa 节点的边

		LCA(int n, vector<vector<int>>& e)
		{
			f.assign(n + 10, vector<int>(31));
			depth.assign(n + 10, 0);
			// w.assign(n + 10, 0);

			init(1, 0, e); // 邻接表
		}

		int lca(int x, int y)
		{
			if (depth[x] < depth[y])
				swap(x, y);
			// 后面进行x节点默认比y节点深
			for (int i = 29; i >= 0; i--)
				if (depth[x] - (1 << i) >= depth[y])
					x = f[x][i];
			if (x == y)
				return x; // 特判：y就是原本x的祖宗
			for (int i = 29; i >= 0; i--)
				if (f[x][i] != f[y][i]) // 说明还没找到祖宗，更新a、b后接着跳
					x = f[x][i], y = f[y][i];
			return f[x][0];
		}

	private:
		vector<vector<int>> f; // f[x][i]即x的第2^i个祖先 (31是倍增用的，最大跳跃为2^30)

		void init(int now, int fa, vector<vector<int>>& e) // 邻接表
		{
			depth[now] = depth[fa] + 1;
			f[now][0] = fa;                                 // 第一个祖先
			for (int i = 1; (1 << i) <= depth[now]; i++) // 求now的各个祖先
				f[now][i] = f[f[now][i - 1]][i - 1];
			for (int to : e[now])
			{ // now这个的点的祖先都找完了，dfs处理别的点
				if (to == fa)
					continue;
				init(to, now, e);
				// w[to] = e[i].w;
			}
		}
	};

	template <const int T>
	class ModInt
	{
	private:
		const static int mod = T;

	public:
		int x;
		ModInt(int x = 0) : x(x% mod) {}
		ModInt(long long x) : x(int(x% mod)) {}
		int val() { return x; }
		ModInt operator+(const ModInt& a) const
		{
			int x0 = x + a.x;
			return ModInt(x0 < mod ? x0 : x0 - mod);
		}
		ModInt operator-(const ModInt& a) const
		{
			int x0 = x - a.x;
			return ModInt(x0 < 0 ? x0 + mod : x0);
		}
		ModInt operator*(const ModInt& a) const { return ModInt(1LL * x * a.x % mod); }
		ModInt operator/(const ModInt& a) const { return *this * a.inv(); }
		bool operator==(const ModInt& a) const { return x == a.x; };
		bool operator!=(const ModInt& a) const { return x != a.x; };
		void operator+=(const ModInt& a)
		{
			x += a.x;
			if (x >= mod)
				x -= mod;
		}
		void operator-=(const ModInt& a)
		{
			x -= a.x;
			if (x < 0)
				x += mod;
		}
		void operator*=(const ModInt& a) { x = 1LL * x * a.x % mod; }
		void operator/=(const ModInt& a) { *this = *this / a; }
		friend ModInt operator+(int y, const ModInt& a)
		{
			int x0 = y + a.x;
			return ModInt(x0 < mod ? x0 : x0 - mod);
		}
		friend ModInt operator-(int y, const ModInt& a)
		{
			int x0 = y - a.x;
			return ModInt(x0 < 0 ? x0 + mod : x0);
		}
		friend ModInt operator*(int y, const ModInt& a) { return ModInt(1LL * y * a.x % mod); }
		friend ModInt operator/(int y, const ModInt& a) { return ModInt(y) / a; }
		friend ostream& operator<<(ostream& os, const ModInt& a) { return os << a.x; }
		friend istream& operator>>(istream& is, ModInt& t) { return is >> t.x; }

		ModInt pow(long long n) const
		{
			ModInt res(1), mul(x);
			while (n)
			{
				if (n & 1)
					res *= mul;
				mul *= mul;
				n >>= 1;
			}
			return res;
		}

		ModInt inv() const
		{
			int a = x, b = mod, u = 1, v = 0;
			while (b)
			{
				int t = a / b;
				a -= t * b;
				swap(a, b);
				u -= t * v;
				swap(u, v);
			}
			if (u < 0)
				u += mod;
			return u;
		}
	};

	static int kmp(string& t, string& s)
	{ // 在文本串 t 中找到模式串 s 出现的次数

		// build
		int nn = s.size();
		vector<int> nt(nn);
		for (int i = 1; i < nn; i++)
		{
			int j = nt[i - 1];
			while (j > 0 && s[i] != s[j])
				j = nt[j - 1];
			if (s[i] == s[j])
				j += 1;
			nt[i] = j;
		}

		// kmp
		int n = t.size(), m = s.size(), j = 0;
		int last = -1e9, ans = 0;
		for (int i = 0; i < n; i++)
		{
			while (j > 0 && t[i] != s[j])
				j = nt[j - 1];
			if (t[i] == s[j])
				j += 1;
			if (j == m)
			{
				int head = i - m + 1;
				if (head >= last + m)
				{
					ans += 1;
					last = head;
				}
			}
		}
		return ans;
	}

	class KMP
	{
	private:
		vector<int> nt;
		string s;

	public:
		// 在文本串 t 中找到模式串 s 出现的次数

		// 存入模式串 s
		KMP(string& s) : s(s)
		{
			int n = s.size();
			nt.resize(n);
			for (int i = 1; i < n; i++)
			{
				int j = nt[i - 1];
				while (j > 0 && s[i] != s[j])
					j = nt[j - 1];
				if (s[i] == s[j])
					j += 1;
				nt[i] = j;
			}
		}

		// 查询文本串 t
		int kmp(string& t)
		{
			int n = t.size(), m = s.size(), j = 0;
			int last = -1e9, ans = 0;
			for (int i = 0; i < n; i++)
			{
				while (j > 0 && t[i] != s[j])
					j = nt[j - 1];
				if (t[i] == s[j])
					j += 1;
				if (j == m)
				{
					int head = i - m + 1;
					if (head >= last + m)
					{
						ans += 1;
						last = head;
					}
				}
			}
			return ans;
		}
	};

	class ACAutomaton {
	private:
		int cnt = 1;
		vector<int>in;

		struct kkk {
			int son[26] = { 0 };    // 子节点
			int fail = 0;           // 失败指针
			int flag = 0;           // 模式串起点
			int ans = 0;            // 当前节点匹配次数
			void clear() {
				memset(son, 0, sizeof(son));
				fail = flag = ans = 0;
			}
		};

		vector<kkk>trie; // Trie树

		// 拓扑排序优化
		void topu() {
			queue<int>q;
			for (int i = 1; i <= cnt; i++)
				if (!in[i])q.push(i);

			while (!q.empty()) {
				int u = q.front();
				q.pop();

				output[trie[u].flag] = trie[u].ans; // 更新输出

				int v = trie[u].fail;
				in[v]--;
				trie[v].ans += trie[u].ans;

				if (!in[v])q.push(v);
			}
		}

		int MAXN;
		int ASCII_SIZE = 26;

	public:
		vector<int>Map;                // 模式串下标 对应的 模式串起点的节点
		vector<int>output; // 模式串起点的节点 对应的 模式串在文本串中出现的个数


		// ASCII_SIZE : 26、52、128
		ACAutomaton(int MAXN, int ASCII_SIZE = 26) :MAXN(MAXN), ASCII_SIZE(ASCII_SIZE),
			in(MAXN + 10, 0), Map(MAXN + 10, 0), output(MAXN + 10, 0), trie(MAXN + 10) {}

		void clear() { // ( 这个 clear 可能有些问题 )
			for (int i = 0; i < MAXN + 5; i++) {
				Map[i] = in[i] = output[i] = 0;
				trie[i].clear();
			}
		}

		// 插入模式串
		void insert(string& s, int num) {
			int u = 1, len = s.size();
			for (int i = 0; i < len; i++) {
				int v = s[i] - ((ASCII_SIZE <= 52) ? 'a' : 0);
				if (!trie[u].son[v])trie[u].son[v] = ++cnt;
				u = trie[u].son[v];
			}
			if (!trie[u].flag)trie[u].flag = num; // 模式串起点赋值
			Map[num] = trie[u].flag;
		}

		// 构建失败指针
		void getFail() {
			queue<int>q;

			for (int i = 0; i < ASCII_SIZE; i++)trie[0].son[i] = 1;
			q.push(1);

			while (!q.empty()) {
				int u = q.front();
				q.pop();

				int Fail = trie[u].fail;

				for (int i = 0; i < ASCII_SIZE; i++) {
					int v = trie[u].son[i];
					if (!v) {
						trie[u].son[i] = trie[Fail].son[i];
						continue;
					}

					trie[v].fail = trie[Fail].son[i];
					in[trie[v].fail]++;
					q.push(v);
				}
			}
		}

		// 查询文本串
		void query(string& s) {
			int u = 1, len = s.size();
			for (int i = 0; i < len; i++)
				u = trie[u].son[s[i] - ((ASCII_SIZE <= 52) ? 'a' : 0)], trie[u].ans++;
			topu();
		}
	};

	template<typename T>
	class MinCostMaxFlow {
	public:
		// 边的结构体
		struct Edge {
			int to;   // 目标节点
			T cap;  // 边的容量
			T cost; // 边的费用
			int rev;  // 反向边在邻接表中的索引
		};

		// 构造函数，初始化节点数
		MinCostMaxFlow(int n) : n(n), graph(n + 1), dist(n + 1), prevv(n + 1), preve(n + 1), h(n + 1) {}

		// 添加边
		void addEdge(int from, int to, T cap, T cost = 0) {
			graph[from].push_back(Edge{ to, cap, cost, (int)graph[to].size() });
			graph[to].push_back(Edge{ from, 0, -cost, (int)graph[from].size() - 1 });
		}

		// 计算最小费用最大流的函数
		T minCostMaxFlow(int s, int t, T& flow) {
			T res = 0; // 最小费用
			fill(h.begin(), h.end(), 0); // 初始化势能数组
			while (true) {
				// 使用优先队列实现的Dijkstra算法
				priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
				fill(dist.begin(), dist.end(), INF); // 初始化距离数组
				dist[s] = 0;
				pq.push({ 0, s });
				while (!pq.empty()) {
					auto [d, v] = pq.top();
					pq.pop();
					if (dist[v] < d) continue;
					for (int i = 0; i < graph[v].size(); ++i) {
						Edge& e = graph[v][i];
						if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
							dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
							prevv[e.to] = v;
							preve[e.to] = i;
							pq.push({ dist[e.to], e.to });
						}
					}
				}
				if (dist[t] == INF) break; // 如果无法到达汇点，结束
				for (int i = 0; i <= n; ++i) h[i] += dist[i]; // 更新势能
				T d = INF;
				for (int v = t; v != s; v = prevv[v]) {
					d = min(d, graph[prevv[v]][preve[v]].cap); // 找到增广路径上的最小容量
				}
				flow += d; // 增加总流量
				res += d * h[t]; // 增加总费用
				for (int v = t; v != s; v = prevv[v]) {
					Edge& e = graph[prevv[v]][preve[v]];
					e.cap -= d; // 更新正向边的容量
					graph[v][e.rev].cap += d; // 更新反向边的容量
				}
			}
			return res; // 返回最小费用
		}

	private:
		int n; // 节点数
		const int INF = 1e9; // 定义无穷大
		vector<vector<Edge>> graph; // 邻接表表示的图
		vector<T> dist; // 最短路径费用
		vector<int> prevv; // 前驱节点
		vector<int> preve; // 前驱边
		vector<T> h; // 势能数组
	};

	class XorBase {
	private:
		vector<long long> a; // 线性基基底
		const int MN = 62;
		bool flag = false;

	public:
		XorBase() :a(70, 0) {};

		void print() {
			for (int i : a)
				cout << i << ' ';
			cout << endl;
		}

		// XorBase[x]：说明第 x 位上存在代表性数 XorBase[x]
		// 这个代表数的特点就是，最高位即为 2 ^ x
		long long& operator[](int x) {
			return a[x];
		}

		// 清除基底
		void clear() {
			a.clear();
		}

		// 插入新数
		void insert(long long x) {
			for (int i = MN; ~i; i--)
				if (x & (1ll << i))
					if (!a[i]) { a[i] = x; return; }
					else x ^= a[i];
			flag = true;
		}

		// 插入新数
		void operator +=(long long x) {
			insert(x);
		}

		// 线性基合并
		void operator +=(XorBase& x) {
			for (int i = MN; i >= 0; i--)if (x[i])*this += x[i];
		}
		friend XorBase operator +(XorBase& x, XorBase& y) {
			XorBase z = x;
			for (int i = 62; i >= 0; i--)if (y[i])z += y[i];
			return z;
		}

		// 查是否存在线性基内
		bool check(long long x) {
			for (int i = MN; ~i; i--)
				if (x & (1ll << i))
					if (!a[i])return false;
					else x ^= a[i];
			return true;
		}

		// 查最大
		long long qmax(long long res = 0) {
			for (int i = MN; ~i; i--)
				res = max(res, res ^ a[i]);
			return res;
		}

		// 查最小
		long long qmin() {
			if (flag)return 0;
			for (int i = 0; i <= MN; i++)
				if (a[i])return a[i];
		}

		// 查询第 k 小
		long long query(long long k) {
			long long tmp[70] = { 0 };
			long long res = 0; int cnt = 0;
			k -= flag; if (!k)return 0;
			for (int i = 0; i <= MN; i++) {
				for (int j = i - 1; ~j; j--)
					if (a[i] & (1ll << j))a[i] ^= a[j];
				if (a[i])tmp[cnt++] = a[i];
			}
			if (k >= (1ll << cnt))return -1;
			for (int i = 0; i < cnt; i++)
				if (k & (1ll << i))res ^= tmp[i];
			return res;
		}
	};

	template<typename T>
	class fast {
	public:
		// 使用 __int128 直接传入 T = __int128 就行
		inline static T in()
		{
			T x = 0, f = 1;
			char ch = getchar();
			while (ch < '0' || ch>'9')
			{
				if (ch == '-')
					f = -1;
				ch = getchar();
			}
			while (ch >= '0' && ch <= '9')
				x = x * 10 + ch - '0', ch = getchar();
			return x * f;
		}
		static void out(T x)
		{
			if (x < 0)
				putchar('-'), x = -x;
			if (x > 9)
				out(x / 10);
			putchar(x % 10 + '0');
			return;
		}
		static void outln(T x)
		{
			out(x);
			putchar('\n');
		}
	};

	class PersistentSegmemtTree {
		// 可持久化权值线段树(主席树)
		// 可能需要离散化，根据离散化数组进行初始化
		// 下标从 1 开始

		/* 求第 k 小模板
			int n, m; cin >> n >> m;
			auto a = vector<int>(n + 1);
			auto b = vector<int>();

			fa(i, 1, n)cin >> a[i], b.pb(a[i]);

			sort(all(b));
			b.erase(unique(all(b)), b.end());

			int len = b.size();
			PersistentSegmemtTree sg(len, n);

			auto find = [&](int value)->int {
				return upper_bound(all(b), value) - b.begin();
				};

			// 初始化主席树，记得赋值
			fa(i, 1, n) sg.root[i] = sg.update(find(a[i]), 1, sg.root[i - 1]);

			while (m--) {
				int l, r, k; cin >> l >> r >> k;
				// 求区间相减，传入 l - 1
				cout << b[sg.query_k_min(l - 1, r, k) - 1] << endl;
			}
		*/

		/* 求区间多少不同元素模板
			int n; cin >> n;
			PersistentSegmemtTree sg(n, n);
			HashMap<int, int>mp;
			fa(i, 1, n) {
				int x; cin >> x;
				if (mp.count(x)) {
					// 如果之前出现过，且出现在 mp[x] 位置，
					// 就删掉之前出现的，转而把这个值放在现在的 i 上，
					// 这样能保证每个线段树都存在这个数，同时也不会重复
					int t = sg.update(mp[x], -1, sg.root[i - 1]);
					sg.root[i] = sg.update(i, 1, t);
				}
				else sg.root[i] = sg.update(i, 1, sg.root[i - 1]);
				mp[x] = i;
			}
			int m; cin >> m;
			while (m--) {
				int l, r; cin >> l >> r;
				cout << sg.query(l, r) << endl;
			}
		*/

	private:
		int tot = 0;
		struct tree { int l = 0, r = 0, sum = 0; };
		vector<tree>t;
		int len;

		int build(int l, int r) { // 初始化建树，建 len 个节点的
			int node = ++tot;
			if (l == r)return node;
			int mid = l + r >> 1;
			t[node].l = build(l, mid);
			t[node].r = build(mid + 1, r);
			return node;
		}
	public:
		vector<int>root;

		// m 传入实际离散化后大小即可，不用 + 1
		// n 传入离散化前的个数
		PersistentSegmemtTree(int m, int n) :len(m), t((n << 6) + 10), root(n + 10) {
			root[0] = build(1, len);
		}

		// 主席树的更新继承上一个线段树的根节点
		int update(int l, int r, int pos, int value, int pre) {
			int node = ++tot;
			t[node] = t[pre];
			t[node].sum += value;
			if (l == r)return node;
			int mid = l + r >> 1;
			if (pos <= mid)  // 新的左子节点会继承前一个版本的左子节点进行更新
				t[node].l = update(l, mid, pos, value, t[pre].l);
			else             // 同理
				t[node].r = update(mid + 1, r, pos, value, t[pre].r);
			return node;
		}

		// 传入离散化数组对应的下标，更新的值，上一个已更新的线段树的根节点
		int update(int pos, int value, int pre) {
			return update(1, len, pos, value, pre);
		}

		// update 是加，change 是直接改变
		int change(int l, int r, int pos, int value, int pre) {
			int node = ++tot;
			t[node] = t[pre];
			t[node].sum = value;
			if (l == r)return node;
			int mid = l + r >> 1;
			if (pos <= mid)
				t[node].l = change(l, mid, pos, value, t[pre].l);
			else
				t[node].r = change(mid + 1, r, pos, value, t[pre].r);
			return node;
		}

		int change(int pos, int value, int pre) {
			return change(1, len, pos, value, pre);
		}

		// 本质其实是同时算两个权值线段树在 [1, l] 和 [1, r] 两个区间查询 
		int query_k_min(int u, int v, int l, int r, int k) {
			int mid = l + r >> 1;

			// 通过区间减法得左儿子中存的数值个数
			int lnum = t[t[v].l].sum - t[t[u].l].sum;

			if (l == r)return l;
			if (k <= lnum) // 第 k 小在左子
				return query_k_min(t[u].l, t[v].l, l, mid, k);
			else           // 第 k 小在右子，并注意相减
				return query_k_min(t[u].r, t[v].r, mid + 1, r, k - lnum);
		}

		// 原理是前缀和，要传入 L - 1
		int query_k_min(int L, int R, int k) {
			return query_k_min(root[L], root[R], 1, len, k);
		}

		// 朴素区间查询，但只需要传入一棵树
		int queryRange(int l, int r, int L, int R, int pre) {
			if (L <= l and r <= R) return t[pre].sum;
			int mid = l + r >> 1;
			int res = 0;
			if (L <= mid)res += queryRange(l, mid, L, R, t[pre].l);
			if (R > mid)res += queryRange(mid + 1, r, L, R, t[pre].r);
			return res;
		}

		// v 为线段树版本，注意这个版本必须大于等于 R
		int queryRange(int L, int R, int v = -1) {
			if (v == -1)v = root[R];
			// 这里只会传入一个线段树版本然后接着朴素查询
			return queryRange(1, len, L, R, v);
		}
	};

	template<typename T = long long>
	class Frac
	{
	private:
		T abs(const T& x)const { return x < 0 ? -x : x; }
		T gcd(const T& x, const T& y)const { return y ? gcd(y, x % y) : x; }
		Frac reduce()
		{
			bool flag = 0;
			if (a < 0 && b < 0) a = -a, b = -b;
			if (a < 0) a = -a, flag = 1;
			if (b < 0) b = -b, flag = 1;
			T ggcd = gcd(a, b);
			a /= ggcd;
			b /= ggcd;
			if (flag) a = -a;
			return *this;
		}
		void swap() { std::swap(a, b); }
		Frac _swap(const Frac& t)const { return Frac(t.b, t.a); }
		T FastPow(T x, T p, T mod)const
		{
			T ans = 1, bas = x;
			for (; p; bas = bas * bas % mod, p >>= 1)
				if (p & 1) ans = ans * bas % mod;
			return ans;
		}
	public:
		T a, b;
		Frac(T A = 0, T B = 1) { a = A, b = B; }
		T to_inv(const T& mod = 1e9 + 7)const { return a * FastPow(b, mod - 2, mod) % mod; }
		Frac abs()const { return Frac(abs(a), abs(b)); }
		friend ostream& operator<<(ostream& out, const Frac& a) { out << a.a << ' ' << a.b; return out; }
		Frac operator =(const Frac& t) { return a = t.a, b = t.b, t; }
		bool operator ==(const Frac& t)const { Frac A(*this), B(t); return (A.reduce().a == B.reduce().a) && (A.b == B.b); }
		bool operator !=(const Frac& t)const { Frac A(*this), B(t); return (A.a != B.a) || (A.b != B.b); }
		bool operator >(const Frac& t)const { Frac A(*this), B(t); T ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a > A.b / ggcd * B.a; }
		bool operator <(const Frac& t)const { Frac A(*this), B(t); T ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a < A.b / ggcd * B.a; }
		bool operator >=(const Frac& t)const { Frac A(*this), B(t); T ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a >= A.b / ggcd * B.a; }
		bool operator <=(const Frac& t)const { Frac A(*this), B(t); T ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a <= A.b / ggcd * B.a; }
		Frac operator +(const Frac& t)const { T ggcd = gcd(b, t.b); return Frac(b / ggcd * t.a + t.b / ggcd * a, b / ggcd * t.b).reduce(); }
		Frac operator +=(const Frac& t) { return *this = *this + t; }
		Frac operator *(const Frac& t)const { return Frac(a * t.a, b * t.b).reduce(); }
		Frac operator *=(const Frac& t) { return *this = *this * t; }
		Frac operator -(const Frac& t)const { return (*this + Frac(-t.a, t.b)).reduce(); }
		Frac operator -=(const Frac& t) { return *this = *this - t; }
		Frac operator /(const Frac& t)const { return (t._swap(t) * (*this)).reduce(); }
		Frac operator /=(const Frac& t) { return *this = *this / t; }
		Frac operator -()const { return Frac(-a, b); }
	};


	//////// CalGeo ////////
	template<typename T>
	class Point;

	template<typename T>
	class Line;

	template<typename T>
	class Polygon;

	template<typename T>
	class Circle;

	template<typename T>
	using Vector = Point<T>;

	template<typename T>
	using Segment = Line<T>;

	namespace Geo {
		const double eps = 1e-8;
		const double PI = acos(-1.0);

		// 浮点数 x 的符号
		template<typename T>
		int sgn(T x) {
			if (fabs(x) < eps) return 0;
			return x > 0 ? 1 : -1;
		}

		// 比较两个浮点数
		template<typename T>
		int cmp(T x, T y) {
			if (fabs(x) < eps)return 0; // x == y，返回 0
			else return x < y ? -1 : 1; // x < y，返回 -1; x > y，返回 1
		}

		// 两点距离
		template<typename T>
		T dist(const Point<T>& A, const Point<T>& B) {
			return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
		}

		// 点积
		template<typename T>
		T dot(const Vector<T>& A, const Vector<T>& B) {
			return A.x * B.x + A.y * B.y;
		}

		// 叉积
		template<typename T>
		T cross(const Vector<T>& A, const Vector<T>& B) {
			return A.x * B.y - A.y * B.x;
		}

		// 向量长度
		template<typename T>
		T len(const Vector<T>& A) {
			return sqrt(dot(A, A));
		}

		// 向量长度的平方
		template<typename T>
		T len2(const Vector<T>& A) {
			return dot(A, A);
		}

		// 两向量夹角
		template<typename T>
		double angle(const Vector<T>& A, const Vector<T>& B) {
			return acos(dot(A, B) / len(A) / len(B));
		}

		// 计算两向量构成的平行四边形有向面积
		// 三个点A、B、C，以A为公共点，得到2个向量B-A和C-A，它们构成的平行四边形
		template<typename T>
		T area2(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
			return cross(B - A, C - A);
		}

		// 向量旋转	
		/*
			特殊情况是旋转90度：
			逆时针旋转90度：Rotate(A, pi/2)，返回Vector(-A.y, A.x)；
			顺时针旋转90度：Rotate(A, -pi/2)，返回Vector(A.y, - A.x)。
		*/
		template<typename T>
		Vector<T> rotate(const Vector<T>& A, double rad) {
			return Vector<T>(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
		}

		// 有时需要求单位法向量，即逆时针转90度，然后取单位值。
		template<typename T>
		Vector<T> normal(const Vector<T>& A) {
			return Vector<T>(-A.y / len(A), A.x / len(A));
		}

		// 两个向量是否平行或重合
		template<typename T>
		bool parallel(const Vector<T>& A, const Vector<T>& B) {
			return sgn(cross(A, B)) == 0; // 返回true表示平行或重合
		}

		// 点和直线的位置关系
		template<typename T>
		int point_line_relation(const Point<T>& p, const Line<T>& v) {
			int c = sgn(cross(p - v.p1, v.p2 - v.p1));
			if (c < 0)return 1;              // 1 ：p在v的左边
			if (c > 0)return 2;              // 2 ：p在v的右边
			return 0;                        // 0 ：p在v上
		}

		// 点和线段的位置关系
		template<typename T>
		bool point_is_on_segment(const Point<T>& p, const Line<T>& v) { // 点和线段：0 点不在线段v上；1 点在线段v上
			return sgn(cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(dot(p - v.p1, p - v.p2)) <= 0;
		}

		// 点到直线的距离
		template<typename T>
		double point_line_dis(const Point<T>& p, const Line<T>& v) {
			return fabs(cross(p - v.p1, v.p2 - v.p1)) / dist(v.p1, v.p2);
		}

		// 点在直线上的投影
		template<typename T>
		Point<T> point_line_proj(const Point<T>& p, const Line<T>& v) {
			double k = dot(v.p2 - v.p1, p - v.p1) / Len2(v.p2 - v.p1);
			return v.p1 + (v.p2 - v.p1) * k;
		}

		// 点关于直线的对称点
		template<typename T>
		Point<T> point_line_symmetry(const Point<T>& p, const Line<T>& v) {
			Point<T> q = point_line_proj(p, v);
			return Point<T>(2 * q.x - p.x, 2 * q.y - p.y);
		}

		// 点到线段的距离
		template<typename T>
		double point_segment_dis(const Point<T>& p, const Segment<T>& v) {
			if (sgn(dot(p - v.p1, v.p2 - v.p1)) < 0 || sgn(dot(p - v.p2, v.p1 - v.p2)) < 0)
				return min(dist(p, v.p1), dist(p, v.p2));
			return point_line_dis(p, v);           // 点的投影在线段上
		}

		// 叉积判断两条向量的位置关系，AB * AC，两向量共点
		template<typename T>
		int vector_vector_relation(const Vector<T>& v1, const Vector<T>& v2) {
			int sign = sgn(cross(v1, v2));
			if (sign == 0)return 0; // 共线
			if (sign > 0)return 1;  // v2 在 v1 的逆时针方向 
			if (sign < 0)return 2;  // v2 在 v1 的顺时针方向 
		}

		// 叉积判断两条直线的位置关系
		template<typename T>
		int line_line_relation(const Line<T>& v1, const Line<T>& v2) {
			if (sgn(cross(v1.p2 - v1.p1, v2.p2 - v2.p1)) == 0) {
				if (point_line_relation(v1.p1, v2) == 0) return 1;  // 1: 重合
				else return 0;                                      // 0: 平行
			}
			return 2;                                               // 2: 相交
		}

		// 两条直线的交点
		template<typename T>
		Point<T> line_line_cross_point(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
			// Line1 : ab, Line2 : cd
			double s1 = cross(b - a, c - a);
			double s2 = cross(b - a, d - a);                    // 叉积有正负
			return Point<T>(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
		}

		// 两个线段是否相交
		template<typename T>
		bool segment_segment_is_cross(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
			// Line1 : ab, Line2 : cd
			double c1 = cross(b - a, c - a), c2 = cross(b - a, d - a);
			double d1 = cross(d - c, a - c), d2 = cross(d - c, b - c);
			return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0;  // 1: 相交；0: 不相交
		}

		// 点和多边形的关系
		template<typename T>
		int point_polygon_relation(const Point<T>& pt, const Polygon<T>& p) {
			// 点pt，多边形 p
			int n = p.size();
			for (int i = 0; i < n; i++) {
				if (p[i] == pt)  return 3;                    // 3：点在多边形的顶点上
			}
			for (int i = 0; i < n; i++) {
				Line<T> v = Line<T>(p[i], p[(i + 1) % n]);
				if (point_is_on_segment(pt, v)) return 2;     // 2：点在多边形的边上
			}
			int num = 0;
			for (int i = 0; i < n; i++) {
				int j = (i + 1) % n;
				int c = sgn(cross(pt - p[j], p[i] - p[j]));
				int u = sgn(p[i].y - pt.y);
				int v = sgn(p[j].y - pt.y);
				if (c > 0 && u < 0 && v >= 0) num++;
				if (c < 0 && u >= 0 && v < 0) num--;
			}
			return num != 0;                                  // 1：点在内部; 0：点在外部
		}

		// 计算多边形周长
		template<typename T>
		T polygon_perimeter(const Polygon<T>& p) {
			T ans = 0;
			int n = p.size();
			for (int i = 0; i < n; i++)
				ans += dist(p[i], p[(i + 1) % n]);
			return ans;
		}

		// 多边形的面积
		template<typename T>
		T polygon_area(const Polygon<T>& p) {
			T area = 0;
			int n = p.size();
			for (int i = 0; i < n; i++)
				area += cross(p[i], p[(i + 1) % n]);
			return area / 2;                    // 面积有正负，返回时不能简单地取绝对值
		}

		// 多边形的重心
		template<typename T>
		Point<T> polygon_center_point(const Polygon<T>& p) {        //求多边形重心
			Point<T> ans(0, 0);
			int n = p.size();
			if (polygon_area(p, n) == 0) return ans;
			for (int i = 0; i < n; i++)
				ans = ans + (p[i] + p[(i + 1) % n]) * cross(p[i], p[(i + 1) % n]);
			return ans / polygon_area(p, n) / 6;
		}

		// 求凸包，凸包顶点放在ch中
		// 凸多边形：是指所有内角大小都在 [0, 180] 范围内的简单多边形
		// 凸包：在平面上能包含所有给定点的最小凸多边形叫做凸包
		template<typename T>
		Polygon<T> convex_hull(const vector<Point<T>>& p) {
			Polygon<T> ch;
			int n = p.size();
			n = unique(p.begin(), p.end()) - p;    // 去除重复点    
			ch.resize(n);
			sort(p.begin(), p.begin() + n);        // 对点排序：按 x 从小到大排序，如果 x 相同，按 y 排序    
			int v = 0;
			// 求下凸包，如果p[i]是右拐弯的，这个点不在凸包上，往回退
			for (int i = 0; i < n; i++) {
				while (v > 1 && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0) // 把后面 ch[v-1] 改成 ch[v-2] 也行
					v--;
				ch[v++] = p[i];
			}
			int j = v;
			// 求上凸包
			for (int i = n - 2; i >= 0; i--) {
				while (v > j && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0) // 把后面 ch[v-1] 改成 ch[v-2] 也行
					v--;
				ch[v++] = p[i];
			}
			ch.erase(unique(ch.begin(), ch.end()), ch.end());
			return ch;
		}

		// 点和圆的关系，根据点到圆心的距离判断
		template<typename T>
		int point_circle_relation(const Point<T>& p, const Circle<T>& C) {
			double dst = dist(p, C.c);
			if (sgn(dst - C.r) < 0) return 0;       // 0: 点在圆内
			if (sgn(dst - C.r) == 0) return 1;      // 1: 圆上
			return 2;                               // 2: 圆外
		}

		// 直线和圆的关系，根据圆心到直线的距离判断
		template<typename T>
		int line_circle_relation(const Line<T>& v, const Circle<T>& C) {
			double dst = point_line_dis(C.c, v);
			if (sgn(dst - C.r) < 0) return 0;       // 0: 直线和圆相交
			if (sgn(dst - C.r) == 0) return 1;      // 1: 直线和圆相切
			return 2;                               // 2: 直线在圆外
		}

		// 线段和圆的关系，根据圆心到线段的距离判断
		template<typename T>
		int segment_circle_relation(const Segment<T> v, const Circle<T> C) {
			double dst = point_segment_dis(C.c, v);
			if (sgn(dst - C.r) < 0) return 0;       // 0: 线段在圆内
			if (sgn(dst - C.r) == 0) return 1;      // 1: 线段和圆相切
			return 2;                               // 2: 线段在圆外
		}

		//pa, pb是交点。返回值是交点个数
		template<typename T>
		int line_cross_circle(const Line<T>& v, const Circle<T>& C, Point<T>& p1, Point<T>& p2) {
			if (line_circle_relation(v, C) == 2)  return 0;    // 无交点
			Point<T> q = point_line_proj(C.c, v);              // 圆心在直线上的投影点
			double d = point_line_dis(C.c, v);                 // 圆心到直线的距离
			double k = sqrt(C.r * C.r - d * d);
			if (sgn(k) == 0) {                                 // 1个交点，直线和圆相切
				p1 = q;	p2 = q;	return 1;
			}
			Point<T> n = (v.p2 - v.p1) / len(v.p2 - v.p1);     // 单位向量
			p1 = q + n * k;  p2 = q - n * k;
			return 2;                                          // 2个交点
		}

	};

	template<typename T>
	class Point {
	public:
		T x, y;
		Point(T x = 0, T y = 0) : x(x), y(y) {}

		// 向量长度
		T len() {
			return sqrt(len2());
		}
		// 向量长度的平方
		T len2() {
			return (*this) * (*this);
		}

		Point operator- (const Point& B) const { return Point(x - B.x, y - B.y); }
		Point operator+ (const Point& B) const { return Point(x + B.x, y + B.y); }
		T operator^ (const Point<T>& B) const { return x * B.y - y * B.x; } // 叉积
		T operator* (const Point<T>& B) const { return x * B.x + y * B.y; } // 点积
		Point operator* (const T& B) const { return Point(x * B, y * B); }
		Point operator/ (const T& B) const { return Point(x / B, y / B); }
		bool operator< (const Point& B) const { return x < B.x || (x == B.x && y < B.y); }
		bool operator> (const Point& B) const { return x > B.x || (x == B.x && y > B.y); }
		bool operator== (const Point& B) const { return Geo::sgn(x - B.x) == 0 && Geo::sgn(y - B.y) == 0; }
		bool operator!= (const Point& B) const { return Geo::sgn(x - B.x) || Geo::sgn(y - B.y); }
		friend ostream& operator<<(ostream& out, const Point& a) { out << '(' << a.x << ',' << a.y << ')'; return out; }
	};

	template<typename T>
	class Line {
	public:
		Point<T> p1, p2;                         // 线上的两个点
		Line() {}
		Line(Point<T> p1, Point<T> p2) :p1(p1), p2(p2) {}
		Line(Point<T> p, double angle) {         // 根据一个点和倾斜角 angle 确定直线，0 <= angle < pi
			p1 = p;
			if (Geo::sgn(angle - Geo::PI / 2) == 0) { p2 = (p1 + Point<T>(0, 1)); }
			else { p2 = (p1 + Point<T>(1, tan(angle))); }
		}
		Line(double a, double b, double c) {     // ax + by + c = 0
			if (Geo::sgn(a) == 0) {
				p1 = Point<T>(0, -c / b);
				p2 = Point<T>(1, -c / b);
			}
			else if (Geo::sgn(b) == 0) {
				p1 = Point<T>(-c / a, 0);
				p2 = Point<T>(-c / a, 1);
			}
			else {
				p1 = Point<T>(0, -c / b);
				p2 = Point<T>(1, (-c - a) / b);
			}
		}
		friend ostream& operator<<(ostream& out, const Point<T>& a) { out << a.x << ',' << a.y; return out; }
	};

	template<typename T>
	class Polygon : public vector<Point<T>> {
	public:
		Polygon(int n) :vector<Point<T>>(n) {};

		friend ostream& operator<<(ostream& out, const Polygon<T>& a) {
			for (auto& i : a)
				out << i << ' ';
			return out;
		}
	};

	template<typename T>
	class Circle {
	public:
		Point<T> c;       // 圆心
		T r;         // 半径
		Circle() {}
		Circle(Point<T> c, T r) :c(c), r(r) {}
		Circle(T x, T y, T _r) { c = Point<T>(x, y); r = _r; }
		friend ostream& operator<<(ostream& out, const Circle<T>& a) {
			out << a.c << ',' << a.r;
			return out;
		}
	};
	////////////////////////
}

namespace MT = MyTools;
using Math = MT::Math<ll>;
using mint = MT::ModInt<998244353>;

const int mod = 1e9 + 7;
const int N = 1e6 + 10;


void solve(int CASE)
{
	int r, c; cin >> r >> c;
	var a = vector<string>(r + 1);
	fa(i, 1, r)cin >> a[i], a[i] = ' ' + a[i];

	// 扩展域并查集
	var s = vector<int>(2 * r + 1);
	fa(i, 1, 2 * r)s[i] = i;

	// 每列出现 1 的各个行
	var g = vector<vector<int>>(c + 1);
	fa(i, 1, r)
		fa(j, 1, c)
		if (a[i][j] == '1')
			g[j].pb(i);

	var find = [&](var find, int x)->int {
		if (x != s[x])return s[x] = find(find, s[x]);
		return s[x];
		};

	var merge = [&](int x, int y)->void {
		s[find(find, y)] = find(find, x);
		};

	// 中心的怎么翻转都没用了
	if (c % 2 == 1 and g[(c + 1) / 2].size() > 1) {
		cout << 0 << endl;
		return;
	}

	fa(i, 1, c / 2) { // 枚举列
		var j = c - i + 1;
		var tot = g[i].size() + g[j].size();
		// 这列和对称列 1 的个数不能大于 2
		if (tot > 2) {
			cout << 0 << endl;
			return;
		}
		if (tot <= 1)continue;
		if (g[i].size() == 2) {
			merge(g[i][0], g[i][1] + r);
			merge(g[i][1], g[i][0] + r);
		}
		else if (g[j].size() == 2) {
			merge(g[j][0], g[j][1] + r);
			merge(g[j][1], g[j][0] + r);
		}
		else {
			merge(g[i][0], g[j][0]);
			merge(g[i][0] + r, g[j][0] + r);
		}
	}
	fa(i, 1, r) {
		if (s[find(find, i)] == s[find(find, i + r)]) {
			cout << 0 << '\n';
			return;
		}
	}
	int ans = 0;
	fa(i, 1, 2 * r)ans += (s[i] == i);
	cout << Math::fastPow(2, ans / 2, mod) << endl;
	return;
}

int main()
{
	//SetConsoleOutputCP(CP_UTF8);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	fa(i, 1, _)solve(i);
	return 0;
}