struct nd{
    int d, u;
    bool operator < (const nd &a) const {
        return d>a.d;
    }
};
int d[maxn]; bool vis[maxn]; priority_queue<nd>q;
void dijkstra(int s,int t){
    inc(i,0, n) d[i]=INF; d[s] = 0; q.push((nd){0, s});
    while (!q.empty()) {
        int x; while (!q.empty() && vis[x = q.top().u]) q.pop();
        if (vis[x]) break; vis[x] = 1;
        for (int i = g[x]; i; i = es[i].n)
            if (d[es[i].t] > d[x] + es[i].w) {
                d[es[i].t] = d[x] + es[i].w;
                q.push((nd){d[es[i].t], es[i].t});
            }
    }
}

int cnt[maxn]; int d[maxn]; bool inq[maxn]; deque<int> q;
int spfa(int s, int t) {
    memset(inq, false, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    inc(i, 0, n) d[i] = INF;
    q.push_back(s); inq[s] = true; d[s] = 0; cnt[s] = 1;
    while (!q.empty()) {
        int x = q.front(); q.pop_front(); inq[x] = false;
        for(int i = g[x]; i; i = es[i].n)
            if (d[es[i].t] > d[x] + es[i].w) {
            d[es[i].t] = d[x] + es[i].w;
            if (!inq[es[i].t]) {
                if (!q.empty() && d[es[i].t] < d[q.front()])
                    q.push_front(es[i].t);
                else q.push_back(es[i].t);
                inq[es[i].t] = true; cnt[es[i].t]++;
                if(cnt[es[i].t] >= n) return -1;
            }
        }
    }
    if(d[t] == INF) return -2; return d[t];
}

void pe(int f, int t, int c) {
    es[++ess] = (e){t, c, g[f]}; g[f]=ess;
    es[++ess]= (e) {f, 0, g[t]}; g[t]=ess;
}
void init() {
    ess = -1; memset(g, -1, sizeof(g));
}
queue <int> q; int h[maxn];
bool bfs(int s, int t) {
    memset(h, -1, sizeof(h)); while (!q.empty()) q.pop();
    h[s] = 0; q.push(s);
    while (! q.empty()) {
        int x = q.front(); q.pop();
        for (int i = g[x]; i != -1; i = es[i].n)
            if (es[i].c && h[es[i].t] == -1) {
                h[es[i].t]=h[x]+1; q.push(es[i].t);
            }
    }
    return h[t] != -1;
}
int dfs(int x, int t, int f) {
    if (x == t)return f; int u = 0;
    for(int i = g[x]; i != -1; i = es[i].n)
        if (es[i].c && h[es[i].t] == h[x] + 1) {
            int w = dfs(es[i].t, t, min(f, es[i].c));
            f -= w; u += w; es[i].c -= w; es[i ^ 1].c += w;
            if(f == 0) return u;
        }
    if (u == 0) h[x] = -1; return u;
}
int dinic(int s, int t) {
    int f = 0; while (bfs(s, t)) f += dfs(s, t, INF); return f;
}

void pe(int f, int t, int c, int w) {
    es[++ess] = (e){f, t, c, w, g[f]}; g[f] = ess;
    es[++ess] = (e){t, f, 0, -w, g[t]}; g[t] = ess;
}
void init() {
    ess = -1; memset(g, -1, sizeof(g));
}
int d[maxn], fr[maxn]; bool inq[maxn]; queue<int> q;
bool spfa(int s, int t) {
    while (!q.empty()) q.pop(); memset(inq, false, sizeof(inq));
    inc(i, 0, n) d[i] = INF;
    inq[s] = true; d[s] = 0; q.push(s); fr[s] = -1;
    while (! q.empty()) {
        int x = q.front(); q.pop(); inq[x] = false;
        for (int i = g[x]; i != -1; i = es[i].n)
            if (es[i].c && d[es[i].t] > d[x] + es[i].w) {
                d[es[i].t] = d[x] + es[i].w; fr[es[i].t] = i;
                if (!inq[es[i].t]) {
                    inq[es[i].t] = true; q.push(es[i].t);
                }
            }
    }
    return d[t] != INF;
}
int advanced(int s, int t) {
    int a = INF, c = 0;
    for(int i = fr[t]; i != -1; i = fr[es[i].f]) a = min(a, es[i].c);
    for(int i = fr[t]; i != -1; i = fr[es[i].f]) {
        es[i].c -= a; es[i ^ 1].c += a; c += a * es[i].w;
    }
    return c;
}
int maxflowmincost(int s, int t) {
    int c = 0; while (spfa(s, t)) c += advanced(s,t); return c;
}

int ch[maxn][2], v[maxn], fa[maxn];
int find(int x) {
    while (fa[x]) x = fa[x]; return x;
}
int merge(int x, int y) {
    if (!x || !y) return x + y; if (v[x] > v[y]) swap(x, y);
    ch[x][1] = merge(ch[x][1], y); fa[ch[x][1]] = x;
    swap(ch[x][0], ch[x][1]); return x;
}
void pop(int x) {
    fa[ch[x][0]] = fa[ch[x][1]] = 0;
    merge(ch[x][0], ch[x][1]); ch[x][0] = ch[x][1]=0;
}

bool leave[3 * 100001], tag[3 * 100001]; int color[3 * 100001];
void build(int x, int l, int r) {
    tag[x] = false; color[x] = 1;
    if (l == r) leave[x] = true; else {
        leave[x] = false; int mid = (l + r) >> 1;
        build(x << 1, l, mid); build(x << 1 | 1, mid + 1, r);
    }
}
void pushdown(int x) {
    if (tag[x] && !leave[x]) {
        color[x << 1] = color[x << 1 | 1] = color[x];
        tag[x << 1] = tag[x << 1 | 1] = 1; tag[x] = 0;
    }
}
void update(int x) {
    color[x] = color[x << 1] | color[x << 1 | 1];
}
void modify(int x, int l, int r, int ql, int qr, int c) {
    pushdown(x);
    if (ql <= l && r <= qr) {
        color[x] = 1 << c; tag[x] = 1;
    } else {
        int mid = (l + r) >> 1;
        if (ql <= mid) modify(x << 1, l, mid, ql, qr, c);
        if (qr >= mid + 1) modify(x << 1 | 1, mid + 1, r, ql, qr, c);
        update(x);
    }
}
int query(int x, int l, int r, int ql, int qr) {
    pushdown(x);
    if (ql <= l && r <= qr) return color[x];
    int mid = (l + r) >> 1, q = 0;
    if (ql <= mid) q |= query(x << 1, l, mid, ql, qr);
    if (qr >= mid + 1) q |= query(x << 1 | 1, mid + 1, r, ql, qr);
    return q;
}

struct q {
    int v, n;
} qs[500000];
int qg[1001], qss;
struct e {
    int t, n;
} es[2002];
int g[1001], ess;
int res[1001], fa[1001]; bool vis[1001];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void dfs(int x) {
    for (int i = g[x]; i; i = es[i].n) {
        dfs(es[i].t); fa[es[i].t] = x; vis[es[i].t] = true;
    }
    for (int i = qg[x]; i; i = qs[i].n)
        if (vis[qs[i].v]) res[find(qs[i].v)]++;
}

void dfs(int x,int fa){
    for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa){
        f[0][es[i].t]=x; h[0][es[i].t]=es[i].w; dep[es[i].t]=dep[x]+1; dfs(es[i].t,x);
    }
}
void init(){
    for(k=0;(1<<k)<=n;k++); k--;
    inc(i,1,k)inc(j,1,n)f[i][j]=f[i-1][f[i-1][j]],h[i][j]=h[i-1][j]+h[i-1][f[i-1][j]];
}
int query(int x,int y){
    if(dep[x]<dep[y])swap(x,y); int t=dep[x]-dep[y],q=0;
    inc(i,0,k)if(t&(1<<i))q+=h[i][x],x=f[i][x];
    for(int i=k;i>=0;i--)if(f[i][x]!=f[i][y])q+=(h[i][x]+h[i][y]),x=f[i][x],y=f[i][y];
    if(x==y)return q;else return q+=(h[0][x]+h[0][y]);
}

string Manacher(string s) {
    // Insert '#'
    string t = "$#";
    for (int i = 0; i < s.size(); ++i) {
        t += s[i];
        t += "#";
    }
    // Process t
    vector<int> p(t.size(), 0);
    int mx = 0, id = 0, resLen = 0, resCenter = 0;
    for (int i = 1; i < t.size(); ++i) {
        p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
        while (t[i + p[i]] == t[i - p[i]]) ++p[i];
        if (mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }
        if (resLen < p[i]) {
            resLen = p[i];
            resCenter = i;
        }
    }
    return s.substr((resCenter - resLen) / 2, resLen - 1);
}

inline int read(){
    char ch=getchar(); int f=1,x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f*x;
}

insert(iterator, T); // 把T插在iterator左边
insert(iterator, int, T); // 把int个T插在iterator左边
insert(iterator, otheri1, otheri2); // 把另一个vector的otheri1到otheri2插在iterator左边
erase(iterator);
erase(iterator1, iterator2);

merge(list); // 将另一个排好序的list和这个排好序的list合并
splice(iterator, list); // 把另一个list的所有元素移动到iterator前面
splice(iterator, list, otheri1, otheri2); // 把另一个list的otheri1到otheri2元素移动到iterator前面
remove(T);
remove(function);
reverse();
unique(); // 把重复元素删掉
sort();
sort(function);

count(T);
erase(iterator);
erase(T);
pair<iterator, iterator> equal_range(T); // 第一个大于等于到第一个大于的迭代器
lower_bound(T); // 第一个大于等于的迭代器
upper_bound(T); // 第一个大于的迭代器

hypot(x, y); // sqrt(x*x+y*y)
atan2(x, y); // (x, y)对应的角度，-pi到pi
ceil(x); //向上
floor(x); //向下

isalnum(c); //数字或字母
isalpha(c);
isblank(c); //空白字符
isdigit(c);
islower(c); //小写字母
isspace(c);
isupper(c);
isxdigit(c); //十六进制字符
tolower(c);
toupper(c);

atoi(charp);
atof(charp); // to double
atoll(charp);
strtol(beginp, endpp, base); // 会让endpp指向最后一个数字下一位置
strtoll(beginp, endpp, base);
strtod(beginp, endpp);
strtold(beginp, endpp);

strncpy(des, src, num);
strncpy(des, src, num);
strncmp(str1, str2, num);
strchr(str, char); // 第一次出现
strrchr(str, char); // 第二次出现
strpbrk(str1, str2); // str2中任意字符在str1的第一次出现
strspn(str1, str2); // str1中只包含str2中任意字符的首段的字符个数
strstr(char1, char2); // str1中查str2，null表示没有
char str[] ="- This, a sample string.";
char * pch;
pch = strtok (str," ,.-");
while (pch != NULL) {
    printf ("%s\n",pch);
    pch = strtok (NULL, " ,.-");
}
// 按行输出This、a、sample、string这些单词，注意str会被修改

std::bitset<16> foo;
std::bitset<16> bar (0xfa2);
std::bitset<16> baz (std::string("0101111001"));
[];
count(); // 1 个数
size();
any();
none();
all();
reset(); // 全变为0
set(); // 全变为1
flip(); // 反转
to_string();
to_ulong();
to_ullong();

all_of(begin, end, func);
any_of(begin, end, func);
none_of(begin, end, func);
for_each(begin, end, func);
find(begin, end, val);
find_if(begin, end, func);
count(begin, end, val);
count_if(begin, end, func);
equal(begin, end, begin2);
equal(begin, end, begin2, func);
is_permutation(begin, end, begin2, func);
search(begin, end, begin2, end2);
transform(begin, end, begin2, func);
transform(begin, end, begin2, begin3, func); // 计算begin和begin2存在begin3
replace(begin, end, oldv, newv);
replace_if(begin, end, func, newv);
fill(begin, end, v);
remove(begin, end, v);
remove_if(begin, end, func);
unique(begin, end);
unique(begin, end, func);
reverse(begin, end);
rotate(begin, middle, end); // middle前面这些放到end后
partial_sort(begin, middle, end); // 小的元素都被放在middle前且排好序了
nth_element(begin, middle, end); // 确保middle这个位置元素排序是对的
make_heap(begin, end);
sort_heap(begin, end);
pop_heap(begin, end); // 最大值被放在最后
push_heap(begin, end); // 最后一个元素放在应有的位置
min_element(begin, end, func);
max_element(begin, end, func);
next_permutation(begin, end);
prev_permutation(begin, end);

.c_str();
.substr(pos, len); // 返回的是拷贝
.compare(string);
.copy(char* c, len, pos=0); // 拷贝字符串到字符数组
stoi(string);
stoll(string);
stod(string);

accumulate(begin, end, val, func); // 求和，初值为val
adjacent_difference(begin, end, begin2); // 差分
partial_sum(begin, end, begin2, func); // 前缀和
iota(begin, end, val);

int myint;
char mychar;
std::tuple<int,float,char> mytuple;
mytuple = std::make_tuple (10, 2.6, 'a');          // packing values into tuple
std::tie (myint, std::ignore, mychar) = mytuple;   // unpacking tuple into variables
std::get<0>(mytuple) = 20;

string str; 
string str_cin("one#two#three");
stringstream ss;
ss << str_cin;
while (getline(ss, str, '#')) cout << str<< endl;

const char cstr[] = "subject";
std::string s ("subject");
std::regex e ("(sub)(.*)");
if (std::regex_match(s,e)) std::cout << "string object matched\n";
if (std::regex_match(s.begin(), s.end(), e)) std::cout << "range matched\n";
std::cmatch cm;    // same as std::match_results<const char*> cm;
std::regex_match (cstr,cm,e);
std::cout << "string literal with " << cm.size() << " matches\n";
std::smatch sm;    // same as std::match_results<string::const_iterator> sm;
std::regex_match (s,sm,e);
std::cout << "string object with " << sm.size() << " matches\n";

std::regex reg("<(.*)>(.*)</(\\1)>");
std::cmatch m;
auto ret = std::regex_search("123<xml>value</xml>456", m, reg);
if (ret) {
    for (auto& elem : m)
        std::cout << elem << std::endl;
}
std::cout << "prefix:" << m.prefix() << std::endl;
std::cout << "suffix:" << m.suffix() << std::endl;

std::regex reg("<(.*)>(.*)</(\\1)>");
std::string content("123<xml>value</xml>456<widget>center</widget>hahaha<vertical>window</vertical>the end");
std::smatch m;
auto pos = content.cbegin();
auto end = content.cend();
for (; std::regex_search(pos, end, m, reg); pos = m.suffix().first)
{
    std::cout << "----------------" << std::endl;
    std::cout << m.str() << std::endl;
    std::cout << m.str(1) << std::endl;
    std::cout << m.str(2) << std::endl;
    std::cout << m.str(3) << std::endl;
}

std::string mail("123@qq.vip.com,456@gmail.com,789@163.com,abcd@my.com");
std::regex reg(",");
std::sregex_token_iterator pos(mail.begin(), mail.end(), reg, -1);
decltype(pos) end;
for (; pos != end; ++pos)
{
    std::cout << pos->str() << std::endl;
}

char data[] = "001-Neo,002-Lucia";
std::regex reg("(\\d+)-(\\w+)");
// output: 001 name=Neo,002 name=Lucia
std::cout << std::regex_replace(data, reg, "$1 name=$2");

#define inc(i, j, k) for (int i = (int)(j); i < (int)(k); i++)
#define dec(i, j, k) for (int i = (int)((j) - 1); i >= (int)(k); i--)
#define FE(i, j) for (auto i: (j))
#define FER(i, j) for (auto &i: (j))
#define INF 0x3fffffff
#define MOD 1000000007
#define LL long long
#define I iterator
#define B begin()
#define E end()
#define A(T) (T).begin(), (T).end()
#define S size()
#define V vector
#define V2(T) V<V<T>>
#define V3(T) V<V<V<T>>>
#define ST string
#define PB push_back
#define M unordered_map
#define MII M<int, int>
#define MSI M<ST, int>
#define F find
#define P pair
#define PII P<int, int>
#define MP make_pair
#define P1 first
#define P2 second
#define T tuple
#define MT make_tuple
#define Q queue
#define PQ priority_queue

inline int read() {
    char ch = getchar(); int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return f * x;
}

set nocp
set go=
set nu
set cul
set nowrap
set hls
set wmnu
syn on
colo desert
set fencs=utf-8,gbk
set nobk
set noudf
set noswapfile
set ai
set ts=4
set sts=4
set sw=4
set et
set gfn=Consolas:h14
set bs=indent,eol,start
filetype plugin indent on
func Comp()
    exec 'w'
    exec 'silent ! start cmd /C "C:/PROGRA~2/Dev-Cpp/MinGW64/bin/g++ %<.cpp -Wall -std=c++11 -g -o %<.exe & pause"'
endfunc
func Run()
    exec 'silent ! start cmd /C "%<.exe & pause"'
endfunc
map <C-F5> :call Comp()<CR>
map <C-F6> :call Run()<CR>