#pragma once

/*
 * STRICT.H
 * Tool for validation of input data for the programming contest problems
 * Copyright (c) Vladimir Yakovlev, 2011-2014
 * http://acm.timus.ru/stricth
 * Version 0.2
 *
 * History:
 *  22.07.2011 v.0.1. first release
 *  17.01.2014 v.0.2. new features added
 */

#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

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

/* interface */

class Input
{
	FILE* m_file;
	int c;
	int line;
	int pos;

	void setBinaryMode();
	void nextChar();
	void assertDigit();
	void init();
	void parsePattern(const char* charPattern, bool valid[256]);

public:
	Input();
	Input(const char* fileName);
	~Input();
	bool isSpace() const;
	bool isWhitespace() const;
	bool isEoln() const;
	bool isEof() const;
	void readSpace();
	void readOneOrMoreSpaces();
	void readEoln();
	void readSpaceOrEoln();
	void readEof();
	int readChar();
	std::string readToken();
	// charPattern is a list of correct chars like "SWNE" or a range of chars like "0-9"
	// or a combination of them like "-_a-zA-Z"
	std::string readToken(int minLength, int maxLength, const char* charPattern);
	// read whole line and advance to the beginning of the next line
	std::string readLine();
	std::string readLine(int minLength, int maxLength, const char* charPattern);
	int readInt(int minValue, int maxValue);
	long long readLong(long long minValue, long long maxValue);
	unsigned long long readULong(unsigned long long minValue, unsigned long long maxValue);
	double readDouble(double minValue, double maxValue, int maxDigits);
	// read an array of ints separated by single spaces
	std::vector<int> readIntVector(int count, int minValue, int maxValue);
	// read an array of ints each in a separate lines,
	// advance to the beginning of the next line
	std::vector<int> readIntVectorLines(int count, int minValue, int maxValue);
	void _assert(bool noerror, const char* expr);
	void error(const char* fmt, ...);

private:
	Input(const Input&);
	Input& operator =(const Input&);
};

#undef assert
#define assert(expr) _assert((expr), #expr)

void error(const char* fmt, ...);
bool isConnected(int n, const std::vector< std::pair<int, int> >& edges);
void assertTree(const std::vector< std::pair<int, int> >& tree);
void assertConnected(int n, const std::vector< std::pair<int, int> >& edges);
void assertPrime(int p);
void assertSum(const std::vector<int>& values, long long minValue, long long maxValue);

// verifies that all values in the given vector are distinct
template<typename T>
void assertDistinct(const std::vector<T>& values);

// verifies that the sequence of values in the given vector is monotone
// in the way described by the relation:
//   "<"  each term is less than the following one (strictly increasing sequence)
//   "<=" each term is less than or equal to the following one (nondecreasing sequence)
//   ">"  each term is greater than the following one (strictly decreasing sequence)
//   ">=" each term is greater than or equal to the following one (nonincreasing sequence)
template<typename T>
void assertMonotone(const std::vector<T>& values, const char* relation);

/* implementation */

void Input::setBinaryMode()
{
#ifdef ON_WINDOWS
#ifdef STDIN_FILENO
	int stdinFileno = STDIN_FILENO;
#else
	int stdinFileno = _fileno(stdin);
#endif
	if (_setmode(stdinFileno, O_BINARY) == -1)
		::error("Cannot set stdin to binary mode");
#endif
}

void Input::nextChar()
{
	if (isEoln())
	{
		line++;
		pos = 1;
	}
	else
		pos++;
	c = getc(m_file);
#ifdef ON_WINDOWS
	if (c == 10)
		error("Unix style EOLN");
	if (c == 13)
	{
		c = getc(m_file);
		if (c != 10)
			error("Character 13 without 10");
	}
#else
	if (c == 13)
		error("Windows style EOLN");
#endif
}

void Input::assertDigit()
{
	if (c >= '0' && c <= '9')
		return;
	if (isEof())
		error("EOF instead of number");
	if (isEoln())
		error("EOLN instead of number");
	if (isSpace())
		error("SPACE instead of number");
	if (c == '\t')
		error("TAB instead of number");
	error("'%c' instead of number", (char)c);
}

void Input::init()
{
	line = 1;
	pos = 0;
	c = 0;
	nextChar();
}

void Input::parsePattern(const char* charPattern, bool valid[256])
{
	for (int b = 0; b < 256; b++)
		valid[b] = false;
	for (int i = 0; charPattern[i]; i++)
	{
		unsigned char u = (unsigned char)charPattern[i];
		if (u == '-' && i > 0 && charPattern[i + 1])
		{
			unsigned char from = (unsigned char)charPattern[i - 1];
			unsigned char to = (unsigned char)charPattern[i + 1];
			if (from > to)
				error("wrong pattern: '%s'", charPattern);
			for (int v = from; v <= to; v++)
				valid[v] = true;
		}
		else
		{
			valid[u] = true;
		}
	}
}

Input::Input()
{
	setBinaryMode();
	m_file = stdin;
	init();
}

Input::Input(const char* fileName)
{
	m_file = fopen(fileName, "rb");
	if (!m_file)
		::error("Cannot open file %s", fileName);
	init();
}

Input::~Input()
{
	fclose(m_file);
}

bool Input::isWhitespace() const
{
	return c == ' ' || c == '\t' || c == '\n';
}

bool Input::isSpace() const
{
	return c == ' ';
}

bool Input::isEoln() const
{
	return c == '\n';
}

bool Input::isEof() const
{
	return c == EOF;
}

void Input::readSpace()
{
	if (!isSpace())
		error("SPACE expected");
	nextChar();
}

void Input::readOneOrMoreSpaces()
{
	if (!isSpace())
		error("SPACE expected");
	nextChar();
	while (isSpace())
		nextChar();
}

void Input::readEoln()
{
	if (!isEoln())
		error("EOLN expected");
	nextChar();
}

void Input::readSpaceOrEoln()
{
	if (!isSpace() && !isEoln())
		error("EOLN or SPACE expected");
	nextChar();
}

void Input::readEof()
{
	if (!isEof())
		error("EOF expected");
}

int Input::readChar()
{
	if (isEof())
		error("EOF instead of char");
	int oldc = c;
	nextChar();
	return oldc;
}

std::string Input::readToken()
{
	if (isEof())
		error("EOF instead of token");
	if (isWhitespace())
		error("whitespace instead of token");
	std::string res;
	while (!isWhitespace() && !isEof())
	{
		res += (char)c;
		nextChar();
	}
	return res;
}

std::string Input::readToken(int minLength, int maxLength, const char* charPattern)
{
	bool valid[256];
	parsePattern(charPattern, valid);
	if (isEof())
		error("EOF instead of token");
	if (isWhitespace())
		error("whitespace instead of token");
	std::string res;
	while (!isWhitespace() && !isEof())
	{
		res += (char)c;
		if ((int)res.length() > maxLength)
			error("the length of token exceeded %d", maxLength);
		if (!valid[c])
			error("character '%c' does not match pattern '%s'", (char)c, charPattern);
		nextChar();
	}
	if ((int)res.length() < minLength)
		error("the length of token is less than %d", minLength);
	return res;
}

std::string Input::readLine()
{
	std::string res;
	while (!isEoln())
	{
		if (isEof())
			error("EOF instead of EOLN");
		res += (char)c;
		nextChar();
	}
	nextChar();
	return res;
}

std::string Input::readLine(int minLength, int maxLength, const char* charPattern)
{
	bool valid[256];
	parsePattern(charPattern, valid);
	std::string res;
	while (!isEoln())
	{
		if (isEof())
			error("EOF instead of EOLN");
		res += (char)c;
		if ((int)res.length() > maxLength)
			error("the length of line exceeded %d", maxLength);
		if (!valid[c])
			error("character '%c' does not match pattern '%s'", (char)c, charPattern);
		nextChar();
	}
	if ((int)res.length() < minLength)
		error("the length of line is less than %d", minLength);
	nextChar();
	return res;
}

int Input::readInt(int minValue, int maxValue)
{
	return (int)readLong(minValue, maxValue);
}

long long Input::readLong(long long minValue, long long maxValue)
{
	bool minus = false;
	long long x = 0;

	if (c == '-')
	{
		minus = true;
		nextChar();
	}
	assertDigit();

	if (c == '0')
	{
		nextChar();
		if (c >= '0' && c <= '9')
			error("integer with leading zero");
		else if (minus)
			error("minus zero");
	}
	else
	{
		const long long MIN_LONG = 0x8000000000000000ll;
		const long long MIN_LONG_DIV10 = MIN_LONG / 10;
		const long long MIN_LONG_MOD10 = -(MIN_LONG % 10);
		const long long MAX_LONG = 0x7fffffffffffffffll;
		const long long MAX_LONG_DIV10 = MAX_LONG / 10;
		const long long MAX_LONG_MOD10 = MAX_LONG % 10;
		while (c >= '0' && c <= '9')
		{
			long long digit = c - '0';
			if (minus)
			{
				if (x < MIN_LONG_DIV10 || (x == MIN_LONG_DIV10 && digit > MIN_LONG_MOD10))
					error("overflow of 64-bit signed integer");
				x = x * 10 - digit;
			}
			else
			{
				if (x > MAX_LONG_DIV10 || (x == MAX_LONG_DIV10 && digit > MAX_LONG_MOD10))
					error("overflow of 64-bit signed integer");
				x = x * 10 + digit;
			}
			nextChar();
		}
	}
	if (x < minValue || x > maxValue)
		error("integer %lld is out of bounds [%lld, %lld]", x, minValue, maxValue);
	return x;
}

unsigned long long Input::readULong(unsigned long long minValue, unsigned long long maxValue)
{
	unsigned long long x = 0;
	assertDigit();
	if (c == '0')
	{
		nextChar();
		if (c >= '0' && c <= '9')
			error("integer with leading zero");
	}
	else
	{
		const unsigned long long MAX_ULONG = 0xffffffffffffffffull;
		const unsigned long long MAX_ULONG_DIV10 = MAX_ULONG / 10ull;
		const unsigned long long MAX_ULONG_MOD10 = MAX_ULONG % 10ull;
		while (c >= '0' && c <= '9')
		{
			unsigned long long digit = c - '0';
			if (x > MAX_ULONG_DIV10 || (x == MAX_ULONG_DIV10 && digit > MAX_ULONG_MOD10))
				error("overflow of 64-bit unsigned integer");
			x = x * 10u + digit;
			nextChar();
		}
	}
	if (x < minValue || x > maxValue)
		error("integer %llu is out of bounds [%llu, %llu]", x, minValue, maxValue);
	return x;
}

double Input::readDouble(double minValue, double maxValue, int maxDigits)
{
	bool minus = false;
	bool wasDigit = false;
	double x = 0.0;

	if (c == '-')
	{
		minus = true;
		nextChar();
	}
	if (c == '0')
	{
		nextChar();
		if (c >= '0' && c <= '9')
			error("double with leading zero");
		wasDigit = true;
	}
	while (c >= '0' && c <= '9')
	{
		x = x * 10.0 + (c - '0');
		nextChar();
		wasDigit = true;
	}
	if (c == '.')
	{
		if (!wasDigit)
			error("double starts with dot");
		nextChar();
		if (c < '0' || c > '9')
			error("double ends with dot");
		double y = 0.1;
		for (int k = 1; c >= '0' && c <= '9'; k++)
		{
			if (k > maxDigits)
				error("more than %d digits after decimal point", maxDigits);
			x += y * (double)(c - '0');
			y *= 0.1;
			nextChar();
			wasDigit = true;
		}
	}
	if (!wasDigit)
		assertDigit();
	if (minus && x == 0.0)
		error("minus zero");
	if (minus)
		x = -x;
	if (minValue - x > 1e-10 || x - maxValue > 1e-10)
		error("number %g is out of bounds [%g, %g]", x, minValue, maxValue);
	return x;
}

std::vector<int> Input::readIntVector(int count, int minValue, int maxValue)
{
	std::vector<int> result;
	for (int i = 0; i < count; i++)
	{
		if (i > 0)
			readSpace();
		result.push_back(readInt(minValue, maxValue));
	}
	return result;
}

std::vector<int> Input::readIntVectorLines(int count, int minValue, int maxValue)
{
	std::vector<int> result;
	for (int i = 0; i < count; i++)
	{
		result.push_back(readInt(minValue, maxValue));
		readEoln();
	}
	return result;
}

void Input::_assert(bool noerror, const char* expr)
{
	if (!noerror)
		error("condition failed: %s ", expr);
}

void Input::error(const char* fmt, ...)
{
	va_list argptr;
	va_start(argptr, fmt);
	fprintf(stderr, "Line %d, pos %d: ", line, pos);
	vfprintf(stderr, fmt, argptr);
	fprintf(stderr, " ");
	va_end(argptr);
	exit(1);
}

void error(const char* fmt, ...)
{
	va_list argptr;
	va_start(argptr, fmt);
	vfprintf(stderr, fmt, argptr);
	fprintf(stderr, " ");
	va_end(argptr);
	exit(1);
}

bool isConnected(int n, const std::vector< std::pair<int, int> >& edges)
{
	std::vector<bool> used(n, false);
	std::vector< std::vector<int> > adj(n);
	std::queue<int> q;
	for (unsigned int i = 0; i < edges.size(); i++)
	{
		if (edges[i].first < 1 || edges[i].first > n)
			error("Incorrect vertex number: %d", edges[i].first);
		if (edges[i].second < 1 || edges[i].second > n)
			error("Incorrect vertex number: %d", edges[i].second);
		adj[edges[i].first - 1].push_back(edges[i].second - 1);
		adj[edges[i].second - 1].push_back(edges[i].first - 1);
	}
	used[0] = true;
	q.push(0);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (unsigned int j = 0; j < adj[x].size(); j++)
		{
			int y = adj[x][j];
			if (!used[y])
			{
				used[y] = true;
				q.push(y);
			}
		}
	}
	for (int u = 0; u < n; u++)
		if (!used[u])
			return false;
	return true;
}

void assertTree(const std::vector< std::pair<int, int> >& tree)
{
	if (!isConnected((int)tree.size() + 1, tree))
		error("Graph is not a tree");
}

void assertConnected(int n, const std::vector< std::pair<int, int> >& edges)
{
	if (!isConnected(n, edges))
		error("Graph is not connected");
}

void assertPrime(int p)
{
	int i;
	for (i = 2; i * i <= p; i++)
		if (p % i == 0) break;
	if (p < 2 || i * i <= p)
		error("Number is not a prime: %d", p);
}

void assertSum(const std::vector<int>& values, long long minValue, long long maxValue)
{
	long long sum = 0;
	for (unsigned int i = 0; i < values.size(); i++)
		sum += values[i];
	if (sum < minValue || sum > maxValue)
		error("The sum of array %lld is out of bounds [%lld, %lld]", sum, minValue, maxValue);
}

template<typename T>
void assertDistinct(const std::vector<T>& values)
{
	std::map<T, int> index;
	for (unsigned int i = 0; i < values.size(); i++)
	{
		if (!index.insert(std::pair<T, int>(values[i], i)).second)
			error("Duplicate elements at positions %d and %d", index[values[i]] + 1, i + 1);
	}
}

template<typename T>
void assertMonotone(const std::vector<T>& values, const char* relation)
{
	int rel = 0;
	if (!strcmp(relation, "<"))
		rel = 1;
	else if (!strcmp(relation, "<="))
		rel = 2;
	else if (!strcmp(relation, ">"))
		rel = 3;
	else if (!strcmp(relation, ">="))
		rel = 4;
	else
		error("Wrong relation: '%s'", relation);
	for (unsigned int i = 1; i < values.size(); i++)
	{
		const T& x = values[i - 1];
		const T& y = values[i];
		if (!(rel == 1 && x < y || rel == 2 && x <= y || rel == 3 && x > y || rel == 4 && x >= y))
			error("The sequence is not monotone: wrong relation at positions %d and %d", i, i + 1);
	}
}