#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define fi first
#define se second
using namespace std;
typedef pair<int,int>PII; 
#define endl "\n"
typedef unsigned long long ull;
typedef long long ll;
const int M=2010;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
const long double eps=1e-9;
using point_t = long double; 
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
ll exgcd(ll a, ll b, ll& x, ll& y) { ll d = a; if (b != 0) d = exgcd(b, a % b, y, x), y -= (a / b) * x; else x = 1, y = 0; return d; }
ll gcd(ll a, ll b) { if (a < b) swap(a, b); if (b != 0) while (b ^= a ^= b ^= a %= b); return a; }
ll qmi(ll a, ll b, const ll p) { a %= p; if (a == 0) return 0ll; ll r = 1; for (; b > 0; a = a * a % p, b >>= 1) if (b & 1) r = r * a % p; return r; }
ll fmul(ll a, ll b, ll mod) { return ((a * b - (ll)((ll)((long double)a / mod * b + 1e-3) * mod)) % mod + mod) % mod; }
string YN(bool flag) { return (flag ? "Yes" : "No"); }
long double x[3],y[3],px,py;
bool equal(long double x,long double y,long double q,long double w){
	if(fabs(x-q)<eps&&fabs(y-w)<eps) return 1;
	return 0;
}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mset(x, a) memset(x, a, sizeof (x))
#define rep(i, l, r) for(LL i = l; i <= (r); ++ i)
#define per(i, r, l) for(LL i = r; i >= (l); -- i)
#define reps(i, l, r, d) for(LL i = l; i <= (r); i += d)
#define pers(i, r, l, d) for(LL i = r; i >= (l); i -= d)

template<class T> bool ckmax(T& a, T b) { return a < b ? (a = b, 1) : 0; }
template<class T> bool ckmin(T& a, T b) { return a > b ? (a = b, 1) : 0; }
template<class T> vector<T> & operator + (vector<T> & a, vector<T> & b) { a.insert(a.end(), b.begin(), b.end()); return a; }
template<class T> vector<T> & operator += (vector<T> & a, vector<T> & b) { return a = a + b; }

using point_t = long double;  //全局数据类型，可修改为 long long 等

const long double PI = acosl(-1);

// 点与向量
template<typename T> struct point
{
	T x, y;

	bool operator == (const point & a) const { return abs(x - a.x) <= eps && abs(y - a.y) <= eps; }
	bool operator < (const point & a) const { if(abs(x - a.x) > eps) return x < a.x - eps; return y < a.y - eps; }
	bool operator > (const point & a) const { return !((*this) < a || (*this) == a); }
	point operator + (const point & a) const { return {x + a.x, y + a.y}; }
	point operator - (const point & a) const { return {x - a.x, y - a.y}; }
	point operator - () const { return {-x, -y}; }
	point operator * (const T k) const { return {x * k, y * k}; }
	point operator / (const T k) const { return {x / k, y / k}; }
	T operator * (const point & a) const { return x * a.x + y * a.y; }
	T operator ^ (const point & a) const { return x * a.y - y * a.x; }
	int toleft (const point & a) const { const auto t = (*this) ^ a; return (t > eps) - (t < -eps); } // a 向量在该向量的左半平面 / 上 / 右半平面
	T len2 () const { return x * x + y * y; }
	T dis2 (const point & a) const { return ((*this) - a).len2(); }

	// 涉及浮点数
	long double len () const { return sqrtl(len2()); }
	long double dis (const point & a) const { return sqrtl(dis2(a)); }
	long double ang (const point & a) const { return acosl(max(-1.0l, min(1.0l, ((*this) * a) / (len() * a.len())))); }
	long double toang (const point & a) const { const auto t = ang(a); return (*this ^ a) > 0 ? t : 2 * PI - t; }
	point rot () const { return {-y, x}; }
	point rot (const long double rad) const { return {x * cosl(rad) - y * sinl(rad), x * sinl(rad) + y * cosl(rad)}; }
	point rot (const long double cosr, const long double sinr) const { return {x * cosr - y * sinr, x * sinr + y * cosr}; }
};

using Point = point<point_t>;


// 极角排序
struct argcmp
{
	bool operator () (const Point & a, const Point & b) const
	{
		const auto quad = [] (const Point & a)
		{
			if(a.y < -eps) return 1;
			if(a.y > eps) return 4;
			if(a.x < -eps) return 5;
			if(a.x > eps) return 3;
			return 2;
		};
		const int qa = quad(a), qb = quad(b);
		if(qa != qb) return qa < qb;
		const auto t = a ^ b;
		// if(abs(t) <= eps) return a * a < b * b - eps;  // 不同长度的向量需要分开
		return t > eps;
	}
};

// 直线
template<typename T> struct line
{
	point<T> p, v;
	
	bool operator == (const line & a) const { return v.toleft(a.v) == 0 && v.toleft(p - a.p) == 0; }
	int toleft (const point<T> & a) const { return v.toleft(a - p); } // 点 a 在该直线的左半平面 / 上 / 右半平面

	// 涉及浮点数
	long double dis (const point<T> & a) const { return abs(v ^ (a - p)) / v.len(); }
	point<T> inter (const line & a) const { return p + v * ( (a.v ^ (p - a.p)) / (v ^ a.v) ); }
	long double inter_dis (const line & a) const { return v.len() * (a.v ^ (p - a.p)) / (v ^ a.v); }
  	point<T> proj (const point<T> & a) const { return p + v * ( (v * (a - p)) / (v * v) ); }
	long double proj_dis (const point<T> & a) const { return v * (a - p) / v.len(); }
};

using Line = line<point_t>;


// 线段
template<typename T> struct segment
{
	point<T> a, b;
    
	bool operator < (const segment & s) const { return make_pair(a, b) < make_pair(s.a, s.b) ; }

    // 判定性函数建议在整数域使用

    // 判断点是否在线段上
    // -1 点在线段端点 | 0 点不在线段上 | 1 点严格在线段上
	int is_on (const point<T> & p) const
	{
		if(p == a || p == b) return -1;
		return (p - a).toleft(p - b) == 0 && (p - a) * (p - b) < -eps;
	}

    // 判断线段直线是否相交
    // -1 直线经过线段端点 | 0 线段和直线不相交 | 1 线段和直线严格相交
	int is_inter (const line<T> & l) const
	{
		if(l.toleft(a) == 0 || l.toleft(b) == 0) return -1;
		return l.toleft(a) != l.toleft(b);
	}

	// 判断两线段是否相交
    // -1 在某一线段端点处相交 | 0 两线段不相交 | 1 两线段严格相交
	int is_inter (const segment & s) const
	{
		if(is_on(s.a) || is_on(s.b) || s.is_on(a) || s.is_on(b)) return -1;
		const line<T> l = {a, b - a}, ls = {s.a, s.b - s.a};
		return l.toleft(s.a) * l.toleft(s.b) == -1 && ls.toleft(a) * ls.toleft(b) == -1;
	}

	// 点到线段距离
	long double dis (const point<T> & p) const
	{
		if((b - a) * (p - a) < -eps || (a - b) * (p - b) < -eps) return min(p.dis(a), p.dis(b));
		const line<T> l = {a, b - a};
		return l.dis(p);
	}

	// 两线段间距离
	long double dis (const segment & s) const
	{
		if(is_inter(s)) return 0;
		return min({dis(s.a), dis(s.b), s.dis(a), s.dis(b)});
	}

    // 判断一点在线段的哪一侧
    int relation(Point & C)
    {
        // 1 left -1 right 0 in
        int c = (b - a) ^ (C - a);
        if(c < 0) return 1;
        else if(c > 0) return -1;
        return 0;
    }
};

using Segment = segment<point_t>;


// 射线
template<typename T> struct ray
{
	point<T> p, v;

	// 判定性函数建议在整数域使用

    // 判断点是否在射线上
    // -1 点在射线端点 | 0 点不在射线上 | 1 点严格在射线上
	int is_on (const point<T> & a) const
	{
		if(p == a) return -1;
		return v.toleft(a - p) == 0 && v * (a - p) > eps;
	}

	// 判断射线直线是否相交
    // -1 直线经过射线端点 | 0 射线和直线不相交 | 1 射线和直线严格相交
	int is_inter (const line<T> & l) const
	{
		if(l.toleft(p) == 0) return -1;
		return l.v.toleft(p - l.p) * l.v.toleft(v) == -1;
	}

	// 判断射线线段是否相交
    // -1 在线段端点或射线端点处相交 | 0 射线和线段不相交 | 1 射线和线段严格相交
	int is_inter (const segment<T> & s) const
	{
		if(is_on(s.a) || is_on(s.b) || s.is_on(p)) return -1;
		const point<T> sv = s.b - s.a;
		return v.toleft(s.a - p) * v.toleft(s.b - p) == -1 && sv.toleft(p - s.a) * sv.toleft(v) == -1;
	}

	// 判断两射线是否相交
    // -1 在某一射线端点处相交 | 0 两射线不相交 | 1 两射线严格相交
	int is_inter (const ray & r) const
	{
		if(is_on(r.p) || r.is_on(p)) return -1;
		const line<T> l = {p, v}, lr = {r.p, r.v};
		return is_inter(lr) && r.is_inter(l);
	}

	// 点到射线距离
	long double dis (const point<T> & a) const
	{
		if(v * (a - p) < -eps) return a.dis(p);
		const line<T> l = {p, v};
		return l.dis(a);
	}

	// 线段到射线距离
	long double dis (const segment<T> & s) const
	{
		if(is_inter(s)) return 0;
		return min({dis(s.a), dis(s.b), s.dis(p)});
	}

	// 射线到射线距离
	long double dis (const ray & r) const
	{
		if(is_inter(r)) return 0;
		return min(dis(r.p), r.dis(p));
	}

	// 射线从点 p 沿着方向 v 到达 直线/线段/射线 的距离
	// 1. 直线
	long double dis_from_p_in_v (const line<T> & l) const
	{
		const int t = is_inter(l);
		if(t <= 0) return t ? 0 : -1;
		return line<T>{p, v}.inter_dis(l);
	}

	// 2. 线段
	long double dis_from_p_in_v (const segment<T> & s) const
	{
		const int t = is_inter(s);
		if(t == 0) return -1;
		if(t == -1) {
			if(s.is_on(p)) return 0;
			else if(is_on(s.a) && is_on(s.b)) return min(p.dis(s.a), p.dis(s.b));
		}
		return line<T>{p, v}.inter_dis(line<T>{s.a, s.b - s.a});
	}

	// 3. 射线
	long double dis_from_p_in_v (const ray & r) const
	{
		const int t = is_inter(r);
		if(t == 0) return -1;
		if(t == -1) return r.is_on(p) ? 0 : p.dis(r.p);
		return line<T>{p, v}.inter_dis(line<T>{r.p, r.v});
	}
};

using Ray = ray<point_t>;


// 多边形
template<typename T> struct polygon
{
	vector<point<T>> p;  // 以逆时针顺序存储

	size_t nxt (const int i) const { return i == p.size() - 1 ? 0 : i + 1; }
	size_t pre (const int i) const { return i == 0 ? p.size() - 1 : i - 1; }

    // 回转数
    // 返回值第一项表示点是否在多边形边上
    // 对于狭义多边形，回转数为 0 表示点在多边形外，否则点在多边形内
	pair<bool, int> winding (const point<T> & a) const
	{
		int cnt = 0;
		for(size_t i = 0; i < p.size(); i ++ )
		{
			const point<T> u = p[i], v = p[nxt(i)];
			if(abs((a - u) ^ (a - v)) <= eps && (a - u) * (a - v) <= eps) return {true, 0};
			if(abs(u.y - v.y) <= eps) continue;
			const line<T> uv = {u, v - u};
			if(u.y < v.y - eps && uv.toleft(a) <= 0) continue;
			if(u.y > v.y + eps && uv.toleft(a) >= 0) continue;
			if(u.y < a.y - eps && v.y >= a.y - eps) cnt ++ ;
			if(u.y >= a.y - eps && v.y < a.y - eps) cnt -- ;
		}
		return {false, cnt};
	}

	// 多边形面积的两倍
   	// 可用于判断点的存储顺序是顺时针或逆时针
	T area () const
	{
		T sum = 0;
		for(size_t i = 0; i < p.size(); i ++ ) sum += p[i] ^ p[nxt(i)];
		return sum;
	}

	long double circ() const
	{
		long double sum = 0;
		for(size_t i = 0; i < p.size(); i ++ ) sum += p[i].dis(p[nxt(i)]);
		return sum;
	}
};

using Polygon = polygon<point_t>;


// 凸多边形
template<typename T> struct convex : polygon<T>
{
	// 多边形的邻点叉积前缀和，用于计算凸多边形的凸壳的面积
	// 注意：如果是顺时针储存，sum 储存的面积为负数
	vector<T> sum;

	void get_sum ()
	{
		const auto & p = this -> p;
		vector<T> a(p.size());
		for(size_t i = 0; i < p.size(); i ++ ) a[i] = p[this -> pre(i)] ^ p[i];
		sum.resize(p.size());
		partial_sum(a.begin(), a.end(), sum.begin());
	}

	T query_sum (const size_t l, const size_t r) const
	{
		const auto & p = this -> p;
		if(l <= r) return sum[r] - sum[l] + (p[r] ^ p[l]);
		return sum.back() - sum[l] + sum[r] + (p[r] ^ p[l]);
	}
	T query_sum () const { return sum.back(); }


	// 闵可夫斯基和
	// 复杂度 O(n)
	convex operator + (const convex & c) const
	{
		const auto & p = this -> p;
		if(!p.size()) return c; if(!c.p.size()) return *this;
		vector<segment<T>> e1(p.size()), e2(c.p.size()), edge(p.size() + c.p.size());
		vector<point<T>> res; res.reserve(p.size() + c.p.size());
		const auto cmp = [] (const segment<T> & u, const segment<T> & v) {
			return argcmp() (u.b - u.a, v.b - v.a);
		};
		for(size_t i = 0; i < p.size(); i ++ ) e1[i] = {p[i], p[this -> nxt(i)]};
		for(size_t i = 0; i < c.p.size(); i ++ ) e2[i] = {c.p[i], c.p[c.nxt(i)]};
		rotate(e1.begin(), min_element(e1.begin(), e1.end(), cmp), e1.end());
		rotate(e2.begin(), min_element(e2.begin(), e2.end(), cmp), e2.end());
		merge(e1.begin(), e1.end(), e2.begin(), e2.end(), edge.begin(), cmp);
		const auto check = [] (const vector<point<T>> & res, const point<T> & u)
		{
			const auto v = *prev(res.end(), 2), w = res.back();
			return (w - v).toleft(u - w) == 0 && (w - v) * (u - w) >= -eps;
		};
		auto u = e1[0].a + e2[0].a;
		for(const auto & v : edge)
		{
			while(res.size() > 1 && check(res, u)) res.pop_back();
			res.push_back(u);
			u = u + v.b - v.a;
		}
		if(res.size() > 1 && check(res, res[0])) res.pop_back();
		return {res};
	}

	// 旋转卡壳
    // func 为更新答案的函数，可以根据题目调整位置
    template<typename F> void rotcaliper (const F & func) const
    {
        const auto & p = this -> p;
        const auto area = [] (const point<T> & u, const point<T> & v, const point<T> & w) { return (w - v) ^ (u - v); };
        for(size_t i = 0, j = 1; i < p.size(); i ++ )
        {
            const auto nxti = this -> nxt(i);
            while(area(p[this -> nxt(j)], p[i], p[nxti]) >= area(p[j], p[i], p[nxti]))
            {
                j = this -> nxt(j);
            }
            func(p[j], p[i], p[nxti]);
        }
    }

	// 凸多边形的直径的平方
    T diameter2 () const
    {
        const auto & p = this -> p;
        if(p.size() <= 2) return 0;
        T ans = 1e18;
        const auto func = [&] (const point<T> & u, const point<T> & v, const point<T> & w) {
            ans = min(ans, Line{v, w - v}.dis(u));
        };
        rotcaliper(func);
        return ans;
    }
    
    // 判断点是否在凸多边形内
    // 复杂度 O(logn)
    // -1 点在多边形边上 | 0 点在多边形外 | 1 点在多边形内
    int is_in (const point<T> & a) const
    {
        const auto & p = this -> p;
        if(p.size() == 1) return a == p[0] ? -1 : 0;
        if(p.size() == 2) return segment<T>{p[0], p[1]}.is_on(a) ? -1 : 0;
        if(a == p[0]) return -1;
        if((p[1] - p[0]).toleft(a - p[0]) == -1 || (p.back() - p[0]).toleft(a - p[0]) == 1) return 0;
        const auto cmp = [&] (const point<T> & u, const point<T> & v) {
            return (u - p[0]).toleft(v - p[0]) == 1;
        };
        const size_t i = lower_bound(p.begin() + 1, p.end(), a, cmp) - p.begin();
        if(i == 1) return segment<T>{p[0], p[1]}.is_on(a) ? -1 : 0;
        if(i == p.size() - 1 && segment<T>{p[0], p.back()}.is_on(a)) return -1;
        if(segment<T>{p[i - 1], p[i]}.is_on(a)) return -1;
        return (p[i] - p[i - 1]).toleft(a - p[i - 1]) > 0;
    }
    
    // 凸多边形关于某一方向的极点
    // 复杂度 O(logn)
    // 参考资料：https://codeforces.com/blog/entry/48868
	template<typename F> size_t extreme (const F & dir) const
	{
		const auto & p = this -> p;
		const auto check = [&] (const size_t i) {
			return dir(p[i]).toleft(p[this -> nxt(i)] - p[i]) >= 0;
		};
		const auto dir0 = dir(p[0]); const auto check0 = check(0);
		if(!check0 && check(p.size() - 1)) return 0;
		const auto cmp = [&] (const point<T> & v)
		{
			const size_t vi = &v - p.data();
			if(vi == 0) return 1;
			const auto checkv = check(vi);
			const auto t = dir0.toleft(v - p[0]);
			if(vi == 1 && checkv == check0 && t == 0) return 1;
			return checkv ^ (checkv == check0 && t <= 0);
		};
		return partition_point(p.begin(), p.end(), cmp) - p.begin();
	}

	// 过凸多边形外一点求凸多边形的切线，返回切点下标
    // 复杂度 O(logn)
    // 必须保证点在多边形外
    // 必须保证凸多边形点数大于等于 3，点数小于等于 2 的 case 需要特判
	pair<size_t, size_t> tangent (const point<T> & a) const
	{
		const size_t i = extreme([&] (const point<T> & u) { return u - a; });
		const size_t j = extreme([&] (const point<T> & u) { return a - u; });
		return {i, j};
	}

    // 求平行于给定直线的凸多边形的切线，返回切点下标
    // 复杂度 O(logn)
    // 必须保证凸多边形点数大于等于 3，点数小于等于 2 的 case 需要特判
	pair<size_t, size_t> tangent (const line<T> & a) const
	{
		const size_t i = extreme([&] (...) { return a.v; });
		const size_t j = extreme([&] (...) { return -a.v; });
		return {i, j};
	}
};

using Convex = convex<point_t>;

// 圆
struct Circle
{
	Point c;
	long double r;

	bool operator == (const Circle & a) const { return c == a.c && abs(r - a.r) <= eps; }
	long double circ () const { return 2 * PI * r; }  // 周长
	long double area () const { return PI * r * r; }  // 面积

	// 点与圆的关系
    // -1 圆上 | 0 圆外 | 1 圆内
	int is_in (const Point & p) const
	{
		const long double d = p.dis(c);
		if(abs(d - r) <= eps) return -1;
		return d < r - eps;
	}

	// 直线与圆关系
    // 0 相离 | 1 相切 | 2 相交
	int relation (const Line & l) const
	{
		const long double d = l.dis(c);
		if(d < r - eps) return 2;
		return abs(d - r) <= eps;
	}

    // 圆与圆关系
    // -1 相同 | 0 相离 | 1 外切 | 2 相交 | 3 内切 | 4 内含
	int relation (const Circle & a) const
	{
		if((*this) == a) return -1;
		const long double d = c.dis(a.c);
		if(d > r + a.r + eps) return 0;
		if(abs(d - r - a.r) <= eps) return 1;
		if(abs(d - abs(r - a.r)) <= eps) return 3;
		if(d < abs(r - a.r) - eps) return 4;
		return 2;
	}

	// 直线与圆的交点
	vector<Point> inter (const Line & l) const
	{
		const long double d = l.dis(c);
		const Point p = l.proj(c);
		const int t = relation(l);
		if(t == 0) return {};
		if(t == 1) return {p};
		const long double k = sqrt(r * r - d * d);
		return {p - l.v * k / l.v.len(), p + l.v * k / l.v.len()};
	}

	// 圆与圆交点
	vector<Point> inter (const Circle & a) const
	{
		const long double d = c.dis(a.c);
		const int t = relation(a);
		if(t == -1 || t == 0 || t == 4) return {};
		Point e = a.c - c; e = e * r / e.len();
		if(t == 1 || t == 3)
		{
			if(r * r + d * d - a.r * a.r >= -eps) return {c + e};
			return {c - e};
		}
		const long double costh = (r * r + d * d - a.r * a.r) / (2 * d * r), sinth = sqrt(1 - costh * costh);
		return {c + e.rot(costh, -sinth), c + e.rot(costh, sinth)};
	}

	// 圆与圆交面积
	long double inter_area (const Circle & a) const
	{
		const long double d = c.dis(a.c);
		const int t = relation(a);
		if(t == -1) return area();
		if(t <= 1) return 0;
		if(t >= 3) return min(area(), a.area());
		const long double costh1 = (r * r + d * d - a.r * a.r) / (2 * r * d), costh2 = (a.r * a.r + d * d - r * r) / (2 * a.r * d);
		const long double sinth1 = sqrt(1 - costh1 * costh1), sinth2 = sqrt(1 - costh2 * costh2);
		const long double th1 = acos(costh1), th2 = acos(costh2);
		return r * r * (th1 - costh1 * sinth1) + a.r * a.r * (th2 - costh2 * sinth2);
	}

	// 过圆外一点圆的切线
	vector<Line> tangent (const Point & a) const
	{
		const int t = is_in(a);
		if(t == 1) return {};
		if(t == -1) return {{a, (a - c).rot()}};
		Point e = a - c; e = e * r / e.len();
		const long double costh = r / c.dis(a), sinth = sqrt(1 - costh * costh);
		const Point t1 = c + e.rot(costh, -sinth), t2 = c + e.rot(costh, sinth); // t1, t2 对应为切点
		return {{a, t1 - a}, {a, t2 - a}};
	}

	// 两圆的公切线
	vector<Line> tangent (const Circle & a) const
	{
		const int t = relation(a);
		if(t == -1 || t == 4) return {};
		vector<Line> lines;
		if(t == 1 || t == 3)
		{
			const Point p = inter(a)[0], v = (a.c - c).rot();
			lines.push_back({p, v}); // t = 1: 内切线; t = 3: 外切线
		}
		const long double d = c.dis(a.c);
		const Point e = (a.c - c) / (a.c - c).len();
		const auto add = [&] (int sign)
		{
			const long double costh = (r - a.r * sign) / d, sinth = sqrt(1 - costh * costh);
			const Point d1 = e.rot(costh, -sinth), d2 = e.rot(costh, sinth);
			const Point u1 = c + d1 * r, u2 = c + d2 * r, v1 = a.c + d1 * sign * a.r, v2 = a.c + d2 * sign * a.r;
			lines.push_back({u1, v1 - u1}), lines.push_back({u2, v2 - u2});
		};
		if(t <= 2) add(1); // 外切线
		if(t == 0) add(-1); // 内切线
		return lines;
	}

	// 圆上反演
	tuple<bool, Point> inverse (const Point & a) const
	{
		if(a == c) return {0, {}};
		const Point v = a - c;
		const long double d = r * r / c.dis(a);
		return {1, c + v * d / v.len()};
	}

	tuple<int, Circle, Line> inverse (const Line & l) const
	{
		if(l.toleft(c) == 0) return {2, {}, l};
		const Point v = l.toleft(c) == 1 ? -l.v.rot() : l.v.rot();
		const long double d = r * r / l.dis(c);
		const Point p = c + v * d / v.len();
		return {1, {(c + p) / 2, d / 2}, {}};
	}

	tuple<int, Circle, Line> inverse (const Circle & a) const
	{
		const Point v = a.c - c;
		if(a.is_in(c) == -1)
		{
			const long double d = r * r / (a.r + a.r);
			const Point p = c + v * d / v.len();
			return {2, {}, {p, v.rot()}};
		}
		if(c == a.c) return {1, {c, r * r / a.r}, {}};
		const long double d1 = r * r / (c.dis(a.c) - a.r), d2 = r * r / (c.dis(a.c) + a.r);
		const Point p = c + v * d1 / v.len(), q = c + v * d2 / v.len();
		return {1, {(p + q) / 2, p.dis(q) / 2}, {}};
	}
};
bool equal(long double x,long double y){
	return fabs(x-y)<eps;
}
void solve(){
	for(int i=0;i<3;i++)
    	scanf("%Lf %Lf",&x[i],&y[i]);
    scanf("%Lf %Lf",&px,&py);
    for(int i=0;i<3;i++){
    	if(equal(px,py,x[i],y[i])){
    		swap(x[i],x[0]);
    		swap(y[i],y[0]);
    		printf("%.15Lf %.15Lf\n",(x[1]+x[2])/2,(y[1]+y[2])/2);
    		return ;
    	}
    }
    Point p[3] = {{x[0], y[0]},{x[1], y[1]},{x[2], y[2]}},pp={px,py};
    Segment s1={p[0],p[1]},s2={p[0],p[2]},s3={p[2],p[1]};

    if(s1.is_on(pp)){

    }else if(s2.is_on(pp)){
    	swap(p[1],p[2]);
    }else if(s3.is_on(pp)){
    	swap(p[2],p[0]);
    }else{
    	printf("-1\n");
    	return ;
    }
    if((pp-p[0]).len()>(p[1]-p[0]).len()/2){
    	swap(p[0],p[1]);
    } 
    if(equal((pp-p[0]).len(),(p[1]-p[0]).len()/2)){
    	printf("%.15Lf %.15Lf\n",p[2].x,p[2].y);
    	return ;
    }
    long double ss=1.0/2/((pp-p[1]).len()/(p[0]-p[1]).len());
    long double x=(p[2].x-p[1].x)*ss,y=(p[2].y-p[1].y)*ss;
    long double ans1=p[1].x+x,ans2=p[1].y+y;
    printf("%.15Lf %.15Lf\n",ans1,ans2);
}
int main(){
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
}