/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 *
 * Created: 2012.12.10
 *
 * About:
 *   This is minimalistic and fast variation of
 *   "testlib.h", v.0.7.4, Copyright (c) Mike Mirzayanov
 *   Look at http://code.google.com/p/testlib/ to get original "testlib.h"
 *   Look at http://acm.spbgu.ru/~sk1/download/my_testlib to get latest version
 *
 * Notes:
 *   1. Here there is no STL, no std::string. Only fast code, only hardcore.
 *   2. I tried to make this library maximal compatible with original "teslib.h"
 *   3. This library can be used only to create "validators" and "checkers". 
 *		If you want to use random, use c++11 random.
 */

#define VERSION "0.5.3"

#define MY_TESTLIB

#define __USE_MINGW_ANSI_STDIO 1

#ifdef _MSC_VER
#	define _CRT_SECURE_NO_DEPRECATE
#	include <crtdefs.h>
#endif

#if ( _WIN32 || __WIN32__ || _WIN64 || __WIN64__ )
#	define ON_WINDOWS
#	include <windows.h>
#	include <io.h>
#endif

#define I64 "%lld"
#define I64U "%llu"

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cctype>
#include <climits>
#include <fcntl.h>

#ifndef EJUDGE // testsys, pcms2
#	define OK_EXIT_CODE 0
#	define WA_EXIT_CODE 1
#	define PE_EXIT_CODE 2
#	define FAIL_EXIT_CODE 3
#	define DIRT_EXIT_CODE 4
#	define PC_BASE_EXIT_CODE 0
#else // ejudge
#	define OK_EXIT_CODE 0
#	define WA_EXIT_CODE 5
#	define PE_EXIT_CODE 4
#	define DIRT_EXIT_CODE 6
#	define FAIL_EXIT_CODE 6
#	define PC_BASE_EXIT_CODE 0
#endif
#define SV_EXIT_CODE WA_EXIT_CODE

#ifdef TESTSYS
#	undef PC_BASE_EXIT_CODE
#	define PC_BASE_EXIT_CODE 50
#endif

#define LF    10
#define CR    13
#define TAB   9
#define SPACE 32
#define EOFC  26

typedef unsigned char byte;
typedef unsigned long long ullong;

enum TResult {
	_ok = 0, 
	_wa = 1,
	_pe = 2, 
	_fail = 3,
	_dirt = 4, 
	_sv = 6,
	_partially = 16
};

#define _pc(exitCode) (TResult(_partially + (exitCode)))

int resultExitCode( TResult r ) {
	if (r == _ok) return OK_EXIT_CODE;
	if (r == _wa) return WA_EXIT_CODE;
	if (r == _pe) return PE_EXIT_CODE;
	if (r == _sv) return SV_EXIT_CODE;
	if (r == _dirt) return DIRT_EXIT_CODE;
	if (r == _fail) return FAIL_EXIT_CODE;
	return PC_BASE_EXIT_CODE + (r - _partially);
}

enum TColor {
	LightGray = 0x07,
	LightRed = 0x0c,
	LightCyan = 0x0b,
	LightGreen = 0x0a,
	LightYellow = 0x0e
}; 

void textColor( unsigned short color ) {
#ifdef ON_WINDOWS
	static HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleTextAttribute(handle, color);
#else 
	if (color == LightGray)
		printf("\e[0m");
	else {
		int c = 0;
		switch (color) {
			case LightRed: c = 31; break;
			case LightCyan: c = 36; break;
			case LightGreen: c = 32; break;
			case LightYellow: c = 33; break;
		}
		char buf[20];
		sprintf(buf, "\e[0;1;%dm", c);
		printf("%s", buf);
	}
#endif
}

void quitscr( TColor color, const char *msg, ... ) {
	va_list list;
	va_start(list, msg);
	textColor(color);
	vprintf(msg, list);
	textColor(LightGray);
}

#define ensure(cond) do { if (!(cond)) quitf(_fail, "assertion failed, line: %d, condition: %s", __LINE__, #cond); } while (0)
#define ensuref(cond, ...) do { if (!(cond)) quitf(_fail, __VA_ARGS__); } while (0)
#define quit quitf

void _quitf( TResult result, const char *msg, va_list list );
void quitf( TResult result, const char *msg, ... );
void quitif( bool condition, TResult result, const char *msg, ... );

enum TMode {
	_input, _output, _answer, _validator
};

FILE *resultFile = stdout;
const char *varName = 0;

/** Declarations */

void registerValidation();
void registerValidation(int, char *) { registerValidation(); } 
void setName( const char *, ... ); // compatibility with testlib.h
void registerTestlibCmd(int, char *);
char* cutted( char *s );

struct InStream {
	FILE *file;
	TMode mode;
	bool opened;

	static const int buf_size = 4096;
	char mem[buf_size + 1], *buf;
	int len, pos;

	InStream() {
		len = pos = 0, buf = mem + 1;
		file = NULL;
	}

	void init( FILE *f, TMode mode, const char *fileName = 0 );
	void init( const char *fileName, TMode mode );

	virtual void unreadChar( int c );
	virtual int readChar(); 
	int readChar( byte c );
	int nextChar(); 
	int curChar();

	bool eof();
	bool eoln(); // chars are skipped iff eoln = TRUE
	void readEof();
	void readEoln();
	void readEoln( int i, int n ); // readSpace or readEoln
	int readSpace();
	bool seekEoln();
	bool seekEof();
	void skipBlanks();
	void skipSpaces();

	double readDouble();
	double readDouble( double l, double r );
	int readInt();
	int readInt( int l, int r );
	ullong readULong();
	ullong readULong( ullong l, ullong r );
	long long readLong();
	long long readLong( long long l, long long r );
	char *readWord();
	char *readToken() { return readWord(); }
	char *readLine();
	char *readString() { return readLine(); }

	int readInt( int l, int r, const char *name ) { varName = name; return readInt(l, r); }
	long long readLong( long long l, long long r, const char *name ) { varName = name; return readLong(l, r); }
	double readDouble( double l, double r, const char *name ) { varName = name; return readDouble(l, r); }

	void quitf( TResult result, const char *msg, ... ) const {
		va_list list;
		va_start(list, msg);
		::_quitf(mode == _output ? result : _fail, msg, list);
	}
	void quitif( bool condition, TResult result, const char *msg, ... ) const {
		va_list list;
		va_start(list, msg);
		if (condition)
			::_quitf(mode == _output ? result : _fail, msg, list);
	}

	inline void _addToBuffer( char c ) const;
};

struct StrInStream : InStream {
	const char *s;
	int pos, len;

	StrInStream( const char *s, TMode mode ) : s(s), pos(0), len(strlen(s)) { 
		this->mode = mode;
		this->opened = true;
	}
	
	virtual void unreadChar( int c ) {
		if (c != EOF)
			ensure(pos-- > 0 && s[pos] == c);
	}
	virtual int readChar() {
		return pos == len ? EOF : s[pos++];
	} 
};

InStream inf;
InStream ouf;
InStream ans;

void _quitf( TResult result, const char *msg, va_list list ) {
	if (result == _ok && ouf.opened && !ouf.seekEof())
		quitf(_pe, "Extra information in the output file");
	if (result == _fail)      quitscr(LightRed,   "FAIL ");
	else if (result == _ok)   quitscr(LightGreen, "ok ");
	else if (result == _wa)   quitscr(LightRed,   "wa ");
	else if (result == _pe)   quitscr(LightCyan,  "pe ");
	else if (result == _sv)   quitscr(LightRed,   "sv ");
	else if (result == _dirt) quitscr(LightRed,   "dirt ");
	else                      quitscr(LightYellow, "partially correct (%d) ", result - _partially);
	if (varName && result != _ok)
		fprintf(resultFile, "[name=%s] ", varName);
	vfprintf(resultFile, msg, list);
	puts("");
	exit(resultExitCode(result));
}

void quitf( TResult result, const char *msg, ... ) {
	va_list list;
	va_start(list, msg);
	_quitf(result, msg, list);
}

void quitif( bool condition, TResult result, const char *msg, ... ) {
	va_list list;
	va_start(list, msg);
	if (condition)
		_quitf(result, msg, list);
}

void InStream::init( FILE *f, TMode mode, const char *fileName ) {
	if (!f)
		quitf(_fail, "can not open file '%s'", fileName ? fileName : "unknown");
#ifdef ON_WINDOWS
#ifdef _MSC_VER
	_setmode(_fileno(f), O_BINARY);
#else
	setmode(fileno(f), O_BINARY);
#endif
#endif
	file = f;
	this->mode = mode;
	opened = false;
}

void InStream::init( const char *fileName, TMode mode ) {
	init(fopen(fileName, "rb"), mode, fileName);
	opened = true;
}

inline bool isEof(char c) {
	return (c == EOF || c == EOFC);
}

inline bool isBlanks( int c ) {
	return (c == SPACE || c == LF || c == CR || c == TAB);
}

inline bool isSpaces( int c ) {
	return (c == SPACE || c == TAB);
}

inline char* outputChar( int x ) {
	char buf[8];
	if (x == -1)
		strcpy(buf, "EOF");
	else if (x == 10 || x == 13 || x == 26 || x == 8 || x == 7 || x == 0)
		sprintf(buf, "\\%d", x);
	else
		sprintf(buf, "%c", (char)x);
	return strdup(buf);
}

inline bool isEoln( int c ) {
	return (c == LF || c == CR);
}

inline int InStream::readChar() {
	if (pos == len)
		pos = 0, len = fread(buf, 1, buf_size, file);
	return pos == len ? -1 : buf[pos++];
}

inline void InStream::unreadChar( int c ) {
	assert(pos >= 0);
	buf[--pos] = c;
}

inline int InStream::nextChar() {
	return readChar();
}

inline int InStream::curChar() {
	int res = readChar();
	unreadChar(res);
	return res;
}

inline int InStream::readChar( byte c ) {
	int res = readChar();
	if (res == -1)
		quitf(_pe, "Unexpected end of file");
	else if (res != c)
		quitf(_pe, "Expected char '%c', but '%s' found", c, outputChar(res));
	return res;
}

inline int InStream::readSpace() {
	return readChar(SPACE);
}

inline bool InStream::eoln() {
	int c = readChar(), back = -1;
#ifdef ON_WINDOWS // CR LF
	if (c != CR) {
		unreadChar(c);
		return false;
	}
	back = c, c = readChar();
#endif // else only LF
	if (c != LF) {
		unreadChar(c);
		if (back != -1)
			unreadChar(back);
		return false;
	}
	return true;
}

inline bool InStream::eof() {
	return isEof(curChar());
}

inline void InStream::readEoln() {
	if (!eoln())
		quitf(_pe, "Expected EOLN");
}

inline void InStream::readEoln( int i, int n ) {
	if (i == n - 1)
		readEoln();
	else
		readSpace();
}

inline void InStream::readEof() {
	if (!eof())
		quitf(_pe, "Expected EOF");
}

inline void InStream::skipSpaces() {
	int c;
	while (isSpaces(c = readChar()))
		;
	unreadChar(c);
}

inline void InStream::skipBlanks() {
	if (mode == _validator)
		return;
	int c;
	while (isBlanks(c = readChar()))
		;
	unreadChar(c);
}

inline bool InStream::seekEoln() {
	skipSpaces();
	return eoln() || eof();
}

inline bool InStream::seekEof() {
	int c;
	while (isBlanks(c = readChar()))
		;
	if (isEof(c))
		return true;
	unreadChar(c);
	return false;
}

long long InStream::readLong( long long l, long long r ) {
	static const ullong MAX_X = LLONG_MAX / 10 + 1;
	static const ullong MAX_L = LLONG_MAX;
	skipBlanks();

	ullong x = 0;
	int sign = 1, c = readChar();
	if (c == '-') 
		sign = -1, c = readChar();
	if (isdigit(c)) {
		int len = 0, zeroes = 0;
		while (c == '0')
			c = readChar(), zeroes++;
		while (isdigit(c)) {
			if (x > MAX_X)
				quitf(_pe, "64-bit signed integer overflow");
			x = x * 10 + c - '0';
			c = readChar();
			len++;
		}
		if ((x > MAX_L && sign == 1) || (sign == -1 && x > MAX_L + 1ULL))
			quitf(_pe, "64-bit signed integer overflow (little bit overflow)");
		if (zeroes && zeroes + len > 1)
			quitf(_pe, "Leading zeroes are not allowed [zeroes = %d, len = %d]", zeroes, len);
	}
	else
		quitf(_pe, "Expected integer, but '%s' found", outputChar(c));
	unreadChar(c);

	long long y = (x == MAX_L + 1ULL ? LLONG_MIN : x * sign);
	if (!(l <= y && y <= r))
		quitf(_pe, "parse integer: out of range [" I64 ".." I64 "]", l, r);
	return y;
}

ullong InStream::readULong( ullong l, ullong r ) {
	static const ullong MAX_X = ULLONG_MAX / 10;
	skipBlanks();

	ullong x = 0;
	int c = readChar();
	if (isdigit(c)) {
		int len = 0, zeroes = 0;
		while (c == '0')
			c = readChar(), zeroes++;
		while (isdigit(c)) {
			if (x > MAX_X)
				quitf(_pe, "64-bit unsigned integer overflow");
			x = x * 10;

			unsigned add = c - '0';
			if (x > ULLONG_MAX - add)
				quitf(_pe, "64-bit unsigned integer overflow");
			x += add;
			
			c = readChar();
			len++;
		}
		if (zeroes && zeroes + len > 1)
			quitf(_pe, "Leading zeroes are not allowed [zeroes = %d, len = %d]", zeroes, len);
	}
	else
		quitf(_pe, "Expected integer, but '%s' found", outputChar(c));
	unreadChar(c);

	if (!(l <= x && x <= r))
		quitf(_pe, "parse integer: out of range [" I64U ".." I64U "]", l, r);
	return x;
}

int InStream::readInt(int l, int r) { return readLong(l, r); }
int InStream::readInt()				{ return readLong(INT_MIN, INT_MAX); }
long long InStream::readLong()		{ return readLong(LLONG_MIN, LLONG_MAX); }
ullong InStream::readULong()		{ return readULong(0ULL, ULLONG_MAX); }

double InStream::readDouble() {
	char *s = readWord(), *t = s;
	int bad = 0;
	if (*t == '-' || *t == '+')
		t++;
	bad |= !isdigit(*t);
	while (isdigit(*t))
		t++;
	if (*t == '.')
		for (t++; isdigit(*t); t++)
			;
	if (*t == 'e' || *t == 'E') {
		t++;
		if (*t == '-')
			t++;
		bad |= !isdigit(*t);
		while (isdigit(*t))
			t++;
	}
	if (bad)
		quitf(_pe, "parse double: digit expected");
	if (*t)
		quitf(_pe, "parse double: extra information");

	double x;
	if (sscanf(s, "%lf", &x) != 1)
		quitf(_fail, "parse double: sscanf can not parse string");
	return x; 
}

double InStream::readDouble( double l, double r ) {
	double x = readDouble();
	if (!(l <= x && x <= r))
		quitf(_pe, "parse double: out of range [%f to %f]", l, r);
	return x;
}

namespace __testlib {
	const int maxMem = 2e8;
	char mem[maxMem], *memPos = mem;
	const char *memEnd = mem + maxMem;

	inline void resetBuffer() {
		memPos = mem;
	}
	inline int length() {
		return memPos - mem;
	}
};

inline void InStream::_addToBuffer( char c ) const {
	if (__testlib::memPos == __testlib::memEnd)
		quitf(_pe, "__testlib::mem overflow [ML = %d bytes]", __testlib::maxMem);
	*__testlib::memPos++ = c;
}

char *InStream::readWord() {
	skipBlanks();
	char *res = __testlib::memPos;
	while (1) {
		int c = readChar();
		if (isBlanks(c) || c == -1)	{
			unreadChar(c);
			break;
		}
		_addToBuffer(c);
	}
	_addToBuffer(0);
	if (*res == 0)
		quitf(_pe, "readWord: unexpected end of file");
	return res;
}

char *InStream::readLine() {
	char *res = __testlib::memPos;
	int c, last = -1;
	while ((c = readChar()) != -1 && c != LF)
		_addToBuffer(last = c);
	if (mode == _validator)
		ensure(c == LF);
	#ifdef ON_WINDOWS
	if (mode == _validator)
		ensure(last == CR);
	if (last == CR)
		__testlib::memPos--;
	#endif
	_addToBuffer(0);
	return res;
}

void registerValidation() {
	inf.init(stdin, _validator);
}

void registerTestlibCmd( int argc, char *argv[] ) {
	if (argc < 4)
		quitf(_fail, "Usage: <input-file> <output-file> <answer-file> [report-file]");

	inf.init(argv[1], _input);
	ouf.init(argv[2], _output);
	ans.init(argv[3], _answer);

	resultFile = argc < 5 ? stdout : fopen(argv[4], "wt");
}

void setName( const char *, ... ) { }

char* cutted( char *s ) {
	const char *ending = "...";
	const int MAX = 30, ADD = strlen(ending);
	int len = strlen(s);
	if (len > MAX + ADD) {
		sprintf(s + MAX, "%s", ending);
	}
	return s;
}