def f2(n)

	n = (n * 3 + 1) / 2 while (n % 2 == 1)
	n /= 2 while (n % 2 == 0)
	return n

	end

	def adv(x)

	n1 = n = x['n']
	l = [n]
	while (n >= n1 && n != 1)

	n = f2(n)
	l << n
	end


	x['l'] = l
	x['ls'] = l.size

	x['ns'] = x['n'].to_s(2).length
	x['h'] = x['ls'].to_f / x['ns']
	x['h2'] = (x['h'] * $g).to_i

	return x

	end

	def next2(z)

	l = [z]
	p = z['p'] + 1

	l << adv({'n'=>z['n'] + 2**p, 'p'=>p})
	l << z.merge({'p'=>p})
	return l
	end

	def insert(l, x)
	l << x
	end

	def delete(l, j)
	z = l.delete_at(j)
	return z
	end

	def sum(l)

	t = 0
	l.each { |x| t += x }
	return t
	end

	def stat(l)
	t = t2 = 0
	l.each \
	{
	|x|
	t += x
	t2 += x ** 2
	}
	c = l.size
	a = t.to_f / c
	z = t2.to_f / c - a ** 2
	sd = Math.sqrt(z < 0 ? 0 : z)

	return a, sd, l.max.to_f, l.min.to_f
	end

	def dist(l)

	l2 = []
	l.each_with_index \
	{
	|x, i|
	h = x[1]['h2']
	l2[h] = [] if (l2[h].nil?)
	l2[h] << i
	}
	l1 = (0...l2.size).sort_by { |i| l2[i].nil? ? 0 : l2[i].size }

	return l2, l1
	end

	def rank(l1, l2)

	l1h, l1s = dist(l1)
	l2h, l2s = dist(l2)

	j = l1s.find { |x| !l2h[x].nil? && (l1h[x].nil? || l1h[x].size < $n) }

	j = l2h.size - 1 if (j.nil?)
	k = l2s.find { |x| !l2h[x].nil? }

	l = (0...l2.size).to_a
	l = l.sort_by { |x| l2[x][1]['ls'] }
	k = l.find { |x| x != j }


	return l2h[j][rand(l2h[j].size)], k

	end

	def opt(c)

	l = []
	l1 = []

	insert(l, next2({'n'=>1, 'p'=>0}))


	puts('# ' + Time.now.to_s)
	t = Time.now.to_i

	c.times \
	{
	|i|
	$stderr.puts([i, sprintf('%.1fm', (Time.now.to_i - t) / 60.0), Time.now.to_s].join("\t")) if (i % 100 == 0)

	j, k = rank(l1, l)

	if (l.size > 1000) then

	z2 = delete(l, [j, k].max)
	z1 = delete(l, [j, k].min)

	l1 += [z1, z2]
	z = j < k ? z1 : z2
	else
	z = delete(l, j)
	l1 += [z]
	end

	insert(l, next2(z[1]))
	insert(l, next2(z[2]))

	$stdout.flush
	}

	puts('# ' + Time.now.to_s)
	return l1.map { |x| x[1] }
	end

	def stat2(l, t)
	return stat(l).map { |x| x / t }
	end

	def stat1(l)
		l1 = stat(l)
		l1 = l1.map { |x| sprintf("%.3f", x).to_f }
		return {'a' => l1[0], 'sd' => l1[1], 'mx' => l1[2], 'mn' => l1[3] }
	end

	def d(s)
	c = s.split('').select { |x| x == '1' }.size
	d = c.to_f / s.length
	return d

	end

	def data(x)

	n = x['n']
	ns = n.to_s(2)
	nl = ns.length
	m = nl / 2

	nsh = ns[0..m]
	nsl = ns[m..-1]

	asdm1 = stat2(ns.split(/0+/).map { |y| y.length }, nl)

	l1 = ns.split(/1+/)
	l1.shift
	asdm0 = stat2(l1.map { |y| y.length }, nl)

	return [nl, x['ls'], x['h2'], d(ns), d(nsh), d(nsl), asdm1].flatten
	end

	def out(fn, l)

	f = File.open("#{fn}.txt", 'w')
	l.each { |x| f.puts(x.join("\t")) }
	f.close

	end

	def sample(c)

	l = opt(c)

	a = {}
	h = {}
	l.each \
	{
	|x|
	n = x['n']
	h2 = x['h2']

	h[h2] = h.fetch(h2, {}).merge!({ n => nil })
	a[n] = x
	}
	# h.sort.each { |k, v| p([k, v.size]) }; exit;


	l3 = []

	c1 = 10

	h1 = h.select { |k, v| v.size >= c1 }.sort

	h1.each_with_index \
	{
	|kv, n|

	k, v = kv
	l1 = v.keys.sort

	c1.times \
	{
	|i|
	n = l1[(i.to_f / (c1 - 1) * (l1.size - 1)).to_i]
	l3 << a[n]
	}
	}

	l2 = l3.map { |x| data(x) }

	return l2

	end

	def av(l)
	return nil if (l.empty?)
	return sum(l) / l.size
	end

	def d0(p, d, l, j, z0)

		r = (0...p.size)
		r0 = r.select { |x| !d[x].finite? }

		if (!r0.empty?)  then

			r0.each \
			{
				|x|
				$l << ['+', j, l[x]] if (p[x][$c] != z0)
			}
			return av(r0.map { |x| p[x][$c] })
		end

		t = sum(d)
		w = d.map { |x| x / t }

		z = 0
		r.each { |x| z += (w[x] * p[x][$c]) }

		r.each \
		{
			|x|
			w0 = w[x] * p.size
			p0 = w0 * p[x][$c]
			$l << [{true => '+', false => '-'}[p0 > z0], j, l[x]]
		}
		return z

	end

	def near2(l, j, a)

	l3 = a['l']
	l2 = []
	l1 = {'a' => ['a'], 'b' => ['a'], 'c' => ['a', 'b']}[$b[j]]
	l.size.times \
	{
	|i|
	next if (i == j)
	next if (!l1.member?($b[i]))
	d = 0
	l3.each { |x| d += (l[i][x] - l[j][x]) ** 2 }
	l2 << {'i' => i, 'd' => d}
	}
	l2 = l2.sort_by { |x| x['d'] }

	r = (0..a['r'])
	l4 = r.map { |x| l2[x]['i'] }
	p = l4.map { |x| l[x] }

	return d0(p, r.map { |x| 1.0 / l2[x]['d'] }, l4, j, l[j][$c])
	end


	def inc(x, y)
	x['t'] += y
	x['c'] += 1
	return x
	end

	def avg(x)
	return x['t'] / x['c']
	end

	def reshuffle()

		l = $b.select { |x| x != 'c' }.shuffle
		$b[0...l.size] = l
	end

	def near(l, l3)

	reshuffle()
	s = {'t' => 0.0, 'c' => 0}

	e2 = {'a' => s.dup, 'b' => s.dup, 'c' => s.dup}
	$l = []

	l.size.times \
	{
	|i|
	x = near2(l, i, l3)
	e = (l[i][$c] - x) ** 2
	inc(e2[$b[i]], e)
	}
	return Hash[e2.keys.map { |x| [x, avg(e2[x])] }]
	end

	def abc(n)

	$b = []
	a = {'a' => 3, 'b' => 2, 'c' => 1}

	t = sum(a.values)
	a.each \
	{
		|k, v|
		$b += [k] * (v.to_f / t * n).to_i
	}
	$b[$b.size...n] = [a.keys.last] * (n - $b.size)

	end

	def subset(l2)

		l1 = (2..l2.size).to_a
		c = l1.delete_at(rand(l1.size))
		l3 = []
		c.times { l3 << l2.delete_at(rand(l2.size)) }
		return l3
	end

	def subset2(l2, i2)
		l2 = l2.dup
		x = l2.pop
		l = subset(l2) + ((i2 == 1) ? [x] : [])
		a = {'l' => l.sort, 'r' => 10}
		return a
	end

	def compare(l, n, i0 = nil)

		$x = {} if ($x.nil?)
		$x[n] = {'s' => {}, 'l' => []} if (!$x.member?(n))
		s = $x[n]['s']
		l0 = $x[n]['l']

		m = l[0].size - 1
		l2 = (($c + 1)..m).to_a
		i = 0

		begin
			i2 = i % 2
			l3 = subset2(l2, i2)

			next if (s.member?(l3))

			s[l3] = nil
			l0 << near(l, l3).merge({'l3' => l3, 'i2' => i2})

			i += 1
		end while (i < 10)

		l0 = l0.select { |x| x['i2'] == i0 } if (!i0.nil?)
		l0.sort_by! { |x| x['a'] }
		x = l0.shift.merge({ 'm' => m })
		$f[n].puts('# ' + x.inspect)
		$f[n].flush
		return x
	end

	def opt0(l, l3, n)

		ls = l.size
		l = l.transpose
		l << [0] * ls
		l = l.transpose

		w = l[0].size - 1
		l3 += [w]
		a = {'l' => l3, 'r' => 10}

		m = nil
		x0 = nil
		c = 0
		loop \
		{
			x = near(l, a)
			x0 = x if (x0.nil?)
			$f[n].puts(x.values_at('a', 'b', 'c').join("\t"))
			$f[n].flush

			x['l'] = l.transpose[-1]
			if (m.nil? || x['a'] < m['a']) then
				m = x
				c = 0
			else
				c += 1
			end
			break if (c == 5)

			$l.shuffle
			f = 0.1

			$l.each \
			{
				|d, a, b|

				a, b = [a, b].sort_by { |x| l[x][w] }
				a, b = [b, a] if (d == '-')

				l1 = l[a]
				l2 = l[b]

				l1[w] = (l1[w] == 0) ? f : l1[w] * (1 - f)
				l2[w] = (l2[w] == 0) ? f : l2[w] * (1 + f)
			}
		}

		l = l.transpose
		l[-1] = m['l']
		l = l.transpose
		$f[n].puts
		return l
	end

	def opt1(l)

		x = compare(l, 1)

		l = opt0(l, x['l3']['l'], 1)
		return l
	end

	def opt2(l)
		$i = 0 if ($i.nil?)
		$i += 1
		x = compare(l, 2, $i % 2)
		l = opt0(l, x['l3']['l'], 2)
		return l
	end

	def opt3(l)
		l = opt0(l, (($c + 1)...l[0].size).to_a, 3)
	end

	$n = 40
	$g = 50
	l = sample(1000)
	l.shuffle!
	ls = l.size

	$stderr.puts("ls=#{ls}")

	# out('out', l)

	abc(ls)

	$c = 2

	l1 = l.dup
	l2 = l.dup
	l3 = l.dup
	$f = {}
	(1..3).each { |i| $f[i] = File.open("out#{i}.txt", 'w') }

	loop \
	{
		l1 = opt1(l1)
		l2 = opt2(l2)
		l3 = opt3(l3)
	}