#define新用法

#include<cstdio>

#include<cctype>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<climits>

#include<iostream>

#include<sstream>

#include<algorithm>

#include<functional>

#include<numeric>

#include<utility>

#include<vector>

#include<string>

#include<bitset>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<set>

#include<map>

usingnamespacestd;

#defineFin(f) freopen(f, "r", stdin)

#defineFout(f) freopen(f, "w", stdout)

#defineSR() srand((unsigned)time(NULL))

#definerandom(m) ((rand() << 16 | rand()) % m) /// [0,m)之间的伪随机数

#defineall(a) a.begin(), a.end()

#defineInter(v, a, n, b, m) v.resize(set_intersection(a, a + (n), b, b + (m), v.begin()) - v.begin())

#defineSInter(v, a, n, b, m) v.resize((n) + (m)); sort(a, a + (n)); sort(b, b + (m)); Inter(v, a, n, b, m)

#defineUnion(v, a, n, b, m) v.resize(set_union(a, a + (n), b, b + (m), v.begin()) - v.begin());

#defineSUnion(v, a, n, b, m) v.resize((n) + (m)); sort(a, a + (n)); sort(b, b + (m)); Union(v, a, n, b, m)

#defineDiff(v, a, n, b, m) v.resize(set_difference(a, a + (n), b, b + (m), v.begin()) - v.begin())

#defineSDiff(v, a, n, b, m) v.resize((n) + (m)); sort(a, a + (n)); sort(b, b + (m)); Diff(v, a, n, b, m)

#defineSym(v, a, n, b, m) v.resize(set_symmetric_difference(a, a + (n), b, b + (m) v.begin()) - v.begin())

#defineSSym(v, a, n, b, m) v.resize((n) + (m)); sort(a, a + (n)); sort(b, b + (m)); Sym(v, a, n, b, m)

#definePB push_back

#defineMP make_pair

#defineCnt1(n) (__builtin_popcount(n))

#defineCntt1(n) (__builtin_popcountll(n)) /// 参数必须为ull类型

#definecb(n) (32 - __builtin_clz(n))

#definecbb(n) (64 - __builtin_clzll(n)) /// 参数必须为ull类型

#definesq(x) ((x) * (x))

#defineSqrt(n) (int)sqrt(0.5 + n)

#definePB push_back

#defineMP make_pair

#defineall(a) a.begin(), a.end()

#defineUni(a) a.resize(unique(all(a)) - a.begin()) /// STL专用

#defineSUni(a) sort(all(a)); Uni(a) /// STL专用

#defineUnii(a, n) (unique(a, a + (n)) - a) /// 使用前请sort

#defineAcc(a, n) (accumulate(a, a + (n), 0)) /// 注意0LL!!!!!以及0.0!!!

#defineAaddB(a, n, b) transform(a, a + (n), b, a, plus<int>()) /// *慢的话就改为For(i, n) a[i] += b[i](注意加int i)

#defineCnt1(n) (__builtin_popcount(n))

#defineCntt1(n) (__builtin_popcountll(n)) /// 参数必须为ull类型

#definecb(n) (32 - __builtin_clz(n))

#definecbb(n) (64 - __builtin_clzll(n)) /// 参数必须为ull类型

#definesq(x) ((x) * (x))

#defineSqrt(n) (int)sqrt(0.5 + n)

#definemem(a, num) memset(a, num, sizeof(a))

#definecpy(to, from) memcpy(to, from, sizeof(from))

#defineRcpy(l, r, b) reverse_copy(l, r, b) /// 注意为左闭右开区间

#defineFor(i, n) for (i = 0; i < (n); ++i)

#defineForr(i, start, n) for (i = start; i < (n); ++i)

#defineForrr(i, start, n, step) for (i = start; i < (n); i += (step))

#definerFor(i, n) for (i = (n); i >= 0; --i)

#definerForr(i, n, end) for (i = n; i >= (end); --i)

#definerForrr(i, n, end, step) for (i = n; i >= (end); i -= (step))

#defineSI(a) scanf("%d", &a)

#defineSII(a, b) scanf("%d%d", &a, &b)

#defineSIII(a, b, c) scanf("%d%d%d", &a, &b, &c)

#defineSIIII(a, b, c, d) scanf("%d%d%d%d", &a, &b, &c, &d)

#defineSIIIII(a, b, c, d, e) scanf("%d%d%d%d%d", &a, &b, &c, &d, &e)

#defineSIIIIII(a, b, c, d, e, f) scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f)

#defineSL(a) scanf("%lld", &a)

#defineSLL(a, b) scanf("%lld%lld", &a, &b)

#defineSLLL(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)

#defineSLLLL(a, b, c, d) scanf("%lld%lld%lld%lld", &a, &b, &c, &d)

#defineSD(a) scanf("%lf", &a)

#defineSDD(a, b) scanf("%lf%lf", &a, &b)

#defineSDDD(a, b, c) scanf("%lf%lf%lf", &a, &b, &c)

#defineSDDDD(a, b, c, d) scanf("%lf%lf%lf%lf", &a, &b, &c, &d)

#defineSA(a, i, n) For(i, n) scanf("%d", a + i) /// 便于扩展 *不要在后面加逗号！

#defineSAA(a, i, n, j, m) For(i, n) For(j, m) SI(a[i][j]) /// *不要在后面加逗号！

#defineGC(c) (c = getchar())

#defineGCn() getchar()

#defineUC(c) ungetc(c, stdin)

#defineSS(s) scanf("%s", s)

#defineSSS(s, s2) scanf("%s%s", s, s2)

#defineSC(c) scanf(" %c", &c)

#definePI(a) printf("%dn", a)

#definePII(a, b) printf("%d%dn", a, b)

#definePIII(a, b, c) printf("%d%d%dn", a, b, c)

#definePIIII(a, b, c, d) printf("%d%d%d%dn", a, b, c, d)

#definePIIIII(a, b, c, d, e) printf("%d%d%d%d%dn", a, b, c, d, e)

#definePL(a) printf("%lldn", a)

#definePLL(a, b) printf("%lld%lldn", a, b)

#definePLLL(a, b, c) printf("%lld%lld%lldn", a, b, c)

#definePD(a) printf("%fn", a)

#definePDD(a, b) printf("%f%fn", a, b)

#definePDDD(a, b, c) printf("%f%f%fn", a, b, c)

#definePA(a, i, n) For(i, (n) - 1) printf("%d ", a[i]); PI(a[(n) - 1]) /// *(有时要在前面加花括号)由于要支持STL的数据类型，故不用+的形式，必要时请手动改成+

#definePAA(a, i, n, j, m) For(i, n) {For(j, (m) - 1) printf("%d ", a[i][j]); PI(a[i][(m) - 1]);}

#definePAn(a, i, n) For(i, n) PI(a[i])

#definePiA(a, i, n) For(i, n) PII(i, a[i]) /// debug用

#definerPA(a, i, n) rForr(i, n - 1, 1) printf("%d ", a[i]); PI(a[0]) /// *(有时要在前面加花括号)

#definerPAn(a, i, n) rFor(i, n - 1) PI(a[i])

#definePC(c) putchar(c)

#definePn() putchar(10)

#definePs() putchar(32)

#defineUni(a) a.resize(unique(all(a)) - a.begin()) /// STL专用

#defineSUni(a) sort(all(a)); Uni(a) /// STL专用

#defineUnii(a, n) (unique(a, a + (n)) - a)

#defineSUnii(a, n) sort(a, a + n); Unii(a, n)

#defineAcc(a, n) (accumulate(a, a + (n), 0)) /// 注意0LL!!!!!以及0.0!!!

#defineAaddB(a, n, b) transform(a, a + (n), b, a, plus<int>()) /// *慢的话就改为For(i, n) a[i] += b[i](注意加int i)

#definemem(a, num) memset(a, num, sizeof(a))

#definecpy(to, from) memcpy(to, from, sizeof(from))

#defineRcpy(l, r, b) reverse_copy(l, r, b) /// 注意为左闭右开区间

#definekTo10(ans, str, s, m, k) strncpy(str, s, m), str[m] = 0, ans = strtol(str, NULL, k)

#definegr() greater<int>()

#definenth(a, k, n) nth_element(a + 0, a + k, a + n) /// *可能要事先--k

#definenthg(a, k, n) nth_element(a + 0, a + k, a + n, greater<int>()) /// *可能要事先--k

#defineMin(a, n) (*min_element(a, a + (n)))

#defineMax(a, n) (*max_element(a, a + (n)))

#defineMinpos(a, n) (min_element(a, a + (n)) - (a))

#defineMaxpos(a, n) (max_element(a, a + (n)) - (a))

#defineLowpos(a, n, x) (lower_bound(a, a + (n), x) - (a)) /// *加个gr()变成<=

#defineUpppos(a, n, x) (upper_bound(a, a + (n), x) - (a)) /// *加个gr()变成<

#defineBS(a, n, x) binary_search(a, a + (n), x) /// 返回bool值

#defineRange(a, n, x) equal_range(a, a + (n), x) /// 返回pair

#defineFpos(a, n, x) (find(a, a + (n), x) - (a))

#defineFd(a, x) (find(all(a), x) != a.end())

constint inf = 0x3f3f3f3f; /// 1.06e9 (INT_MAX为2.147e9)

constlonglong llinf = 0x3f3f3f3f3f3f3f3fLL; /// 4.56e18 (LLONG_MAX为9.22e18)

constdouble pi = acos(-1.0);

//const double tens[11] = {0.0, 1e-1, 1e-2, 1e-3, 1e-4, 1e-5, 1e-6, 1e-7, 1e-8, 1e-9, 1e-10};

//double fgcd(double a, double b) {return fabs(b) > eps ? fgcd(b, fmod(a, b)) : a;}

//const int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

//const int dirr[8][2] = {1, 0, 1, 1, 0, 1, -1, 1, -1, 0, -1, -1, 0, -1, 1, -1};

//const int knight_dir[8][2] = {1, 2, 1, -2, -1, 2, -1, -2, 2, 1, 2, -1, -2, 1, -2, -1};

/// 不可使用如下间接保留字：rank, tm,time, write, j0,j1,jn,y0,y1,yn

/// 如果用gets(s), GC(ch)读入WA的话，请用SS(s), scanf(" %c ", &ch)代替

/// 在main()中大量初始化STL类型容易死机

/// 注意strncpy不会加尾0，请手动添加

/// 相对位置不变的排序stable_sort(a, a + n);

/// C++会帮你往上类型转换，但G++不会

/*G++扩栈

int __size__ = 256 << 20; // 256MB

char *__p__ = (char*)malloc(__size__) + __size__;

__asm__("movl %0, %%espn" :: "r"(__p__));

*/

//ios_base::sync_with_stdio(false);

typedefunsignedint ui;

typedeflonglong ll;

typedefunsignedlonglong ull;

typedeflongdouble ld;

typedef vector<int>::iterator viter;

typedef set<int>::iterator siter; /// *请即时修改模板参数

typedef map<int, int>::iterator miter; /// *请即时修改模板参数

typedef multiset<int>::iterator msiter;

typedef multimap<int, int>::iterator mmter;

typedef priority_queue<int> pqi; /// *请即时修改模板参数

typedef priority_queue<int, vector<int>, greater<int> > spqi; /// 小的在top  *请即时修改模板参数

typedef pair<int, int> p2; /// 赋值时直接SII(a[i].x, a[i].y)就行, 有时候用LL

typedef pair<pair<int, int>, int> p3;

typedef pair<int, pair<int, int> > pi3;

//#define x first

//#define y second

//#define MT(a, b, c) make_pair(make_pair(a, b), c)

#defineloop(it, a) for (it = a.begin(); it != a.end(); ++it)

//const double eps = 1e-8;

//const ll mod = ll(1e9) + 7; /// *或int

#definePcas() printf("Case %d: ", ++cas) /// *注意C的大小写