// Made By nPr123f
// Fast Input && Output (for integers)

#include <cstdio>

#ifndef WIN64	// ___gchar 和 ___pchar 是
#define __gchar_default getchar_unlocked
#define __pchar_default putchar_unlocked
#else
#define __gchar_default getchar
#define __pchar_default putchar
#endif

namespace FastIO
{
	/*
		getint 是整数类型的快速读入，使用 getchar() 之类的字符函数实现
		先过滤掉非数字字符，再读数字。
		可以处理正负，但如果是 unsigned 类型读入负数会爆掉。
		getint 是无参函数，返回读入的数字
		
		调用方法：
			int n;
			n = getint<int>();
	
			long long x;
			x = getint<long long>();
	
		如果读入 int 类型的整数，那么 <int> 可以省略：
			n = getint<int>(); 等价于 n = getint();
	*/
	
	template <typename Tp_ = int, int (*___gchar)() = __gchar_default>
	inline Tp_ getint()	
	{
		Tp_ sign = 1, num = 0;	// sign 存储符号，num 存储数字的绝对值
		char c;					// 读入的字符
		
		for (c = ___gchar(); (c < '0' || c > '9') && c != EOF; c = ___gchar())	// 过滤非数字字符
			if (c == '-')		// 特判负号
				sign *= -1;		// 反转符号
		
		for (; c >= '0' && c <= '9'; c = ___gchar())	// 读入数字字符
			num = num * 10 + (c - '0');					// 原有数字乘上 10，加上新的数位
		
		return num * sign;		// 返回，记得乘上符号
	}
	
	/*
		putint 是整数类型的快速输出，使用 putchar() 之类的字符函数以及栈实现。
		可以输出负数，适用于任意整数类型，不会自动换行。
		putint 无返回值。
		
		使用方法：
			putint(n);
	*/
	
	template <typename Tp_, int (*___pchar)(int) = __pchar_default>
	inline void putint(Tp_ num)
	{
		static int stk[30] = {};	// 栈的数组
		int top = 0;				// 栈顶指针
		
		if (num < 0)				// 特判负数
			___pchar('-'), num = -num;
		
		do
		{
			stk[top++] = num % 10;	// 分解数位，存入栈中
			num /= 10;
		}
		while (num);
		
		for (int i = top - 1; i >= 0; i--)	// 倒序输出
			___pchar(stk[i] + '0');
	}
}