#pragma once
#include <vector>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <boost\operators.hpp>
#include <sstream>
#include <iomanip>
#include <string>
#include <exception>




namespace Numeric
{
	//numeric_limitが constexprに対応していないので、それに対処する
	template< typename T >
	struct Max;
	//最大値を計算する
	template <>
	struct Max< unsigned long >
	{
		static const unsigned long value = ULONG_MAX;
	};

	template <>
	struct Max< unsigned long long >
	{
		static const unsigned long long value = ULLONG_MAX;
	};

	template<>
	struct Max< unsigned short >
	{
		static const unsigned short value = USHRT_MAX;
	};

	template<>
	struct Max< unsigned char >
	{
		static const unsigned char value = UCHAR_MAX;
	};

	template < typename Type, Type n >
	struct CalcMaxPoweredTen{
		static const Type value = CalcMaxPoweredTen<Type, n / 10>::value * 10;
		static const Type digit = CalcMaxPoweredTen<Type, n / 10 >::digit + 1;
	};

	template <>
	struct CalcMaxPoweredTen<unsigned long long,0>{
		static const unsigned long long value = 1;
		static const unsigned long long digit = 0;
	};

	template <>
	struct CalcMaxPoweredTen<unsigned long ,0>{
		static const unsigned long value = 1;
		static const unsigned long digit = 0;
	};

	template <>
	struct CalcMaxPoweredTen<unsigned short,0>{
		static const unsigned short value = 1;
		static const unsigned short digit = 0;
	};

	template <>
	struct CalcMaxPoweredTen<unsigned char,0>{
		static const unsigned char value = 1;
		static const unsigned char digit = 0;
	};

	template <>
	struct CalcMaxPoweredTen<unsigned int,0>{
		static const unsigned int value = 1;
		static const unsigned int digit = 0;
	};
	
	template <typename Type >
	struct  MaxPoweredTen
	{
		static const Type value = CalcMaxPoweredTen<Type, (Max<Type>::value) /10>::value;
		static const Type digit = CalcMaxPoweredTen<Type,(Max<Type>::value) / 10>::digit + 1;
	};

	//Typeのビット数を求める
	template< typename Type >
	struct Bit{
		//Bitすうを求めるコア関数
		template< unsigned long long Num >
		struct CalculateBit
		{
			enum
			{
				value = ( CalculateBit< (Num >> 1) >::value ) + 1
			};
		};
		template <>
		struct CalculateBit< 0 >
		{
			enum{ value = 0 };
		};

		//ビット数
		enum{ 
			value = CalculateBit<Max<Type>::value>::value, 
		};

		//最大の桁のビットのみがONの時の値
		static const Type leftMost = ( static_cast<Type>(1) << ( value - 1 ));
	};

	template< typename T, unsigned long U>
	class basic_BigInteger;

	template< typename T , unsigned long U>
	const basic_BigInteger<T, U> operator << ( basic_BigInteger<T, U> lhs, typename basic_BigInteger<T, U>::SizeType rhs );

	template< typename T , unsigned long U>
	const basic_BigInteger<T, U> operator >> ( basic_BigInteger<T, U> lhs, typename basic_BigInteger<T, U>::SizeType rhs );



	template< typename ContainerType, unsigned long SizeAtFirst = 10 >
	class basic_BigInteger:
		boost::operators<basic_BigInteger<ContainerType>>
	{
	public:
		typedef typename ContainerType::value_type ValueType;
		typedef typename ContainerType::size_type SizeType;

		enum InternalStatus
		{
			Status		= 0,								//ステータスを格納する配列番号
			ValueOffset,									//実際に値が格納される配列番号
			NumOfBits	= Bit<ValueType>::value,			//ValueTypeのビット数
			Plus		= 0x008,							//正の数を表す（Status上では反映されない）
			Minus		= 0x001,							//負の数を表すビット数
			Infinity	= 0x002,							//無限大を表すビット数
			Null		= 0x004,							//数が無効になっているときのビット数
			Invalid		= Infinity | Null,					//何らかの不正な値を保持している
		};
		static const ValueType GreatestBit = Bit<ValueType>::leftMost;


		ContainerType value_;

	public:

		/*
		constructors
		*/
		basic_BigInteger()
			:value_( SizeAtFirst, 0)
		{
			value_[0] = Null;
		}

		basic_BigInteger( const basic_BigInteger& other )
		{
			value_ = other.value_;
		}

		/*basic_BigInteger( const basic_BigInteger &&  other )
		{
		value_ = other.value_;
		}*/

		basic_BigInteger& operator = ( const basic_BigInteger & other )
		{
			value_ = other.value_;
			return *this;
		}

		/*basic_BigInteger& operator = ( const basic_BigInteger&& other )
		{
			value_ = other.value_;

		}*/

		explicit basic_BigInteger( long long value )
			:value_( SizeAtFirst, 0)
		{
			value_[Status] = (value < 0)? Minus:0;
			value_[1] = abs( value );
		}

		basic_BigInteger( std::string value )
			:value_( SizeAtFirst, 0 )
		{
			if( value[0] == '-' )
			{
				value_[Status] |= (ValueType)Minus;
				value.erase( value.begin() );
			}
			if( value.find_first_not_of( "0123456789" ) != std::string::npos )
			{
				throw std::runtime_error( "コンストラクタにて変換不可能な文字を検出しました" );
			}


			ValueType digit = MaxPoweredTen<ValueType>::digit - 2;
			basic_BigInteger ten( MaxPoweredTen<ValueType>::value / 10 );
			ValueType count = 0;
			basic_BigInteger shift( 1 );
			basic_BigInteger result( 0 );

			string buf;

			auto it = value.rbegin();
			while( it != value.rend() )
			{
				buf.insert( buf.begin(), *it );

				++count;
				if( count == digit )
				{
					stringstream ss;
					ValueType numericBuf;
					ss << buf;
					ss >> numericBuf;
					count = 0;
					result += basic_BigInteger( numericBuf ) * shift;
					shift *= ten;

					buf = "";
				}

				++it;
			}
			if( count != 0 )
			{
					stringstream ss;
					ValueType numericBuf;
					ss << buf;
					ss >> numericBuf;
					result += basic_BigInteger(numericBuf ) * shift;
			}

			this -> value_ = result.value_;

		}

		void swap( basic_BigInteger& other )
		{
			using std::swap;
			swap( value_, other.value_ );
		}


		/*加減算*/
		basic_BigInteger& operator ++()
		{
			return *this += basic_BigInteger(1); 
		}

		basic_BigInteger& operator --()
		{
			return *this -= basic_BigInteger(1);
		}

		basic_BigInteger& operator +=( const basic_BigInteger& other)
		{	
						
			if( IsAbsSmallerThan( other ) )
			{
				basic_BigInteger temp = other;
				swap( temp );
				if(IsSameSigns( temp ) )
					AbsAdd( temp );
				else
					AbsSub( temp );
			}
			else
			{
				if(IsSameSigns( other ) )
					AbsAdd( other );
				else
					AbsSub( other );
			}
			return *this;
		}

		basic_BigInteger& operator -=( const basic_BigInteger& other )
		{
			if( IsAbsSmallerThan( other ) )
			{
				basic_BigInteger temp = other;
				swap( temp );
				if(IsSameSigns( temp ) )
					AbsSub( temp );
				else
					AbsAdd( temp );
				this->value_[Status]^= Minus;
			}
			else
			{
				if(IsSameSigns( other ) )
					AbsSub( other );
				else
					AbsAdd( other );
			}
			return *this;
		}

		/*ビット演算*/
		basic_BigInteger& operator <<= ( SizeType value )
		{
			SizeType insert	= value / NumOfBits;
			SizeType shift	= value % NumOfBits;

			ValueType next = 0;
			for( auto itr = value_.begin() + ValueOffset; itr != value_.end(); ++itr )
			{
				ValueType nextTemp = next;
				next = *itr >> ( NumOfBits - shift );
				*itr <<= shift;
				*itr += nextTemp;
			}
			if( next != 0 ) value_.push_back( next );
			if( insert )	value_.insert( value_.begin() + ValueOffset, insert, 0 );

			return *this;

		}

		basic_BigInteger& operator >>= ( SizeType value )
		{
			SizeType remove	= value / NumOfBits;
			SizeType shift	= value % NumOfBits;
			if( remove )
			{
				auto vbegin = value_.begin() + ValueOffset;
				value_.erase( vbegin, vbegin + remove );
			}

			ValueType next = 0;
			for( auto itr = value_.rbegin(); itr != value_.rend() - ValueOffset; ++itr )
			{
				
				ValueType nextTemp = next;
				next = *itr << ( NumOfBits - shift );
				(*itr) >>= shift;
				(*itr) += nextTemp;
			}
			return *this;
		}

		basic_BigInteger& operator &= ( const basic_BigInteger& other )
		{
			if( value_.size() > other.value_.size() )
			{
				std::fill(value_.begin() + other.value_.size(), value_.end(), 0 );
				std::transform( 
					other.value_.begin() + ValueOffset,
					other.value_.end(),
					value_.begin() + ValueOffset,
					value_.begin() + ValueOffset,
					[]( ValueType lhs, ValueType rhs )
					{
						return lhs & rhs;
					}
				);

				auto ritr = value_.rbegin();
				return *this;
			}
			std::transform( 
				value_.begin() + ValueOffset,
				value_.end(),
				other.value_.begin() + ValueOffset,
				value_.begin() + ValueOffset,
				[]( ValueType lhs, ValueType rhs )
				{
					return lhs & rhs;
				}
			);
			return *this;
		}

		basic_BigInteger& operator |= ( const basic_BigInteger& other )
		{

			if( value_.size() < other.value_.size() )
			{
				value_.reserve( other.value_.size() );
				std::fill_n( std::back_inserter( value_ ), other.value_.size() - value_.size(), 0 );
			}
			std::transform( 
				other.value_.begin() + ValueOffset,
				other.value_.end(),
				value_.begin() + ValueOffset,
				value_.begin() + ValueOffset,
				[]( ValueType lhs, ValueType rhs )
				{
					return lhs | rhs;
				}
			);
			return *this;
		}

		basic_BigInteger& operator ^= ( const basic_BigInteger& other )
		{

			if( value_.size() < other.value_.size() )
			{
				value_.reserve( other.value_.size() );
				std::fill_n( std::back_inserter( value_ ), other.value_.size() - value_.size(), 0 );
			}
			std::transform( 
				other.value_.begin() + ValueOffset,
				other.value_.end(),
				value_.begin() + ValueOffset,
				value_.begin() + ValueOffset,
				[]( ValueType lhs, ValueType rhs )
				{
					return lhs ^ rhs;
				}
			);
			return *this;
		}

		//ビットの反転は保留
		/*basic_BigInteger& operator ~ ()
		{
			std::for_each(
				value_.begin() + ValueOffset,
				value_.end(),
				[]( ValueType value )
				{
					return ~value;
				}
			);
			return *this;
		}*/
	
		/* 乗算,除算　*/
		basic_BigInteger& operator *= ( const basic_BigInteger& other )
		{
			basic_BigInteger temp( 0 );

			bool minus = *this == Minus;
			value_[Status] &= ~( (ValueType)Minus);

			std::for_each( 
				other.value_.begin() + ValueOffset,
				other.value_.end(),
				[&]( ValueType value )
				{
					ValueType bitFlag = 1;
					for( SizeType i = 0; i < NumOfBits; ++i)
					{
						if( value & bitFlag )
						{
							temp += *this;
						}
						*this <<= 1;
						bitFlag <<= 1;
					}
				}
			);

			swap(temp);
			if( (other == Minus && !minus) || (other == Plus && minus) )
				value_[Status] |= (ValueType)Minus;
			return *this;
		}

		basic_BigInteger& operator /= ( const basic_BigInteger& other )
		{
			if( other == basic_BigInteger( 0 ) )
			{
				value_[ Status ] |= Infinity;
				throw std::runtime_error( "0除算が発生しました" );
			}
			basic_BigInteger quotient(0);
			GetQuotientAndRemainder( other, quotient );
			swap( quotient );
			return *this;
		}

		basic_BigInteger& operator %= ( const basic_BigInteger& other)
		{
			if( other == basic_BigInteger( 0 ) )
			{
				value_[ Status ] |= NULL;
				throw std::runtime_error( "0除算が発生しました" );
			}
			GetQuotientAndRemainder( other, basic_BigInteger(0) );
			return *this;
		}
	

		/* 比較 */
		bool operator < ( const basic_BigInteger& other ) const
		{
			if( *this == Null || other == Null ) throw std::runtime_error("basic_BigIntegerが不正な値を保持しています");

			if( *this == Minus && other == Plus )
				return true;
			if( *this == Plus && other == Minus )
				return false;
			if( *this == Minus && other == Minus )
				return !IsAbsSmallerThan( other );
			else
				return IsAbsSmallerThan( other );
		}

		bool operator == ( const basic_BigInteger& other ) const
		{
			using std::swap;
			if( *this == Null || other == Null ) throw std::runtime_error("basic_BigIntegerが不正な値を保持しています");

			auto it = value_.begin() + ValueOffset, oit = other.value_.begin() + ValueOffset;
			for(  ;it != value_.end() && oit != other.value_.end(); ++it, ++oit )
			{
				if( *it != *oit )
					return false;
			}
			if( it != value_.end() )
				for( ;it != value_.end(); ++it )
				{
					if( *it != 0 )
						return false;
				}
			else if( oit != other.value_.end() )
				for( ;oit != other.value_.end(); ++oit )
				{
					if( *it != 0 )
						return false;
				}

			return true;

		}

		/*operator bool ()
		{
			return *this != basic_BigInteger(0);
		}
		*/

	public:
		/*文字列への変換*/
		/*std::string ToString() const
		{
			basic_BigInteger value( *this );
			basic_BigInteger ten(10);
			std::stringstream ss;
			while ( !value.IsAbsSmallerThan( ten ) )
			{
				basic_BigInteger temp(0);
				value.GetQuotientAndRemainder( ten, temp );
				ss << (unsigned long long)value.value_[ ValueOffset ];
				value.swap( temp );
			}
			ss << (unsigned long long)value.value_[ ValueOffset ];
			if( *this < basic_BigInteger(0) )
				ss << "-" ;

			std::string rss = ss.str();
			std::reverse( rss.begin(), rss.end() );
			return rss;
		}*/

		std::string ToString() const
		{
			basic_BigInteger value( *this );
			basic_BigInteger ten(MaxPoweredTen<ValueType>::value / 10);
			std::string rss;

			while ( /*value >= ten*/ !value.IsAbsSmallerThan( ten ) )
			{
				basic_BigInteger temp;
				value.GetQuotientAndRemainder( ten, temp );
				std::stringstream ss;
				ss <<  std::setw(MaxPoweredTen<ValueType>::digit - 2 ) << std::setfill('0') << (unsigned long long)value.value_[ ValueOffset ];

				string s = ss.str();
				rss.insert(rss.begin(), s.begin(), s.end() );

				value.swap( temp );
			}
			std::stringstream ss;
			ss <<  std::setw(MaxPoweredTen<ValueType>::digit - 2) << std::setfill('0') << (unsigned long long)value.value_[ ValueOffset ];
			string s = ss.str();
			rss.insert(rss.begin(), s.begin(), s.end() );
			if( *this < basic_BigInteger(0) )
				rss.insert( 0, "-", 1);
			return rss;
		}



		std::string ToBits() const
		{
			basic_BigInteger value(1);
			value <<= GetGreatestBit() - 1;
			std::string returnValue;
			while ( value > basic_BigInteger(0) )
			{
				if( (*this & value) != basic_BigInteger(0) )
					returnValue += "1";
				else 
					returnValue += "0";
				value >>= 1;
			}
			return returnValue;
		}
		
		//以下ロジック
	private:
		bool IsAbsSmallerThan( const basic_BigInteger& other ) const
		{
			using std::swap;
			if( *this == Infinity) return false;
			if( other == Infinity) return true;

			
			auto itr  = value_.rbegin();
			auto oitr = other.value_.rbegin();

			if( value_.size() < other.value_.size() )
			{
				for( SizeType i = 0; i < other.value_.size() - value_.size(); ++i, ++oitr )
					if( *oitr != 0 )
						return true;
			}
			else
			{
				for( SizeType i = 0; i < value_.size() - other.value_.size(); ++i, ++itr )
					if( *itr != 0 )
						return false;
			}

			for( ; itr != value_.rend() - ValueOffset && oitr != other.value_.rend() - ValueOffset ; ++itr, ++oitr )
			{
				if( *itr != *oitr ) return *itr < *oitr;
			}

			return false;
		}

		bool IsSameSigns( const basic_BigInteger& other ) const
		{
			if( other == Minus && *this == Minus ) 
				return true;
			if( other != Minus && *this != Minus )
				return true;
			return false;
		}

		bool operator == ( InternalStatus s ) const
		{
			if( s == Null )
				return ( value_[Status] & Null ) != 0;
			if( s == Plus )
				return ( value_[Status] & Minus ) == 0;
			if( s == Minus )
				return ( value_[Status] & Minus ) != 0;
			if( s == Infinity )
				return ( value_[Status] & Infinity ) != 0;
			if( s == Invalid )
				return ( value_[Status] & Invalid ) != 0;

			return false;
		}

		bool operator != ( InternalStatus s ) const
		{
			return !( *this == s );
		}

		void AbsAdd( const basic_BigInteger& other )
		{
			auto IncreaseInDigit = [&]( SizeType i )
			{
				++i;
				while( i < value_.size() )
				{
					if( value_[i] != std::numeric_limits<ValueType>::max() )
					{
						++value_[i];
						return;
					}
					value_[i] = 0;
					++i;
				}
				value_.push_back(1);
				return;
			};

			for( SizeType i = ValueOffset; i < other.value_.size(); ++i )
			{
				ValueType  o = other.value_[i];
				ValueType& t = value_[i];

				//オーバーフロー対策
				bool bitOff = ( t & GreatestBit ) != 0;
				if( bitOff ) 
					t -= GreatestBit;	
				bool obitOff = ( o & GreatestBit ) != 0;
				if( obitOff ) 
					o -= GreatestBit;

				t += o;

				//繰り上がり調整
				if( t & GreatestBit )
				{
					if( bitOff || obitOff )
					{
						//前の桁の値を調整
						if( !bitOff || !obitOff )
							t -= GreatestBit;
						
						//繰り上がりが確定
						if( i == value_.size() - 1 )
						{
							value_.push_back( 1 );
							return;
						}
						else
						{
							IncreaseInDigit( i );
						}
					}
				}
				else
				{
					if( bitOff && obitOff )
					{
						//繰り上がり確定（前の桁の値は0）
						if( i == value_.size() - 1 )
						{
							value_.push_back( 1 );
							return;
						}
						else
						{
							IncreaseInDigit( i );
						}
					}
					else if( bitOff || obitOff )
					{
						//繰り上がりしない(バッファしていた桁を元に戻す。)
						t += GreatestBit;
					}
				}
			}
		}
		void AbsSub( const basic_BigInteger& other )
		{
			//繰り下がりを計算
			auto DecreaseInDigit = []( ContainerType::iterator it )
			{
				++it;
				while( *it == 0 )
				{
					*it = std::numeric_limits<ValueType>::max();
					++it;
				}
				*it -= 1;
			};
			
			auto oitr = other.value_.begin() + ValueOffset;
			auto itr =  value_.begin() + ValueOffset;
			for( ;oitr != other.value_.end() && itr != value_.end(); ++oitr, ++itr )
			{
				if( *itr >= *oitr )
				{
					*itr -= *oitr;
					continue;
				}

				//oitrはconst_iteratorなので、内部の変数をバッファ
				ValueType o = (~*oitr) + 1; //*oitrのビットを反転
				*itr += o;
				DecreaseInDigit( itr );
			}

		}

		SizeType GetGreatestBit() const
		{
			auto itr = value_.rbegin();
			SizeType size = value_.size();
			while( *itr == 0 && itr != value_.rend() ) --size, ++itr;

			SizeType i = 0;
			ValueType v = *itr;
			for( ; v > 0; ++i )
			{
				v >>= 1;
			}
			if( size <= ValueOffset ) return 0;
			return ( size - ValueOffset - 1 )*NumOfBits + i;

		}

		//商と余りを求める低級な関数。
		//quotientにはbasic_BigInteger(0)が入っていることを前提にしており、thisは余りに変更される
		void GetQuotientAndRemainder( const basic_BigInteger& rhs, basic_BigInteger& quotient )
		{
			if( IsAbsSmallerThan( rhs ) )
			{
				return;
			}

			bool minus = *this == Minus;
			value_[Status] &= ~( (ValueType)Minus);

			while( /*rhs <= *this*/ !IsAbsSmallerThan( rhs ) )
			{
				//割る数と割られる数の桁の差を求める
				SizeType  shift = GetGreatestBit() - rhs.GetGreatestBit();
				
				//割る数と割られるかずの桁をそろえる
				basic_BigInteger temp = ( rhs << shift );
				temp.value_[Status] &= ~( (ValueType)Minus);

				//引き算可能ならば、ひいてしまう
				if( /* temp <= *this */ !IsAbsSmallerThan( temp ) )
				{
					*this -= temp;
					//ここで商を一桁求める
					quotient += ( basic_BigInteger(1) << shift );
					continue;
				}
				//もしも、その桁を割ることができなければ、次の桁まで考えたとき必ず割られる数のほうが大きくなる
				else if( shift > 0 )
				{
					temp >>= 1;
					*this -= temp;
					quotient += ( basic_BigInteger(1) << ( shift - 1 ) );
					continue;
				}
			}

			if( (rhs == Minus && !minus) || (rhs == Plus && minus) )
				quotient.value_[Status] |= (ValueType)Minus;

			if( minus )
				value_[Status] |= (ValueType)Minus;
			return;
		}

	};

	template< typename T , unsigned long U>
	const basic_BigInteger<T, U> operator << ( basic_BigInteger<T, U> lhs, typename basic_BigInteger<T, U>::SizeType rhs )
	{
		return (lhs <<= rhs );
	}

	template< typename T , unsigned long U>
	const basic_BigInteger<T, U> operator >> ( basic_BigInteger<T, U> lhs, typename basic_BigInteger<T, U>::SizeType rhs )
	{
		return (lhs >>= rhs );
	}

	template< typename T , unsigned long U>
	std::ostream&  operator << ( std::ostream& lhs, const basic_BigInteger<T, U>& rhs )
	{
		lhs << rhs.ToString();
		return lhs;
	}

	typedef basic_BigInteger< std::vector< unsigned long long > > BigInteger;

	template<  typename T , unsigned long U >
	std::istream&  operator >> ( std::istream& lhs, basic_BigInteger<T, U>& rhs )
	{
		istream_iterator<string> iit( lhs );

		rhs = basic_BigInteger<T, U>( *iit );
		return lhs;
	}
}