#pragma once

/*
 * STRICT.H version 0.3.1
 * Library for validation of input data for the programming contest problems. Requires C++17.
 * Copyright (c) Vladimir Yakovlev, 2011-2024
 * http://acm.timus.ru/stricth
 */

#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <regex>
#include <optional>

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

// ==================================================== INTERFACE ====================================================

// Provides primitives for reading the input stream and strictly checking its validity.
// Example usage:
//   Input in;
//   int n = in.readInt(1, 50);
//   in.readSpace();
//   int m = in.readInt(1, 50);
//   in.assert(n + m <= 50);
//   in.readEoln();
//   in.readEof();
class Input
{
	FILE* m_file;
	int c;
	int line;
	int pos;

	void setBinaryMode();
	void nextChar();
	void assertDigit() const;
	void init();
	void parsePattern(const char* charPattern, bool valid[256]) const;
	template<typename T>
	void checkConstraints(const T&) const;
	template<typename T, typename First, typename... Args>
	void checkConstraints(const T& value, First&& first, Args&&... constraints) const;

public:
	// Initializes reading from stdin.
	Input();

	// Initializes reading from a file.
	Input(const char* fileName);

	// Makes the class non-copyable.
	Input(const Input&) = delete;
	Input& operator=(const Input&) = delete;

	~Input();

	// Returns whether the next character is SPACE (ASCII 32).
	bool isSpace() const;

	// Returns whether the next character is whitespace (SPACE, TAB, EOLN).
	bool isWhitespace() const;

	// Returns whether the next character is EOLN (ASCII 13 for Unix, ASCII 13 10 for Windows).
	bool isEoln() const;

	// Returns whether the next character is EOF (end of file).
	bool isEof() const;

	// Returns whether the next character matches the pattern, e.g. "-_a-zA-Z". Note that this is NOT a regexp.
	bool isChar(const char* charPattern) const;

	// Reads the next character and checks that it equals to SPACE.
	void readSpace();

	// Reads the next characters while they are equal to SPACE.
	void readZeroOrMoreSpaces();

	// Reads the next character and checks that it equals to SPACE,
	// then reads next characters while they are equal to SPACE.
	void readOneOrMoreSpaces();

	// Reads the next character and checks that it equals to EOLN (end of line).
	void readEoln();

	// Reads the next character and checks that it equals to SPACE or EOLN.
	void readSpaceOrEoln();

	// Reads the next character and checks that it equals to EOF (end of file).
	void readEof();

	// Reads and returns the next character (from 0 to 255).
	int readChar();

	// Reads and returns the next character (from 0 to 255).
	// Checks that the character matches the pattern, e.g. "-_a-zA-Z". Note that this is NOT a regexp.
	int readChar(const char* charPattern);

	// Reads characters until the next whitespace or EOF. Checks that the result is non-empty.
	std::string readToken();

	// Reads characters until the next whitespace or EOF. Checks that the result is non-empty. Checks the length
	// of the result and that its characters match the pattern, e.g. "-_a-zA-Z". Note that this is NOT a regexp.
	// Checks the result with all provided constraint objects.
	template<typename... Args>
	std::string readToken(int minLength, int maxLength, const char* charPattern, Args&&... constraints);

	// Reads characters until the next whitespace or EOF. Checks that the result is non-empty. Checks that the result
	// matches the regexp, e.g. "[a-z]{1,10}". Checks the result with all provided constraint objects.
	template<typename... Args>
	std::string readToken(const std::string& regexp, Args&&... constraints);

	// Reads characters until the next EOLN and skips the EOLN character.
	std::string readLine();

	// Reads characters until the next EOLN and skips the EOLN character. Checks the length of the result
	// and that its characters match the pattern, e.g. "-_a-zA-Z". Note that this is NOT a regexp.
	std::string readLine(int minLength, int maxLength, const char* charPattern);

	// Reads characters until the next EOLN and skips the EOLN character. Checks that the result matches
	// the regexp, e.g. "[a-z]{1,10}".
	std::string readLine(const std::string& regexp);

	// Reads a signed 32-bit integer, checks that it's well-formed and lies in the given range. Checks the result
	// with all provided constraint objects.
	template<typename... Args>
	int readInt(int minValue, int maxValue, Args&&... constraints);

	// Reads a signed 64-bit integer, checks that it's well-formed and lies in the given range.
	long long readLong(long long minValue, long long maxValue);

	// Reads an unsigned 64-bit integer, checks that it's well-formed and lies in the given range.
	unsigned long long readULong(unsigned long long minValue, unsigned long long maxValue);

	// Reads a floating point number, checks that it's well-formed, lies in the given range and
	// has not more than a given number of digits after the decimal point.
	double readDouble(double minValue, double maxValue, int maxDigits);

	// Reads a floating point number, checks that it's well-formed, lies in the given range (">" or ">=" for min value,
	// "<" or "<=" for max value) and has not more than a given number of digits after the decimal point.
	double readDouble(const std::string& minRelation, double minValue, const std::string& maxRelation,
		double maxValue, int maxDigits);

	// Reads a series of signed 32-bit integers of a fixed length, where the numbers are separated with a single SPACE.
	// Checks that each number lies in the given range. Checks each number with all provided constraint objects.
	// Example: readIntVector(3, 1, 50) given the input "1 2 3" returns {1, 2, 3}.
	template<typename... Args>
	std::vector<int> readIntVector(int count, int minValue, int maxValue, Args&&... constraints);

	// Reads a series of signed 32-bit integers of a fixed length, where the numbers are followed by a single EOLN.
	// Checks that each number lies in the given range. Checks each number with all provided constraint objects.
	// Example: readIntVectorLines(3, 1, 50) given the input "1\n2\n3\n" returns {1, 2, 3}.
	template<typename... Args>
	std::vector<int> readIntVectorLines(int count, int minValue, int maxValue, Args&&... constraints);

	// Reads a series of signed 32-bit integers until the given end marker number, all separated with a single SPACE.
	// Checks that each number lies in the given range. Checks each number with all provided constraint objects.
	// Example: readIntVectorUntil(1, 50, -1) given the input "1 2 3 -1" returns {1, 2, 3}.
	template<typename... Args>
	std::vector<int> readIntVectorUntil(int minValue, int maxValue, int endMarker, Args&&... constraints);

	// Reads a series of signed 32-bit integers until the given end marker number, all followed by a single EOLN.
	// Checks that each number lies in the given range. Checks each number with all provided constraint objects.
	// Example: readIntVectorUntilLines(1, 50, -1) given the input "1\n2\n3\n-1\n" returns {1, 2, 3}.
	template<typename... Args>
	std::vector<int> readIntVectorUntilLines(int minValue, int maxValue, int endMarker, Args&&... constraints);

	// Reads a series of signed 32-bit integers of a fixed length, where the numbers are separated with a single SPACE.
	// Checks that the numbers form a permutation with the given start number.
	// Example: readPermutation(3) accepts "2 3 1", but rejects "1 2 2" and "0 1 2".
	// Example: readPermutation(3, 0) accepts "1 2 0", but rejects "0 1 1" and "1 2 3".
	std::vector<int> readPermutation(int count, int start = 1);

	// Reads a series of signed 32-bit integers of a fixed length, where the numbers are followed by a single EOLN.
	// Checks that the numbers form a permutation with the given start number.
	// Example: readPermutationLines(3) accepts "2\n3\n1\n", but rejects "1\n2\n2\n" and "0\n1\n2\n".
	// Example: readPermutationLines(3, 0) accepts "1\n2\n0\n", but rejects "0\n1\n1\n" and "1\n2\n3\n".
	std::vector<int> readPermutationLines(int count, int start = 1);

	// Check the condition and if it's not satisfied prints an error adding the current input position to it and
	// finishes the program with the exit code 1. Should be called using the macro assert() defined below.
	void _assert(bool condition, const char* expr) const;

	// Prints a printf-style message adding the current input position to it. Finishes the program with the exit code 1.
	void error(const char* fmt, ...) const;
};

// Check the condition and if it's not satisfied prints an error and finishes the program with the exit code 1.
// Should be called on an Input object, for example: Input in; int x = in.readInt(-10, 10); in.assert(x != 0);
#undef assert
#define assert(condition) _assert((condition), #condition)

// Prints a printf-style message. Finishes the program with the exit code 1.
void error(const char* fmt, ...);

// Returns whether the given graph is connected. Edges are given as pairs of 1-based node numbers.
// Example: isConnected(3, {{1, 2}, {2, 3}}) returns true. isConnected(4, {{1, 2}, {3, 4}}) returns false.
bool isConnected(int n, const std::vector<std::pair<int, int>>& edges);

// Check that the given graph is a tree. Edges are given as pairs of 1-based node numbers.
// Example: assertTree({{1, 2}, {1, 3}}) passes, while assertTree({{1, 3}}) and assertTree({{1, 2}, {1, 2}}) fail.
void assertTree(const std::vector<std::pair<int, int>>& tree);

// Check that the given graph is connected. Edges are given as pairs of 1-based node numbers.
// Example: assertConnected(3, {{1, 2}, {2, 3}}) passes, while assertConnected(4, {{1, 2}, {3, 4}}) fails.
void assertConnected(int n, const std::vector<std::pair<int, int>>& edges);

// Check that the given number is prime.
void assertPrime(int p);

// Returns the greatest common divisor of the given numbers.
long long gcd(long long a, long long b);

// Constraint checking the sum of the consumed numbers.
// Example: readIntVector(3, 1, 10, MaxSum(15)) accepts "2 3 10", but rejects "2 4 10".
class MaxSum
{
	long long maxSum;
	long long sum;
	int pos;
public:
	MaxSum(long long maxSum);
	void operator()(long long value, const Input* in = nullptr);
};

// Checks that the sum of the numbers in the vector doesn't exceed the limit.
template<typename T>
void assertMaxSum(const std::vector<T>& values, long long maxSum);

// Constraint checking the monotonicity of the consumed values. Supports relations "<", "<=", ">", ">=".
// Example: readIntVector(3, 1, 10, Monotone<int>("<=")) accepts "1 3 3", but rejects "1 3 2".
template<typename T>
class Monotone
{
	std::string rel;
	std::optional<T> prev;
	int pos;
public:
	Monotone(const std::string& relation);
	void operator()(const T& value, const Input* in = nullptr);
};

// Checks that the values in the vector are monotonic. Supports relations "<", "<=", ">", ">=".
template<typename T>
void assertMonotone(const std::vector<T>& values, const std::string& relation);

// Constraint checking that the consumed values are unique.
// Example: readIntVector(3, 1, 10, Unique<int>()) accepts "1 2 3", but rejects "1 2 2".
// Example: Unique<std::pair<int, int>> u; u({1, 2}); u({2, 1}); u({1, 2}); fails at the last call.
template<typename T>
class Unique
{
	std::map<T, int> index;
public:
	void operator()(const T& value, const Input* in = nullptr);
};

// Checks that the values in the vector are unique.
template<typename T>
void assertDistinct(const std::vector<T>& values);

// Constraint checking that the consumed numbers aren't equal to the given one.
// Example: readIntVector(3, 1, 10, NotEqual(5)) accepts "1 4 10", but rejects "1 5 10".
class NotEqual
{
	long long notEqualValue;
public:
	NotEqual(long long notEqualValue);
	void operator()(long long value, const Input* in = nullptr);
};

// Constraint checking that the consumed numbers are odd.
// Example: readIntVector(3, 1, 9, Odd()) accepts "1 3 5", but rejects "1 3 4".
class Odd
{
public:
	void operator()(long long value, const Input* in = nullptr);
};

// Constraint checking that the consumed numbers are even.
// Example: readIntVector(3, 2, 10, Even()) accepts "2 4 6", but rejects "2 4 5".
class Even
{
public:
	void operator()(long long value, const Input* in = nullptr);
};

// ================================================== 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() const
{
	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]) const
{
	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;
		}
	}
}

template<typename T>
void Input::checkConstraints(const T&) const
{
}

template<typename T, typename First, typename... Args>
void Input::checkConstraints(const T& value, First&& first, Args&&... constraints) const
{
	first(value, this);
	checkConstraints(value, constraints...);
}

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;
}

bool Input::isChar(const char* charPattern) const
{
	if (isEof())
		return false;
	bool valid[256];
	parsePattern(charPattern, valid);
	return valid[c];
}

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

void Input::readZeroOrMoreSpaces()
{
	while (isSpace())
		nextChar();
}

void Input::readOneOrMoreSpaces()
{
	readSpace();
	readZeroOrMoreSpaces();
}

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;
}

int Input::readChar(const char* charPattern)
{
	bool valid[256];
	parsePattern(charPattern, valid);
	if (isEof())
		error("EOF instead of char");
	if (!valid[c])
		error("character '%c' does not match pattern '%s'", (char)c, charPattern);
	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;
}

template<typename... Args>
std::string Input::readToken(int minLength, int maxLength, const char* charPattern, Args&&... constraints)
{
	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);
	checkConstraints(res, std::forward<Args>(constraints)...);
	return res;
}

template<typename... Args>
std::string Input::readToken(const std::string& regexp, Args&&... constraints)
{
	std::string token = readToken();
	if (!std::regex_match(token, std::regex(regexp)))
		error("token does not match regexp %s", regexp.c_str());
	checkConstraints(token, std::forward<Args>(constraints)...);
	return token;
}

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;
}

std::string Input::readLine(const std::string& regexp)
{
	std::string res;
	while (!isEoln())
	{
		if (isEof())
			error("EOF instead of EOLN");
		res += (char)c;
		nextChar();
	}
	if (!std::regex_match(res, std::regex(regexp)))
		error("line does not match regexp %s", regexp.c_str());
	nextChar();
	return res;
}

template<typename... Args>
int Input::readInt(int minValue, int maxValue, Args&&... constraints)
{
	int value = (int)readLong(minValue, maxValue);
	checkConstraints(value, std::forward<Args>(constraints)...);
	return value;
}

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(const std::string& minRelation, double minValue, const std::string& maxRelation,
	double maxValue, int maxDigits)
{
	if (!(minRelation == ">" || minRelation == ">="))
		error("Unsupported minRelation: '%s'", minRelation.c_str());
	if (!(maxRelation == "<" || maxRelation == "<="))
		error("Unsupported maxRelation: '%s'", maxRelation.c_str());
	if (maxDigits < 1 || maxDigits > 15)
		error("Unsupported maxDigits: %d", 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;
	double eps = std::pow(10.0, -(maxDigits + 1));
	if (!(((minRelation == ">" && x > minValue + eps) || (minRelation == ">=" && x >= minValue - eps)) &&
		  ((maxRelation == "<" && x < maxValue - eps) || (maxRelation == "<=" && x <= maxValue + eps))))
		error("number %g is out of bounds %c%g, %g%c", x, minRelation == ">" ? '(' : '[', minValue, maxValue,
			maxRelation == "<" ? ')' : ']');
	return x;
}

double Input::readDouble(double minValue, double maxValue, int maxDigits)
{
	return readDouble(">=", minValue, "<=", maxValue, maxDigits);
}

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

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

template<typename... Args>
std::vector<int> Input::readIntVectorUntil(int minValue, int maxValue, int endMarker, Args&&... constraints)
{
	std::vector<int> result;
	while (true)
	{
		int value = readInt(-2147483648, 2147483647);
		if (value == endMarker)
			break;
		if (!(value >= minValue && value <= maxValue))
			error("integer %d is out of bounds [%d, %d]", value, minValue, maxValue);
		checkConstraints(value, std::forward<Args>(constraints)...);
		result.push_back(value);
		readSpace();
	}
	return result;
}

template<typename... Args>
std::vector<int> Input::readIntVectorUntilLines(int minValue, int maxValue, int endMarker, Args&&... constraints)
{
	std::vector<int> result;
	while (true)
	{
		int value = readInt(-2147483648, 2147483647);
		if (value == endMarker)
			break;
		if (!(value >= minValue && value <= maxValue))
			error("integer %d is out of bounds [%d, %d]", value, minValue, maxValue);
		checkConstraints(value, std::forward<Args>(constraints)...);
		result.push_back(value);
		readEoln();
	}
	readEoln();
	return result;
}

std::vector<int> Input::readPermutation(int count, int start)
{
	return readIntVector(count, start, start + count - 1, Unique<int>());
}

std::vector<int> Input::readPermutationLines(int count, int start)
{
	return readIntVectorLines(count, start, start + count - 1, Unique<int>());
}

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

void Input::error(const char* fmt, ...) const
{
	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)
{
	if (p <= 0)
		error("Non-positive number: %d", 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);
}

long long gcd(long long a, long long b)
{
	a = a < 0 ? -a : a;
	b = b < 0 ? -b : b;
	while (b > 0) {
		long long c = a % b;
		a = b;
		b = c;
	}
	return a;
}

#define InputOrFreeError(in, ...) \
	do { if ((in) != nullptr) (in)->error(__VA_ARGS__); else error(__VA_ARGS__); } while (false)

MaxSum::MaxSum(long long maxSum)
	: maxSum(maxSum), sum(0), pos(0)
{
}

void MaxSum::operator()(long long value, const Input* in)
{
	pos++;
	if (value < 0)
		InputOrFreeError(in, "negative number at position %d", pos);
	sum += value;
	if (sum > maxSum)
		InputOrFreeError(in, "sum exceeded %lld at position %d", maxSum, pos);
}

template<typename T>
void assertMaxSum(const std::vector<T>& values, long long maxSum)
{
	MaxSum sum(maxSum);
	for (const T& value : values)
		sum(value);
}

template<typename T>
Monotone<T>::Monotone(const std::string& relation)
	: rel(relation), pos(0)
{
	if (!(rel == "<" || rel == "<=" || rel == ">" || rel == ">="))
		error("Unsupported relation: '%s'", rel.c_str());
}

template<typename T>
void Monotone<T>::operator()(const T& value, const Input* in)
{
	pos++;
	if (prev.has_value())
	{
		const T& x = *prev;
		const T& y = value;
		if (!(rel == "<" && x < y || rel == "<=" && x <= y || rel == ">" && x > y || rel == ">=" && x >= y))
			InputOrFreeError(in, "expected relation %s at positions %d and %d", rel.c_str(), pos - 1, pos);
	}
	prev = value;
}

template<typename T>
void assertMonotone(const std::vector<T>& values, const std::string& relation)
{
	Monotone<T> monotone(relation);
	for (const T& value : values)
		monotone(value);
}

template<typename T>
void Unique<T>::operator()(const T& value, const Input* in)
{
	int position = static_cast<int>(index.size()) + 1;
	auto [it, inserted] = index.insert({value, position});
	if (!inserted)
		InputOrFreeError(in, "duplicate elements at positions %d and %d", it->second, position);
}

template<typename T>
void assertDistinct(const std::vector<T>& values)
{
	Unique<T> unique;
	for (const T& value : values)
		unique(value);
}

NotEqual::NotEqual(long long notEqualValue)
	: notEqualValue(notEqualValue)
{
}

void NotEqual::operator()(long long value, const Input* in)
{
	if (value == notEqualValue)
		InputOrFreeError(in, "unexpected integer %lld", value);
}

void Odd::operator()(long long value, const Input* in)
{
	if (value % 2 == 0)
		InputOrFreeError(in, "integer %lld is not odd", value);
}

void Even::operator()(long long value, const Input* in)
{
	if (value % 2 != 0)
		InputOrFreeError(in, "integer %lld is not even", value);
}