#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
//#define int ll

bool dbg=false;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;
using vvi=vc<vc<int>>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

ll rand_int(ll l, ll r) { //[l, r]
	//#ifdef LOCAL
	static mt19937_64 gen;
	/*#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif*/
	return uniform_int_distribution<ll>(l, r)(gen);
}

ll rand_int(ll k){ //[0,k)
	return rand_int(0,k-1);
}
string rand_string(int n,char lw,char up){
	string s(n,'?');
	rep(i,n)s[i]=rand_int(lw,up);
	return s;
}

int current_run_id,run_batch_size=1000;
int calc_random_limit(){
	return current_run_id/run_batch_size+1;
}
template<class t>
void generate_single(t&a){
	a=rand_int(1,calc_random_limit());
}
void generate_single(string&a){
	int n;generate_single(n);
	a=rand_string(n,'a','b');
}
template<class t,class u>
void generate_single(pair<t,u>&a){
	generate_single(a.a);
	generate_single(a.b);
}
//https://trap.jp/post/1224/
template<class... Args>
void input(Args&... a){
	if(dbg){
		(generate_single(a),...);
	}else{
		#ifdef USE_FAST_IO
		sc.read(a...);
		#else
		(cin >> ... >> a);
		#endif
	}
}
#define INT(...) int __VA_ARGS__;input(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;input(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;input(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;input(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;input(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;input(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;input(__VA_ARGS__)
#define overload3(a,b,c,d,...) d
#define VI2(name,size) vi name(size);rep(i_##name,size)input(name[i_##name]);
#define VI3(name,size,offset) vi name(size);rep(i_##name,size)input(name[i_##name]),name[i_##name]+=offset;
#define VI(...) overload3(__VA_ARGS__,VI3,VI2)(__VA_ARGS__)
#define VPI(name,size) vc<pi> name(size);rep(i_##name,size)input(name[i_##name].a,name[i_##name].b);
#define VVI(name,sizeN,sizeM) vvi name(sizeN,vi(sizeM));\
rep(i_##name,sizeN)rep(j_##name,sizeM)input(name[i_##name][j_##name]);
#define VS(name,size) vc<string> name(size);rep(i_##name,size)input(name[i_##name]);
#define VMI(name,size) vc<mint> name(size);rep(i_##name,size){INT(tmp_##name);name[i_##name]=tmp_##name;};

#define overload5(a,b,c,d,e,f,...) f
#define VVC4(type,name,sizeN,sizeM) vvc<type> name(sizeN,vc<type>(sizeM));
#define VVC5(type,name,sizeN,sizeM,ini) vvc<type> name(sizeN,vc<type>(sizeM,ini));
#define VVC(...) overload5(__VA_ARGS__,VVC5,VVC4)(__VA_ARGS__)

template<class T>
T vvvc(T v){
	return v;
}

template<class T,class...Args>
auto vvvc(int n,T v,Args...args){
	return vector(n,vvvc(v,args...));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

void printsuc(int suc){
	#ifdef USE_FAST_IO
		if(suc==1)pr.write('\n');
		if(suc==2)pr.write(' ');
	#else
		if(suc==1){
			if(dbg)cout<<endl;
			else{
				#ifdef LOCAL
				cout<<endl;
				#else
				cout<<"\n";
				#endif
			}
		}
		if(suc==2)
			cout<<" ";
	#endif
}

template<class t>
void print_single(t x,int suc=1){
	#ifdef USE_FAST_IO
	pr.write(x);
	#else
	cout<<x;
	#endif
	printsuc(suc);
}

template<class t,class u>
void print_single(const pair<t,u>&p,int suc=1){
	print_single(p.a,2);
	print_single(p.b,suc);
}

template<class T>
void print_single(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print_single(v[i],i==int(v.size())-1?3:2);
	printsuc(suc);
}

template<class T,size_t N>
void print_single(const array<T,N>&v,int suc=1){
	rep(i,N)
		print_single(v[i],i==int(N)-1?3:2);
	printsuc(suc);
}

template<class T>
void print(const T&t){
	print_single(t);
}

template<class T,class ...Args>
void print(const T&t,const Args&...args){
	print_single(t,2);
	print(args...);
}

template<class T>
void printvv(const vvc<T>&vs){
	for(const auto&row:vs)print(row);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

void YES(bool ex=true){
	cout<<"YES\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void NO(bool ex=true){
	cout<<"NO\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void Yes(bool ex=true){
	cout<<"Yes\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void No(bool ex=true){
	cout<<"No\n";
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
//#define CAPITAL
/*
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}*/
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int topbit(ull t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int botbit(ull a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
int popcount(ull t){
	return __builtin_popcountll(t);
}
int bitparity(ll t){
	return __builtin_parityll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}
ull umask(int i){
	return (ull(1)<<i)-1;
}
ll minp2(ll n){
	if(n<=1)return 1;
	else return ll(1)<<(topbit(n-1)+1);
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class S> void mkuni(S&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

template<class t> bool isuni(vc<t> v){
	int s=si(v);
	mkuni(v);
	return si(v)==s;
}

bool isperm(const vi&p){
	int n=si(p);
	vc<bool> used(n);
	for(auto v:p){
		if(!inc(0,v,n-1))return false;
		if(used[v])return false;
		used[v]=true;
	}
	return true;
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class S,class u>
int lwb(const S&v,const u&a){
	return lower_bound(all(v),a)-v.bg;
}
template<class t,class u>
bool bis(const vc<t>&v,const u&a){
	return binary_search(all(v),a);
}

//VERIFY: yosupo
//KUPC2017J
//AOJDSL1A
//without rank
struct unionfind{
	vi p,s;
	int c;
	unionfind(int n):p(n,-1),s(n,1),c(n){}
	void clear(){
		fill(all(p),-1);
		fill(all(s),1);
		c=si(p);
	}
	int find(int a){
		return p[a]==-1?a:(p[a]=find(p[a]));
	}
	//set b to a child of a
	bool unite(int a,int b){
		a=find(a);
		b=find(b);
		if(a==b)return false;
		p[b]=a;
		s[a]+=s[b];
		c--;
		return true;
	}
	bool same(int a,int b){
		return find(a)==find(b);
	}
	int sz(int a){
		return s[find(a)];
	}
};

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> rand_tree(int n){
	vvc<int> t(n);
	unionfind uf(n);
	while(uf.c>1){
		int a=rand_int(n);
		int b=rand_int(n);
		if(uf.unite(a,b)){
			t[a].pb(b);
			t[b].pb(a);
		}
	}
	return t;
}

vvc<int> readTree(int n){
	if(dbg){
		return rand_tree(n);
	}else{
		return readGraph(n,n-1);
	}
}

vi readRooted(int n){
	assert(!dbg);
	vi par(n,-1);
	rng(i,1,n){
		input(par[i]);
		par[i]--;
		assert(inc(0,par[i],i-1));
	}
	return par;
}

void printTree(const vvc<int> t){
	int n=si(t);
	int degsum=0;
	rep(i,n)degsum+=si(t[i]);
	if(degsum==n-1){
		//directed
		rep(i,si(t))for(auto j:t[i]){
			print(i+1,j+1);
		}
	}else if(degsum==2*(n-1)){
		//undirected
		rep(i,si(t))for(auto j:t[i])if(i<j){
			print(i+1,j+1);
		}
	}else{
		assert(false);
	}
}

template<class t>
vc<t> presum(const vc<t>&a){
	vc<t> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
vc<ll> presum(const vi&a){
	vc<ll> s(si(a)+1);
	rep(i,si(a))s[i+1]=s[i]+a[i];
	return s;
}
//BIT で数列を管理するときに使う (CF850C)
template<class t>
vc<t> predif(vc<t> a){
	gnr(i,1,si(a))a[i]-=a[i-1];
	return a;
}
template<class t>
vvc<ll> imos(const vvc<t>&a){
	int n=si(a),m=si(a[0]);
	vvc<ll> b(n+1,vc<ll>(m+1));
	rep(i,n)rep(j,m)
		b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j];
	return b;
}

//verify してないや
void transvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void transvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[j][i]=a[i][j];
	}
	a.swap(b);
	transvvc(n,m,args...);
}
//CF854E
void rotvvc(int&n,int&m){
	swap(n,m);
}
template<class t,class... Args>
void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){
	assert(si(a)==n);
	vvc<t> b(m,vi(n));
	rep(i,n){
		assert(si(a[i])==m);
		rep(j,m)b[m-1-j][i]=a[i][j];
	}
	a.swap(b);
	rotvvc(n,m,args...);
}

//ソートして i 番目が idx[i]
//CF850C
template<class t>
vi sortidx(const vc<t>&a){
	int n=si(a);
	vi idx(n);iota(all(idx),0);
	sort(all(idx),[&](int i,int j){return a[i]<a[j];});
	return idx;
}
//vs[i]=a[idx[i]]
//例えば sortidx で得た idx を使えば単にソート列になって返ってくる
//CF850C
template<class t>
vc<t> a_idx(const vc<t>&a,const vi&idx){
	int n=si(a);
	assert(si(idx)==n);
	vc<t> vs(n);
	rep(i,n)vs[i]=a[idx[i]];
	return vs;
}
//CF850C
vi invperm(const vi&p){
	int n=si(p);
	vi q(n);
	rep(i,n)q[p[i]]=i;
	return q;
}

template<class t,class s=t>
s SUM(const vc<t>&a){
	return accumulate(all(a),s(0));
}
template<class t,size_t K,class s=t>
s SUM(const array<t,K>&a){
	return accumulate(all(a),s(0));
}

template<class t>
t MAX(const vc<t>&a){
	return *max_element(all(a));
}

template<class t>
pair<t,int> MAXi(const vc<t>&a){
	auto itr=max_element(all(a));
	return mp(*itr,itr-a.bg);
}

template<class A>
auto MIN(const A&a){
	return *min_element(all(a));
}

template<class t>
pair<t,int> MINi(const vc<t>&a){
	auto itr=min_element(all(a));
	return mp(*itr,itr-a.bg);
}

vi vid(int n){
	vi res(n);iota(all(res),0);
	return res;
}

template<class S>
void soin(S&s){
	sort(all(s));
}

template<class S,class F>
void soin(S&s,F&&f){
	sort(all(s),forward<F>(f));
}

template<class S>
S soout(S s){
	soin(s);
	return s;
}

template<class S>
void rein(S&s){
	reverse(all(s));
}

template<class S>
S reout(S s){
	rein(s);
	return s;
}

template<class t,class u>
pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){
	a.a+=b.a;a.b+=b.b;return a;}
template<class t,class u>
pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){
	a.a-=b.a;a.b-=b.b;return a;}
template<class t,class u>
pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(a.a-b.a,a.b-b.b);}
template<class t,class u,class v>
pair<t,u>&operator*=(pair<t,u>&a,v b){
	a.a*=b;a.b*=b;return a;}
template<class t,class u,class v>
pair<t,u> operator*(pair<t,u> a,v b){return a*=b;}
template<class t,class u>
pair<t,u> operator-(pair<t,u> a){return mp(-a.a,-a.b);}
namespace std{
template<class t,class u>
istream&operator>>(istream&is,pair<t,u>&a){
	return is>>a.a>>a.b;
}
}

template<class t,size_t n>
array<t,n>&operator+=(array<t,n>&a,const array<t,n>&b){
	rep(i,n)a[i]+=b[i];
	return a;
}
template<class t,size_t n>
array<t,n>&operator-=(array<t,n>&a,const array<t,n>&b){
	rep(i,n)a[i]-=b[i];
	return a;
}
template<class t,size_t n,class v>
array<t,n>&operator*=(array<t,n>&a,v b){
	rep(i,n)a[i]*=b;
	return a;
}
template<class t,size_t n>
array<t,n> operator+(array<t,n> a,const array<t,n>&b){return a+=b;}
template<class t,size_t n>
array<t,n> operator-(array<t,n> a,const array<t,n>&b){return a-=b;}
template<class t,size_t n,class v>
array<t,n> operator*(array<t,n> a,v b){return a*=b;}

template<class t>
t gpp(vc<t>&vs){
	assert(si(vs));
	t res=move(vs.back());
	vs.pop_back();
	return res;
}

template<class t,class u>
void pb(vc<t>&a,const vc<u>&b){
	a.insert(a.ed,all(b));
}

template<class t,class...Args>
vc<t> cat(vc<t> a,Args&&...b){
	(pb(a,forward<Args>(b)),...);
	return a;
}

template<class t,class u>
vc<t>& operator+=(vc<t>&a,u x){
	for(auto&v:a)v+=x;
	return a;
}

template<class t,class u>
vc<t> operator+(vc<t> a,u x){
	return a+=x;
}

template<class t>
vc<t>& operator+=(vc<t>&a,const vc<t>&b){
	a.resize(max(si(a),si(b)));
	rep(i,si(b))a[i]+=b[i];
	return a;
}

template<class t>
vc<t> operator+(const vc<t>&a,const vc<t>&b){
	vc<t> c(max(si(a),si(b)));
	rep(i,si(a))c[i]+=a[i];
	rep(i,si(b))c[i]+=b[i];
	return c;
}

template<class t,class u>
vc<t>& operator-=(vc<t>&a,u x){
	for(auto&v:a)v-=x;
	return a;
}
template<class t,class u>
vc<t> operator-(vc<t> a,u x){
	return a-=x;
}
template<class t>
vc<t>& operator-=(vc<t>&a,const vc<t>&b){
	a.resize(max(si(a),si(b)));
	rep(i,si(b))a[i]-=b[i];
	return a;
}
/*
template<class t>
vc<t> operator-(const vc<t>&a,const vc<t>&b){
	vc<t> c(max(si(a),si(b)));
	rep(i,si(a))c[i]+=a[i];
	rep(i,si(b))c[i]-=b[i];
	return c;
}
*/
template<class t,class u>
vc<t>& operator*=(vc<t>&a,u x){
	for(auto&v:a)v*=x;
	return a;
}
template<class t,class u>
vc<t> operator*(vc<t> a,u x){
	return a*=x;
}

template<class t,class u>
vc<t>& operator/=(vc<t>&a,u x){
	for(auto&v:a)v/=x;
	return a;
}
template<class t,class u>
vc<t> operator/(vc<t> a,u x){
	return a/=x;
}

template<class t>
vc<t>& operator<<=(vc<t>&a,int k){
	assert(k>=0);
	a.insert(a.bg,k,t(0));
	return a;
}
template<class t>
vc<t> operator<<(vc<t> a,int k){
	return a<<=k;
}

template<class t>
vc<t>& operator>>=(vc<t>&a,int k){
	if(si(a)<=k)a.clear();
	else a.erase(a.bg,a.bg+k);
	return a;
}
template<class t>
vc<t> operator>>(vc<t> a,int k){
	return a>>=k;
}

template<class t,class u>
void remval(vc<t>&a,const u&v){
	a.erase(remove(all(a),v),a.ed);
}
//消した要素の個数を返してくれる
//UCUP 2-8-F
template<class t,class F>
int remif(vc<t>&a,F f){
	auto itr=remove_if(all(a),f);
	int res=a.ed-itr;
	a.erase(itr,a.ed);
	return res;
}
template<class t>
void rempos(vc<t>&a,int i){
	assert(inc(0,i,si(a)-1));
	a.erase(a.bg+i);
}

template<class VS,class u>
void fila(VS&vs,const u&a){
	fill(all(vs),a);
}

template<class t,class u>
int findid(const vc<t>&vs,const u&a){
	auto itr=find(all(vs),a);
	if(itr==vs.ed)return -1;
	else return itr-vs.bg;
}

template<class t>
void rtt(vc<t>&vs,int i){
	rotate(vs.bg,vs.bg+i,vs.ed);
}

//Multiuni2023-8 C
//f(lw)=false,...,f(n-1)=false,f(n)=true,...,f(up)=true,
//のときに n を返す
template<class F>
int find_min_true(int lw,int up,F f){
	while(up-lw>1){
		const int mid=(lw+up)/2;
		if(f(mid))up=mid;
		else lw=mid;
	}
	return up;
}
//f(lw)=true,f(up)=false
template<class F>
int find_max_true(int lw,int up,F f){
	while(up-lw>1){
		const int mid=(lw+up)/2;
		if(f(mid))lw=mid;
		else up=mid;
	}
	return lw;
}

template<class t> using pqmin=priority_queue<t,vc<t>,greater<t>>;
template<class t> using pqmax=priority_queue<t>;
using T=tuple<int,int,int>;

//N() が単位元
//VERIFY: yosupo
//CF407E
template<class N>
struct segtree{
	vc<N> x;
	int n,s;
	segtree(){}
	template<class t>
	segtree(const vc<t>&a){
		n=a.size();
		s=1;
		while(s<n){s*=2;}
		x.resize(s*2);
		rep(i,n)
			x[s+i]=N(a[i]);
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	//NOT Verified
	segtree(int nn){
		resize(nn);
	}
	void resize(int nn){
		n=nn;
		s=1;
		while(s<n){s*=2;}
		x.assign(s*2,N());
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	template<class t>
	void init(const vc<t>&a){
		n=a.size();
		s=1;
		while(s<n){s*=2;}
		x.resize(s*2);
		rep(i,n)
			x[s+i]=N(a[i]);
		rng(i,n,s)
			x[s+i]=N();
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	void clear(){
		rep(i,n)
			x[s+i]=N();
		gnr(i,1,s)
			x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	N point_get(int i){
		assert(inc(0,i,n-1));
		return x[i+s];
	}
	void point_set(int i,const N&t){
		assert(inc(0,i,n-1));
		i+=s;
		x[i]=t;
		while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	void point_merge(int i,const N&t){
		assert(inc(0,i,n-1));
		i+=s;
		x[i]=N::merge(x[i],t);
		while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	template<class F,class...Args>
	void point_change(int i,F f,Args&&...args){
		assert(inc(0,i,n-1));
		i+=s;
		(x[i].*f)(forward<Args>(args)...);
		while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
	}
	N composite(int b,int e){
		assert(0<=b&&b<=e&&e<=n);
		N lf,rt;
		for(int l=b+s,r=e+s;l<r;l>>=1,r>>=1){
			if (l&1){
				lf=N::merge(lf,x[l]);
				l++;
			}
			if (r&1){
				r--;
				rt=N::merge(x[r],rt);
			}
		}
		return N::merge(lf,rt);
	}
	N getall(){
		return x[1];
	}
	//used in namori-bisect
	template <class F,class... Args> 
	pair<int,N> max_right_withinit(int l,N sm,F f,Args&&... args){
		assert((sm.*f)(forward<Args>(args)...));
		assert(0<=l&&l<=n);
		if(l==n)return mp(n,sm);
		l+=s;
		
		assert((sm.*f)(forward<Args>(args)...));
		do {
			while (l % 2 == 0) l >>= 1;
			if (!(N::merge(sm,x[l]).*f)(forward<Args>(args)...)){
				while (l < s) {
					l = (2 * l);
					N tmp=N::merge(sm,x[l]);
					if ((tmp.*f)(forward<Args>(args)...)) {
						sm = tmp;
						l++;
					}
				}
				return mp(l - s,sm);
			}
			sm = N::merge(sm, x[l]);
			l++;
		} while ((l & -l) != l);
		return mp(n,sm);
	}
	//UCUP-2-22-K
	template <class F,class... Args> 
	pair<int,N> min_left_withinit(int r,N sm,F f,Args&&... args){
		assert((sm.*f)(forward<Args>(args)...));
		assert(0<=r&&r<=n);
        if(r==0)return mp(0,sm);
        r+=s;
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!(N::merge(x[r],sm).*f)(forward<Args>(args)...)) {
                while (r < s) {
                    r = (2 * r + 1);
                    N tmp=N::merge(x[r],sm);
                    if ((tmp.*f)(forward<Args>(args)...)) {
                        sm = tmp;
                        r--;
                    }
                }
                return mp(r + 1 - s,sm);
            }
            sm = N::merge(x[r], sm);
        } while ((r & -r) != r);
        return mp(0,sm);
    }
	//UTPC2020E
	//n 超えるかもしれない
	template <class F,class... Args> 
	pair<int,N> max_right(int l,F f,Args&&... args){
		return max_right_withinit(l,N(),f,forward<Args>(args)...);
	}
	//UTPC2020E
	template <class F,class... Args> 
	pair<int,N> min_left(int r,F f,Args&&... args){
		return min_left_withinit(r,N(),f,forward<Args>(args)...);
    }
    //行列とか乗せて必要なのはベクトルとの積，みたいなときに使える？
    //CF Goodbye 2016 E
    //CF 896 F
	template<class F,class T,class... Args>
	T accumulate(int l,int r,F f,T t,Args&&... args) {
		assert(0<=l&&l<=r&&r<=n);
		static int buf[2][30];
		int cnt[2]{};
		for(l+=s,r+=s;l<r;l>>=1,r>>=1){
			if(l&1)buf[0][cnt[0]++]=l;
			if(r&1)buf[1][cnt[1]++]=r-1;
			l++;
		}
		rep(i,cnt[0])t=(x[buf[0][i]].*f)(t,forward<Args>(args)...);
		per(i,cnt[1])t=(x[buf[1][i]].*f)(t,forward<Args>(args)...);
		return t;
	}
};

//i->par[i] と遷移すると raw[i] かかるとする
//i->...->j までの raw を全部 composite したものを考える
//これが ok な最大の j というものを取ってくる
//そこまでの composite も取ってくる
//サイクルにも対応!
//高々 upto 回までの遷移を行う
//stress-tested! (others に入れた)
template<class N>
struct namori_bisect{
	vi par;
	const int n;
	vc<N> acc;
	vi sub,head,pos,sop;
	segtree<N> seg;
	template<class t>
	vc<N> init(const vc<t>&raw){
		vvc<int> g(n);
		rep(i,n)if(par[i]!=-1)g[par[i]].pb(i);
		vi deg(n);
		rep(i,n)deg[i]=si(g[i]);
		vi q;
		rep(i,n)if(deg[i]==0)q.pb(i);
		while(si(q)){
			int v=gpp(q);
			if(par[v]!=-1){
				sub[par[v]]+=sub[v];
				if(--deg[par[v]]==0)q.pb(par[v]);
			}
		}
		int ord=0;
		vc<N> res(n);
		auto dfs=[&](auto self,int v,int h)->void{
			head[v]=h;
			if(v==h) acc[v]=raw[v];
			else acc[v]=N::merge(raw[v],acc[par[v]]);
			if(si(g[v])){
				rng(i,1,si(g[v]))
					if(sub[g[v][0]]<sub[g[v][i]])
						swap(g[v][0],g[v][i]);
				rng(i,1,si(g[v]))
					self(self,g[v][i],g[v][i]);
				self(self,g[v][0],h);
			}
			pos[v]=ord++;
			res[pos[v]]=raw[v];
			sop[pos[v]]=v;
		};
		auto work=[&](int root){
			dfs(dfs,root,root);
		};
		rep(i,n)if(par[i]==-1){
			for(auto r:g[i]){
				work(r);
			}
		}
		rep(i,n)if(deg[i]>0){
			int x=i;
			while(1){
				deg[x]=0;
				int y=par[x];
				if(y!=i){
					sub[y]+=sub[x];
					x=y;
				}else break;
			}
			remval(g[i],x);
			work(x);
			par[x]=n+i;
		}
		res.resize(ord);
		return res;
	}
	template<class t>
	namori_bisect(const vi&pp,const vc<t>&raw):par(pp),n(si(par)),
	acc(n),sub(n,1),head(n,-1),pos(n,-1),sop(n,-1),
	seg(init(raw)){}
	//v から start してどの長さまで遷移できるか
	//steps,last_vertex,data
	template <class F,class... Args> 
	tuple<int,int,N> max_len_withinit(int v,int upto,N sm,F f,Args&&... args){
		assert(inc(0,v,n-1));
		assert((sm.*f)(forward<Args>(args)...));
		int step=0;
		auto adv=[&](int u){
			assert(inc(0,u,upto));
			assert(inc(0,v,n-1));
			assert(inc(0,u,pos[head[v]]-pos[v]));
			v=sop[pos[v]+u];
			step+=u;
			upto-=u;
		};
		while(v<n&&par[v]!=-1&&upto>0){
			int h=head[v];
			int dist=pos[h]-pos[v]+1;
			if(upto<dist){//definitely ends here
				auto [u,z]=seg.max_right_withinit(pos[v],sm,f,forward<Args>(args)...);
				if(pos[v]+upto<u){
					sm=N::merge(sm,seg.composite(pos[v],pos[v]+upto));
					adv(upto);
				}else{
					sm=z;
					adv(u-pos[v]);
				}
				break;
			}else{
				N tmp=N::merge(sm,acc[v]);
				if((tmp.*f)(forward<Args>(args)...)){
					adv(dist-1);
					v=par[v];
					step++;
					upto--;
					sm=tmp;
				}else{
					auto [u,z]=seg.max_right_withinit(pos[v],sm,f,forward<Args>(args)...);
					sm=z;
					adv(u-pos[v]);
					break;
				}
			}
		}
		assert(v!=-1);
		if(upto==0||v<n){return mt(step,v%n,sm);}
		v-=n;
		int dist=0;
		N sc;
		{
			for(int x=v;x!=v+n;){
				int h=head[x];
				dist+=pos[h]-pos[x]+1;
				sc=N::merge(sc,acc[x]);
				x=par[h];
			}
		}
		static vc<N> cyc; cyc.clear();
		cyc.pb(sc);
		rep(i,100){
			if((N::merge(sm,cyc[i]).*f)(forward<Args>(args)...)&&(dist<<i)<=upto){
				cyc.pb(N::merge(cyc.back(),cyc.back()));
			}else break;
		}
		per(i,si(cyc)){
			N tmp=N::merge(sm,cyc[i]);
			if((tmp.*f)(forward<Args>(args)...)&&(dist<<i)<=upto){
				sm=tmp;
				step+=dist<<i;
				upto-=dist<<i;
			}
		}
		auto [rstep,rv,rsm]=max_len_withinit(v,upto,sm,f,forward<Args>(args)...);
		rstep+=step;
		return mt(rstep,rv,rsm);
	}
	template <class F,class... Args> 
	tuple<int,int,N> max_len(int v,F f,Args&&... args){
		return max_len_withinit(v,inf,N(),f,forward<Args>(args)...);
	}
};

//point2d_general,wavelet 等で使用
template<class t>
struct vec2d{
	int n,s,used;
	vc<t*> x;
	vi lens;
	unique_ptr<t[]> p;
	vec2d(int nn,int ss):n(nn),s(ss),used(0),x(n,nullptr),lens(n),p(new t[s]){}
	void init(int i,int len){
		assert(lens[i]==0);
		assert(len>=0);
		x[i]=p.get()+used;
		lens[i]=len;
		used+=len;
		assert(used<=s);
	}
	t* operator[](int i){
		assert(inc(0,i,n-1));
		return x[i];
	}
};

//pos と言ったときには元の数列での位置を意味する．
//id と言ったときにはソート済み列での位置を意味する．
template<class t,class V>
struct wavelet{
	const vc<t> a;
	const vc<V> wei;
	const int n,L,s;
	vc<t> st;
	vi i2p;
	vec2d<int> pos;
	vec2d<pi> cut;
	vec2d<V> sum;
	void presum(int len,int*b,V*z){
		rep(i,len)z[i+1]=z[i]+wei[b[i]];
	}
	void merge_with_cut(int ls,int *l,int rs,int *r,int *b,pi *c){
		c[0]=pi(0,0);
		int x=0,y=0;
		rep(i,ls+rs){
			bool usel=true;
			if(x==ls||(y<rs&&l[x]>r[y]))usel=false;
			if(usel)b[i]=l[x++];
			else b[i]=r[y++];
			c[i+1]=pi(x,y);
		}
	}
	wavelet(const vc<t>&aa,const vc<V>&ww):a(aa),wei(ww),n(si(a)),L(topbit(max<int>(n-1,1))+1),s(1<<L),
		st(n),i2p(n),pos(s*2,(L+1)*n),cut(s*2,L*n+s),sum(s*2,(L+1)*n+s*2)
	{
		{
			iota(all(i2p),0);
			stable_sort(all(i2p),[&](int i,int j){return a[i]<a[j];});
			rep(i,n)st[i]=a[i2p[i]];
			rep(i,n){
				pos.init(s+i,1);
				pos[s+i][0]=i2p[i];
			}
		}
		gnr(i,1,s){
			int ls=pos.lens[i*2];
			int rs=pos.lens[i*2+1];
			pos.init(i,ls+rs);
			cut.init(i,ls+rs+1);
			merge_with_cut(ls,pos[i*2],rs,pos[i*2+1],pos[i],cut[i]);
		}
		rng(i,1,s*2){
			sum.init(i,pos.lens[i]+1);
			presum(pos.lens[i],pos[i],sum[i]);
		}
	}
	pi lrL(int i,int l,int r){
		return pi(cut[i][l].a,cut[i][r].a);
	}
	pi lrR(int i,int l,int r){
		return pi(cut[i][l].b,cut[i][r].b);
	}
	//kth-smallest value in a
	t kth(int k){
		assert(inc(0,k,n-1));
		return st[k];
	}
	//value v 以上になる最初の id を返す
	int lwbval(t v){
		return lwb(st,v);
	}
	//id of kth-smallest value in [l,r)
	int kthid(int l,int r,int k){
		assert(0<=l&&l<=r&&r<=n);
		assert(inc(0,k,r-l-1));
		int i=1;
		while(i<s){
			auto [x,y]=lrL(i,l,r);
			auto [z,w]=lrR(i,l,r);
			if(y-x<=k){
				k-=y-x;
				i=i*2+1;
				l=z,r=w;
			}else{
				i=i*2;
				l=x,r=y;
			}
		}
		assert(k==0);
		return i-s;
	}
	//value of kth-smallest value in [l,r)
	t kthval(int l,int r,int k){
		assert(0<=l&&l<=r&&r<=n);
		return kth(kthid(l,r,k));
	}
	//positin [l,r) にある値のなかで，tar 以上の最小の id 返す
	//ないなら S
	int lwbid(int l,int r,int tar){
		assert(0<=l&&l<=r&&r<=n);
		assert(inc(0,tar,n));
		if(tar==n)return s;
		if(inc(l,i2p[tar],r-1))return tar;
		tar+=s;
		pi buf[30];
		per(h,L){
			int i=tar>>(h+1);
			if((tar>>h)&1){
				tie(l,r)=lrR(i,l,r);
			}else{
				buf[h]=lrR(i,l,r);
				tie(l,r)=lrL(i,l,r);
			}
		}
		rep(h,L)if(((tar>>h)&1)==0){
			int i=(tar>>h)+1;
			tie(l,r)=buf[h];
			if(l==r)continue;
			while(i<s){
				auto [x,y]=lrL(i,l,r);
				auto [z,w]=lrR(i,l,r);
				if(x==y){
					i=i*2+1;
					l=z,r=w;
				}else{
					i=i*2;
					l=x,r=y;
				}
			}
			return i-s;
		}
		return s;
	}
	//position [l,r) にある値のなかで，id が tar 未満の個数を返す
	int countid(int l,int r,int tar){
		assert(0<=l&&l<=r&&r<=n);
		assert(inc(0,tar,n));
		if(tar==n)return r-l;
		
		tar+=s;
		int res=0;
		per(h,L){
			int i=tar>>(h+1);
			if((tar>>h)&1){
				auto [x,y]=lrL(i,l,r);
				res+=y-x;
				tie(l,r)=lrR(i,l,r);
			}else{
				tie(l,r)=lrL(i,l,r);
			}
		}
		
		return res;
	}
	//position [l,r) にある値のなかで，value が val 未満の個数を返す
	int countval(int l,int r,t val){
		return countid(l,r,lwbval(val));
	}
	//position [l,r) にある値のなかで，value が [d,u) の個数を返す
	int countval(int l,int r,t d,t u){
		return countval(l,r,u)-countval(l,r,d);
	}
	//position [l,r) にある値のなかで，id が tar 未満の要素に紐付いた sum を返す
	V sumid(int l,int r,int tar){
		assert(0<=l&&l<=r&&r<=n);
		assert(inc(0,tar,n));
		if(tar==n)return sum[1][r]-sum[1][l];
		
		tar+=s;
		V res=0;
		per(h,L){
			int i=tar>>(h+1);
			if((tar>>h)&1){
				auto [x,y]=lrL(i,l,r);
				res+=sum[i*2][y]-sum[i*2][x];
				tie(l,r)=lrR(i,l,r);
			}else{
				tie(l,r)=lrL(i,l,r);
			}
		}
		
		return res;
	}
	//position [l,r) にある値のなかで，value が val 未満の要素に紐付いた sum を返す
	V sumval(int l,int r,t val){
		return sumid(l,r,lwbval(val));
	}
};

//平面上に点がたくさん (static)
//矩形クエリ
//stress-tested (without define int ll)
template<class V> //重み
struct wavelet_helper{
	const int n;
	vi xs,ys;
	vc<V> ws;
	wavelet<int,V> wv;
	void init(vc<tuple<int,int,V>>xyw){
		soin(xyw);
		rep(i,n){
			auto [x,y,w]=xyw[i];
			xs[i]=x;
			ys[i]=y;
			ws[i]=w;
		}
	}
	wavelet_helper(const vc<tuple<int,int,V>>&xyw):
		n(si(xyw)),xs(n),ys(n),ws(n),
		wv((init(xyw),ys),ws){}
	//[l,r)*[-inf,y) 内の点の重みの総和
	V rect_low(int l,int r,int y){
		assert(l<=r);
		l=lwb(xs,l);
		r=lwb(xs,r);
		return wv.sumval(l,r,y);
	}
};

//[l,r)
//Yandex Finals 2024 C
void meld(vc<pi>&vs){
	//soin(vs);
	int s=0;
	for(auto&[l,r]:vs){
		if(s&&vs[s-1].b>=l){
			chmax(vs[s-1].b,r);
		}else{
			vs[s++]={l,r};
		}
	}
	vs.resize(s);
}

#ifdef LOCAL
const int V=10;
#else
const int V=ten(6)+1;
#endif

struct N{
	int len;
	ll cost;
	N():len(0),cost(0){}
	N(int a,ll b):len(a),cost(b){}
	static N merge(const N&x,const N&y){
		return N(x.len+y.len,x.cost+y.cost);
	}
	bool ok(int v){return len<=v;}
};

template<class HF,class VF>
struct UpperPath{
	const int flip;
	const int ward;
	const vvc<pi>&blocks;
	HF hff;
	VF vff;
	vi off;
	int n;
	vi par;
	vc<N> val;
	vc<pi> xys;
	namori_bisect<N> z;
	ll hf(int v,int l,int r){
		if(ward){
			v=V-v;
			l=V-l;
			r=V-r;
			swap(l,r);
		}
		return flip?vff(v,l,r):hff(v,l,r);
	}
	ll vf(int v,int l,int r){
		if(ward){
			v=V-v;
			l=V-l;
			r=V-r;
			swap(l,r);
		}
		return flip?hff(v,l,r):vff(v,l,r);
	}
	void init(){
		off.resize(V+1);
		rep(i,V)off[i+1]=off[i]+si(blocks[i]);
		n=off[V];
		par.resize(n,-1);
		val.resize(n);
		xys.resize(n);
		rep(i,V)rep(j,si(blocks[i]))xys[off[i]+j]=pi(i+1,blocks[i][j].a);
		rep(i,V){
			rep(j,si(blocks[i])){
				int k=-1;
				if(i+1<V){
					k=lwb(blocks[i+1],pi(blocks[i][j].a,-1));
					if(k==si(blocks[i+1]))k=-1;
				}
				if(k!=-1){
					int l=blocks[i][j].a,r=blocks[i+1][k].a;
					int len=r-l+1;
					int cost=vf(i+1,l,r)+hf(r,i+1,i+2);
					par[off[i]+j]=off[i+1]+k;
					val[off[i]+j]=N(len,cost);
				}
			}
		}
	}
	UpperPath(int fl,int wa,const vvc<pi>&bb,HF hh,VF vv):
	flip(fl),ward(wa),
	blocks(bb),hff(hh),vff(vv),z((init(),par),val){}
	tuple<int,int,ll> ask(int x,int y,int steps,bool calccost){
		if(flip)swap(x,y);
		if(ward){
			x=V-x;
			y=V-y;
		}
		auto hfc=[&](int v,int l,int r)->ll{
			if(calccost){
				return hf(v,l,r);
			}else{
				return 0;
			}
		};
		auto vfc=[&](int v,int l,int r)->ll{
			if(calccost){
				return vf(v,l,r);
			}else{
				return 0;
			}
		};
		ll cost=0;
		auto advh=[&](int u){
			cost+=hfc(y,x,x+u);
			x+=u;
			steps-=u;
		};
		auto advv=[&](int u){
			cost+=vfc(x,y,y+u);
			y+=u;
			steps-=u;
		};
		int k=lwb(blocks[x],pi(y,-1));
		if(k==si(blocks[x])||blocks[x][k].a-y>=steps){
			advv(steps);
		}else{
			int start=off[x]+k;
			advv(blocks[x][k].a-y);
			advh(1);
			auto [dummy,v,nd]=z.max_len(start,&N::ok,steps);
			tie(x,y)=xys[v];
			cost+=nd.cost;
			steps-=nd.len;
			advv(steps);
		}
		if(ward){
			x=V-x;
			y=V-y;
		}
		if(flip)swap(x,y);
		return mt(x,y,cost);
	}
};

void slv(){
	INT(n,q);
	VPI(xy,n);
	if(dbg){
		mkuni(xy);
		n=si(xy);
	}
	
	vvc<pi> blocks[2][2];
	
	rep(flip,2){
		vvc<pi> obs(V);
		for(auto[x,y]:xy){
			obs[x].eb(y,y+1);
		}
		rep(x,V)soin(obs[x]);
		rep(_,2){
			rep(x,V)if(si(obs[x])){
				for(auto&[l,r]:obs[x]){
					int i=lwb(obs[x-1],pi(r+1,-1));
					if(i>0)chmax(r,obs[x-1][i-1].b);
				}
				meld(obs[x]);
			}
			rein(obs);
			for(auto&ls:obs){
				rein(ls);
				for(auto&[l,r]:ls){
					l=V-l;
					r=V-r;
					swap(l,r);
				}
			}
		}
		rep(ward,2){
			blocks[flip][ward]=obs;
			rein(obs);
			for(auto&ls:obs){
				rein(ls);
				for(auto&[l,r]:ls){
					l=V-l;
					r=V-r;
					swap(l,r);
				}
			}
		}
		for(auto&[x,y]:xy)swap(x,y);
	}
	
	dmp(blocks[0][0]);
	dmp(blocks[1][0]);
	dmp(blocks[1][1]);
	
	vi freecnt(V,V);
	rep(i,V)for(auto [l,r]:blocks[0][0][i])
		freecnt[i]-=r-l;
	vc<ll> freesum=presum(freecnt);
	
	vc<tuple<int,int,ll>> bottoms;
	rep(i,V)for(auto [l,r]:blocks[0][0][i])
		bottoms.eb(i,l,r-l);
	wavelet_helper<ll> wh(bottoms);
	
	auto belowgood=[&](int h,int l,int r){
		assert(inc(0,h,V));
		assert(0<=l&&l<=r&&r<=V);
		ll res=ll(h)*(r-l);
		res-=wh.rect_low(l,r,h);
		return res;
	};
	auto abovegood=[&](int h,int l,int r){
		return (freesum[r]-freesum[l])-belowgood(h,l,r);
	};
	auto zerogood=[&](int,int,int){return 0;};
	
	UpperPath U(0,0,blocks[0][0],belowgood,zerogood);
	UpperPath D(0,1,blocks[0][1],abovegood,zerogood);
	UpperPath R(1,0,blocks[1][0],abovegood,zerogood);
	UpperPath L(1,1,blocks[1][1],belowgood,zerogood);
	
	auto inside=[&](int x,int y){
		int k=lwb(blocks[0][0][x],pi(y+1,-1));
		return k>0&&y<blocks[0][0][x][k-1].b;
	};
	
	rep(_,q){
		INT(sx,sy,tx,ty);
		if(dbg){
			if(sx>tx)swap(sx,tx);
			if(sy>ty)swap(sy,ty);
		}
		if(inside(sx,sy)||inside(tx,ty)){
			print(0);
		}else{
			tx++;
			ty++;
			int dist=tx-sx+ty-sy;
			{
				auto [x,y,dummy]=U.ask(sx,sy,dist,false);
				if(tx<x){
					print(0);
					continue;
				}
			}
			{
				auto [x,y,dummy]=R.ask(sx,sy,dist,false);
				if(x<tx){
					print(0);
					continue;
				}
			}
			{
				auto [x,y,dummy]=L.ask(tx,ty,dist,false);
				if(sx<x){
					print(0);
					continue;
				}
			}
			{
				auto [x,y,dummy]=D.ask(tx,ty,dist,false);
				if(x<sx){
					print(0);
					continue;
				}
			}
			dmp2(sx,sy,tx,ty);
			ll ans=0;
			ans+=[&](){
				int l=-1,r=dist+1;
				while(1){
					int m=(l+r)/2;
					assert(l<m&&m<r);
					auto [x,y,tmp1]=U.ask(sx,sy,m,false);
					auto [u,v,tmp2]=L.ask(tx,ty,dist-m,false);
					if(x==u){
						return
							get<2>(U.ask(sx,sy,m,true))+
							get<2>(L.ask(tx,ty,dist-m,true));
					}else if(x<u){
						r=m;
					}else{
						l=m;
					}
				}
			}();
			ans+=[&](){
				int l=-1,r=dist+1;
				while(1){
					int m=(l+r)/2;
					assert(l<m&&m<r);
					auto [x,y,tmp1]=R.ask(sx,sy,m,false);
					auto [u,v,tmp2]=D.ask(tx,ty,dist-m,false);
					dmp(m);
					dmp2(x,y);
					dmp2(u,v);
					if(x==u){
						return
							get<2>(R.ask(sx,sy,m,true))+
							get<2>(D.ask(tx,ty,dist-m,true));
					}else if(x>u){
						r=m;
					}else{
						l=m;
					}
				}
			}();
			ans-=(freesum[tx]-freesum[sx]);
			print(ans);
		}
	}
}

signed main(signed argc,char*argv[]){
	if(argc>1&&strcmp(argv[1],"D")==0)dbg=true;
	
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	if(dbg){
		while(1){
			if(current_run_id%run_batch_size==0){
				cerr<<"Current Run "<<current_run_id<<endl;
			}
			slv();
			current_run_id++;
		}
	}else{
		//INT(t);rep(_,t)
		slv();
	}
}