/*	(c) WhiZTiM __ionogu(<_at__)>acm.org
	Cheat sheats.... :-)
	*/

#include <type_traits>
#include <algorithm>
#include <iostream>
#include <string>
#include <chrono>
#include <cmath>

namespace detail {
	template<typename M, typename N>
	constexpr typename std::common_type<M, N>::type lcm_Impl(M m, N n, M increment){
		return m % n == 0 ? m : lcm_Impl(m + increment, n, increment);
	}
}

template<typename Func, typename... Args>
void timeit(Func func, Args&&... args){
	auto start = std::chrono::high_resolution_clock::now();
	func(std::forward<Args&&>(args)...);
	auto stop = std::chrono::high_resolution_clock::now();
	std::cout.precision(8);
	std::cout << 
		"Took: " << std::chrono::duration<double, std::ratio<1,1>>(stop - start).count()
		<< " seconds\n";
}



/*! Returns the Greatest Common Divisor of two numbers
    Precondition: m > n; */
template<typename M, typename N>
constexpr typename std::common_type<M, N>::type gcd(M m, N n){
	return n == 0 ? m : gcd(n, m%n);
}

/*! Returns the Lowest Common Multiple of two numbers
    Precondition: m > n; */
template<typename M, typename N>
constexpr auto lcm(M m, N n){
	return detail::lcm_Impl(m, n, m);
}

/*! Returns all the factors of 'number'
    Precondition: number > 0; */
template<typename T>
std::vector<T> simple_factors(T number){
	std::vector<T> rtn;
	T bound = std::sqrt(number);
	for(T i=1; i < bound; i++)
		if(number % i == 0){
			rtn.emplace_back(i);
			rtn.emplace_back(number / i);
		}
	std::sort(rtn.begin(), rtn.end());
	return rtn;
}

/*! Simple but Fast Fibonacci solver; (Memorization)
    Postcondition: memory consumed is the maximum index computed;
	Example: 
	* Fibonacci fb; auto m = fb.compute(50);
	* int fib = Fibonacci().compute(21);
	* auto fib = Fibonacci().compute(100);
	*/
class Fibonacci {
public: //... once you, the client alter memory, there's no guarantee of correctness again
	std::vector<std::uint64_t> memory = {0, 1, 1};
public:
	std::uint64_t compute(std::size_t index){
		if(index < memory.size())
			return memory[index];
		auto c1 = compute(index - 1);
		auto c2 = compute(index - 2);
		auto c3 = c1 + c2;
		memory.emplace_back(c3);
		return c3;
	}
};



struct DumbCallback{
	template<typename T>
	constexpr bool operator () (T) { return true; }
};



/*! Fast Prime Number Generator using Sieve of Eratosthenes;
    Example:
    *  auto primes = EratosthenesSieve<>().sieve();
    *  auto primes = EratosthenesSieve<10'000'000>().sieve();
    *  std::vector<std::size_t> primes = EratosthenesSieve<>().sieve();
    *  auto primes = EratosthenesSieve<10'000'000, std::int64_t>().sieve();
    *  etc.... */
template<std::size_t max = 1'000'000,
			typename Type = typename std::conditional<
					(max <= std::numeric_limits<std::size_t>::max()), std::size_t, unsigned long
					>::type
    >
class EratosthenesSieve{
public:
    static_assert(max > 2, "Sieve size must be greater than 2");
	
	using value_type = Type;
    
	template<typename Callback = DumbCallback>
    inline std::vector<Type> sieve(Callback callback = DumbCallback()) const {
		
		std::vector<Type> rtn;
		bool flag[max];
		//! std::fill will use memset
		std::fill(std::begin(flag) + 2, std::end(flag), false);
		std::fill(std::begin(flag), std::begin(flag) + 2, true);
		for(std::size_t index = 2; index < max; index++)
			if(not flag[index])
			for(std::size_t i = 2*index; i < max; i += index)
				flag[i] = true;
				
		for(std::size_t idx = 0; idx < max; idx++)
			if(not flag[idx] and callback(idx)){
				rtn.emplace_back(idx);
			}
			
		return rtn;
    }
};


int main(){
	return 0;
}