// Tested: SRM 454 Lv2
template<typename T>
struct DP2
{
	const int N1, N2;
	vector<T> data;
	DP2(int N1, int N2, const T& t = T())
		: N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
	T& operator()(int i1, int i2)
		{ return data[ (i1*N2)+i2 ]; }
	void swap(DP2& rhs)
		{ data.swap(rhs.data); }
};

// Tested: Codeforces #13 C
template<typename T>
struct DP2x
{
	const int N1, N2;
	vector<T> data;
	DP2x(int, int N2, const T& t = T())
		: N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
	T& operator()(int i1, int i2)
		{ i1&=1; return data[ (i1*N2)+i2 ]; }
	void swap(DP2x& rhs)
		{ data.swap(rhs.data); }
};

// Tested: SRM 452 Lv3
template<typename T>
struct DP3
{
	int N1, N2, N3;
	vector<T> data;
	DP3(int N1, int N2, int N3, const T& t = T())
		: N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
	T& operator()(int i1, int i2, int i3)
		{ return data[ ((i1*N2)+i2)*N3+i3 ]; }
	void swap(DP3& rhs)
		{ data.swap(rhs.data); }
};

// Tested: SRM 468 Lv2
template<typename T>
struct DP3x
{
	int N1, N2, N3;
	vector<T> data;
	DP3x(int, int N2, int N3, const T& t = T())
		: N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<26)); }
	T& operator()(int i1, int i2, int i3)
		{ i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; }
	void swap(DP3x& rhs)
		{ data.swap(rhs.data); }
};

// Tested: SRM 520 Lv2
template<typename T>
struct DP4
{
	int N1, N2, N3, N4;
	vector<T> data;
	DP4(int N1, int N2, int N3, int N4, const T& t = T())
		: N1(N1), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(data.size()*sizeof(T)<(1<<26)); }
	T& operator()(int i1, int i2, int i3, int i4)
		{ return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; }
	void swap(DP4& rhs)
		{ data.swap(rhs.data); }
};

// Not Tested
template<typename T>
struct DP4x
{
	int N1, N2, N3, N4;
	vector<T> data;
	DP4x(int, int N2, int N3, int N4, const T& t = T())
		: N1(2), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(data.size()*sizeof(T)<(1<<26)); }
	T& operator()(int i1, int i2, int i3, int i4)
		{ i1&=1; return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; }
	void swap(DP4x& rhs)
		{ data.swap(rhs.data); }
};


// Tested: SRM 351 Lv2
template<typename T>
struct DP5
{
	int N1, N2, N3, N4, N5;
	vector<T> data;
	DP5(int N1, int N2, int N3, int N4, int N5, const T& t = T())
		: N1(N1), N2(N2), N3(N3), N4(N4), N5(N5), data(N1*N2*N3*N4*N5, t) { assert(data.size()*sizeof(T)<(1<<26)); }
	T& operator()(int i1, int i2, int i3, int i4, int i5)
		{ return data[ ((((i1*N2)+i2)*N3+i3)*N4+i4)*N5+i5 ]; }
	void swap(DP5& rhs)
		{ data.swap(rhs.data); }
};

// Not Tested
template<typename T>
struct DP5x
{
	int N1, N2, N3, N4, N5;
	vector<T> data;
	DP5x(int, int N2, int N3, int N4, int N5, const T& t = T())
		: N1(2), N2(N2), N3(N3), N4(N4), N5(N5), data(N1*N2*N3*N4*N5, t) { assert(data.size()*sizeof(T)<(1<<26)); }
	T& operator()(int i1, int i2, int i3, int i4, int i5)
		{ i1&=1; return data[ ((((i1*N2)+i2)*N3+i3)*N4+i4)*N5+i5 ]; }
	void swap(DP5x& rhs)
		{ data.swap(rhs.data); }
};
