package main

// Pair ...
type Pair struct {
	_1 int
	_2 int
}

// Equals ...
func (p1 Pair) Equals(p2 Pair) bool {
	return p1._1 == p2._1 && p1._2 == p2._2
}

// PairStack ...
type PairStack []Pair

// Len ...
func (ps PairStack) Len() int { return len(ps) }
func (ps PairStack) Less(i, j int) bool {
	if ps[i]._1 == ps[j]._1 {
		return ps[i]._2 < ps[j]._2
	}
	return ps[i]._1 < ps[j]._1
}
func (ps PairStack) Swap(i, j int) { ps[i], ps[j] = ps[j], ps[i] }

// Top ...
func (ps PairStack) Top() Pair {
	return ps[len(ps)-1]
}

// Empty ...
func (ps PairStack) Empty() bool {
	return len(ps) == 0
}

// Push ...
func (ps *PairStack) Push(p interface{}) {
	*ps = append(*ps, p.(Pair))
}

// Pop ...
func (ps *PairStack) Pop() interface{} {
	x := (*ps)[len(*ps)-1]
	*ps = (*ps)[:len(*ps)-1]
	return x
}