#include<bits/stdc++.h>
#define ll long long
using namespace std;
void read(ll& x)
{
    int f = 1;
    x = 0;
    char ch = getchar();
    
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    x *= f;
}

void read(int& x)
{
    int f = 1;
    x = 0;
    char ch = getchar();
    
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    x *= f;
}
///--------------head-----------------------------------------------------------------------------///
///--------------head-----------------------------------------------------------------------------///
///--------------head-----------------------------------------------------------------------------///
///--------------head-----------------------------------------------------------------------------///
///--------------head-----------------------------------------------------------------------------///
///--------------head-----------------------------------------------------------------------------///
///--------------head-----------------------------------------------------------------------------///
///--------------head-----------------------------------------------------刚好五十行----------------///

  

//究极读入挂
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int _read(){
    char ch=nc();int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}