#!/usr/bin/python
from operator import mod, sub
from random import random as rand, seed

def eea(a,b):
	v1 = [a,1,0]
	v2 = [b,0,1]
	while v2[0]<>0:
	   p = v1[0]//v2[0]
	   v2, v1 = map(sub,v1,[p*vi for vi in v2]), v2
	return v1

def minv(m,k):
	v = eea(m,k)
	if v[1]>=0:
		return v[1]
	else:
		return k+v[1]
		
def euc(ar0, ar1):
    while ar0>0:
        rx=ar1%ar0
        ar1=ar0
        ar0=rx
    return ar1

class cons:
	def __init__(self):
		self.rads=[]
		self.mxms=[]
		self.mxm=1
		self.invs=[]
	def ad(self, rad):
		self.mxms.append(self.mxm)
		res=self.mxm%rad
		self.invs.append(minv(res, rad))
		self.mxm*=rad
		self.rads.append(rad)
	def dec2res(self, inum):
		lst=[]
		for rad in self.rads:
			lst.append(inum%rad)
		return lst
	def res2dec(self, ires):
		lim=len(ires)
		tot=ires[0]
		ind=1
		while ind<lim:
			rad=self.rads[ind]
			cry=mod(tot, rad)
			dig=mod((ires[ind]-cry)*self.invs[ind], rad)
			tot+=dig*self.mxms[ind]
			ind+=1
		return tot
	def __str__(self):
		return '%d,%d'%(self.mxm, len(self.rads))

class consx:
	def __init__(self, irads):
		self.cns=[]
		self.mxm=1
		self.mxms=[]
		for rad in irads:
			dun=0
			for cn in self.cns:
				if rad>=2:
					gcd=euc(cn.mxm, rad)
					if gcd==1:
						cn.ad(rad)
						dun=1
						break
			if dun==0:
				self.cns.append(cons())
				self.cns[-1].ad(rad)
		for cn in self.cns:
			self.mxms.append(self.mxm)
			self.mxm*=cn.mxm
	def dec2mix(self,inum):
		inum%=self.mxm
		lim=len(self.mxms)
		lst=[0]*lim
		ind=lim-1
		while ind>=0:
			mxm=self.mxms[ind]
			if inum>mxm:
				dig=inum/mxm
				inum-=mxm*dig
				lst[ind]=(dig)
			ind-=1
		ind=lim-1
		while ind>=0 and lst[ind]==0:
			ind-=1
		ind+=1
		if ind<1:
			ind=1
		return lst[:ind]
	def dec2res(self, inum):
		mx=self.dec2mix(inum)
		return self.mix2res(mx)
	def mix2dec(self, imx):
		ind=0
		lim=len(imx)
		tot=0
		while ind<lim:
			tot+=imx[ind]*self.mxms[ind]
			ind+=1
		return tot
	def mix2res(self, mx):
		lst=[]
		ind=0
		lim=len(mx)
		while ind<lim:
			dig=mx[ind]
			lst.append(self.cns[ind].dec2res(dig))
			ind+=1
		return lst
	def res2mix(self, rlst):
		lst=[]
		ind=0
		lim=len(rlst)
		while ind<lim:
			lst.append(self.cns[ind].res2dec(rlst[ind]))
			ind+=1
		return lst
	def res2dec(self, rlst):
		mx=self.res2mix(rlst)
		return self.mix2dec(mx)
	def sho(self):
		for cn in self.cns:
			print cn.rads, cn.mxm
	def __str__(self):
		str=''
		for cn in self.cns:
			str+='%d,'%cn.mxm
		return str

def man():
	rads=[]
	seed(24)
	ind=0
	while ind<10:
		if ind==7:
			seed(24)
		rads.append(int(rand()*100))
		ind+=1
	cnx=consx(rads)
	print rads
	cnx.sho()
	rs=cnx.dec2res(1000000000)
#	rs=cnx.dec2res(cnx.mxm-1)
	print rs
	print cnx.res2dec(rs)
	print cnx.mxm

man()