class poly:
	"polynomial arithmetic"
	
	def __init__(self, coeff):
		self.COEFF = coeff
		self.trim()
	
	def __repr__(self):
		r, n = " p(x) = ", len(self.COEFF)
		if (n == 0):
			r = r + "none"
		else:
			if (self.COEFF[0] < 0):
				vz = "-"
				r = r + vz + str(self.COEFF[0])
			elif (self.COEFF[0] > 0):
				vz = "+"
				r = r + str(self.COEFF[0])
			else:
				vz = "!"
			grad = 1
			for i in self.COEFF[1:]:
				if (i == 0):
					grad = grad + 1
					continue
				elif (i > 0):
					if (vz != "!"):
						vz = " + "
					else:
						vz = ""
				else:
					if (vz != "!"):
						vz = " - "
					else:
						vz = "- "
				if (abs(i) == 1):
					c = ""
				else:
					c = str(abs(i))
				if (grad == 1):
					r = r + vz + c + "x"
				else:
					r = r + vz + c + "x^" + str(grad)
				grad = grad + 1
		return r
	
	def __cmp__(self, other):
		if (len(self) > len(other)):
			return 1
		elif (len(self) < len(other)):
			return -1
		else:
			return 0

	def __rcmp__(self, other):
		return -self.__cmp_(self, other)

	def __len__(self):
		return len(self.COEFF)

	def __getitem__(self, key):
		if (key < len(self.COEFF)):
			return self.COEFF[key]
		else:
			return 0
		
	def __setitem__(self, key, value):
		self.COEFF[key] = value
		
	def __add__(self, other):
		NEW_COEFF = []
		for i in range(0, min([len(self.COEFF), len(other.COEFF)])):
			NEW_COEFF.append(self.COEFF[i] + other.COEFF[i])
		if (len(self.COEFF) > len(other.COEFF)):
			for i in range(len(other.COEFF), len(self.COEFF)):
				NEW_COEFF.append(self.COEFF[i])
		elif (len(self.COEFF) < len(other.COEFF)):
			for i in range(len(self.COEFF), len(other.COEFF)):
				NEW_COEFF.append(other.COEFF[i])
		return poly(NEW_COEFF)
	
	def __radd__(self, other):
		return self.__add__(self, other)
	
	def __mul__(self, other):
		if (isinstance(other, spoly)):
			return other.__mul__(self)
		elif (isinstance(other, poly)):
			NEW_COEFF = []
			for i in range(0, 2 * max([len(self.COEFF), len(other.COEFF)])):
				NEW_COEFF.append(0)
			for i in range(0, len(self.COEFF)):
				for j in range(0, len(other.COEFF)):
					NEW_COEFF[i + j] = NEW_COEFF[i + j] + (self.COEFF[i] * other.COEFF[j])
			return poly(NEW_COEFF)
		else:
			return None
		
	def __rmul__(self, other):
		return self.__mul__(self, other)
	
	def __xor__(self, other):
		NEW_POLY = self + other
		for i in range(0, len(NEW_POLY)):
			NEW_POLY[i] = NEW_POLY[i] % 2
		return NEW_POLY
	
	def __rxor__(self, other):
		return self.__xor__(self, other)
		
	def grad(self):
		return len(self.COEFF) - 1
	
	def copy(self):
		return poly(self.COEFF[:])
		
	def trim(self):
		for i in range(len(self.COEFF) - 1, -1, -1):
			if (self.COEFF[i] != 0):
				self.COEFF = self.COEFF[:(i + 1)]
				break
	
	def resize(self, n):
		if (len(self.COEFF) < n):
			for i in range(0, (n - len(self.COEFF))):
				self.COEFF.append(0)
		else:
			self.COEFF = self.COEFF[:n]

class spoly(poly):
	"single coefficient polynom"
	
	def __init__(self, grad, coeff):
		self.COEFF = []
		for i in range(0, grad):
			self.COEFF.append(0)
		self.COEFF.append(coeff)
		self.trim()
	
	def __mul__(self, other):
		if (isinstance(other, spoly)):
			return spoly(self.grad() + other.grad(), self[-1] * other[-1])
		elif (isinstance(other, poly)):
			NEW_COEFF = []
			for i in range(0, (len(other) + len(self)) - 1):
				NEW_COEFF.append(0)
			for i in range(0, len(other)):
				NEW_COEFF[i + self.grad()] = self[-1] * other[i]
			return poly(NEW_COEFF)
		else:
			return None
			
	def __rmul__(self, other):
		return self.__mul__(self, other)