from random import random
from array import *
from math import sqrt, log, floor
from sys import stdout
from string import split

def gcd(a,b):
	while b != 0:
		a,b = b,a%b
	return a

def contfrac(a):
	terms=[]
	count=0
	b=1
	while ((b != 0) and (count < 24)):
		terms.append(int(a/(b+0.0)))
		a,b = b, a % b
		count = count + 1
	return terms

def ra(x):
	numerators=[0,1]
	denominators=[1,0]
	expansion=contfrac(x)
	for num in expansion:
		numerators.append((num*numerators[-1])+numerators[-2])
		denominators.append((num*denominators[-1])+denominators[-2])
	for index in range(len(numerators)):
		print "%i/%i" % (numerators[index], denominators[index])
	print

def primes(up_to):
	prime_array=array('l',[2,3,5])
	for current in range(7,up_to+1,2):
		for test in prime_array:
			if (current%test==0):
				break
			elif (test*test > current):
				prime_array.append(current)
				break
	return prime_array

def primes_mod(up_to,modulus):
	z = primes(up_to)
	for y in range(len(z)):
		z[y] = z[y] % modulus
	return z

def factors(num):
	return [x for x in range(1,num+1,1) if num % x == 0]

def prime_factors(num):
	if num <= 1:
		return [1]
	array=[]
	for prime in primes(num):
		while num%prime==0:
			array.append(prime)
			num=num/prime
	return array

def symmetrical(num):
	check = 1
	remtwo = 2*check
	while remtwo < num:
		remthree = num - remtwo
		if remthree % 3 == 0:
			remthree = remthree/3
			if (remthree + check) % 2 == 1:
				print "2*%i + 3*%i" % (check,remthree)
		check += 1
		remtwo = 2*check

def hotpo(n):
	while 1:
		if n%2==0:
			n=n/2
		elif n==1:
			print n
			break
		else:
			n=n*3+1
		print n

def lucky():
    nums=range(1,10000,2)
    x=1
    while x< len(nums):
        victim=nums[x]
        increment=victim-1
        while victim < len(nums):
            nums.pop(victim-1)
            victim+=increment
        x+=1
    return nums

combos=["010","420","543", "476", "776","1234","515", "632"]

def fill_combos_recursive():
    for x in range(5000):
	for y in range(3):
	    lookup=int(combos[x][y])
	    new=combos[lookup]
	    combos.append(new)

def binary(number):
    out=''
    while number>0:
        number,remain=divmod(number,2)
        out=str(remain)+out
    return out
    
    
def digit_sum(number,base):
    sum=0
    while number>0:
        number,remain=divmod(number,base)
        sum=sum+remain
    return sum
	
def hex(n):
    return (3*n*n)-(3*n)+1
	
def tri(n):
    return (n*(n+1))/2

def tetra(n):
    return(n*(n+1)*(n+2))/6
	
def fibo():
    x,y=0,1
    print x,y,
    for z in range(100):
            print x+y,
            x,y=y,x+y
            
def fibo_random(size,seed_1,seed_2):
    next_1,next_2=seed_1,seed_2
    print next_1,next_2
    for x in range(1000):
            carry,answer=divmod(next_1+next_2,size)
            print answer,
            next_1,next_2=(next_2+carry),answer

def sb_tree(fractions,times):
	"""usage: sb_tree(fractions,times)
	Do a Stern-Brocot tree on a seed string of two fractions (in quotes) 'times' times"""
	fractions=fractions.split()
	frac1=fractions[0].split('/')
	frac2=fractions[1].split('/')
	starting_tops=[int(frac1[0]),int(frac2[0])]
	starting_bottoms=[int(frac1[1]),int(frac2[1])]
    	ending_tops=[]
	ending_bottoms=[]
	for x in range(times):
		for y in range(len(starting_tops)-1):
			ending_tops.append(starting_tops[y])
			ending_tops.append(starting_tops[y]+starting_tops[y+1])
			ending_bottoms.append(starting_bottoms[y])
			ending_bottoms.append(starting_bottoms[y]+starting_bottoms[y+1])
		ending_tops.append(starting_tops[-1])
		ending_bottoms.append(starting_bottoms[-1])
		starting_tops=ending_tops[:]
		starting_bottoms=ending_bottoms[:]
		ending_tops=[]
		ending_bottoms=[]
    ###now print them!!!####
	outstr=""
	for x in range(len(starting_tops)):
		outstr=outstr+ repr(starting_tops[x])+ "/" + repr(starting_bottoms[x]) +" "
	return starting_tops,starting_bottoms,outstr

def myseq(num):
    start=[0,1]
    for x in range(1,num):
        start.append(abs(start[x]-start[x-1]))
        start.append(start[x]+start[x+1])
    return start

def minus(b):
	return b-1

def bulgarian(list):
	oldset=list
	while 1:
		cont=raw_input()
		if cont!="":
			break
		length=len(oldset)
		set=map(minus,oldset)
		while 1:
			try:
				set.remove(0)
			except:
				break
		set.append(length)
		print set
		oldset=set
counts=[3]
numbers=[1]

def uniques(array):
	array.sort()
	x=0
	while x<len(array):
		if array.count(array[x])>1:
			array.remove(array[x])
		else:
			x=x+1
	return array


def generate(counts,numbers):
	new_set=counts+numbers
	new_numbers=uniques(counts+numbers)
	new_counts=[]
	for x in new_numbers:
		try:
			old_count=counts[numbers.index(x)]
		except ValueError:
			old_count=0
		new_count=new_set.count(x)
		total_count=old_count+new_count
		new_counts.append(total_count)
	return new_counts,new_numbers

#print map(None,counts,numbers)	
#for x in range(times):
#	x,y=generate(counts,numbers)
#	print map(None,x,y)
#	counts,numbers=x,y		

def flip_coin():
	return int(round(random()))

def sixteen_flip():
	start=0
	for x in range(5):
		start=start+((2**x)*flip_coin())
	return start

def sample(times):
	array=[]
	for x in range(32):
		array.append(0)
	for x in range(times):
		hit=sixteen_flip()
		array[hit]=array[hit]+1
	for number in range(len(array)):
		print "%i has been hit %i times." % (number,array[number])

def pascal_triangle_line(input_list):
    input_list_size=len(input_list)
    output_list=[1L]
    for x in range(1,input_list_size):
	output_list.append(input_list[x]+input_list[x-1])
    output_list.append(1)
    return output_list

def pascal_triangle(number):
    seed_list=[1]
    for x in range(number):
	y=pascal_triang

def monthly_payment(p,r,m): # principle, rate, months
	r = r / 1200.0
	return (p*r)/(1-(1+r)**(m*-1))