#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=1e6+10;
ll read()
{
ll ret=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ret;
}
void write(ll x)
{
if(x>9) write(x/10);
putchar(x%10+'0');
}
bool prime[N];
void Prime(ll n)
{
for(ll i=2;i<=n;i++)
prime[i]=true;
for(ll i=2;i<=n;i++)
if(prime[i])
{
if((ll)(i*i)>n)
continue;
for(ll j=i*i;j<=n;j+=i)
prime[j]=false;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
return 0;
}