package main

import (
	. "fmt"
	"math"
	"math/big"
	"math/rand"
	. "sort"
	"time"
)

func main() {
	var input string
	Scan(&input)
	if input == "LOCAL" {
		runLocal()
		return
	}
	if input == "MULTI" {
		runMulti()
		return
	}
	var n int
	Sscan(input, &n)
	a := make([]int64, n, n)
	b := make([]int64, n, n)
	for i := range a {
		Scan(&a[i], &b[i])
	}
	s := NewSolver(n, a, b)
	s.Solve()
	u, v := s.Answer()
	if err := check(n, u, v); err != nil {
		if err == errZeroIndexed {
			fixIndex(u, v)
		} else {
			Println(err)
			panic(err)
		}
	}
	output(u, v)
}

func output(u, v []int) {
	Println(len(u))
	for i, ui := range u {
		Println(ui, v[i])
	}
}

func fixIndex(u, v []int) {
	isZeroIndexed := false
	for i, ui := range u {
		if ui == 0 || v[i] == 0 {
			isZeroIndexed = true
			break
		}
	}
	if isZeroIndexed {
		for i := range u {
			u[i]++
			v[i]++
		}
	}
}

const (
	N     = 45
	ABmax = int64(1e18)
	ABmin = int64(1e17)
	X     = 50
	Base  = int64(5e17)
	Seed  = 12121212
)

func generate(n int, seed int64) (a, b []int64) {
	a = make([]int64, n, n)
	b = make([]int64, n, n)
	r := rand.New(rand.NewSource(seed))
	for i := range a {
		a[i] = r.Int63n(ABmax-ABmin) + ABmin
	}
	for i := range b {
		b[i] = r.Int63n(ABmax-ABmin) + ABmin
	}
	return
}

var errZeroIndexed = Errorf("ErrZeroIndexed")

func check(n int, u, v []int) error {
	if len(u) != len(v) {
		return Errorf("<<<WA>>> len(u)=%d != len(v)=%d ", len(u), len(v))
	}
	if len(u) > X {
		return Errorf("<<<WA>>> len(u) > %d", len(u), X)
	}
	if len(u) == 0 {
		return nil
	}
	min, max := n, 0
	for i, ui := range u {
		if ui == v[i] {
			return Errorf("<<<WA>>> u[%d]=%d == v[%d]=%d", i, ui, i, v[i])
		}
		if ui < min {
			min = ui
		}
		if v[i] < min {
			min = v[i]
		}
		if ui > max {
			max = ui
		}
		if v[i] > max {
			max = v[i]
		}
	}
	if !((min == 0 && max < n) || (min == 1 && max <= n)) {
		return Errorf("<<<WA>>> min(u,v)=%d, max(u,v)=%d", min, max)
	}
	if min == 0 {
		return errZeroIndexed
	}
	return nil
}

func show(n int, a, b []int64) {
	Println("N =", n)
	for i, ai := range a {
		Printf("A[%2d] = %19d, B[%2d] = %19d\n", i, ai, i, b[i])
	}
}

func abs(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

func max(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func min(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func process(n int, a, b []int64, u, v []int) {
	ta := make([]int64, n, n)
	tb := make([]int64, n, n)
	copy(ta, a)
	copy(tb, b)
	a, b = nil, nil
	Println("Len = ", len(u))
	for i, ui := range u {
		vi := v[i]
		Printf("u[%2d] = %2d, v[%2d] = %2d\n", i, ui, i, vi)
		Printf("    A[%2d] = %19d, B[%2d] = %19d\n", ui, ta[ui], ui, tb[ui])
		Printf("    A[%2d] = %19d, B[%2d] = %19d\n", vi, ta[vi], vi, tb[vi])
		aa, bb := (ta[ui]+ta[vi])/2, (tb[ui]+tb[vi])/2
		Printf("    A[**] = %19d, B[**] = %19d\n", aa, bb)
		da, db := abs(aa-Base), abs(bb-Base)
		Printf("     diff = %19d,  diff = %19d\n", da, db)
		Printf("     max  = %19d,  len  = %2d\n", max(da, db), len(Sprint(max(da, db))))
		ta[ui], tb[ui] = aa, bb
		ta[vi], tb[vi] = aa, bb
	}
	va, vb := abs(ta[0]-Base), abs(tb[0]-Base)
	Printf("V(A) = %19d, V(B) = %19d\n", va, vb)
	Printf(" max = %19d, len  = %2d\n", max(va, vb), len(Sprint(max(va, vb))))
	score := int64(2e6) - int64(1e5*math.Log10(float64(max(va, vb)+1)))
	if max(va, vb) == 0 {
		score += X - int64(len(u))
	}
	Printf("SCORE = %7d, SCORE*50 = %9d\n", score, score*50)
}

func runLocal() {
	var n int = N
	var seed int64 = Seed
	Scan(&n, &seed)
	a, b := generate(n, seed)
	show(n, a, b)
	t := time.Now()
	s := NewSolver(n, a, b)
	s.Solve()
	u, v := s.Answer()
	Println(time.Since(t))
	Println(s.info)
	if err := check(n, u, v); err != nil {
		if err != errZeroIndexed {
			Println(err)
			panic(err)
		}
	}
	process(n, a, b, u, v)
}

func calc(n int, a, b []int64, u, v []int) (a0, b0 int64) {
	ta := make([]int64, n, n)
	tb := make([]int64, n, n)
	copy(ta, a)
	copy(tb, b)
	for i, ui := range u {
		vi := v[i]
		aa := (ta[ui] + ta[vi]) / 2
		bb := (tb[ui] + tb[vi]) / 2
		ta[ui], tb[ui] = aa, bb
		ta[vi], tb[vi] = aa, bb
	}
	a0, b0 = ta[0], tb[0]
	return
}

func runMulti() {
	var test int = 10
	var seed int64 = Seed
	Scan(&test, &seed)
	var total int64
	for t := 0; t < test; t, seed = t+1, seed^abs(seed*1717+int64(t)) {
		Printf("Test %2d/%2d: Seed = %20d, ", t+1, test, seed)
		a, b := generate(N, seed)
		start := time.Now()
		s := NewSolver(N, a, b)
		s.Solve()
		u, v := s.Answer()
		end := time.Since(start)
		Printf("%v, %s\n", end, s.info)
		if err := check(N, u, v); err != nil {
			if err != errZeroIndexed {
				Println(err)
				panic(err)
			}
		}
		a0, b0 := calc(N, a, b, u, v)
		va, vb := abs(a0-Base), abs(b0-Base)
		score := int64(2e6) - int64(1e5*math.Log10(float64(max(va, vb)+1)))
		if max(va, vb) == 0 {
			score += X - int64(len(u))
		}
		total += score
		Printf(" SCORE = %7d, max(Va,Vb) = %18d, len = %2d\n",
			score, max(va, vb), len(Sprint(max(va, vb))))
	}
	Printf("TOTAL SCORE = %9d ( estimated 50 cases = %10d )\n",
		total, total*50/int64(test))
}

type Solver struct {
	n    int
	a, b []int64
	u, v []int
	info string
}

func NewSolver(n int, a, b []int64) *Solver {
	ta := make([]int64, n, n)
	tb := make([]int64, n, n)
	copy(ta, a)
	copy(tb, b)
	return &Solver{n, ta, tb, []int{}, []int{}, ""}
}

func (s *Solver) Clone() *Solver {
	ta := make([]int64, s.n, s.n)
	tb := make([]int64, s.n, s.n)
	copy(ta, s.a)
	copy(tb, s.b)
	return &Solver{s.n, ta, tb, []int{}, []int{}, ""}
}

func (s *Solver) Answer() (u, v []int) {
	return s.u, s.v
}

func (s *Solver) score() int64 {
	return max(abs(s.a[0]-Base), abs(s.b[0]-Base))
}

func (s *Solver) Solve() {
	if s.n != N {
		s.greedy()
		return
	}
	// s.info = "bigfoot"
	// s.bigfoot()
	s.info = "walk"
	s.walk()
}

func (s *Solver) goodluck() *Solver {
	var best *Solver
	{
		g := s.Clone()
		g.info = "greedy"
		g.greedy()
		best = g
	}
	for p := 4; p <= 32; p *= 2 {
		t := s.Clone()
		t.info = Sprint("greedy&average(", p, ")")
		if !t.greedy() || len(s.u)+p+1 >= X {
			continue
		}
		if err := t.average(p); err != nil {
			continue
		}
		if t.greedy() {
			t.info += "&greedy"
		}
		if t.score() < best.score() {
			best = t
		}
	}
	for p := 4; p <= 32; p *= 2 {
		for i := 0; i < 100; i++ {
			t := s.Clone()
			t.info = Sprint("avarage(", p, ")")
			t.average(p)
			if t.greedy() {
				t.info += "&greedy"
			}
			if t.score() < best.score() {
				best = t
			}
		}
	}
	for p := 4; p <= 32; p *= 2 {
		for sz := 10; sz+p < X-2; sz++ {
			for i := 0; i < 100; i++ {
				t := s.Clone()
				t.info = Sprint("random(", sz, ")&avarage(", p, ")")
				t.random(sz)
				if err := t.average(p); err != nil {
					continue
				}
				if t.greedy() {
					t.info += "&greedy"
				}
				if t.score() < best.score() {
					best = t
				}
			}
		}
	}
	for sz := 15; sz < X; sz++ {
		for i := 0; i < 2000; i++ {
			t := s.Clone()
			t.info = Sprint("random(", sz, ")")
			t.random(sz)
			if t.greedy() {
				t.info += "&greedy"
			}
			if t.score() < best.score() {
				best = t
			}
		}
	}
	return best
}

func (s *Solver) greedy() bool {
	before := len(s.u)
	for i := len(s.u); i < X; i++ {
		best := s.score()
		zk := -1
		for k := 1; k < s.n; k++ {
			aa := (s.a[0] + s.a[k]) / 2
			bb := (s.b[0] + s.b[k]) / 2
			s := max(abs(aa-Base), abs(bb-Base))
			if s < best {
				best, zk = s, k
			}
		}
		if zk < 0 {
			break
		}
		s.u = append(s.u, 0)
		s.v = append(s.v, zk)
		aa := (s.a[0] + s.a[zk]) / 2
		bb := (s.b[0] + s.b[zk]) / 2
		s.a[0], s.b[0] = aa, bb
		s.a[zk], s.b[zk] = aa, bb
	}
	return before != len(s.u)
}

// size .. 2,4,8,16,32
func (s *Solver) average(size int) error {
	switch size {
	default:
		return Errorf("wrong size %d", size)
	case 2, 4, 8, 16, 32:
		if len(s.u)+size+1 >= X {
			return Errorf("over")
		}
	}
	const Div = 100
	target := (Base / Div) * int64(size)
	idx := rand.Perm(N)
	for i, x := range idx {
		if x == 0 {
			idx[0], idx[i] = idx[i], idx[0]
			break
		}
	}
	var sumA, sumB int64
	for _, i := range idx[:size] {
		sumA += s.a[i] / Div
		sumB += s.b[i] / Div
	}
	best := max(abs(sumA-target), abs(sumB-target))
	for {
		update := 0
		for i := 1; i < size; i++ {
			ii := idx[i]
			sumA -= s.a[ii] / Div
			sumB -= s.b[ii] / Div
			xk := -1
			for k := size; k < N; k++ {
				ik := idx[k]
				sumA += s.a[ik] / Div
				sumB += s.b[ik] / Div
				v := max(abs(sumA-target), abs(sumB-target))
				if v < best {
					best, xk = v, k
				}
				sumA -= s.a[ik] / Div
				sumB -= s.b[ik] / Div
			}
			if xk < 0 {
				sumA += s.a[ii] / Div
				sumB += s.b[ii] / Div
			} else {
				ik := idx[xk]
				sumA += s.a[ik] / Div
				sumB += s.b[ik] / Div
				idx[i], idx[xk] = ik, ii
				update++
			}
		}
		if update == 0 {
			break
		}
	}
	for p := 1; p < size; p *= 2 {
		for i := 0; i < size; i += p * 2 {
			ii, ip := idx[i], idx[i+p]
			s.u = append(s.u, ii)
			s.v = append(s.v, ip)
			aa := (s.a[ii] + s.a[ip]) / 2
			bb := (s.b[ii] + s.b[ip]) / 2
			s.a[ii], s.b[ii] = aa, bb
			s.a[ip], s.b[ip] = aa, bb
		}
	}
	return nil
}

func (s *Solver) random(size int) {
	for ; size > 0; size-- {
		x := rand.Intn(s.n)
		y := (x + rand.Intn(s.n-1) + 1) % s.n
		s.u = append(s.u, x)
		s.v = append(s.v, y)
		aa := (s.a[x] + s.a[y]) / 2
		bb := (s.b[x] + s.b[y]) / 2
		s.a[x], s.b[x] = aa, bb
		s.a[y], s.b[y] = aa, bb
	}
}

func (s *Solver) dp() {
	const (
		Div  = 100
		Vmax = 1e4
	)

	type State struct {
		c                int
		flag, sumA, sumB int64
	}
	score := func(st *State) int64 {
		a := abs(st.sumA - Base/Div*int64(st.c))
		b := abs(st.sumB - Base/Div*int64(st.c))
		return max(a, b)
	}
	index := func(st *State) int {
		return int(score(st) / (Base / Div * int64(st.c) / Vmax))
	}
	add := func(st *State, x int) *State {
		if st == nil {
			return &State{
				c:    1,
				flag: 1 << uint(x),
				sumA: s.a[x] / Div,
				sumB: s.b[x] / Div,
			}
		} else {
			return &State{
				c:    st.c + 1,
				flag: st.flag | (1 << uint(x)),
				sumA: st.sumA + s.a[x]/Div,
				sumB: st.sumB + s.b[x]/Div,
			}
		}
	}
	better := func(st1, st2 *State) *State {
		if st1 == nil {
			return st2
		} else if st2 == nil {
			return st1
		} else if score(st1)/int64(st1.c) < score(st2)/int64(st2.c) {
			return st1
		} else {
			return st2
		}
	}

	dp := make([][]*State, 33)
	for i := range dp {
		dp[i] = make([]*State, Vmax+1)
	}

	first := add(nil, 0)
	dp[1][index(first)] = first

	for x := 1; x < N; x++ {
		for i := 31; i > 0; i-- {
			for _, e := range dp[i] {
				if e == nil {
					continue
				}
				st := add(e, x)
				idx := index(st)
				dp[i+1][idx] = better(dp[i+1][idx], st)
			}
		}
	}

	xx := []*State{}
	for i := 2; i <= 32; i *= 2 {
		for _, e := range dp[i] {
			if e != nil {
				xx = append(xx, e)
			}
		}
	}
	Slice(xx, func(i, j int) bool {
		return score(xx[i])/int64(xx[i].c) < score(xx[j])/int64(xx[j].c)
	})
	best := xx[0]

	pp := make([]int, 0, best.c)
	rr := make([]int, 0, N-best.c)
	for i := 0; i < N; i++ {
		if best.flag&(1<<uint(i)) != 0 {
			pp = append(pp, i)
		} else {
			rr = append(rr, i)
		}
	}

	b2 := 32
	for len(s.u)+b2+best.c+1 >= 45 {
		b2 /= 2
	}

	if b2 >= 2 {
		bestii := -1
		bestiiScore := score(best) / int64(best.c)
		var bestiiState *State

		for ii := 1; ii < len(pp); ii++ {
			w := pp[ii]
			wa := best.sumA - s.a[w]/Div
			wb := best.sumB - s.b[w]/Div
			baseA := min((ABmax-1)/Div, max(ABmin/Div, Base/Div*int64(best.c)-wa))
			baseB := min((ABmax-1)/Div, max(ABmin/Div, Base/Div*int64(best.c)-wb))
			score2 := func(st *State) int64 {
				a := abs(st.sumA - baseA*int64(st.c))
				b := abs(st.sumB - baseB*int64(st.c))
				return max(a, b)
			}
			index2 := func(st *State) int {
				a := abs(st.sumA - baseA*int64(st.c))
				b := abs(st.sumB - baseB*int64(st.c))
				if a > b {
					return int(min(Base/Div, a) / (Base / Div * int64(st.c) / Vmax))
				} else {
					return int(min(Base/Div, b) / (Base / Div * int64(st.c) / Vmax))
				}
			}
			better2 := func(st1, st2 *State) *State {
				if st1 == nil {
					return st2
				} else if st2 == nil {
					return st1
				} else if score2(st1)/int64(st1.c) < score2(st2)/int64(st2.c) {
					return st1
				} else {
					return st2
				}
			}
			dp2 := make([][]*State, b2+1)
			for i := range dp2 {
				dp2[i] = make([]*State, Vmax+1)
			}
			dp2[0][0] = &State{}
			rr = append(rr, w)
			for _, r := range rr {
				for i := b2 - 1; i >= 0; i-- {
					for _, e := range dp2[i] {
						if e == nil {
							continue
						}
						st := add(e, r)
						idx := index2(st)
						dp2[i+1][idx] = better2(dp2[i+1][idx], st)
					}
				}
			}

			yy := []*State{}
			for i := 2; i <= b2; i *= 2 {
				for _, e := range dp2[i] {
					if e != nil {
						yy = append(yy, e)
					}
				}
			}
			Slice(yy, func(i, j int) bool {
				return score2(yy[i])/int64(yy[i].c) < score2(yy[j])/int64(yy[j].c)
			})
			best2 := yy[0]
			wsa := abs(wa + best2.sumA/int64(best2.c) - Base/Div*int64(best.c))
			wsb := abs(wb + best2.sumB/int64(best2.c) - Base/Div*int64(best.c))
			// Printf("expect elem A: %18d, B: %18d\n", baseA, baseB)
			// Printf("before elem A: %18d, B: %18d\n", s.a[w]/Div, s.b[w]/Div)
			// Printf("after  elem A: %18d, B: %18d\n", best2.sumA/int64(best2.c), best2.sumB/int64(best2.c))
			// Printf("before elem diff A: %18d, B: %18d\n", abs(baseA-s.a[w]/Div), abs(baseB-s.b[w]/Div))
			// Printf("after  elem diff A: %18d, B: %18d\n", abs(baseA-best2.sumA/int64(best2.c)), abs(baseB-best2.sumB/int64(best2.c)))
			// Printf("before max(Va,Vb): %19d\n", score(best)/int64(best.c))
			// Printf("after  max(Va,Vb): %19d\n", max(wsa, wsb)/int64(best.c))
			if max(wsa, wsb)/int64(best.c) < bestiiScore {
				bestii = ii
				bestiiScore = max(wsa, wsb) / int64(best.c)
				bestiiState = best2
			}
		}

		if bestii > 0 {
			ppp := []int{}
			for i := 0; i < N; i++ {
				if bestiiState.flag&(1<<uint(i)) != 0 {
					ppp = append(ppp, i)
				}
			}
			pp[bestii] = ppp[0]
			for p := 1; p < bestiiState.c; p *= 2 {
				for i := 0; i < bestiiState.c; i += p * 2 {
					p1 := ppp[i]
					p2 := ppp[i+p]
					s.u = append(s.u, p1)
					s.v = append(s.v, p2)
					aa := (s.a[p1] + s.a[p2]) / 2
					bb := (s.b[p1] + s.b[p2]) / 2
					s.a[p1], s.b[p1] = aa, bb
					s.a[p2], s.b[p2] = aa, bb
				}
			}
		}
	}

	for p := 1; p < best.c; p *= 2 {
		for i := 0; i < best.c; i += p * 2 {
			p1 := pp[i]
			p2 := pp[i+p]
			s.u = append(s.u, p1)
			s.v = append(s.v, p2)
			aa := (s.a[p1] + s.a[p2]) / 2
			bb := (s.b[p1] + s.b[p2]) / 2
			s.a[p1], s.b[p1] = aa, bb
			s.a[p2], s.b[p2] = aa, bb
		}
	}
}

func (s *Solver) tree() {
	trees := [][]int{}
	limit := X - len(s.u) - 1

	var take func(depth, inner, leaf int, nodes []int)
	take = func(depth, inner, leaf int, nodes []int) {
		if depth == 0 {
			nodes[0] = 1
			take(depth+1, 0, 1, nodes)
			nodes[0] = 0
			return
		}
		if leaf > N {
			return
		}
		if inner <= limit {
			t := make([]int, depth)
			copy(t, nodes[:depth])
			trees = append(trees, t)
		}
		if depth == len(nodes) {
			return
		}
		nodes[depth] = 0
		for i := 0; i < nodes[depth-1]; i++ {
			nodes[depth] += 2
			inner--
			leaf += 2
			take(depth+1, inner, leaf, nodes)
		}
		nodes[depth] = 0
	}

	const MaxDepth = 10

	take(0, 0, 0, make([]int, MaxDepth))

	// Println("Tree = ", len(trees))

	bestScore := max(abs(s.a[0]-Base), abs(s.b[0]-Base))
	bestCs := make([]int64, N)
	bestPs := make([]int, N)
	cs := make([]int64, N)
	ps := rand.Perm(N)
	for _, tree := range trees {
		var ncnt int
		tcs := cs[:0]
		for i, c := range tree {
			if i+1 < len(tree) {
				c -= tree[i+1] / 2
			}
			ncnt += c
			for ; c > 0; c-- {
				tcs = append(tcs, 1<<uint(i))
			}
		}
		// Println(tree)
		// Println(nc, cs[:ncnt])
		for i, p := range ps {
			if p == 0 && i >= ncnt {
				ps[0], ps[i] = 0, ps[0]
				break
			}
		}
		var va, vb int64
		for i, t := range tcs {
			p := ps[i]
			va += s.a[p] / t
			vb += s.b[p] / t
		}
		score := max(abs(va-Base), abs(vb-Base))
		for li := 0; li < ncnt; li++ {
			lp, lt := ps[li], tcs[li]
			tempVa, tempVb, tempScore := va, vb, score
			tempRi := -1
			for ri := li + 1; ri < N; ri++ {
				if lp == 0 && ri >= ncnt {
					break
				}
				rp := ps[ri]
				tva := va - s.a[lp]/lt + s.a[rp]/lt
				tvb := vb - s.b[lp]/lt + s.b[rp]/lt
				if ri < ncnt {
					rt := tcs[ri]
					tva += s.a[lp]/rt - s.a[rp]/rt
					tvb += s.b[lp]/rt - s.b[rp]/rt
				}
				temp := max(abs(tva-Base), abs(tvb-Base))
				if temp < tempScore {
					tempVa, tempVb, tempScore = tva, tvb, temp
					tempRi = ri
				}
			}
			if tempRi >= 0 {
				va, vb, score = tempVa, tempVb, tempScore
				ps[li], ps[tempRi] = ps[tempRi], ps[li]
			}
		}

		if score < bestScore {
			bestScore = score
			bestCs = bestCs[:ncnt]
			copy(bestCs, tcs)
			bestPs = bestPs[:ncnt]
			copy(bestPs, ps)
		}
	}
	{
		ps, cs := bestPs[:], bestCs[:]
		for i := 0; i < N; i++ {
			found := false
			for _, p := range ps {
				if i == p {
					found = true
					break
				}
			}
			if !found {
				ps = append(ps, i)
			}
		}
		var va, vb int64
		for i, c := range cs {
			p := ps[i]
			va += s.a[p] / c
			vb += s.b[p] / c
		}
		score := bestScore
		for {
			updated := false
			for li := 0; li < len(cs); li++ {
				lp, lt := ps[li], cs[li]
				tempRi, tempVa, tempVb, tempScore := -1, va, vb, score
				for ri := li + 1; ri < N; ri++ {
					if lp == 0 && ri >= len(cs) {
						break
					}
					rp := ps[ri]
					tva := va - s.a[lp]/lt + s.a[rp]/lt
					tvb := vb - s.b[lp]/lt + s.b[rp]/lt
					if ri < len(cs) {
						rt := cs[ri]
						tva += s.a[lp]/rt - s.a[rp]/rt
						tvb += s.b[lp]/rt - s.b[rp]/rt
					}
					temp := max(abs(tva-Base), abs(tvb-Base))
					if temp < tempScore {
						tempRi, tempVa, tempVb, tempScore = ri, tva, tvb, temp
					}
				}
				if tempRi >= 0 {
					va, vb, score = tempVa, tempVb, tempScore
					ps[li], ps[tempRi] = ps[tempRi], ps[li]
					updated = true
				}
			}
			if !updated {
				bestScore = score
				break
			}
		}
	}
	// Println(bestScore, len(Sprint(bestScore)))
	// Println(bestPs)
	// Println(bestCs)
	for {
		var maxC int64 // = slices.Max(bestCs)
		for _, c := range bestCs {
			if c > maxC {
				maxC = c
			}
		}
		if maxC < 2 {
			break
		}
		another := -1
		for i, c := range bestCs {
			if c != maxC {
				continue
			}
			if another < 0 {
				another = i
			} else {
				p1, p2 := bestPs[i], bestPs[another]
				s.u = append(s.u, p1)
				s.v = append(s.v, p2)
				aa := (s.a[p1] + s.a[p2]) / 2
				bb := (s.b[p1] + s.b[p2]) / 2
				s.a[p1], s.b[p1] = aa, bb
				s.a[p2], s.b[p2] = aa, bb
				if p1 < p2 {
					bestCs[i] /= 2
					bestCs[another] = 0
				} else {
					bestCs[i] = 0
					bestCs[another] /= 2
				}
				another = -1
			}
		}
	}
}

func (s *Solver) walk() {
	ps := rand.Perm(N)
	for i, p := range ps {
		if p == 0 {
			ps[0], ps[i] = ps[i], ps[0]
			break
		}
	}

	const C = N / 2

	cs := make([]uint, 0, N)
	for i := 1; i <= C; i++ {
		cs = append(cs, uint(i))
	}
	cs = append(cs, C)
	cs = cs[:N]

	leaf := C + 1

	var va, vb int64
	for i, c := range cs {
		if c != 0 {
			p := ps[i]
			va += s.a[p] >> c
			vb += s.b[p] >> c
		}
	}
	score := max(abs(va-Base), abs(vb-Base))

	hs := make([]int, N, N)
	gs := make([]int, 0, N)
	for i, c := range cs {
		if c != 0 {
			hs[i] = len(gs)
			gs = append(gs, i)
		} else {
			hs[i] = -1
		}
	}

	// Println("-- START --")
	// Println("inner:", inner, ", leaf:", leaf)
	// Println("hs:", hs)
	// Println("gs:", gs)
	// Println("ps:", ps)
	// Println("cs:", cs)
	// Printf("Va: %18d, Vb: %18d, Score: %18d, Len: %2d\n", va, vb, score, len(Sprint(score)))
	// Println("----------")

	hasBest := false
	bestScore := score
	bestPs := make([]int, N, N)
	copy(bestPs, ps)
	bestCs := make([]uint, N, N)

	const WW = 500000 * 30

	const Changed = 50
	const NoChanged = 1
	const NoChangesLimit = 1500
	const KickSize = 100
	const Kick = 1
	nochanges, kicks := 0, 0

	for ww := 0; ww < WW; ww++ {
		if nochanges > NoChangesLimit {
			// Printf("[%07d] Kick\n", ww)
			nochanges = 0
			kicks = KickSize
			if !hasBest || score < bestScore {
				bestScore = score
				copy(bestPs, ps)
				copy(bestCs, cs)
				hasBest = true
			}
		}
		lgi := rand.Intn(len(gs))
		li := gs[lgi]
		//ri := (li + rand.Intn(N-1) + 1) % N
		ri := (li + ww%(N-1) + 1) % N
		lp, rp := ps[li], ps[ri]
		lc, rc := cs[li], cs[ri]
		switch {
		case rc > 0 && lc == rc && lp == 0 && rp != 0:
			// Merge
			{
				tva1 := va - s.a[lp]>>lc - s.a[rp]>>rc + s.a[lp]>>(lc-1)
				tvb1 := vb - s.b[lp]>>lc - s.b[rp]>>rc + s.b[lp]>>(lc-1)
				tscore1 := max(abs(tva1-Base), abs(tvb1-Base))
				if tscore1 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
					// Printf("[%07d] Merge: %2d %2d -> %d (%d -> %d)\n", ww, lp, rp, lp, lc, lc-1)
					cs[li], cs[ri] = lc-1, 0
					va, vb, score = tva1, tvb1, tscore1
					rgi := hs[ri]
					gs[rgi] = gs[len(gs)-1]
					hs[gs[rgi]] = rgi
					gs = gs[:len(gs)-1]
					hs[ri] = -1
					leaf--
					if kicks > 0 {
						kicks -= Kick
					} else {
						nochanges -= Changed
					}
				} else {
					nochanges += NoChanged
				}
			}
		case rc > 0 && lc == rc && lp != 0 && rp == 0:
			// Merge
			{
				tva2 := va - s.a[lp]>>lc - s.a[rp]>>rc + s.a[rp]>>(rc-1)
				tvb2 := vb - s.b[lp]>>lc - s.b[rp]>>rc + s.b[rp]>>(rc-1)
				tscore2 := max(abs(tva2-Base), abs(tvb2-Base))
				if tscore2 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
					// Printf("[%07d] Merge: %2d %2d -> %2d (%d -> %d)\n", ww, lp, rp, rp, rc, rc-1)
					cs[li], cs[ri] = 0, rc-1
					va, vb, score = tva2, tvb2, tscore2
					gs[lgi] = gs[len(gs)-1]
					hs[gs[lgi]] = lgi
					gs = gs[:len(gs)-1]
					hs[li] = -1
					leaf--
					if kicks > 0 {
						kicks -= Kick
					} else {
						nochanges -= Changed
					}
				} else {
					nochanges += NoChanged
				}
			}
		case rc > 0 && lc == rc && lp != 0 && rp != 0:
			// Merge
			{
				tva1 := va - s.a[lp]>>lc - s.a[rp]>>rc + s.a[lp]>>(lc-1)
				tvb1 := vb - s.b[lp]>>lc - s.b[rp]>>rc + s.b[lp]>>(lc-1)
				tscore1 := max(abs(tva1-Base), abs(tvb1-Base))
				tva2 := va - s.a[lp]>>lc - s.a[rp]>>rc + s.a[rp]>>(rc-1)
				tvb2 := vb - s.b[lp]>>lc - s.b[rp]>>rc + s.b[rp]>>(rc-1)
				tscore2 := max(abs(tva2-Base), abs(tvb2-Base))
				if tscore1 <= score && tscore1 <= tscore2 || (kicks > 0 && rand.Intn(KickSize) < kicks) {
					// Printf("[%07d] Merge: %2d %2d -> %2d (%d -> %d)\n", ww, lp, rp, lp, lc, lc-1)
					cs[li], cs[ri] = lc-1, 0
					va, vb, score = tva1, tvb1, tscore1
					rgi := hs[ri]
					gs[rgi] = gs[len(gs)-1]
					hs[gs[rgi]] = rgi
					gs = gs[:len(gs)-1]
					hs[ri] = -1
					leaf--
					if kicks > 0 {
						kicks -= Kick
					} else {
						nochanges -= Changed
					}
				} else if tscore2 <= score && tscore2 <= tscore1 || (kicks > 0 && rand.Intn(KickSize) < kicks) {
					// Printf("[%07d] Merge: %2d %2d -> %2d (%d -> %d)\n", ww, lp, rp, rp, rc, rc-1)
					cs[li], cs[ri] = 0, rc-1
					va, vb, score = tva2, tvb2, tscore2
					gs[lgi] = gs[len(gs)-1]
					hs[gs[lgi]] = lgi
					gs = gs[:len(gs)-1]
					hs[li] = -1
					leaf--
					if kicks > 0 {
						kicks -= Kick
					} else {
						nochanges -= Changed
					}
				} else {
					nochanges += NoChanged
				}
			}
		case rc > 0 && lc != rc:
			// Swap
			{
				tva1 := va - s.a[lp]>>lc - s.a[rp]>>rc + s.a[lp]>>rc + s.a[rp]>>lc
				tvb1 := vb - s.b[lp]>>lc - s.b[rp]>>rc + s.b[lp]>>rc + s.b[rp]>>lc
				tscore1 := max(abs(tva1-Base), abs(tvb1-Base))
				if tscore1 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
					// Printf("[%07d] Swap: %2d <-> %2d (%d <-> %d)\n", ww, lp, rp, lc, rc)
					va, vb, score = tva1, tvb1, tscore1
					ps[li], ps[ri] = ps[ri], ps[li]
					if kicks > 0 {
						kicks -= Kick
					} else {
						nochanges -= Changed
					}
				} else {
					nochanges += NoChanged
				}
			}
		case rc == 0 && lp == 0:
			// Divide
			if leaf+1 <= N {
				tva2 := va - s.a[lp]>>lc + s.a[lp]>>(lc+1) + s.a[rp]>>(lc+1)
				tvb2 := vb - s.b[lp]>>lc + s.b[lp]>>(lc+1) + s.b[rp]>>(lc+1)
				tscore2 := max(abs(tva2-Base), abs(tvb2-Base))
				if tscore2 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
					// Printf("[%07d] Divide: %2d -> %2d (%d -> %d)\n", ww, lp, rp, lc, lc+1)
					cs[li], cs[ri] = lc+1, lc+1
					va, vb, score = tva2, tvb2, tscore2
					hs[ri] = len(gs)
					gs = append(gs, ri)
					leaf++
					if kicks > 0 {
						kicks -= Kick
					} else {
						nochanges -= Changed
					}
				} else {
					nochanges += NoChanged
				}
			}
		case rc == 0 && lp != 0:
			// Swap OR Divide
			{
				tva1 := va - s.a[lp]>>lc + s.a[rp]>>lc
				tvb1 := vb - s.b[lp]>>lc + s.b[rp]>>lc
				tscore1 := max(abs(tva1-Base), abs(tvb1-Base))
				if leaf+1 <= N {
					tva2 := va - s.a[lp]>>lc + s.a[lp]>>(lc+1) + s.a[rp]>>(lc+1)
					tvb2 := vb - s.b[lp]>>lc + s.b[lp]>>(lc+1) + s.b[rp]>>(lc+1)
					tscore2 := max(abs(tva2-Base), abs(tvb2-Base))
					if tscore1 <= score && tscore1 <= tscore2 || (kicks > 0 && rand.Intn(KickSize) < kicks) {
						// Printf("[%07d] Swap: %2d <-> %2d (%d <-> %d)\n", ww, lp, rp, lc, rc)
						va, vb, score = tva1, tvb1, tscore1
						ps[li], ps[ri] = ps[ri], ps[li]
						if kicks > 0 {
							kicks -= Kick
						} else {
							nochanges -= Changed
						}
					} else if tscore2 <= score && tscore2 <= tscore1 || (kicks > 0 && rand.Intn(KickSize) < kicks) {
						// Printf("[%07d] Divide: %2d -> %2d (%d -> %d)\n", ww, lp, rp, lc, lc+1)
						cs[li], cs[ri] = lc+1, lc+1
						va, vb, score = tva2, tvb2, tscore2
						hs[ri] = len(gs)
						gs = append(gs, ri)
						leaf++
						if kicks > 0 {
							kicks -= Kick
						} else {
							nochanges -= Changed
						}
					} else {
						nochanges += NoChanged
					}
				} else if tscore1 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
					// Printf("[%07d] Swap: %2d <-> %2d (%d <-> %d)\n", ww, lp, rp, lc, rc)
					va, vb, score = tva1, tvb1, tscore1
					ps[li], ps[ri] = ps[ri], ps[li]
					if kicks > 0 {
						kicks -= Kick
					} else {
						nochanges -= Changed
					}
				} else {
					nochanges += NoChanged
				}
			}
		}
	}

	// Println("-- END --")
	// Println("inner:", inner, ", leaf:", leaf)
	// Println("hs:", hs)
	// Println("gs:", gs)
	// Println("ps:", ps)
	// Println("cs:", cs)
	// Printf("Va: %18d, Vb: %18d, Score: %18d, Len: %2d\n", va, vb, score, len(Sprint(score)))
	// Println("---------")

	if hasBest && bestScore < score {
		// Printf("HasBest: %d -> %d\n", score, bestScore)
		score = bestScore
		ps = bestPs
		cs = bestCs
	}

	for {
		var maxC uint
		for _, c := range cs {
			if c > maxC {
				maxC = c
			}
		}
		if maxC < 1 {
			break
		}
		another := -1
		for i, c := range cs {
			if c != maxC {
				continue
			}
			if another < 0 {
				another = i
			} else {
				p1, p2 := ps[i], ps[another]
				s.u = append(s.u, p1)
				s.v = append(s.v, p2)
				aa := (s.a[p1] + s.a[p2]) / 2
				bb := (s.b[p1] + s.b[p2]) / 2
				s.a[p1], s.b[p1] = aa, bb
				s.a[p2], s.b[p2] = aa, bb
				if p1 < p2 {
					cs[i]--
					cs[another] = 0
				} else {
					cs[i] = 0
					cs[another]--
				}
				another = -1
			}
		}
	}
}

func maxInt(x, y *big.Int) *big.Int {
	if x.Cmp(y) < 0 {
		return y
	}
	return x
}

var pf *big.Float = new(big.Float)

func prob(diff *big.Int, tm float64) float64 {
	f, _ := pf.SetInt(diff).Float64()
	f = math.Log2(f)
	p := math.Exp(-(1 - 1/f) / tm)
	return p
}

func (s *Solver) bigfoot() {
	ps := rand.Perm(N)
	for i, p := range ps {
		if p == 0 {
			ps[0], ps[i] = ps[i], ps[0]
			break
		}
	}

	const C = N / 2

	cs := make([]uint, 0, N)
	for i := 1; i <= C; i++ {
		cs = append(cs, uint(i))
	}
	cs = append(cs, C)
	cs = cs[:N]

	leaf := C + 1

	tmp1, tmp2 := new(big.Int), new(big.Int)
	tmp3, tmp4 := new(big.Int), new(big.Int)
	tmp5, tmp6 := new(big.Int), new(big.Int)
	tmp7, tmp8 := new(big.Int), new(big.Int)

	const Shift = 64

	A := make([]*big.Int, N, N)
	B := make([]*big.Int, N, N)
	for i := range A {
		A[i] = new(big.Int).Lsh(tmp1.SetInt64(s.a[i]), Shift)
		B[i] = new(big.Int).Lsh(tmp1.SetInt64(s.b[i]), Shift)
	}

	var baseInt *big.Int = new(big.Int).Lsh(tmp1.SetInt64(Base), Shift)

	va, vb := new(big.Int), new(big.Int)
	for i, c := range cs {
		if c != 0 {
			p := ps[i]
			va.Add(va, tmp1.Rsh(A[p], c))
			vb.Add(vb, tmp1.Rsh(B[p], c))
		}
	}
	score := new(big.Int).Set(maxInt(tmp1.Abs(tmp1.Sub(va, baseInt)), tmp2.Abs(tmp2.Sub(vb, baseInt))))

	hs := make([]int, N, N)
	gs := make([]int, 0, N)
	for i, c := range cs {
		if c != 0 {
			hs[i] = len(gs)
			gs = append(gs, i)
		} else {
			hs[i] = -1
		}
	}

	// Println("-- START --")
	// Println("inner:", inner, ", leaf:", leaf)
	// Println("hs:", hs)
	// Println("gs:", gs)
	// Println("ps:", ps)
	// Println("cs:", cs)
	// Printf("Va: %18d, Vb: %18d, Score: %18d, Len: %2d\n", va, vb, score, len(Sprint(score)))
	// Println("----------")

	bestScore := new(big.Int).Set(score)
	bestPs := make([]int, N, N)
	copy(bestPs, ps)
	bestCs := make([]uint, N, N)
	copy(bestCs, cs)

	const WW = 1000000

	diff := new(big.Int)

	for ww := 0; ww < WW; ww++ {
		tm := math.Pow(0.05, 1-float64(ww+1)/WW)
		lgi := rand.Intn(len(gs))
		li := gs[lgi]
		ri := (li + ww%(N-1) + 1) % N
		lp, rp := ps[li], ps[ri]
		lc, rc := cs[li], cs[ri]
		switch {
		case rc > 0 && lc == rc && lp == 0 && rp != 0:
			// Merge
			{
				tva1, tvb1 := tmp1, tmp2
				tva1.Sub(va, tmp3.Rsh(A[lp], lc)).Sub(tva1, tmp3.Rsh(A[rp], rc)).Add(tva1, tmp3.Rsh(A[lp], lc-1))
				tvb1.Sub(vb, tmp3.Rsh(B[lp], lc)).Sub(tvb1, tmp3.Rsh(B[rp], rc)).Add(tvb1, tmp3.Rsh(B[lp], lc-1))
				tscore1 := maxInt(tmp3.Abs(tmp3.Sub(tva1, baseInt)), tmp4.Abs(tmp4.Sub(tvb1, baseInt)))
				if diff.Sub(tscore1, score).Sign() <= 0 || (rand.Float64() < prob(diff, tm)) {
					// Printf("[%07d] Merge: %2d %2d -> %d (%d -> %d)\n", ww, lp, rp, lp, lc, lc-1)
					cs[li], cs[ri] = lc-1, 0
					va.Set(tva1)
					vb.Set(tvb1)
					score.Set(tscore1)
					rgi := hs[ri]
					gs[rgi] = gs[len(gs)-1]
					hs[gs[rgi]] = rgi
					gs = gs[:len(gs)-1]
					hs[ri] = -1
					leaf--
					if score.Cmp(bestScore) < 0 {
						bestScore.Set(score)
						copy(bestPs, ps)
						copy(bestCs, cs)
					}
				}
			}
		case rc > 0 && lc == rc && lp != 0 && rp == 0:
			// Merge
			{
				tva2, tvb2 := tmp5, tmp6
				tva2.Sub(va, tmp7.Rsh(A[lp], lc)).Sub(tva2, tmp7.Rsh(A[rp], rc)).Add(tva2, tmp7.Rsh(A[rp], rc-1))
				tvb2.Sub(vb, tmp7.Rsh(B[lp], lc)).Sub(tvb2, tmp7.Rsh(B[rp], rc)).Add(tvb2, tmp7.Rsh(B[rp], rc-1))
				tscore2 := maxInt(tmp7.Abs(tmp7.Sub(tva2, baseInt)), tmp8.Abs(tmp8.Sub(tvb2, baseInt)))
				if diff.Sub(tscore2, score).Sign() <= 0 || (rand.Float64() < prob(diff, tm)) {
					// Printf("[%07d] Merge: %2d %2d -> %2d (%d -> %d)\n", ww, lp, rp, rp, rc, rc-1)
					cs[li], cs[ri] = 0, rc-1
					va.Set(tva2)
					vb.Set(tvb2)
					score.Set(tscore2)
					gs[lgi] = gs[len(gs)-1]
					hs[gs[lgi]] = lgi
					gs = gs[:len(gs)-1]
					hs[li] = -1
					leaf--
					if score.Cmp(bestScore) < 0 {
						bestScore.Set(score)
						copy(bestPs, ps)
						copy(bestCs, cs)
					}
				}
			}
		case rc > 0 && lc == rc && lp != 0 && rp != 0:
			// Merge
			{
				tva1, tvb1 := tmp1, tmp2
				tva1.Sub(va, tmp3.Rsh(A[lp], lc)).Sub(tva1, tmp3.Rsh(A[rp], rc)).Add(tva1, tmp3.Rsh(A[lp], lc-1))
				tvb1.Sub(vb, tmp3.Rsh(B[lp], lc)).Sub(tvb1, tmp3.Rsh(B[rp], rc)).Add(tvb1, tmp3.Rsh(B[lp], lc-1))
				tscore1 := maxInt(tmp3.Abs(tmp3.Sub(tva1, baseInt)), tmp4.Abs(tmp4.Sub(tvb1, baseInt)))
				tva2, tvb2 := tmp5, tmp6
				tva2.Sub(va, tmp7.Rsh(A[lp], lc)).Sub(tva2, tmp7.Rsh(A[rp], rc)).Add(tva2, tmp7.Rsh(A[rp], rc-1))
				tvb2.Sub(vb, tmp7.Rsh(B[lp], lc)).Sub(tvb2, tmp7.Rsh(B[rp], rc)).Add(tvb2, tmp7.Rsh(B[rp], rc-1))
				tscore2 := maxInt(tmp7.Abs(tmp7.Sub(tva2, baseInt)), tmp8.Abs(tmp8.Sub(tvb2, baseInt)))
				if tscore1.Cmp(tscore2) <= 0 && (diff.Sub(tscore1, score).Sign() <= 0 || rand.Float64() < prob(diff, tm)) {
					// Printf("[%07d] Merge: %2d %2d -> %2d (%d -> %d)\n", ww, lp, rp, lp, lc, lc-1)
					cs[li], cs[ri] = lc-1, 0
					va.Set(tva1)
					vb.Set(tvb1)
					score.Set(tscore1)
					rgi := hs[ri]
					gs[rgi] = gs[len(gs)-1]
					hs[gs[rgi]] = rgi
					gs = gs[:len(gs)-1]
					hs[ri] = -1
					leaf--
					if score.Cmp(bestScore) < 0 {
						bestScore.Set(score)
						copy(bestPs, ps)
						copy(bestCs, cs)
					}
				} else if tscore2.Cmp(tscore1) <= 0 && (diff.Sub(tscore2, score).Sign() <= 0 || rand.Float64() < prob(diff, tm)) {
					// Printf("[%07d] Merge: %2d %2d -> %2d (%d -> %d)\n", ww, lp, rp, rp, rc, rc-1)
					cs[li], cs[ri] = 0, rc-1
					va.Set(tva2)
					vb.Set(tvb2)
					score.Set(tscore2)
					gs[lgi] = gs[len(gs)-1]
					hs[gs[lgi]] = lgi
					gs = gs[:len(gs)-1]
					hs[li] = -1
					leaf--
					if score.Cmp(bestScore) < 0 {
						bestScore.Set(score)
						copy(bestPs, ps)
						copy(bestCs, cs)
					}
				}
			}
		case rc > 0 && lc != rc:
			// Swap
			{
				tva1, tvb1 := tmp1, tmp2
				tva1.Sub(va, tmp3.Rsh(A[lp], lc)).Sub(tva1, tmp3.Rsh(A[rp], rc)).Add(tva1, tmp3.Rsh(A[lp], rc)).Add(tva1, tmp3.Rsh(A[rp], lc))
				tvb1.Sub(vb, tmp3.Rsh(B[lp], lc)).Sub(tvb1, tmp3.Rsh(B[rp], rc)).Add(tvb1, tmp3.Rsh(B[lp], rc)).Add(tvb1, tmp3.Rsh(B[rp], lc))
				tscore1 := maxInt(tmp3.Abs(tmp3.Sub(tva1, baseInt)), tmp4.Abs(tmp4.Sub(tvb1, baseInt)))
				if diff.Sub(tscore1, score).Sign() <= 0 || (rand.Float64() < prob(diff, tm)) {
					// Printf("[%07d] Swap: %2d <-> %2d (%d <-> %d)\n", ww, lp, rp, lc, rc)
					va.Set(tva1)
					vb.Set(tvb1)
					score.Set(tscore1)
					ps[li], ps[ri] = ps[ri], ps[li]
					if score.Cmp(bestScore) < 0 {
						bestScore.Set(score)
						copy(bestPs, ps)
						copy(bestCs, cs)
					}
				}
			}
		case rc == 0 && lp == 0:
			// Divide
			if leaf+1 <= N {
				tva2, tvb2 := tmp5, tmp6
				tva2.Sub(va, tmp7.Rsh(A[lp], lc)).Add(tva2, tmp7.Rsh(A[lp], lc+1)).Add(tva2, tmp7.Rsh(A[rp], lc+1))
				tvb2.Sub(vb, tmp7.Rsh(B[lp], lc)).Add(tvb2, tmp7.Rsh(B[lp], lc+1)).Add(tvb2, tmp7.Rsh(B[rp], lc+1))
				tscore2 := maxInt(tmp7.Abs(tmp7.Sub(tva2, baseInt)), tmp8.Abs(tmp8.Sub(tvb2, baseInt)))
				if diff.Sub(tscore2, score).Sign() <= 0 || (rand.Float64() < prob(diff, tm)) {
					// Printf("[%07d] Divide: %2d -> %2d (%d -> %d)\n", ww, lp, rp, lc, lc+1)
					cs[li], cs[ri] = lc+1, lc+1
					va.Set(tva2)
					vb.Set(tvb2)
					score.Set(tscore2)
					hs[ri] = len(gs)
					gs = append(gs, ri)
					leaf++
					if score.Cmp(bestScore) < 0 {
						bestScore.Set(score)
						copy(bestPs, ps)
						copy(bestCs, cs)
					}
				}
			}
		case rc == 0 && lp != 0:
			// Swap OR Divide
			{
				tva1, tvb1 := tmp1, tmp2
				tva1.Sub(va, tmp3.Rsh(A[lp], lc)).Add(tva1, tmp3.Rsh(A[rp], lc))
				tvb1.Sub(vb, tmp3.Rsh(B[lp], lc)).Add(tvb1, tmp3.Rsh(B[rp], lc))
				tscore1 := maxInt(tmp3.Abs(tmp3.Sub(tva1, baseInt)), tmp4.Abs(tmp4.Sub(tvb1, baseInt)))
				if leaf+1 <= N {
					tva2, tvb2 := tmp5, tmp6
					tva2.Sub(va, tmp7.Rsh(A[lp], lc)).Add(tva2, tmp7.Rsh(A[lp], lc+1)).Add(tva2, tmp7.Rsh(A[rp], lc+1))
					tvb2.Sub(vb, tmp7.Rsh(B[lp], lc)).Add(tvb2, tmp7.Rsh(B[lp], lc+1)).Add(tvb2, tmp7.Rsh(B[rp], lc+1))
					tscore2 := maxInt(tmp7.Abs(tmp7.Sub(tva2, baseInt)), tmp8.Abs(tmp8.Sub(tvb2, baseInt)))
					if tscore1.Cmp(tscore2) <= 0 && (diff.Sub(tscore1, score).Sign() <= 0 || rand.Float64() < prob(diff, tm)) {
						// Printf("[%07d] Swap: %2d <-> %2d (%d <-> %d)\n", ww, lp, rp, lc, rc)
						va.Set(tva1)
						vb.Set(tvb1)
						score.Set(tscore1)
						ps[li], ps[ri] = ps[ri], ps[li]
						if score.Cmp(bestScore) < 0 {
							bestScore.Set(score)
							copy(bestPs, ps)
							copy(bestCs, cs)
						}
					} else if tscore2.Cmp(tscore1) <= 0 && (diff.Sub(tscore2, score).Sign() <= 0 || rand.Float64() < prob(diff, tm)) {
						// Printf("[%07d] Divide: %2d -> %2d (%d -> %d)\n", ww, lp, rp, lc, lc+1)
						cs[li], cs[ri] = lc+1, lc+1
						va.Set(tva2)
						vb.Set(tvb2)
						score.Set(tscore2)
						hs[ri] = len(gs)
						gs = append(gs, ri)
						leaf++
						if score.Cmp(bestScore) < 0 {
							bestScore.Set(score)
							copy(bestPs, ps)
							copy(bestCs, cs)
						}
					}
				} else if diff.Sub(tscore1, score).Sign() <= 0 || (rand.Float64() < prob(diff, tm)) {
					// Printf("[%07d] Swap: %2d <-> %2d (%d <-> %d)\n", ww, lp, rp, lc, rc)
					va.Set(tva1)
					vb.Set(tvb1)
					score.Set(tscore1)
					ps[li], ps[ri] = ps[ri], ps[li]
					if score.Cmp(bestScore) < 0 {
						bestScore.Set(score)
						copy(bestPs, ps)
						copy(bestCs, cs)
					}
				}
			}
		}
	}

	// Println("-- END --")
	// Println("inner:", inner, ", leaf:", leaf)
	// Println("hs:", hs)
	// Println("gs:", gs)
	// Println("ps:", ps)
	// Println("cs:", cs)
	// Printf("Va: %18d, Vb: %18d, Score: %18d, Len: %2d\n", va, vb, score, len(Sprint(score)))
	// Println("---------")

	if bestScore.Cmp(score) < 0 {
		// Printf("HasBest: %d -> %d\n", score, bestScore)
		// score = bestScore
		ps = bestPs
		cs = bestCs
	}

	for {
		var maxC uint
		for _, c := range cs {
			if c > maxC {
				maxC = c
			}
		}
		if maxC < 1 {
			break
		}
		another := -1
		for i, c := range cs {
			if c != maxC {
				continue
			}
			if another < 0 {
				another = i
			} else {
				p1, p2 := ps[i], ps[another]
				s.u = append(s.u, p1)
				s.v = append(s.v, p2)
				aa := (s.a[p1] + s.a[p2]) / 2
				bb := (s.b[p1] + s.b[p2]) / 2
				s.a[p1], s.b[p1] = aa, bb
				s.a[p2], s.b[p2] = aa, bb
				if p1 < p2 {
					cs[i]--
					cs[another] = 0
				} else {
					cs[i] = 0
					cs[another]--
				}
				another = -1
			}
		}
	}
}