
//-------------------------------------------------------------
// Linear Equation Solver
//   O(n^3)
//
// Verified by
//   - SRM 398 Div1 LV3
//   - AOJ 0004
//-------------------------------------------------------------

vector<double> solve_linear_eq( int n, vector< vector<double> > M, const vector<double>& V )
{
	vector<double> A(V);
	for(int i=0; i<n; ++i)
	{
		// pivot
		if( M[i][i] == 0 )
			for(int j=i+1; j<n; ++j)
				if( M[j][i] != 0 )
					{swap(M[i], M[j]); swap(A[i], A[j]); break;}
		if( M[i][i] == 0 )
			throw "no anser";

		// M[i][i] <-- 1
		double p = M[i][i];
		for(int j=i; j<n; ++j)
			M[i][j] /= p;
		A[i] /= p;

		// M[*][i] <-- 0
		for(int j=0; j<n; ++j) if(j!=i)
		{
			double r = M[j][i];
			for(int k=i; k<n; ++k)
				M[j][k] -= M[i][k] * r;
			A[j] -= A[i] * r;
		}
	}
	return A;
}


