//#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define rep(i,a,n)  for(ll i=a;i<=n;i++)
#define per(i,a,n)  for(ll i=a;i>=n;i--)
#define TLE  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define vi vector<int>
#define pii pair<int,int>
#define vpi vector<pii>
#define eb emplace_back 
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int maxn=1e5+10;
const int max1=1e6+7;
const int maxm=4e7+10;
const int mod=1e9+7;     
const int INF=0x3f;
const db PI = acos(-1);       
//int L = (l % x == 0 ? l : l + x - l % x);     int R = L + x;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} 
ll lcm(ll a, ll b){ return a / gcd(a, b)*b;}//顺序不能写反，不然会爆
const double gold = (sqrt(5.0)+1.0)/2.0;//黄金分割比 用于威佐夫博弈
inline ll ...