#include<bits/extc++.h>
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
using namespace std;using ll = long long;using ull = unsigned long long;using ul = unsigned;using db = double;using __gnu_pbds::null_type;
template<typename T> using rbtree = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
#ifdef _debug
#define dout(i) cout << #i << ' ' << i << ' '
#else
#define dout(i) 0&&0
#endif
#define eout(i) {cout << (i) << '\n';exit(0);}
#define priority_queue __gnu_pbds::priority_queue
#define unordered_map __gnu_pbds::gp_hash_table
#define rep(a, b) {for(int i = a;i > 0;--i){b;}}
#define multe int T;for(cin >> T;T--;)
template<typename T> inline long long pow(long long v, long long t, const T &p){long long res = 1;for(;t;t >>= 1, v = v * v % p)if(t & 1)res = res * v % p;return res;}
template<typename T> inline void floyd_warshall(vector<vector<T>> &dp){for(int i = 0;i < dp.size();++i)for(int j = 0;j < dp.size();++j)for(int k = 0;k < dp.size();++k)dp[i][k] = min(dp[i][k], dp[i][j] + dp[j][k]);}
template<typename T> inline ostream& operator << (ostream &ou, const vector<T> &a){for(auto it = a.begin();it != a.end();++it)ou << (it != a.begin() ? " " : "") << *it;return ou;}
template<typename T> inline vector<vector<T>> operator * (const vector<vector<T>> &a, const vector<vector<T>> &b){assert(a.front().size() == b.size());vector<vector<T>> res(a.size(), vector<T>(b.front().size()));for(int i = 0;i < a.size();++i)for(int j = 0;j < b.front().size();++j)for(int k = 0;k < a.front().size();++k)res[i][j] += a[i][k] * b[k][j];return res;}
template<typename T> inline vector<vector<T>> pow(vector<vector<T>> v, long long t){vector<vector<T>> res;for(;t;t >>= 1, v = v * v)if(t & 1)res = (res.empty() ? v : res * v);return res;}
template<typename T1, typename T2>inline istream& operator >> (istream &in, pair<T1, T2> &a){return in >> a.first >> a.second;}
template<typename T1, typename T2>inline ostream& operator << (ostream &ou, const pair<T1, T2> &b){return ou << b.first << ' ' << b.second;}
template<typename T1, typename T2>inline pair<T1,T2> operator + (const pair<T1,T2> &a, const pair<T1,T2> &b){return {a.first + b.first, a.second + b.second};}
template<typename T1, typename T2>inline pair<T1,T2> operator - (const pair<T1,T2> &a, const pair<T1,T2> &b){return {a.first - b.first, a.second - b.second};}
template<typename T1, typename T2>inline long long operator ^ (const pair<T1,T2> &a, const pair<T1,T2> &b){return (long long)a.first * b.second - (long long)a.second * b.first;}
pair<long long, long long> ext_gcd(long long a, long long b){if(a % b == 0)return {0ll, 1ll};auto get = ext_gcd(b, a % b);return {get.second, get.first - a / b * get.second};}
long long ext_inv(long long a, long long p){return (ext_gcd(a, p).first + p) % p;}