template<typename T>void qr(T& x)
{
	x=0;int f=1;char c=getchar();
	for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for( ; isdigit(c);c=getchar())x=x*10+c-48;
	x=x*f;
}
template<typename T>void qw(T x)
{
	if(x<0)x=-x,putchar('-');
	if(x/10)qw(x/10);
	putchar(x%10+48); 
}