template <typename T> inline void read(T& t) {
    int f = 0, c = getchar(); t = 0; 
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
    if (f) t = -t;
}

template <typename T> void print(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) print(x / 10);
    putchar(x % 10 + 48);
} 


#define rep(i, a, b) for(int i = a; i <= b; i ++)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define dbg(a)  cout<<#a<<" : "<<a<<endl;
#define IOS std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define PAUSE   system("pause")
#define sd(a)       scanf("%d",&a)
#define sll(a)      scanf("%intd",&a)
#define sdd(a,b)    scanf("%d%d",&a,&b)
#define sddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sf(a)       scanf("%lf",&a)
#define sff(a,b)    scanf("%lf%lf",&a,&b)

int read()
{
    int x = 0, fx = 1; char c = getchar();
    while (c < '0' || c > '9') { fx ^= ((c == '-') ? 1 : 0); c = getchar(); }
    while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
    if (!fx) return -x;
    return x;
}

#include <bits/stdc++.h>
#include <unordered_set>
//#include <unordered_map>
//#include <regex>
using namespace std;
#define ll long long
#define debug(x) cerr<<#x<<" : "<<x<<endl
//#define rep(i,_begin,_end) for (auto i=(_begin),_step=1-2*((_begin)>(_end));i!=_end;i+=_step)
#define MOD 1000000007
const double PI = acos(-1);
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pii, int> piii;
typedef unsigned long long ull;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
const int ddx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }, ddy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
// INPUT
template<typename T>
inline void in(T& x) {
    T s = 0, w = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-')w = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    x = s * w;
}
// gcd
template<typename T>
T gcd(T a, T b) { return (!b) ? a : gcd(b, a % b); }
// min
template<class T>
T min(const vector<T>& v) { return *min_element(v.begin(), v.end()); }
// max
template<class T>
T max(const vector<T>& v) { return *max_element(v.begin(), v.end()); }
// lowbit
inline int lowbit(int x) { return x & (-x); }
// modadd
inline int modadd(int x, int y) { return (x + y >= MOD ? x + y - MOD : x + y); }
// sgn
inline int sgn(int x) { return (x < 0 ? -1 : (x > 0 ? 1 : 0)); }
// ab
inline ll ab(ll x) { return x < 0 ? -x : x; }
#define modu MOD