667_E. Chain Reaction
Group of Berland scientists, with whom you have a close business relationship, makes a research in the area of peaceful nuclear energy. In particular, they found that a group of four nanobots, placed on a surface of a plate, can run a powerful chain reaction under certain conditions. 

To be precise, researchers introduced a rectangular Cartesian coordinate system on a flat plate and selected four distinct points with integer coordinates where bots will be placed initially. Next each bot will be assigned with one of the four directions (up, down, left or right) parallel to the coordinate axes. After that, each bot is shifted by an integer distance (which may be different for different bots) along its direction. The chain reaction starts, if the bots are in the corners of a square with positive area with sides parallel to the coordinate axes. Each corner of the square must contain one nanobot. This reaction will be stronger, if bots spend less time to move. We can assume that bots move with unit speed. In other words, the lesser is the maximum length traveled by bot, the stronger is reaction.

Scientists have prepared a set of plates and selected starting position for the bots for each plate. Now they ask you to assign the direction for each bot to move after landing such that the maximum length traveled by bot is as small as possible.

Input

The first line contains an integer number t (1 ≤ t ≤ 50) — the number of plates.

t descriptions of plates follow. A description of each plate consists of four lines. Each line consists of a pair of integers numbers xi, yi ( - 108 ≤ xi, yi ≤ 108) — coordinates of the next bot. All bots are in different locations.

Note, though, the problem can include several records in one test, you can hack other people's submissions only with the test of one plate, i.e. parameter t in a hack test should be equal to 1.

Output

Print answers for all plates separately. First goes a single integer number in a separate line. If scientists have made an unfortunate mistake and nanobots are not able to form the desired square, print -1. Otherwise, print the minimum possible length of the longest bot's path.

If a solution exists, in the next four lines print two integer numbers — positions of each bot after moving. Print bots' positions in the order they are specified in the input data.

If there are multiple solution, you can print any of them.

Examples

Input

2
1 1
1 -1
-1 1
-1 -1
1 1
2 2
4 4
6 6


Output

0
1 1
1 -1
-1 1
-1 -1
-1
```python
import sys
sys.stderr = sys.stdout

from collections import namedtuple

Bot = namedtuple('Bot', ('x', 'y', 'i'))


def yxi(bot):
    return bot.y, bot.x, bot.i


def reaction1(B, V):
    Bv = sorted(B[i] for i in range(4) if V[i])
    Bh = sorted((B[i] for i in range(4) if not V[i]), key=yxi)
    S = [None] * 4

    if len(Bv) == 0:
        if not (Bh[0].y == Bh[1].y < Bh[2].y == Bh[3].y):
            return None, None
        y0 = Bh[0].y
        y1 = Bh[2].y
        d = y1 - y0
        X = [Bh[0].x, Bh[1].x - d, Bh[2].x, Bh[3].x - d]
        Xmin = min(X)
        Xmax = max(X)
        x0 = (Xmin + Xmax) // 2
        l = Xmax - x0
        S[Bh[0].i] = x0, y0
        S[Bh[1].i] = x0 + d, y0
        S[Bh[2].i] = x0, y1
        S[Bh[3].i] = x0 + d, y1
        return l, S
    elif len(Bv) == 1:
        if Bh[0].y == Bh[1].y < Bh[2].y:
            y0 = Bh[0].y
            y1 = Bh[2].y
            x0 = Bv[0].x
            d = y1 - y0
            l0 = abs(Bv[0].y - y1)
            l1 = max(abs(x0 - Bh[0].x), abs(x0 + d - Bh[1].x),
                     l0, abs(x0 + d - Bh[2].x))
            l2 = max(abs(x0 - d - Bh[0].x), abs(x0 - Bh[1].x),
                     abs(x0 - d - Bh[2].x), l0)
            if l1 <= l2:
                l = l1
                S[Bh[0].i] = x0, y0
                S[Bh[1].i] = x0 + d, y0
                S[Bv[0].i] = x0, y1
                S[Bh[2].i] = x0 + d, y1
            else:
                l = l2
                S[Bh[0].i] = x0 - d, y0
                S[Bh[1].i] = x0, y0
                S[Bh[2].i] = x0 - d, y1
                S[Bv[0].i] = x0, y1
            return l, S
        elif Bh[0].y < Bh[1].y == Bh[2].y:
            y0 = Bh[0].y
            y1 = Bh[2].y
            x0 = Bv[0].x
            d = y1 - y0
            l0 = abs(Bv[0].y - y0)
            l1 = max(l0, abs(x0 + d - Bh[0].x),
                     abs(x0 - Bh[1].x), abs(x0 + d - Bh[2].x))
            l2 = max(abs(x0 - d - Bh[0].x), l0,
                     abs(x0 - d - Bh[1].x), abs(x0 - Bh[2].x))
            if l1 <= l2:
                l = l1
                S[Bv[0].i] = x0, y0
                S[Bh[0].i] = x0 + d, y0
                S[Bh[1].i] = x0, y1
                S[Bh[2].i] = x0 + d, y1
            else:
                l = l2
                S[Bh[0].i] = x0 - d, y0
                S[Bv[0].i] = x0, y0
                S[Bh[1].i] = x0 - d, y1
                S[Bh[2].i] = x0, y1
            return l, S
        else:
            return None, None
    elif len(Bv) == 2:
        if Bv[0].x < Bv[1].x and Bh[0].y < Bh[1].y:
            x0 = Bv[0].x
            x1 = Bv[1].x
            y0 = Bh[0].y
            y1 = Bh[1].y
            if x1 - x0 != y1 - y0:
                return None, None
            l1 = max(abs(Bh[0].x - x0), abs(Bv[0].y - y1),
                     abs(Bh[1].x - x1), abs(Bv[1].y - y0))
            l2 = max(abs(Bh[0].x - x1), abs(Bv[0].y - y0),
                     abs(Bh[1].x - x0), abs(Bv[1].y - y1))
            S = [None] * 4
            if l1 <= l2:
                l = l1
                S[Bh[0].i] = x0, y0
                S[Bh[1].i] = x1, y1
                S[Bv[0].i] = x0, y1
                S[Bv[1].i] = x1, y0
            else:
                l = l2
                S[Bh[0].i] = x1, y0
                S[Bh[1].i] = x0, y1
                S[Bv[0].i] = x0, y0
                S[Bv[1].i] = x1, y1
            return l, S
        elif Bv[0].x != Bv[1].x:
            x0 = Bv[0].x
            x1 = Bv[1].x
            y0 = Bh[0].y
            d = x1 - x0
            lh = max(abs(Bh[0].x - x0), abs(Bh[1].x - x1))
            l1 = max(lh, abs(y0 - d - Bv[0].y), abs(y0 - d - Bv[1].y))
            l2 = max(lh, abs(y0 + d - Bv[0].y), abs(y0 + d - Bv[1].y))
            S = [None] * 4
            if l1 <= l2:
                l = l1
                S[Bh[0].i] = x0, y0
                S[Bh[1].i] = x1, y0
                S[Bv[0].i] = x0, y0 - d
                S[Bv[1].i] = x1, y0 - d
            else:
                l = l2
                S[Bh[0].i] = x0, y0
                S[Bh[1].i] = x1, y0
                S[Bv[0].i] = x0, y0 + d
                S[Bv[1].i] = x1, y0 + d
            return l, S
        elif Bh[0].y != Bh[1].y:
            y0 = Bh[0].y
            y1 = Bh[1].y
            x0 = Bv[0].x
            d = y1 - y0
            lh = max(abs(Bv[0].y - y0), abs(Bv[1].y - y1))
            l1 = max(lh, abs(x0 - d - Bh[0].x), abs(x0 - d - Bh[1].x))
            l2 = max(lh, abs(x0 + d - Bh[0].x), abs(x0 + d - Bh[1].x))
            S = [None] * 4
            if l1 <= l2:
                l = l1
                S[Bv[0].i] = x0, y0
                S[Bv[1].i] = x0, y1
                S[Bh[0].i] = x0 - d, y0
                S[Bh[1].i] = x0 - d, y1
            else:
                l = l2
                S[Bv[0].i] = x0, y0
                S[Bv[1].i] = x0, y1
                S[Bh[0].i] = x0 + d, y0
                S[Bh[1].i] = x0 + d, y1
            return l, S
        else:
            return None, None
    elif len(Bv) == 3:
        if Bv[0].x == Bv[1].x < Bv[2].x:
            x0 = Bv[0].x
            x1 = Bv[2].x
            y0 = Bh[0].y
            d = x1 - x0
            l0 = abs(Bh[0].x - x1)
            l1 = max(abs(y0 - Bv[0].y), abs(y0 + d - Bv[1].y),
                     l0, abs(y0 + d - Bv[2].y))
            l2 = max(abs(y0 - d - Bv[0].y), abs(y0 - Bv[1].y),
                     abs(y0 - d - Bv[2].y), l0)
            if l1 <= l2:
                l = l1
                S[Bv[0].i] = x0, y0
                S[Bv[1].i] = x0, y0 + d
                S[Bh[0].i] = x1, y0
                S[Bv[2].i] = x1, y0 + d
            else:
                l = l2
                S[Bv[0].i] = x0, y0 - d
                S[Bv[1].i] = x0, y0
                S[Bv[2].i] = x1, y0 - d
                S[Bh[0].i] = x1, y0
            return l, S
        elif Bv[0].x < Bv[1].x == Bv[2].x:
            x0 = Bv[0].x
            x1 = Bv[2].x
            y0 = Bh[0].y
            d = x1 - x0
            l0 = abs(Bh[0].x - x0)
            l1 = max(l0, abs(y0 + d - Bv[0].y),
                     abs(y0 - Bv[1].y), abs(y0 + d - Bv[2].y))
            l2 = max(abs(y0 - d - Bv[0].y), l0,
                     abs(y0 - d - Bv[1].y), abs(y0 - Bv[2].y))
            if l1 <= l2:
                l = l1
                S[Bh[0].i] = x0, y0
                S[Bv[0].i] = x0, y0 + d
                S[Bv[1].i] = x1, y0
                S[Bv[2].i] = x1, y0 + d
            else:
                l = l2
                S[Bv[0].i] = x0, y0 - d
                S[Bh[0].i] = x0, y0
                S[Bv[1].i] = x1, y0 - d
                S[Bv[2].i] = x1, y0
            return l, S
        else:
            return None, None
    elif len(Bv) == 4:
        if not (Bv[0].x == Bv[1].x < Bv[2].x == Bv[3].x):
            return None, None
        x0 = Bv[0].x
        x1 = Bv[2].x
        d = x1 - x0
        Y = [Bv[0].y, Bv[1].y - d, Bv[2].y, Bv[3].y - d]
        Ymin = min(Y)
        Ymax = max(Y)
        y0 = (Ymin + Ymax) // 2
        l = Ymax - y0
        S[Bv[0].i] = x0, y0
        S[Bv[1].i] = x0, y0 + d
        S[Bv[2].i] = x1, y0
        S[Bv[3].i] = x1, y0 + d
        return l, S


def reaction(B):
    l = None
    S = None
    for v0 in (True, False):
        for v1 in (True, False):
            for v2 in (True, False):
                for v3 in (True, False):
                    l1, S1 = reaction1(B, (v0, v1, v2, v3))
                    if l1 is not None and (l is None or l1 < l):
                        l = l1
                        S = S1
    return l, S


def readb(i):
    x, y = readinti()
    return Bot(x, y, i)

def main():
    t = readint()
    L = []
    for _ in range(t):
        B = [readb(i) for i in range(4)]
        l, S = reaction(B)
        if l is None:
            L.append('-1')
        else:
            L.append(str(l))
            L.extend(f'{b1} {b2}' for b1, b2 in S)
    print('\n'.join(L))

##########

def readint():
    return int(input())


def readinti():
   return map(int, input().split())


def readintt():
   return tuple(readinti())


def readintl():
   return list(readinti())


def readinttl(k):
    return [readintt() for _ in range(k)]


def readintll(k):
    return [readintl() for _ in range(k)]


def log(*args, **kwargs):
    print(*args, **kwargs, file=sys.__stderr__)


if __name__ == '__main__':
    main()

```