#ifndef TEMPLATES_H
#define TEMPLATES_H

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>

#define loop(X,N,EXPR)\
{\
	long X;\
	for (X=0;X<N;++X) {\
		EXPR\
	}\
}

#define span(X,S,N,EXPR)\
{\
	long X;\
	for (X=S;X<N;++X) {\
		EXPR\
	}\
}

#define bloop(X,N,EXPR)\
{\
	long BUGIjsf;\
	for (BUGIjsf=7;BUGIjsf<N;BUGIjsf+=8)\
	 {const long X=BUGIjsf-7; EXPR\
	  {const long X=BUGIjsf-6; EXPR\
	   {const long X=BUGIjsf-5; EXPR\
	    {const long X=BUGIjsf-4; EXPR\
	     {const long X=BUGIjsf-3; EXPR\
	      {const long X=BUGIjsf-2; EXPR\
	       {const long X=BUGIjsf-1; EXPR\
	        {const long X=BUGIjsf; EXPR\
	}}}}}}}}\
	span (X,N&(~(long)7),N,EXPR)\
}

#define bspan(X,S,N,EXPR)\
{\
	long BUGIjsf;\
	for (BUGIjsf=S+7;BUGIjsf<N;BUGIjsf+=8)\
	 {const long X=BUGIjsf-7; EXPR\
	  {const long X=BUGIjsf-6; EXPR\
	   {const long X=BUGIjsf-5; EXPR\
	    {const long X=BUGIjsf-4; EXPR\
	     {const long X=BUGIjsf-3; EXPR\
	      {const long X=BUGIjsf-2; EXPR\
	       {const long X=BUGIjsf-1; EXPR\
	        {const long X=BUGIjsf; EXPR\
	}}}}}}}}\
	span (X,S+((N-S)&(~(long)7)),N,EXPR)\
}

#define vloop(VEC,EXPR) bloop(i,VEC.n,EXPR)

template <class C> inline C sqr(C x)
{
	return x*x;
}

template <class C> class vector
{
public:
	C *data;
	size_t n;

	vector() {
		data=NULL;
	}
	~vector() {
		free(data);
	}
	vector(size_t new_n=0) {
		n=new_n;
		if (!(data=(C *)malloc(bytes())))
			throw out_of_memory();
	}
	vector(vector<C> &original) {
		n=original.n;
		if (!(data=(C *)malloc(bytes())))
			throw out_of_memory();
		memcpy(data,original.data,bytes());
	}
	vector<C> &operator=(vector<C> &original) {
		if (&original!=this) {
			n=original.n;
			if (!(data=(C *)realloc((void *)data,bytes())))
				throw out_of_memory();
			memcpy(data,original.data,bytes());
		}
		return *this;
	}
	C &operator[](size_t index) {
		return data[index];
	}
	vector<C> &operator+=(C a) {
		size_t reg_n=n;
		C *reg_data=data;
		bloop (i,reg_n,reg_data[i]+=a;)
		return *this;
	}
	vector<C> &operator-=(C a) {
		size_t reg_n=n;
		C *reg_data=data;
		bloop (i,reg_n,reg_data[i]-=a;)
		return *this;
	}
	vector<C> &operator*=(C a) {
		size_t reg_n=n;
		C *reg_data=data;
		bloop (i,reg_n,reg_data[i]*=a;)
		return *this;
	}
	vector<C> &operator/=(C a) {
		size_t reg_n=n;
		C *reg_data=data;
		bloop (i,reg_n,reg_data[i]/=a;)
		return *this;
	}
	vector<C> &operator+=(vector<C> &a) {
		size_t reg_n=n;
		C *reg_data=data,*reg_data_a=a.data;
		bloop (i,reg_n,reg_data[i]+=reg_data_a[i];)
		return *this;
	}
	vector<C> &operator-=(vector<C> &a) {
		size_t reg_n=n;
		C *reg_data=data,*reg_data_a=a.data;
		bloop (i,reg_n,reg_data[i]-=reg_data_a[i];)
		return *this;
	}
	vector<C> &operator*=(vector<C> &a) {
		size_t reg_n=n;
		C *reg_data=data,*reg_data_a=a.data;
		bloop (i,reg_n,reg_data[i]*=reg_data_a[i];)
		return *this;
	}
	vector<C> &operator/=(vector<C> &a) {
		size_t reg_n=n;
		C *reg_data=data,*reg_data_a=a.data;
		bloop (i,reg_n,reg_data[i]/=reg_data_a[i];)
		return *this;
	}
	void resize(size_t new_n) {
		n=original.n;
		if (!(data=(C *)realloc((void *)data,bytes())))
			throw out_of_memory();
	}
	void zero() {
		memset(data,0,bytes());
	}
	void trash() {
		free(data);
		data=NULL;
	}
	void append(C a) {
		size_t oldn=n;
		++n;
		if (!(data=(C *)realloc((void *)data,bytes())))
			throw out_of_memory();
		data[oldn]=a;
	}
	void fill(C a) {
		size_t reg_n=n;
		C *reg_data=data;
		bloop (i,reg_n,reg_data[i]=a;)
	}
	C sum() {
		size_t reg_n=n;
		C *reg_data=data;
		C acc=0;
		bloop (i,reg_n,acc+=reg_data[i];)
		return acc;
	}
	C sum2() {
		size_t reg_n=n;
		C *reg_data=data;
		C acc=0;
		bloop (i,reg_n,acc+=sqr(reg_data[i]);)
		return acc;
	}
	C mean() {
		return sum()/n;
	}
	C var() {
		size_t reg_n=n;
		C *reg_data=data;
		C tmp,acc=0,acc2=0;
		bloop (i,reg_n,tmp=reg_data[i]; acc+=tmp; acc2+=sqr(tmp);)
		return acc2/n-sqr(acc/n);
	}
	C std() {
		return sqrt(var());
	}
	C min() {
		size_t reg_n=n;
		C *reg_data=data;
		C tmp,x=reg_data[0];
		bloop (i,reg_n,tmp=reg_data[i]; if (tmp<x) x=tmp;)
		return x;
	}
	C max() {
		size_t reg_n=n;
		C *reg_data=data;
		C tmp,x=reg_data[0];
		bloop (i,reg_n,tmp=reg_data[i]; if (tmp>x) x=tmp;)
		return x;
	}
	void minmax(C &minp,C &maxp) {
		size_t reg_n=n;
		C *reg_data=data;
		C tmp,minx=reg_data[0],maxx;
		maxx=minx;
		bloop (i,reg_n,tmp=reg_data[i]; if (tmp<minx) minx=tmp;
			if (tmp>maxx) maxx=tmp;)
		minp=minx;
		maxp=maxx;
	}
	size_t bytes() {
		return n*sizeof(C);
	}
        class out_of_memory {
	public:
		out_of_memory() {
			std::cout << "Vector exception: Out of memory\n";
		}
	};
};

template <class C> std::ostream&
operator<<(std::ostream& os,const vector<C>& a) {
	loop (i,a.n,os << a.data[i] << " ";)
	return os;
}


/*
template <class T> class Array
{
public:
        Array(int len=0);
        Array(Array<T> &source);
        ~Array();
        int length()  // in elements
        {
                return number;
        }
        int size()   // in bytes
        {
                return number*sizeof(T);
        }
        T *pointer()  // use with caution! invalid after resize!
        {
                return adress;
        }
        void resize(int len);   // no margin between length<->alloc
        void lazy_resize(int len);   // works with margin
        void reset()
        {
                resize(0);
        }
        void append(T *element);
        void append(T element);
        void append(Array<T> &source);
        void insert(T *element,int index);
        void insert(T element,int index);
        void insert(Array<T> &source,int index);
        void remove(int index);
        void clear();    // sets elements to zero
        T min();
        T max();
        T mean();
        T var();
        T std()
        {
                return (T)sqrt(var());
        }
#ifdef DEBUG
        T &operator[](int index);     // with boundary-checking
#else
        T &operator[](int index)
        {
                return adress[index];
        }
#endif
        Array<T> &operator=(Array<T> &source);
        Array<T> &deepcopy(Array<T> &source);

        // exceptions follows...

        class exOutOfMemory
        {
        public:
                exOutOfMemory()
                {
                        cout << "Array exception: out of memory" << endl;
                }
        };
        class exEmptyArray
        {
        public:
                exEmptyArray()
                {
                        cout << "Array exception: empty array" << endl;
                }
        };

#ifdef DEBUG
        class exDereferenceNull
        {
        public:
                exDereferenceNull()
                {
                        cout << "Array exception: tried to "
                                "dereference NULL" << endl;
                }
        };
        class exBoundary
        {
        public:
                exBoundary()
                {
                        cout << "Array exception: index outside "
                                "boundary" << endl;
                }
        };
        class exBadLength
        {
        public:
                exBadLength()
                {
                        cout << "Array exception: invalid new length"
                                << endl;
                }
        };
#endif

private:
        T *adress;
        int number;   // these measure elements, not bytes
        int alloc;

        void allocate();
};

// helper functions

template <class T>
void Array<T>::allocate()
{
        if (alloc) {
                if (adress)
                        adress=(T*)realloc(adress,alloc*sizeof(T));
                else
                        adress=(T*)malloc(alloc*sizeof(T));
                if (!adress)
                        throw exOutOfMemory();
        } else {
                if (adress)
                        free(adress);
                adress=0;
        }
}


// constructor

template <class T>
Array<T>::Array(int len=0)
{
        adress=0;
        number=len;
        alloc=len;
#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": constructor" << endl;
#endif
#ifdef DEBUG
        if (len < 0)
                throw exBadLength();
#endif
        allocate();
}

// copy constructor, seems unnecessary...

template <class T>
Array<T>::Array(Array<T> &source)
{
        adress=0;
        number=source.number;
        alloc=source.alloc;
#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": copy constructor" << endl;
#endif
        allocate();
        if (size())
                memcpy(adress,source.adress,size());
}

// destructor

template <class T>
Array<T>::~Array()
{
#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": destructor" << endl;
#endif
        if (adress)
                free(adress);
}

// resize without margin

template <class T>
void Array<T>::resize(int len)
{
#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": resize to " << len << endl;
#endif
#ifdef DEBUG
        if (len < 0)
                throw exBadLength();
#endif
        number=len;
        alloc=len;
        allocate();
}

// resize with margin

template <class T>
void Array<T>::lazy_resize(int len)
{
        int a;

#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": lazy_resize to " << len << endl;
#endif
#ifdef DEBUG
        if (len < 0)
                throw exBadLength();
#endif
        number=len;
        a=alloc;
        while (len < a*4/5)
                a=a*4/5;
        while (len > a)
                a=a*5/4+1;
        if (a == alloc) {
#ifdef VERBOSE
                cout << "(Nothing done)" << endl;
#endif
                return;
        }
        alloc=a;
        allocate();
}

// index[] with boundary-checking

#ifdef DEBUG
template <class T>
T &Array<T>::operator[](int index)
{
#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": operator[" << index << "]" << endl;
#endif
        if (index < 0 || index >= number)
                throw exBoundary();
        return adress[index];
}
#endif

// operator=, shallow copy

template <class T>
Array<T> &Array<T>::operator=(Array<T> &source)
{
        if (&source == this)
                return *this;
        number=source.number;
        alloc=source.alloc;
#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": operator=" << endl;
#endif
        allocate();
        if (size())
                memcpy(adress,source.adress,size());
        return *this;
}

// safer than operator=

template <class T>
Array<T> &Array<T>::deepcopy(Array<T> &source)
{
        T *s,*d,*de;

        if (&source == this)
                return *this;
        number=source.number;
        alloc=source.alloc;
#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": deepcopy" << endl;
#endif
        allocate();
        s=source.adress;
        d=adress;
        de=d+number;
        while (d < de)
                *(d++)=*(s++);
        return *this;
}

// append with pointer

template <class T>
void Array<T>::append(T *element)
{
        int oldnumber;

#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": append" << endl;
#endif
#ifdef DEBUG
        if (!element)
                throw exDereferenceNull();
#endif
        oldnumber=number;
        lazy_resize(oldnumber+1);
        memcpy(adress+oldnumber,element,sizeof(T));
}

// with value

template <class T>
void Array<T>::append(T element)
{
        int oldnumber;

#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": append" << endl;
#endif
        oldnumber=number;
        lazy_resize(oldnumber+1);
        adress[oldnumber]=element;
}

// with another array

template <class T>
void Array<T>::append(Array<T> &source)
{
        int oldnumber;

#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": append array" << endl;
#endif
        oldnumber=number;
        lazy_resize(oldnumber+source.number);
        memcpy(adress+oldnumber,source.adress,source.size());
}

// insert with pointer

template <class T>
void Array<T>::insert(T *element,int index)
{
        int oldnumber;

#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": insert at [" << index << "]" << endl;
#endif
#ifdef DEBUG
        if (!element)
                throw exDereferenceNull();
        if (index < 0 || index > number)
                throw exBoundary();
#endif
        oldnumber=number;
        lazy_resize(oldnumber+1);
        if (index < oldnumber)
                memmove(adress+index+1,adress+index,
                        (oldnumber-index)*sizeof(T));
        memcpy(adress+index,element,sizeof(T));
}

// with value

template <class T>
void Array<T>::insert(T element,int index)
{
        int oldnumber;

#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": insert at [" << index << "]" << endl;
#endif
#ifdef DEBUG
        if (index < 0 || index > number)
                throw exBoundary();
#endif
        oldnumber=number;
        lazy_resize(oldnumber+1);
        if (index < oldnumber)
                memmove(adress+index+1,adress+index,
                        (oldnumber-index)*sizeof(T));
        adress[index]=element;
}

// with another array

template <class T>
void Array<T>::insert(Array<T> &source,int index)
{
        int oldnumber;

#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": insert array at [" << index << "]" << endl;
#endif
#ifdef DEBUG
        if (index < 0 || index > number)
                throw exBoundary();
#endif
        oldnumber=number;
        lazy_resize(oldnumber+source.number);
        if (index < oldnumber)
                memmove(adress+index+source.number,adress+index,
                        (oldnumber-index)*sizeof(T));
        memcpy(adress+index,source.adress,source.size());
}

template <class T>
void Array<T>::remove(int index)
{
#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": remove [" << index << "]" << endl;
#endif
#ifdef DEBUG
        if (index < 0 || index >= number)
                throw exBoundary();
#endif
        if (index < number-1)
                memmove(adress+index,adress+index+1,
                        (number-1-index)*sizeof(T));
        lazy_resize(number-1);
}

template <class T>
void Array<T>::clear()
{
#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": clear" << endl;
#endif
        if (adress && size())
                memset((void *)adress,0,size());
}

template <class T>
T Array<T>::min()
{
        T m,*p,*pe;

#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": min" << endl;
#endif
        if (!number)
                throw exEmptyArray();
        p=adress;
        pe=p+number;
        m=*p++;
        for (;p < pe;p++)
                if (*p < m)
                        m=*p;
        return m;
}

template <class T>
T Array<T>::max()
{
        T m,*p,*pe;

#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": max" << endl;
#endif
        if (!number)
                throw exEmptyArray();
        p=adress;
        pe=p+number;
        m=*p++;
        for (;p < pe;p++)
                if (*p > m)
                        m=*p;
        return m;
}

template <class T>
T Array<T>::mean()
{
        T m=0,*p,*pe;

#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": mean" << endl;
#endif
        if (!number)
                throw exEmptyArray();
        p=adress;
        pe=p+number;
        while (p < pe)
                m+=*p++;
        m/=number;
        return m;
}

template <class T>
T Array<T>::var()
{
        T m=0,m2=0,*p,*pe;

#ifdef VERBOSE
        cout << ARRAYSIGNATURE << ": var" << endl;
#endif
        if (!number)
                throw exEmptyArray();
        p=adress;
        pe=p+number;
        for (;p < pe;p++) {
                m+=*p;
                m2+=(*p)*(*p);
        }
        m/=number;
        m2/=number;
        return m2-m*m;
}
*/

#endif