func (t *tree) SeekLast() (e *enumerator, err error) {
	q := t.last
	if q == nil {
		return nil, io.EOF
	}
	return &enumerator{nil, true, q.c - 1, q.d[q.c-1].k, q, t, t.ver}, nil
}
SeekLast returns an enumerator positioned on the last KV pair in the tree,
if any. For an empty tree, err == io.EOF is returned and e will be nil.
package ql
import (
	"io"
)
const (
	kx = 128  
	kd = 64   
)
type (
	cmp func(a, b []interface{}) int
	d struct {  
		c int
		d [2*kd + 1]de
		n *d
		p *d
	}
	de struct {  
		k []interface{}
		v []interface{}
	}
	enumerator struct {
		err error
		hit bool
		i   int
		k   []interface{}
		q   *d
		t   *tree
		ver int64
	}
	tree struct {
		c     int
		cmp   cmp
		first *d
		last  *d
		r     interface{}
		ver   int64
	}
	xe struct {  
		ch  interface{}
		sep *d
	}
	x struct {  
		c int
		x [2*kx + 2]xe
	}
)
var (  
	zd  d
	zde de
	zx  x
	zxe xe
)
func clr(q interface{}) {
	switch z := q.(type) {
	case *x:
		for i := 0; i <= z.c; i++ {  
			clr(z.x[i].ch)
		}
		*z = zx  
	case *d:
		*z = zd  
	}
}
func newX(ch0 interface{}) *x {
	r := &x{}
	r.x[0].ch = ch0
	return r
}
func (q *x) extract(i int) {
	q.c--
	if i < q.c {
		copy(q.x[i:], q.x[i+1:q.c+1])
		q.x[q.c].ch = q.x[q.c+1].ch
		q.x[q.c].sep = nil  
		q.x[q.c+1] = zxe    
	}
}
func (q *x) insert(i int, d *d, ch interface{}) *x {
	c := q.c
	if i < c {
		q.x[c+1].ch = q.x[c].ch
		copy(q.x[i+2:], q.x[i+1:c])
		q.x[i+1].sep = q.x[i].sep
	}
	c++
	q.c = c
	q.x[i].sep = d
	q.x[i+1].ch = ch
	return q
}
func (q *x) siblings(i int) (l, r *d) {
	if i >= 0 {
		if i > 0 {
			l = q.x[i-1].ch.(*d)
		}
		if i < q.c {
			r = q.x[i+1].ch.(*d)
		}
	}
	return
}
func (l *d) mvL(r *d, c int) {
	copy(l.d[l.c:], r.d[:c])
	copy(r.d[:], r.d[c:r.c])
	l.c += c
	r.c -= c
}
func (l *d) mvR(r *d, c int) {
	copy(r.d[c:], r.d[:r.c])
	copy(r.d[:c], l.d[l.c-c:])
	r.c += c
	l.c -= c
}
func treeNew(cmp cmp) *tree {
	return &tree{cmp: cmp}
}
func (t *tree) Clear() {
	if t.r == nil {
		return
	}
	clr(t.r)
	t.c, t.first, t.last, t.r = 0, nil, nil, nil
	t.ver++
}
func (t *tree) cat(p *x, q, r *d, pi int) {
	t.ver++
	q.mvL(r, r.c)
	if r.n != nil {
		r.n.p = q
	} else {
		t.last = q
	}
	q.n = r.n
	if p.c > 1 {
		p.extract(pi)
		p.x[pi].ch = q
	} else {
		t.r = q
	}
}
func (t *tree) catX(p, q, r *x, pi int) {
	t.ver++
	q.x[q.c].sep = p.x[pi].sep
	copy(q.x[q.c+1:], r.x[:r.c])
	q.c += r.c + 1
	q.x[q.c].ch = r.x[r.c].ch
	if p.c > 1 {
		p.c--
		pc := p.c
		if pi < pc {
			p.x[pi].sep = p.x[pi+1].sep
			copy(p.x[pi+1:], p.x[pi+2:pc+1])
			p.x[pc].ch = p.x[pc+1].ch
			p.x[pc].sep = nil   
			p.x[pc+1].ch = nil  
		}
		return
	}
	t.r = q
}
func (t *tree) Delete(k []interface{}) (ok bool) {
	pi := -1
	var p *x
	q := t.r
	if q == nil {
		return
	}
	for {
		var i int
		i, ok = t.find(q, k)
		if ok {
			switch z := q.(type) {
			case *x:
				dp := z.x[i].sep
				switch {
				case dp.c > kd:
					t.extract(dp, 0)
				default:
					if z.c < kx && q != t.r {
						t.underflowX(p, &z, pi, &i)
					}
					pi = i + 1
					p = z
					q = z.x[pi].ch
					ok = false
					continue
				}
			case *d:
				t.extract(z, i)
				if z.c >= kd {
					return
				}
				if q != t.r {
					t.underflow(p, z, pi)
				} else if t.c == 0 {
					t.Clear()
				}
			}
			return
		}
		switch z := q.(type) {
		case *x:
			if z.c < kx && q != t.r {
				t.underflowX(p, &z, pi, &i)
			}
			pi = i
			p = z
			q = z.x[i].ch
		case *d:
			return
		}
	}
}
func (t *tree) extract(q *d, i int) {  
	t.ver++
	q.c--
	if i < q.c {
		copy(q.d[i:], q.d[i+1:q.c+1])
	}
	q.d[q.c] = zde  
	t.c--
}
func (t *tree) find(q interface{}, k []interface{}) (i int, ok bool) {
	var mk []interface{}
	l := 0
	switch z := q.(type) {
	case *x:
		h := z.c - 1
		for l <= h {
			m := (l + h) >> 1
			mk = z.x[m].sep.d[0].k
			switch cmp := t.cmp(k, mk); {
			case cmp > 0:
				l = m + 1
			case cmp == 0:
				return m, true
			default:
				h = m - 1
			}
		}
	case *d:
		h := z.c - 1
		for l <= h {
			m := (l + h) >> 1
			mk = z.d[m].k
			switch cmp := t.cmp(k, mk); {
			case cmp > 0:
				l = m + 1
			case cmp == 0:
				return m, true
			default:
				h = m - 1
			}
		}
	}
	return l, false
}
func (t *tree) First() (k []interface{}, v []interface{}) {
	if q := t.first; q != nil {
		q := &q.d[0]
		k, v = q.k, q.v
	}
	return
}
func (t *tree) Get(k []interface{}) (v []interface{}, ok bool) {
	q := t.r
	if q == nil {
		return
	}
	for {
		var i int
		if i, ok = t.find(q, k); ok {
			switch z := q.(type) {
			case *x:
				return z.x[i].sep.d[0].v, true
			case *d:
				return z.d[i].v, true
			}
		}
		switch z := q.(type) {
		case *x:
			q = z.x[i].ch
		default:
			return
		}
	}
}
func (t *tree) insert(q *d, i int, k []interface{}, v []interface{}) *d {
	t.ver++
	c := q.c
	if i < c {
		copy(q.d[i+1:], q.d[i:c])
	}
	c++
	q.c = c
	q.d[i].k, q.d[i].v = k, v
	t.c++
	return q
}
func (t *tree) Last() (k []interface{}, v []interface{}) {
	if q := t.last; q != nil {
		q := &q.d[q.c-1]
		k, v = q.k, q.v
	}
	return
}
func (t *tree) Len() int {
	return t.c
}
func (t *tree) overflow(p *x, q *d, pi, i int, k []interface{}, v []interface{}) {
	t.ver++
	l, r := p.siblings(pi)
	if l != nil && l.c < 2*kd && i > 0 {
		l.mvL(q, 1)
		t.insert(q, i-1, k, v)
		return
	}
	if r != nil && r.c < 2*kd {
		if i < 2*kd {
			q.mvR(r, 1)
			t.insert(q, i, k, v)
		} else {
			t.insert(r, 0, k, v)
		}
		return
	}
	t.split(p, q, pi, i, k, v)
}
func (t *tree) Seek(k []interface{}) (e *enumerator, ok bool) {
	q := t.r
	if q == nil {
		e = &enumerator{nil, false, 0, k, nil, t, t.ver}
		return
	}
	for {
		var i int
		if i, ok = t.find(q, k); ok {
			switch z := q.(type) {
			case *x:
				e = &enumerator{nil, ok, 0, k, z.x[i].sep, t, t.ver}
				return
			case *d:
				e = &enumerator{nil, ok, i, k, z, t, t.ver}
				return
			}
		}
		switch z := q.(type) {
		case *x:
			q = z.x[i].ch
		case *d:
			e = &enumerator{nil, ok, i, k, z, t, t.ver}
			return
		}
	}
}
func (t *tree) SeekFirst() (e *enumerator, err error) {
	q := t.first
	if q == nil {
		return nil, io.EOF
	}
	return &enumerator{nil, true, 0, q.d[0].k, q, t, t.ver}, nil
}