#ifndef SEMI_BITSET_HPP
#define SEMI_BITSET_HPP
#include <cstdint>
#include <vector>
#include <bitset>
#include <limits>
using std::size_t;
static const size_t dynamic = std::numeric_limits<size_t>::max();
static const std::uint64_t lower_half = 0x00000000FFFFFFFF;
template<size_t size_>
struct semi_bitset{
	using uint64_t = std::uint64_t;
	using uint32_t = std::uint32_t;
	size_t size = size_;
	inline size_t length(){return size;}
	uint64_t data[size_] = {0};
	inline semi_bitset(size_t s){}
	inline uint64_t chunk(size_t i){
		return data[i];
	}
};
template<>
struct semi_bitset<dynamic>{
	using uint64_t = std::uint64_t;
	using uint32_t = std::uint32_t;
	size_t size;
	std::vector<uint64_t> data;
	inline semi_bitset(size_t _size) : size(_size), data(size, 0){}
	inline size_t length(){return size;};
	inline uint64_t chunk(size_t i){
		return data[i];
	}
};
/*template<size_t size>
inline semi_bitset<size> operator<<(const semi_bitset<size>& set, int o)const{
	if(o < 0){return this->operator>>(-o);}
	if(o == 0){return *this;}
	semi_bitset<size> ret;
	unsigned int jump = o / 32;
	unsigned int mod = o % 32;
	unsigned int counter = 32 - (o % 32);
	for(size_t i = jump;i < size;i++){
		if(i < (size - 1))
			ret.data[i - jump] = ((data[i] << mod) & lower_half) | (data[i + 1] >> counter);
		else
			ret.data[i - jump] = ((data[i] << mod) & lower_half);
	}
	return ret;
}
*/
/*template<size_t size, bool containertype>
struct semi_bitset{
	using uint64_t = std::uint64_t;
	using uint32_t = std::uint32_t;
	std::vector<uint64_t> data;
	inline semi_bitset() : data(size, 0){}
	inline size_t length()const{
		return size;
	}
	inline semi_bitset<size, containertype> operator<<(int o)const{
		if(o < 0){return this->operator>>(-o);}
		if(o == 0){return *this;}
		semi_bitset<size, containertype> ret;
		unsigned int jump = o / 32;
		unsigned int mod = o % 32;
		unsigned int counter = 32 - (o % 32);
		for(size_t i = jump;i < size;i++){
			if(i < (size - 1))
				ret.data[i - jump] = ((data[i] << mod) & lower_half) | (data[i + 1] >> counter);
			else
				ret.data[i - jump] = ((data[i] << mod) & lower_half);
		}
		return ret;
	}
	inline semi_bitset<size, containertype> operator>>(int o)const{
		if(o < 0){return this->operator<<(-o);}
		if(o == 0){return *this;}
		semi_bitset<size, containertype> ret;
		unsigned int jump = o / 32;
		unsigned int mod = o % 32;
		unsigned int counter = 32 - (o % 32);
		for(size_t i = jump;i < size;i++){
			if(i > jump)
				ret.data[i] = (data[i - jump] >> mod) | ((data[i - jump - 1] << counter) & lower_half);
			else
				ret.data[i] = (data[i - jump] >> mod);
		}
		return ret;
	}
	inline semi_bitset<size, containertype>& operator<<=(int o){
		if(o < 0){return this->operator>>=(-o);}
		if(o == 0){return *this;}
		unsigned int jump = o / 32;
		unsigned int mod = o % 32;
		unsigned int counter = 32 - (o % 32);
		for(size_t i = jump;i < size;i++){
			if(i < (size - 1))
				data[i - jump] = ((data[i] << mod) & lower_half) | (data[i + 1] >> counter);
			else
				data[i - jump] = ((data[i] << mod) & lower_half);
		}
		for(size_t i = size - jump;i < size;i++){
			data[i] = 0;
		}
		return *this;
	}
	inline semi_bitset<size, containertype>& operator>>=(int o){
		if(o < 0){return this->operator<<=(-o);}
		if(o == 0){return *this;}
		unsigned int jump = o / 32;
		unsigned int mod = o % 32;
		unsigned int counter = 32 - (o % 32);
		for(size_t i = size - 1;i >= jump;i--){
			if(i > jump)
				data[i] = (data[i - jump] >> mod) | ((data[i - jump - 1] << counter) & lower_half);
			else
				data[i] = (data[i - jump] >> mod);
		}
		if(jump > 0)
		for(size_t i = jump - 1;i >= 0;i--){
			data[i] = 0;
			if(i == 0)break;
		}
		return *this;
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype> operator&(const semi_bitset<osize, ocontainertype>& o)const{
		static_assert(size == osize);
		semi_bitset<size, containertype> ret;
		for(size_t i = 0;i < size;i++){
			ret.data[i] = (data[i] & o.data[i]);
		}
		return ret;
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype> operator^(const semi_bitset<osize, ocontainertype>& o)const{
		static_assert(size == osize);
		semi_bitset<size, containertype> ret;
		for(size_t i = 0;i < size;i++){
			ret.data[i] = (data[i] ^ o.data[i]);
		}
		return ret;
		
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype> operator|(const semi_bitset<osize, ocontainertype>& o)const{
		static_assert(size == osize);
		semi_bitset<size, containertype> ret;
		for(size_t i = 0;i < size;i++){
			ret.data[i] = (data[i] | o.data[i]);
		}
		return ret;
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype>& operator&=(const semi_bitset<osize, ocontainertype>& o){
		static_assert(size == osize);
		for(size_t i = 0;i < size;i++){
			data &= o.data[i];
		}
		return *this;
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype>& operator^=(const semi_bitset<osize, ocontainertype>& o){
		static_assert(size == osize);
		for(size_t i = 0;i < size;i++){
			data ^= o.data[i];
		}
		return *this;
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype>& operator|=(const semi_bitset<osize, ocontainertype>& o){
		static_assert(size == osize);
		for(size_t i = 0;i < size;i++){
			data |= o.data[i];
		}
		return *this;
	}
	template<typename stream, size_t osize,bool ocontainertype>
	inline friend stream& operator<<(stream& s, const semi_bitset<osize, ocontainertype>& o){
		for(size_t i = 0;i < o.data.size();i++)
			s << std::bitset<32>((uint32_t)(o.data[i] & lower_half));
		return s;
	}
};
template<std::size_t size>
struct semi_bitset<size, 0>{
    using uint64_t = std::uint64_t;
	using uint32_t = std::uint32_t;
    uint64_t data[size] = {0};
	static const bool containertype = 0;
	inline semi_bitset<size, containertype> operator<<(int o)const{
		if(o < 0){return this->operator>>(-o);}
		if(o == 0){return *this;}
		semi_bitset<size, containertype> ret;
		unsigned int jump = o / 32;
		unsigned int mod = o % 32;
		unsigned int counter = 32 - (o % 32);
		for(size_t i = jump;i < size;i++){
			if(i < (size - 1))
				ret.data[i - jump] = ((data[i] << mod) & lower_half) | (data[i + 1] >> counter);
			else
				ret.data[i - jump] = ((data[i] << mod) & lower_half);
		}
		return ret;
	}
	inline size_t length()const{
		return size;
	}
	inline semi_bitset<size, containertype> operator>>(int o)const{
		if(o < 0){return this->operator<<(-o);}
		if(o == 0){return *this;}
		semi_bitset<size, containertype> ret;
		unsigned int jump = o / 32;
		unsigned int mod = o % 32;
		unsigned int counter = 32 - (o % 32);
		for(size_t i = jump;i < size;i++){
			if(i > jump)
				ret.data[i] = (data[i - jump] >> mod) | ((data[i - jump - 1] << counter) & lower_half);
			else
				ret.data[i] = (data[i - jump] >> mod);
		}
		return ret;
	}
	inline semi_bitset<size, containertype>& operator<<=(int o){
		if(o < 0){return this->operator>>=(-o);}
		if(o == 0){return *this;}
		unsigned int jump = o / 32;
		unsigned int mod = o % 32;
		unsigned int counter = 32 - (o % 32);
		for(size_t i = jump;i < size;i++){
			if(i < (size - 1))
				data[i - jump] = ((data[i] << mod) & lower_half) | (data[i + 1] >> counter);
			else
				data[i - jump] = ((data[i] << mod) & lower_half);
		}
		for(size_t i = size - jump;i < size;i++){
			data[i] = 0;
		}
		return *this;
	}
	inline semi_bitset<size, containertype>& operator>>=(int o){
		if(o < 0){return this->operator<<=(-o);}
		if(o == 0){return *this;}
		unsigned int jump = o / 32;
		unsigned int mod = o % 32;
		unsigned int counter = 32 - (o % 32);
		for(size_t i = size - 1;i >= jump;i--){
			if(i > jump)
				data[i] = (data[i - jump] >> mod) | ((data[i - jump - 1] << counter) & lower_half);
			else
				data[i] = (data[i - jump] >> mod);
		}
		if(jump > 0)
		for(size_t i = jump - 1;i >= 0;i--){
			data[i] = 0;
			if(i == 0)break;
		}
		return *this;
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype | ocontainertype> operator&(const semi_bitset<osize, ocontainertype>& o)const{
		static_assert(size == osize);
		semi_bitset<size, containertype | ocontainertype> ret;
		for(size_t i = 0;i < size;i++){
			ret.data[i] = (data[i] & o.data[i]);
		}
		return ret;
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype | ocontainertype> operator^(const semi_bitset<osize, ocontainertype>& o)const{
		static_assert(size == osize);
		semi_bitset<size, containertype | ocontainertype> ret;
		for(size_t i = 0;i < size;i++){
			ret.data[i] = (data[i] ^ o.data[i]);
		}
		return ret;
		
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype | ocontainertype> operator|(const semi_bitset<osize, ocontainertype>& o)const{
		static_assert(size == osize);
		semi_bitset<size, containertype | ocontainertype> ret;
		for(size_t i = 0;i < size;i++){
			ret.data[i] = (data[i] | o.data[i]);
		}
		return ret;
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype>& operator&=(const semi_bitset<osize, ocontainertype>& o){
		static_assert(size == osize);
		for(size_t i = 0;i < size;i++){
			data &= o.data[i];
		}
		return *this;
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype>& operator^=(const semi_bitset<osize, ocontainertype>& o){
		static_assert(size == osize);
		for(size_t i = 0;i < size;i++){
			data ^= o.data[i];
		}
		return *this;
	}
	template<size_t osize, bool ocontainertype>
	inline semi_bitset<size, containertype>& operator|=(const semi_bitset<osize, ocontainertype>& o){
		static_assert(size == osize);
		for(size_t i = 0;i < size;i++){
			data |= o.data[i];
		}
		return *this;
	}
};*/
#endif