#include <algorithm>

#include <bitset>

#include <cassert>

#include <cfloat>

#include <climits>

#include <cmath>

#include <complex>

#include <cstddef>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <fstream>

#include <functional>

#include <iomanip>

#include <iostream>

#include <iterator>

#include <list>

#include <limits>

#include <map>

#include <memory>

#include <numeric>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <string>

#include <utility>

#include <vector>

using namespace std;

#define _USE_MATH_DEFINES // exposes constants, eg. M_PI

#define S(n) scanf("%d",&n)

#define SLL(n) scanf("%lld",&n)

#define SD(n) scanf("%lf",&n)

#define SS(n) scanf("%s",n)

#define INF INT_MAX

#define LINF LLONG_MAX

#define EPS std::numeric_limits<double>::epsilon()

#define ABS(x) ((x)<0?-(x):(x))

#define FOR(i,a,b) for(int i=a;i<b;++i)

#define RFOR(i,a,b) for(int i=(a)-1,_b(b);i>=_b;--i)

#define REP(i,n) for(int (i)=0;(i)<(int)(n);++(i))

#define RREP(i,n) for(int (i)=n;(i)>=(int)0;--(i))

#define DREP(a) sort(all(a)); a.erase(unique(all(a)),a.end())

#define INDEX(arr,ind) (lower_bound(all(arr),ind)-arr.begin())

#define FOREACH(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)

#define mp make_pair

#define pb push_back

#define tri(a,b,c) mp(a,mp(b,c))

#define fst first

#define snd second

#define SQT(a) ((a)*(a))

#define ALL(x) x.begin(),x.end()

#define SZ(v) ((int)(v.size()))

#define LOG(a) (cerr<<"\tline#"<<__LINE__<<": "#a" = "<<(a)<<endl)

#define DBG(args...) {cerr<<"\tcase#"<<(cc+1)<<": ";dbg,args;cerr<<endl;}

struct debugger {

} dbg;

typedef long long LL;

typedef long long ll;

typedef unsigned long long ULL;

typedef unsigned int uint;

typedef pair<int, int> PII;

typedef pair<LL, LL> PLL;

typedef pair<int, PII> TRI;

typedef vector<int> VI;

typedef vector<LL> VL;

typedef vector<string> VS;

typedef vector<PII> VII;

typedef vector<PLL> VLL;

typedef vector<TRI> VT;

typedef vector<VI> VVI;

typedef vector<VL> VVL;

typedef vector<VII> VVII;

typedef vector<VLL> VVLL;

typedef vector<VT> VVT;

typedef complex<double> pt;

typedef complex<LL> pti;

const double PI = M_PI;

template<class T> inline T gcd(T a, T b)

{

return b ? gcd(b, a % b) : a;

}

inline double round(double x)

}

inline int cmp(double x, double y = 0, double tol = EPS)

{

return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;

}

template<typename T> inline void print(T *array, int size)

}

template<typename T> inline void print(T **array, int size1, int size2)

}

int T;

int main()

}