#include<cstdio>

 #include<iostream>

 #include<cstdlib>

 #include<iomanip>

 #include<cmath>

 #include<cstring>

 #include<string>

 #include<algorithm>

 #include<time.h>

 #include<queue>

 using namespace std;//一堆头文件

 typedef long long ll;

 typedef long double ld;

 typedef pair<int,int> pr;

 const double pi=acos(-);

 #define rep(i,a,n) for(int i=a;i<=n;i++)

 #define per(i,n,a) for(int i=n;i>=a;i--)//一群for循环

 #define Rep(i,u) for(int i=head[u];i;i=Next[i])

 #define clr(a) memset(a,0,sizeof a)

 #define pb push_back

 #define mp make_pair

 #define fi first

 #define sc second

 ld eps=1e-;

 ll pp=;

 ll mo(ll a,ll pp){if(a>= && a<pp)return a;a%=pp;if(a<)a+=pp;return a;}//模运算优化

 ll powmod(ll a,ll b,ll pp){ll ans=;for(;b;b>>=,a=mo(a*a,pp))if(b&)ans=mo(ans*a,pp);return ans;}//快速幂

 ll read(){

     ll ans=;

     char last=' ',ch=getchar();

     while(ch<'' || ch>'')last=ch,ch=getchar();

     while(ch>='' && ch<='')ans=ans*+ch-'',ch=getchar();

     if(last=='-')ans=-ans;

     return ans;

 }//快读

 //head//防止找不到从哪里开始...