IIST is thinking of acquiring some land nearby to build its new state of the art labs. The land it has chosen incidentaly has some abandoned college buildings which IIST wants to use. The administration decide the value of the building based on the amount of work that has to be done to get it in shape (lower amount of work, higher value). The security experts want to tear down some of the buildings and use the bricks to build a boundary wall. 

The director has chosen you to write a program which determines the buildings which needs to be demolished to maximise the value while fulfilling the above criterion. 

Input Format: 

The first line contains the number of test cases, T.

The next T cases contains information about hypothetical plots.

Each test case starts with a single integer n, 2 ≤ n ≤ 15, the number of abandoned buildings in the plot. The buildings are identified by consecutive integers 1 to n. Each of the subsequent lines contains 4 integers x_i , y_i , v_i , l_i that describe a single building. (x_i, y_i) is the position of the building in the plane, v_i is its value, and l_i is the length of boundary wall that can be built using the bricks from the building. v_i and l_i are between 0 and 10,000.

Output Format:

For each test case, compute a subset of the buildings such that, using the bricks from the buildings from that subset, the remaining buildings can be enclosed in a single boundary. Find the subset with a minimum value. If more than one such minimum-value subset exists, choose one with the smallest number of buildings. 

Display, as shown below, the identity of each building to be demolished, and the length of the excess boundary (accurate to two fractional digits).

Sample Input:  

2

6

0 0 8 3

1 4 3 2

2 1 7 1

4 1 2 3

3 5 4 6

2 3 9 8

3

3 0 10 2

5 5 20 25

7 -3 30 32

Sample Output: 

2 4 5

3.16

2

15.00

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import math\r\nfrom itertools import permutations as p\r\ndef diff(li1, li2): \r\n    li_dif = [i for i in li1 if i not in li2]\r\n    return li_dif \r\ndef segments(b):\r\n        """A sequence of (x,y) numeric coordinates pairs """\r\n        poly = [(i[0],i[1]) for i in b]\r\n        return zip(poly, poly[1:] + [poly[0]])\r\ndef perimeter(poly):\r\n    """A sequence of (x,y) numeric coordinates pairs """\r\n    return abs(sum(math.hypot(x0-x1,y0-y1) for ((x0, y0), (x1, y1)) in segments(poly)))\r\ndef av(b):\r\n    return sum([i[3] for i in b])\r\ndef val(b):\r\n    return sum([i[2] for i in b])\r\nfor _ in range(int(input())):\r\n    b = []\r\n    for _ in range(int(input())):\r\n        b.append(list(map(int,input().split())))\r\n    perm = []\r\n    for i in range(1,len(b)):\r\n        for e in p(b,i):\r\n            perm.append(e)\r\n    perm.sort(key=lambda x:val(x))\r\n    yes = []\r\n    for i in perm:\r\n        if av(i)>=perimeter(diff(b,i)):\r\n            good = val(i)\r\n            yes.append(i)\r\n            break\r\n    #yes.sort(key = lambda x: len(x))\r\n    print(" ".join([str(b.index(i)+1) for i in yes[0]]))\r\n    x = round(av(yes[0])-perimeter(diff(b,yes[0])),2)\r\n    print(f\'{x:.2f}\')\r\n\r\n\r\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 124705