#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;

#ifdef _WIN32
	#define getchar _getchar_nolock
	#define putchar _putchar_nolock
#else
	#define getchar getchar_unlocked
	#define putchar putchar_unlocked
#endif
 
template <typename T>
T _read() {
	T val = 0;
	bool neg = false;
	char ch;
	
	for (ch = getchar(); !isdigit(ch); ch = getchar()) {
		if (ch == '-') neg = true;
		if (ch == EOF) return -1;
	}
	
	for (; isdigit(ch); ch = getchar()) val = val * 10 + (ch - '0');
	
	return neg ? -val : val;
}

#define read(T) (_read <T> ())

void readline(char* str) {
	char ch;
	while ((ch = getchar()) != '\n') *str++ = ch;
	*str = '\0';
}

void readstr(char* str) {
	char ch;
	while (!isspace(ch = getchar())) *str++ = ch;
	*str = '\0';
}

inline void writeline(const char* str) {
	while (*str) putchar(*str++);
	putchar('\n');
}

void writestr(const char* str) {
	while (*str) putchar(*str++);
}

template <typename T>
void write(T val, char End = EOF) {
	static int stk[45];
	int top = 0;
	
	if (val < 0) {
		val = -val;
		putchar('-');
	}
	
	do {
		stk[top++] = val % 10;
		val /= 10;
	} while (val);
	
	while (top) putchar(stk[--top] + '0');
	if (End != EOF) putchar(End);
}

typedef long long ll;

#define DBG(X) do { printf(#X); printf(" = "); write(X, '\n'); } while (false)

const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;

int main() {
	
	
	return 0;
}