To almost all of us solving sets of linear equations is quite obviously the most exciting bit of linear algebra. Benny does not agree though and wants to write a quick program to solve his homework problems for him. Unfortunately Benny's lack of interest in linear algebra means he has no real clue on how to go about this. Fortunately, you can help him!

Write a method ```solve``` that accepts a list of linear equations that your method will have to solve. The output should be a map (a `Map` object in JavaScript) with a value for each variable in the equations. If the system does not have a unique solution (has infinitely many solutions or is unsolvable), return ```null``` (`None` in python).

For example :  
  
"2x + 4y + 6z = 18"  
"3y + 3z = 6"  
"x + 2y = z - 3"
  
should result in a map :  
  
x = 2  
y = -1  
z = 3  
  
Possible input equations have the following rules:  
-   Only the plus and minus operators are used on both the left and right hand side of the equation.  
-   Both sides of the equation can have variables; One variable can appear in multiple terms, on both sides.
-   Variable names are strings of arbitrary length.  
-   All coefficients are integers and generally fall within the range of -150 to 150, with a few ranging from -1000 to 1000. Free terms are integers in range -20000 to 20000.  
-   Equations do not necessarily have variables.  
-   Equations have exactly one operator (+ or -) between terms.  


Comparisons are performed with accuracy of `1e-6`.

**Note on numerical stability:**

There are many possible ways to solve a system of linear equations. One group of such algorithms is based on reduction and elimination methods. If you are going to use any of these, remember that such algorithms are in general *numerically unstable*, i.e. division operations repeated over and over introduce inaccuracies which accumulate from row to row. As a result it might occur that some value which is expected to be zero is actually larger, for example, `2.5e-10`. Such inaccuracies tend to be bigger in large equation systems, and random tests check systems of up to 26 equations. If it happens that small tests pass for you, and large tests fail, it probably means that you did not account for inaccuracies correctly.
Also note that tests do not depend on any reference solution, so the way how test cases are generated _is numrically stable_ - the only source of inaccuracies is your solution, and you need to account for it.

```if:python
___Note for python users:___

`numpy` module has been disabled, so that the task matches the one of the other languages. There is an anti-cheat measure about that, so you won't be able to import some other modules too (either way, you shouldn't need any module to solve this kata...)
```

Difficulty: MEDIUM
Tags: Mathematics

Starter code:
def solve(*equations):
	

Solutions:
from collections import defaultdict
from functools import reduce
import re
P_EQ = re.compile('(?P<eq>=)|(?P<coef>[+-]?\\d*)(?P<var>[a-zA-Z]*)')

def solve(*equations):
	eqsMap = list(map(parse, equations))
	vars = reduce(set.union, (set(e) for e in eqsMap))
	vars = list(set(vars) - {''}) + ['']
	if len(vars) - 1 > len(equations):
		return None
	m = [[eqm[v] for v in vars] for eqm in eqsMap]
	return solveMatrix(m, vars)

def parse(eq):
	(rev, dct) = (1, defaultdict(int))
	for m in P_EQ.finditer(eq.replace(' ', '')):
		if m['eq']:
			rev = -1
		else:
			(gc, gv) = (m['coef'], m['var'])
			if gc or gv:
				coef = 1 if not gc or gc == '+' else -1 if gc == '-' else int(gc)
				dct[m['var']] += coef * rev
	return dct

def solveMatrix(m, vars):
	EPS = 1e-10
	pivots = {}
	toDo = set(range(len(m)))
	for y in range(len(vars) - 1):
		(_, px) = max(((abs(m[x][y]), x) for x in toDo if abs(m[x][y]) > 0), default=(-1, -1))
		if px == -1:
			continue
		pivots[px] = y
		toDo.remove(px)
		(maxP, m[px][y]) = (m[px][y], 1)
		for j in range(y + 1, len(vars)):
			m[px][j] /= maxP
			if abs(m[px][j]) < EPS:
				m[px][j] = 0
		for x in range(0, len(m)):
			if x == px:
				continue
			(coef, m[x][y]) = (m[x][y], 0)
			for j in range(y + 1, len(vars)):
				m[x][j] -= coef * m[px][j]
				if abs(m[x][j]) < EPS:
					m[x][j] = 0
	solvedDct = {}
	for x in range(len(m)):
		yP = pivots.get(x, None)
		if yP is None:
			continue
		solvedDct[vars[yP]] = -m[x][-1]
	if len(solvedDct) == len(vars) - 1:
		return solvedDct


from fractions import Fraction
a = 0
variable = []

def solve(*equations):
	sq = [i for i in equations]
	print(sq)

	def extract_number(s):
		temp = ''
		variable = ''
		L = []
		for i in range(len(s)):
			try:
				if s[i] in ['+', '-'] and temp == '':
					temp += s[i]
					if variable != '':
						L.append(variable)
						variable = ''
				elif s[i] in ['+', '-'] and temp != '':
					L.append(temp)
					temp = s[i]
				else:
					temp += str(int(s[i]))
			except:
				if s[i] not in ['+', '-', '=']:
					variable += s[i]
				if len(L) == 0 and temp == '':
					L.append('1')
				elif temp in ['+', '-']:
					L.append(temp + '1')
				elif temp != '' and s[i] != '=':
					L.append(temp)
				elif temp != '' and s[i] == '=':
					L.extend([temp, '='])
				elif temp == '' and s[i] == '=':
					if variable != '':
						L.append(variable)
						variable = ''
					L.extend(['='])
				else:
					pass
				temp = ''
		if temp != '':
			L.append(temp)
		if variable != '':
			L.append(variable)
		return L

	def refine(raw_matrix):
		refine_dict = dict({})
		flag = 0
		num = 0
		refine_dict['constant'] = 0
		for i in raw_matrix:
			try:
				if num != 0 and str(int(i)) != '':
					refine_dict['constant'] += num
				if flag == 0:
					num = int(i)
				else:
					num = -int(i)
			except:
				if i != '=':
					if i not in refine_dict.keys():
						refine_dict[i] = num
					else:
						refine_dict[i] += num
					num = 0
				else:
					flag = 1
		if num != 0:
			refine_dict['constant'] += num
		else:
			refine_dict['constant'] += 0
		return refine_dict

	def reduction(List_of_dict):
		L = []
		max_number = 0
		max_dict = dict({})
		for findout in range(len(List_of_dict)):
			if len(List_of_dict[findout]) > max_number:
				max_number = len(List_of_dict[findout])
				max_dict = List_of_dict[findout]
		nonlocal variable
		variable = [i for i in max_dict.keys()][::-1]
		insert = 0
		for i in List_of_dict:
			keys_list = [m for m in i.keys()]
			temp_list = []
			for j in variable:
				try:
					temp_list.append(i[j])
					keys_list.remove(j)
				except:
					temp_list.append(0)
			for k in keys_list:
				variable.insert(-1, k)
				temp_list.append(i[k])
			L.append(temp_list)
		print(variable)
		for i in range(len(List_of_dict)):
			if L[i][i] == 0:
				for j in range(i, len(List_of_dict)):
					if L[j][i] != 0:
						temp_list = L[i]
						L[i] = L[j]
						L[j] = temp_list
						break
			a = L[i][i]
			if i == len(variable) - 1 and a == 0:
				return L
			if L[i][:i + 1] == [0] * (i + 1) and L[i][-1] != 0:
				return None
			if L[i] == [0] * len(L[i]) and i < len(variable) - 1:
				return None
			L[i] = list(map(lambda x: Fraction(x, a), L[i]))
			K = [num for num in range(len(List_of_dict))]
			del K[i]
			for j in K:
				if i < len(variable) - 1:
					L[j] = [L[j][index] - L[i][index] * Fraction(L[j][i], L[i][i]) for index in range(len(L[j]))]
				elif a != 0:
					return None
		return L

	def sol(equation):
		L = []
		for s in equation:
			L.append(refine(extract_number(s)))
		Ans = reduction(L)
		if Ans != None:
			show = dict({})
			keys = [i for i in variable]
			nonlocal a
			a = len(keys)
			for i in Ans:
				for j in range(len(i)):
					if i[j] == 1:
						show[keys[j]] = float(-i[-1])
						break
			return show
		else:
			return None
	solution = sol(sq)
	if len(variable) - 1 > len(sq):
		return None
	return solution


import copy
import re

class Fraction:

	def __init__(self, numerator, denominator):
		self.numerator = numerator
		self.denominator = denominator
		if not (isinstance(self.numerator, int) and isinstance(self.denominator, int)):
			raise ValueError('Expecting integer values.')
		if not self.denominator:
			raise ValueError('Division by 0.')
		self.reduce()

	def reduce(self):
		gcd = self._gcd(self.numerator, self.denominator)
		self.numerator = self.numerator // gcd
		self.denominator = self.denominator // gcd

	def to_float(self):
		return self.numerator / self.denominator

	@classmethod
	def to_fraction(cls, obj):
		if isinstance(obj, int):
			return Fraction(obj, 1)
		elif isinstance(obj, float):
			(i, j) = str(obj).split('.')
			return Fraction(int(j) + int(i) * 10 ** len(j), 10 ** len(j))
		else:
			raise ValueError('Only int or float.')

	@staticmethod
	def _gcd(x, y):
		while y:
			(x, y) = (y, x % y)
		return x

	def _lcm(self, x, y):
		return abs(x * y) // self._gcd(x, y)

	def __add__(self, other):
		lcm = self._lcm(self.denominator, other.denominator)
		numerator = self.numerator * (lcm // self.denominator) + other.numerator * (lcm // other.denominator)
		return Fraction(numerator, lcm)

	def __sub__(self, other):
		lcm = self._lcm(self.denominator, other.denominator)
		numerator = self.numerator * (lcm // self.denominator) - other.numerator * (lcm // other.denominator)
		return Fraction(numerator, lcm)

	def __mul__(self, other):
		return Fraction(self.numerator * other.numerator, self.denominator * other.denominator)

	def __truediv__(self, other):
		return Fraction(self.numerator * other.denominator, self.denominator * other.numerator)

	def __bool__(self):
		return self.numerator != 0

	def __str__(self):
		return str(self.numerator) + '/' + str(self.denominator)

class LinearEquation:
	PATTERN = '[+-]?([0-9]+[a-zA-Z]*|[a-zA-Z]+)([+-]([0-9]+[a-zA-Z]*|[a-zA-Z]+))*'

	def __init__(self, eq):
		self.eq = eq.replace(' ', '')
		if not self._validation():
			raise ValueError('Expecting correct Equation.')

	def _validation(self):
		if re.match('^' + LinearEquation.PATTERN + '=' + LinearEquation.PATTERN + '$', self.eq):
			return True
		else:
			return False

	@staticmethod
	def _tokenize(string):
		tokens = re.findall('[+-]?(?:[0-9]+[a-zA-Z]*|[a-zA-Z]+)', string)
		values = dict()
		for token in tokens:
			(value, var) = re.findall('^([+-]?[0-9]*)([a-zA-Z]*)$', token)[0]
			if not value or value == '+':
				value = Fraction(1, 1)
			elif value == '-':
				value = Fraction(-1, 1)
			else:
				value = Fraction.to_fraction(float(value))
			if var in list(values.keys()):
				values[var] += value
			elif value:
				values[var] = value
		return values

	def parse(self):
		(left_side, right_side) = self.eq.split('=')
		values = self._tokenize(left_side)
		for (var, value) in list(self._tokenize(right_side).items()):
			value *= Fraction(-1, 1)
			if var in list(values.keys()):
				values[var] += value
			else:
				values[var] = value
		if '' not in list(values.keys()):
			values[''] = Fraction(0, 1)
		return values

class LinearEquationSystem:

	def __init__(self, m, x, b):
		self.m = m
		self.x = x
		self.b = b
		if not self._validate():
			raise ValueError('Wrong arguments.')

	def _validate(self):
		if not isinstance(self.m, list) and (not isinstance(self.x, list)) and (not isinstance(self.b, list)):
			return False
		if not len(self.m) == len(self.b):
			return False
		for eq in self.m:
			if not isinstance(eq, list) and len(eq) == len(self.x):
				return False
		return True

	@staticmethod
	def _rank(m):
		rank = min(len(m[0]), len(m))
		ind = min(len(m[0]), len(m))
		for i in range(ind):
			if m[i][i]:
				for j in range(i + 1, len(m)):
					multiplier = m[j][i] / m[i][i]
					for k in range(i, len(m[0])):
						m[j][k] -= multiplier * m[i][k]
			else:
				reduce = True
				for j in range(i + 1, len(m)):
					if m[j][i]:
						reduce = False
						(m[i], m[j]) = (m[j], m[i])
						break
				if reduce:
					rank -= 1
				else:
					for j in range(i + 1, len(m)):
						multiplier = m[j][i] / m[i][i]
						for k in range(i, len(m[0])):
							m[j][k] -= multiplier * m[i][k]
		return (rank, m)

	def solve(self):
		m = copy.deepcopy(self.m)
		(m_rank, _) = self._rank(m)
		m_b = copy.deepcopy(self.m)
		for (i, row) in enumerate(m_b):
			row.append(self.b[i])
		(m_b_rank, m_b) = self._rank(m_b)
		if m_rank == m_b_rank and m_rank == len(self.x):
			solutions = dict()
			b = list()
			for row in m_b:
				b.append(Fraction(-1, 1) * row[-1])
				del row[-1]
			while len(m_b) > len(m_b[0]):
				del m_b[-1]
			for i in range(len(m_b))[::-1]:
				multiplier = None
				for j in range(len(m_b[i])):
					if j == i:
						multiplier = Fraction(1, 1) / m_b[i][i]
					elif m_b[i][j]:
						b[i] -= m_b[i][j] * solutions[self.x[j]]
				solutions[self.x[i]] = b[i] * multiplier
			for var in solutions:
				solutions[var] = solutions[var].to_float()
			return solutions
		else:
			return None

def solve(*eqs):
	print(eqs)
	values_list = list()
	variables = set()
	coefficient_matrix = list()
	b = list()
	for (i, eq) in enumerate(eqs):
		values_list.append(LinearEquation(eq).parse())
		for var in list(values_list[i].keys()):
			variables.add(var)
		coefficient_matrix.append(list())
	variables = sorted(list(variables))
	for i in range(len(eqs)):
		for var in variables:
			if not var:
				b.append(values_list[i][var])
			elif var in list(values_list[i].keys()):
				coefficient_matrix[i].append(values_list[i][var])
			else:
				coefficient_matrix[i].append(Fraction(0, 1))
	system = LinearEquationSystem(m=coefficient_matrix, x=variables[1:], b=b)
	return system.solve()


import re
from functools import reduce

def parse_term(term, scale):
	parts = re.findall('[+-]?\\d+|[+-]|[^\\d]+', term)
	if parts[0] in '+-':
		parts[0] += '1'
	if len(parts) == 2:
		return {parts[1]: int(parts[0]) * scale}
	elif len(parts) == 1:
		try:
			return {None: int(parts[0]) * scale}
		except ValueError:
			return {parts[0]: scale}
	else:
		raise Exception('assertion failed')

def combine_term_dicts(a, b):
	common_keys = set(a.keys()).intersection(b.keys())
	common_terms = {k: a[k] + b[k] for k in common_keys}
	unique_terms = lambda c: {k: v for (k, v) in c.items() if k not in common_keys}
	return {**common_terms, **unique_terms(a), **unique_terms(b)}

def parse_side(side, scale):
	no_ws = re.sub(' ', '', side)
	term_str = re.findall('[+-]?\\d*[^\\d+-]*', no_ws)[0:-1]
	term_lst = [parse_term(t, scale) for t in term_str]
	return reduce(combine_term_dicts, term_lst)

def parse_equation(eq):
	sides = eq.split('=')
	lhs = parse_side(sides[0], 1)
	rhs = parse_side(sides[1], -1)
	return combine_term_dicts(lhs, rhs)

def argmax(lst):
	return [i for i in range(len(lst)) if lst[i] == max(lst)][0]
aug = [[1, -4, 0], [2, -8, 0], [1, 1, 5]]

def gaussian_elimination_inplace(aug):
	n_equations = len(aug)
	n_variables = len(aug[0]) - 1
	for i in range(min(n_variables, n_equations - 1)):
		p = i + argmax([abs(aug[j][i]) for j in range(i, n_equations)])
		if abs(aug[p][i]) < 1e-12:
			raise ValueError('system is singular')
		(aug[i], aug[p]) = (aug[p], aug[i])
		for j in range(i + 1, n_equations):
			beta = aug[j][i] / aug[i][i]
			for k in range(n_variables + 1):
				aug[j][k] -= aug[i][k] * beta

def backsolve(aug):
	n_equations = len(aug)
	n_variables = len(aug[0]) - 1
	sol = [aug[i][n_variables] for i in range(n_variables)]
	for i in reversed(range(n_variables)):
		for j in range(i + 1, n_variables):
			sol[i] -= aug[i][j] * sol[j]
		if abs(aug[i][i]) < 1e-12:
			raise ValueError('system is singular')
		sol[i] /= aug[i][i]
	return sol

def solve(*equations):
	lst = [parse_equation(eq) for eq in equations]
	variables = map(set, map(dict.keys, lst))
	variables = [v for v in reduce(set.union, variables) if v]
	n_variables = len(variables)
	n_equations = len(equations)
	if n_equations < n_variables:
		return None
	aug = [[0] * (n_variables + 1) for i in range(n_equations)]
	for i in range(n_equations):
		for j in range(n_variables):
			aug[i][j] = lst[i].get(variables[j], 0)
		aug[i][n_variables] = -lst[i].get(None, 0)
	try:
		gaussian_elimination_inplace(aug)
		sol = backsolve(aug)
	except ValueError:
		return None
	return {k: v for (k, v) in zip(variables, sol)}


import re
from math import gcd

def solve(*eqs):
	for e in eqs:
		print(e)
	parsed_eqs = []
	for e in eqs:
		e = ('' if e[0] == '-' else '+') + e
		parts = re.match('\\A(([+-][0-9]*[a-z]*)+)=(([+-]?[0-9]*[a-z]*)+)\\Z', e).groups()
		parts = (parts[0], ('' if parts[2][0] == '-' else '+') + parts[2])
		parts = [re.findall('[+-][0-9]*[a-z]*', p) for p in parts]
		parts = [[[''.join(re.findall('\\A([+-][0-9]*)', i)), ''.join(re.findall('[a-z]', i))] for i in p] for p in parts]
		parsed = {}
		for (i, p) in enumerate(parts):
			for (v, k) in p:
				if k not in parsed:
					parsed[k] = 0
				parsed[k] += (int(v) if v not in '-+' else int(v + '1')) * [1, -1][i]
		parsed_eqs.append(parsed)
	keys = set()
	for parsed_eq in parsed_eqs:
		for key in parsed_eq:
			keys.add(key)
	for parsed_eq in parsed_eqs:
		for key in keys:
			if key not in parsed_eq:
				parsed_eq[key] = 0
	ordered_keys = sorted(keys - {''}) + ['']
	print('\n' + str(ordered_keys))
	matrix = []
	for parsed_eq in parsed_eqs:
		matrix.append([[parsed_eq[k], 1] for k in ordered_keys])
	for line in matrix:
		print(line)

	def swap(i0, i1):
		tmp = matrix[i0]
		matrix[i0] = matrix[i1]
		matrix[i1] = tmp

	def mul(i, n):
		for l in matrix[i]:
			l[0] *= n

	def div(i, n):
		for l in matrix[i]:
			l[1] *= n

	def add(io, it):
		for c in range(len(matrix[0])):
			matrix[it][c][0] = matrix[it][c][0] * matrix[io][c][1] + matrix[io][c][0] * matrix[it][c][1]
			matrix[it][c][1] *= matrix[io][c][1]

	def sub(io, it):
		for c in range(len(matrix[0])):
			matrix[it][c][0] = matrix[it][c][0] * matrix[io][c][1] - matrix[io][c][0] * matrix[it][c][1]
			matrix[it][c][1] *= matrix[io][c][1]

	def reduce(i):
		for l in matrix[i]:
			divisor = gcd(l[0], l[1])
			if l[1] < 0:
				divisor *= -1
			if divisor != 0:
				(l[0], l[1]) = (l[0] // divisor, l[1] // divisor)

	def ref(r0, c0):
		print()
		if r0 >= len(matrix) or c0 >= len(matrix[0]) - 1:
			return
		if matrix[r0][c0][0] == 0:
			r = r0
			while r < len(matrix) and matrix[r][c0][0] == 0:
				r += 1
			if r == len(matrix):
				return ref(r0, c0 + 1)
			swap(r0, r)
		for i in range(r0, len(matrix)):
			if matrix[i][c0][0] != 0:
				div(i, matrix[i][c0][0])
				reduce(i)
		for i in range(r0, len(matrix)):
			mul(i, matrix[i][c0][1])
			reduce(i)
		for i in range(r0 + 1, len(matrix)):
			if matrix[i][c0][0] != 0:
				sub(r0, i)
				reduce(i)
		return ref(r0 + 1, c0 + 1)
	ref(0, 0)
	matrix = [line for line in matrix if line != [[0, 1] for x in range(len(line))]]
	print('REF:')
	for line in matrix:
		print(line)

	def rref(r0, c0):
		while r0 > 0 and c0 > 0 and (matrix[r0][c0] != [1, 1]):
			if r0 > 0 and matrix[r0][c0][0] == 0:
				r0 -= 1
			elif c0 > 0 and matrix[r0][c0] != [1, 1]:
				c0 -= 1
		if r0 <= 0 or c0 <= 0:
			return
		for i in range(0, r0):
			matrix[-1] = [[0, 1] for x in range(len(matrix[0]))]
			add(r0, -1)
			div(-1, matrix[i][c0][1])
			mul(-1, matrix[i][c0][0])
			sub(-1, i)
			reduce(i)
		return rref(r0 - 1, c0 - 1)
	matrix.append([[0, 1] for x in range(len(matrix[0]))])
	rref(len(matrix) - 2, len(matrix[0]) - 2)
	matrix.pop()
	print()
	for line in matrix:
		print(line)
	print()
	for line in matrix:
		print(line)
	if len(matrix) == 0 or len(matrix) != len(matrix[0]) - 1:
		print('Bad dimensions: {}, {}'.format(len(matrix), len(matrix[0])))
		return None
	result = {}
	for i in range(len(matrix)):
		result[ordered_keys[i]] = -matrix[i][-1][0] / matrix[i][-1][1]
	return result


import re
from fractions import Fraction

def solve(*equations):
	equations2 = []
	for x in equations:
		equations2.append(x)
	equations = equations2

	def parsing(equations):
		vectconstant = []
		matrixcoefficient = []
		listvariables = []
		for equation in equations:
			eqvariables = re.findall('[A-Za-z]+', equation)
			listvariables = listvariables + eqvariables
		listvariables = list(set(listvariables))
		for equation in equations:
			listcoefficient = []
			equation = re.sub('\\s', '', equation)
			eqdivided = equation.split('=')
			(firstp, secondp) = (eqdivided[0], eqdivided[1])
			constantterm1 = re.findall('[\\-\\+]*\\d+\\.?\\d*(?=[+-])|[\\-\\+]*\\d+\\.?\\d*$', firstp)
			constantterm2 = re.findall('[\\-\\+]*\\d+\\.?\\d*(?=[+-])|[\\-\\+]*\\d+\\.?\\d*$', secondp)
			for x in range(len(constantterm1)):
				constantterm1[x] = '-' + constantterm1[x]
				constantterm1[x] = re.sub('\\+\\+|\\-\\-', '+', re.sub('\\+\\-|\\-\\+', '-', constantterm1[x]))
			constantterm = Fraction(sum(list(map(float, constantterm1 + constantterm2))))
			vectconstant.append(constantterm)
			for x in listvariables:
				values1 = re.findall('([\\-\\+]*[\\d.]*)' + re.escape(x) + '(?=[+-]|$)', firstp)
				values2 = re.findall('([\\-\\+]*[\\d.]*)' + re.escape(x) + '(?=[+-]|$)', secondp)
				for x in range(len(values2)):
					values2[x] = '-' + values2[x]
					values2[x] = re.sub('\\+\\+|\\-\\-', '+', re.sub('\\+\\-|\\-\\+', '-', values2[x]))
				values = values1 + values2
				for x in range(len(values)):
					if values[x] == '' or values[x] == '+':
						values[x] = '1'
					elif values[x] == '-':
						values[x] = '-1'
					values[x] = float(values[x])
				coefficient = Fraction(sum(values))
				listcoefficient.append(coefficient)
			matrixcoefficient.append(listcoefficient)
		return (matrixcoefficient, vectconstant, listvariables)

	def eliminateuselessrows(matrixcoefficient, vectconstant):
		(newmatrix, newvector) = ([], [])
		for (t, x) in enumerate(matrixcoefficient):
			for y in x:
				if y != Fraction(0, 1):
					(newmatrix.append(x), newvector.append(vectconstant[t]))
					break
		return (newmatrix, newvector)

	def GaussReduction(matrixcoefficient, vectconstant):
		c = 0
		while c < min(len(matrixcoefficient[0]), len(matrixcoefficient)):
			if matrixcoefficient[c][c] == Fraction(0, 1):
				for (t, x) in enumerate(matrixcoefficient):
					if matrixcoefficient[t][c] != Fraction(0, 1):
						(matrixcoefficient[c], matrixcoefficient[t]) = (matrixcoefficient[t], matrixcoefficient[c])
						(vectconstant[c], vectconstant[t]) = (vectconstant[t], vectconstant[c])
			for (t, x) in enumerate(matrixcoefficient):
				factor = x[c]
				if t > c and matrixcoefficient[c][c] != Fraction(0, 1):
					vectconstant[t] = vectconstant[t] - vectconstant[c] * factor / matrixcoefficient[c][c]
					for (s, y) in enumerate(x):
						matrixcoefficient[t][s] = y - matrixcoefficient[c][s] * factor / matrixcoefficient[c][c]
			(matrixcoefficient, vectconstant) = eliminateuselessrows(matrixcoefficient, vectconstant)
			c = c + 1
		return (matrixcoefficient, vectconstant)
	(matrixcoefficient, vectconstant, listvariables) = parsing(equations)
	(matrixcoefficient, vectconstant) = GaussReduction(matrixcoefficient, vectconstant)
	(rk1, rk2) = (0, 0)
	for (t, x) in enumerate(matrixcoefficient):
		for y in x:
			if y != Fraction(0, 1):
				rk1 = rk1 + 1
				rk2 = rk2 + 1
				break
		else:
			if vectconstant[t] != Fraction(0, 1):
				rk2 = rk2 + 1
	if rk1 < rk2:
		return None
	if rk1 == rk2 < len(listvariables):
		return None
	(matrixcoefficient, vectconstant) = eliminateuselessrows(matrixcoefficient, vectconstant)
	for x in matrixcoefficient:
		x.reverse()
	(matrixcoefficient.reverse(), vectconstant.reverse(), listvariables.reverse())
	(matrixcoefficient, vectconstant) = GaussReduction(matrixcoefficient, vectconstant)
	for (t, x) in enumerate(matrixcoefficient):
		vectconstant[t] = vectconstant[t] * (1 / x[t])
	dictsolutions = {}
	for (t, x) in enumerate(vectconstant):
		dictsolutions.update({listvariables[t]: float(vectconstant[t])})
	return dictsolutions


import re
from fractions import Fraction as fraction

def solve(*equations):
	(A, x, b) = parse_equations(equations)
	answer = gaussian_elimination(A, x, b)
	return answer

def parse_equations(equations):
	create_equation = Equation.from_string
	equations = [create_equation(eq) for eq in equations]
	x = []
	for eq in equations:
		for var in eq.variables.keys():
			x.append(var)
	seen = set()
	x = [var for var in x if not (var in seen or seen.add(var))]
	A = []
	b = []
	for (i, eq) in enumerate(equations):
		A.append([])
		b.append(eq.constant)
		for var in x:
			constant = eq.variables.get(var)
			A[i].append(constant if constant else 0)
	return (A, x, b)

def gaussian_elimination(A, x, b):
	n = len(A)
	if n < len(x):
		return None
	for (a, b) in zip(A, b):
		a.append(b)
	for i in range(len(x)):
		max_el = abs(A[i][i])
		max_row = i
		for j in range(i + 1, n):
			if abs(A[j][i]) > max_el:
				max_el = abs(A[j][i])
				max_row = j
		if max_row != i:
			(A[i], A[max_row]) = (A[max_row], A[i])
		a1 = A[i][i]
		if round(a1, 9) == 0:
			return None
		for j in range(i + 1, n):
			a2 = A[j][i]
			if a2 == 0:
				continue
			c = -a2 / a1
			A[j][i] = 0
			for k in range(i + 1, len(x) + 1):
				A[j][k] += c * A[i][k]
	return back_substitution(A, x)

def back_substitution(U, x):
	answer = {}
	col = len(x) - 1
	for row in range(len(U) - 1, -1, -1):
		if U[row][col] == 0:
			if round(U[row][len(x)], 9) != 0:
				return None
			continue
		answer[x[col]] = U[row][len(x)] / U[row][col]
		for i in range(row - 1, -1, -1):
			U[i][len(x)] -= U[i][col] * answer[x[col]]
		col -= 1
	return answer

class Equation:

	def __init__(self, variables, constant):
		self.variables = variables
		self.constant = constant

	@classmethod
	def from_string(cls, eq):
		obj_list = []
		obj_regex = re.compile('-?\\d*[a-z]+|-?\\d+')
		substring = eq[0:eq.find('=')]
		found_obj = obj_regex.findall(substring)
		if len(found_obj):
			for obj in found_obj:
				obj_list.append(obj)
		substring = eq[eq.find('=') + 1:]
		found_obj = obj_regex.findall(substring)
		if len(found_obj):
			for obj in found_obj:
				obj = obj[1:] if '-' in obj else '-' + obj
				obj_list.append(obj)
		s_regex = re.compile('[a-z]+')
		constant = -sum((int(obj) for obj in obj_list if not s_regex.search(obj)))
		variable_list = [obj for obj in obj_list if s_regex.search(obj)]
		variable_dict = {}
		n_regex = re.compile('-?\\d*')
		for obj in variable_list:
			s = s_regex.search(obj).group()
			n = n_regex.search(obj).group()
			if n == '-':
				n = -1
			elif n == '':
				n = 1
			else:
				n = int(n)
			if variable_dict.get(s):
				variable_dict[s] += n
			else:
				variable_dict[s] = n
		return cls(variable_dict, constant)

	def __repr__(self):
		return 'Variables: {}\nConstant: {}'.format(self.variables, self.constant)


import re
from collections import defaultdict

def parse_terms(term, sn):
	d = defaultdict(int)
	for m in re.finditer('([+-]?)\\s*(\\d*)\\s*([a-z]*)', term):
		(s, n, v) = m.groups()
		if n or v:
			n = sn * (int(n or 1) * (1, -1)[s == '-'])
			d[v or '_'] += n
	return d

def parse_equations(equations):
	res = []
	for eq in equations:
		(a, b) = eq.split('=')
		d = parse_terms(a, 1)
		for (k, v) in parse_terms(b, -1).items():
			d[k] += v
		res.append(d)
	return res

def norm_mat(m, var_pos):
	val = m[var_pos]
	if abs(val) > 1e-08:
		for a in range(len(m)):
			m[a] /= val

def sub_mat(m1, m2, var_pos):
	if non_zero(m1[var_pos]):
		for (c, v) in enumerate(m2):
			m1[c] -= v

def non_zero(x):
	return abs(x) > 1e-08

def solve(*equations):
	print(equations)
	eqs = parse_equations(equations)
	var = sorted({k for d in eqs for k in d}, reverse=True)
	mat = [[d.get(k, 0) for k in var] for d in eqs]
	num_of_vars = len(var) - 1
	seen = set()
	p = 0
	while p < len(mat):
		var_pos = next((c for c in range(num_of_vars) if non_zero(mat[p][c]) and c not in seen))
		seen.add(var_pos)
		norm_mat(mat[p], var_pos)
		for n in range(p + 1, len(mat)):
			norm_mat(mat[n], var_pos)
			sub_mat(mat[n], mat[p], var_pos)
		mat = [m for m in mat if any(map(non_zero, m))]
		p += 1
	seen.clear()
	d = {}
	while mat:
		el = mat.pop()
		p = next((a for a in range(num_of_vars) if el[a] == 1.0 and a not in d))
		for (k, v) in d.items():
			el[-1] += el[k] * v
		d[p] = -el[-1]
	if len(d) == num_of_vars:
		return {var[k]: v for (k, v) in d.items()}


def decode_eq_side(eq_side):
	result = {}
	(sign, factor, var_name) = (1, '', '')

	def add_variable():
		nonlocal factor, var_name, result
		if var_name:
			result[var_name] = result.get(var_name, 0) + sign * int(factor) if factor else result.get(var_name, 0) + sign
		elif factor:
			result[''] = result.get(var_name, 0) + sign * int(factor) if factor else result.get(var_name, 0) + sign
		(factor, var_name) = ('', '')
	for (i, s) in enumerate(eq_side.replace(' ', '')):
		if s == '+':
			add_variable()
			sign = 1
		elif s == '-':
			add_variable()
			sign = -1
		elif s.isdigit():
			factor += s
		else:
			var_name += s
	else:
		add_variable()
	return result

def decode_equation(equation):
	(variables, variables2) = [decode_eq_side(side) for side in equation.split('=')]
	for (var, factor) in variables2.items():
		variables[var] = variables.get(var, 0) - factor
	variables[''] = -1 * variables.get('', 0)
	return variables

def solve(*equations):
	equations_variables = [decode_equation(equation) for equation in equations]
	variable_names = {var_name for eq_vars in equations_variables for var_name in eq_vars}
	variable_names.discard('')
	variable_names = list(variable_names)
	if len(variable_names) > len(equations_variables):
		return None
	equations_matrix = [[variables.get(var_name, 0) for var_name in variable_names] + [variables.get('', 0)] for variables in equations_variables]
	del equations_variables
	gauss_matrix = []
	for i in range(len(variable_names)):
		chosen_row = max(equations_matrix, key=lambda row: abs(row[i]))
		if abs(chosen_row[i]) < 1e-10:
			return None
		equations_matrix.remove(chosen_row)
		gauss_matrix.append([0] * i + [param / chosen_row[i] for param in chosen_row[i:]])
		for (row_i, row) in enumerate(equations_matrix):
			equations_matrix[row_i] = [0] * (i + 1) + [param - row[i] * gauss_matrix[-1][i + j + 1] for (j, param) in enumerate(row[i + 1:])]
	if any((abs(row[-1]) > 1e-10 for row in equations_matrix)):
		return None
	solution = []
	for equation in reversed(gauss_matrix):
		solution.append(equation[-1] - sum([equation[-(2 + i)] * param for (i, param) in enumerate(solution)]))
	return dict(zip(variable_names, reversed(solution)))


import re

def solve(*eqs):
	sysofeq = []
	for x in eqs:
		if '=' not in x:
			return None
		else:
			sysofeq.append(elabString(x))
	varis = {}
	for eq in eqs:
		va = re.findall('[a-z]+', eq)
		for char in va:
			varis.update({char: 0})
	listofvars = list(varis.keys())
	mat = []
	vec = []
	for eq in sysofeq:
		row = []
		for v in range(0, len(listofvars)):
			if eq.get(listofvars[v]) == None:
				row.append(0)
			else:
				row.append(eq.get(listofvars[v]))
		mat.append(row)
		vec.append(eq.get('sum'))
	if len(listofvars) > len(mat):
		return None
	withPivot(mat, vec)
	if len(mat) > len(mat[0]):
		for x in range(len(mat[0]), len(vec)):
			if abs(vec[x]) > 1e-06:
				return None
	for pivot in range(0, len(mat[0])):
		if abs(mat[pivot][pivot]) < 1e-08:
			return None
	result = {}
	for x in range(0, len(listofvars)):
		result.update({listofvars[x]: vec[x]})
	return result

def elabString(equation):
	equation = re.sub('\\+', ' + ', equation)
	equation = re.sub('-', ' - ', equation)
	equation = re.sub('=', ' = ', equation)
	varis = {}
	allvars = re.findall('[a-z]+', equation)
	for char in allvars:
		varis.update({char: 0})
	varis.update({'sum': 0})
	leftpart = equation.split('=')[0]
	rightpart = equation.split('=')[1][1:]
	leftparts = leftpart.split(' ')
	for x in range(0, len(leftparts)):
		if re.search('[a-z]+$', leftparts[x]):
			num = re.search('[0-9]*', leftparts[x]).group()
			if len(num) == 0:
				num = '1'
			if x > 0 and leftparts[x - 1] == '-':
				num = '-' + num
			curvar = re.search('[a-z]+$', leftparts[x]).group()
			curval = varis.get(curvar)
			varis.update({re.search('[a-z]+$', leftparts[x]).group(): int(num) + curval})
		if re.search('[0-9]$', leftparts[x]):
			origval = varis.get('sum')
			if x > 0 and leftparts[x - 1] == '-':
				varis.update({'sum': origval + int(leftparts[x])})
			else:
				varis.update({'sum': origval - int(leftparts[x])})
	rightparts = rightpart.split(' ')
	for x in range(0, len(rightparts)):
		if re.search('[a-z]+$', rightparts[x]):
			num = re.search('[0-9]*', rightparts[x]).group()
			if len(num) == 0:
				num = '1'
			if x > 0 and rightparts[x - 1] == '+':
				num = '-' + num
			if x == 0:
				num = '-' + num
			curvar = re.search('[a-z]+$', rightparts[x]).group()
			curval = varis.get(curvar)
			varis.update({re.search('[a-z]+$', rightparts[x]).group(): int(num) + curval})
		if re.search('[0-9]$', rightparts[x]):
			origval = varis.get('sum')
			if x == 0:
				varis.update({'sum': origval + int(rightparts[x])})
			elif rightparts[x - 1] == '-':
				varis.update({'sum': origval - int(rightparts[x])})
			else:
				varis.update({'sum': origval + int(rightparts[x])})
	return varis

def swapRows(matrix, vector, x, y):
	rowx = matrix[x]
	matrix[x] = matrix[y]
	matrix[y] = rowx
	varx = vector[x]
	vector[x] = vector[y]
	vector[y] = varx

def addRows(matrix, x, y, mul):
	for p in range(0, len(matrix[0])):
		matrix[y][p] = matrix[y][p] - mul * matrix[x][p]

def addScalar(vector, x, y, mul):
	vector[y] = vector[y] - mul * vector[x]

def withPivot(matrix, vector):
	for r in range(0, len(matrix[0])):
		p = [r, matrix[r][r]]
		for v in range(r, len(matrix)):
			if abs(matrix[v][r]) > abs(p[1]):
				p = [v, matrix[v][r]]
		swapRows(matrix, vector, r, p[0])
		for q in range(r + 1, len(matrix)):
			if matrix[r][r] == 0:
				return None
			mult = matrix[q][r] / matrix[r][r]
			addRows(matrix, r, q, mult)
			addScalar(vector, r, q, mult)
	for r in range(len(matrix[0]) - 1, 0, -1):
		for q in range(0, r):
			if matrix[r][r] == 0:
				return None
			mult = matrix[q][r] / matrix[r][r]
			addRows(matrix, r, q, mult)
			addScalar(vector, r, q, mult)
	for s in range(0, len(matrix[0])):
		vector[s] = vector[s] / matrix[s][s]
	return (matrix, vector)