#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;
}