Камоме метеорларды бақылауға өте қызығады. Ол метеорлардың қозғалысын модельдейтін шексіз үлкен екі өлшемді модель жасады (бірақ ол іс жүзінде ештеңені де модельдемейді). Бұл симуляцияда $n$ метеор моделі бар, ал $i$-ші метеор моделінің салмағы $m_i$. Әрбір метеор моделі бекітілген түзу сызық бойымен тұрақты жылдамдықпен қозғалады (ол қозғалмай тұруы да мүмкін).

Камоме бұл модельді іске қосқалы көп уақыт өтті. Бір күні Камомеге кенеттен бір ой келіп, ағымдағы модельді екі рет суретке түсірді. Камоменің орнын координаттар басы ретінде алсақ, әрбір $i$ ($i = 1, 2$) фотосуреті үшін $j$-ші метеор моделі жазықтықта $(x_{i,j}, y_{i,j})$ нүктесінде орналасқан.

Сіз әрбір метеор моделінің траекториясын есептей аласыз, бірақ бұл жеткіліксіз! Камоме сізден әрбір $i$ метеор моделі үшін модель жұмыс істеп тұрған барлық уақыт ішінде (мұны фотосуреттер түсірілгенге дейінгі және кейінгі шексіз уақыт аралығы деп санауға болады) кез келген басқа метеор моделінің оған түсіретін ең үлкен тартылыс күшін есептеуді қалайды.

Әдеттегі тартылыс формуласын $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$ түрінде қайта жазуға болатынын ескеріңіз. Кейбір шеткі жағдайларды қарастырмау үшін Камоме кіріс ретінде $m'_i = \frac{1}{m_i}$ мәндерін береді, ал сізге тек жауапты $G$-ге бөліп, содан кейін кері шамасын алу нәтижесін шығару жеткілікті. Яғни, әрбір $i$ үшін $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$ мәнін есептеңіз, мұндағы $D_t(i, j)$ — $t$ уақыт мезетіндегі $i$ және $j$ метеор модельдерінің арасындағы қашықтық, ал $t$ кез келген нақты сан (теріс, оң немесе нөл) болуы мүмкін.

Кіріс деректер

Әрбір тест бірнеше тест жиынтығынан тұрады. Бірінші жолда тест жиынтықтарының санын білдіретін бір бүтін сан $t$ ($1 \le t \le 10^4$) берілген. Одан кейін тест жиынтықтарының сипаттамасы беріледі.

Бірінші жолда метеор модельдерінің санын білдіретін бір бүтін сан $n$ ($2 \le n, \sum n \le 10^5$) берілген.

Екінші жолда анықтамасы жоғарыда көрсетілген $n$ бүтін сан $m'_i$ ($1 \le m'_i \le 100$) берілген.

Келесі $n$ жолдың әрқайсысында екі фотосуреттегі $i$-ші метеор моделінің орнын білдіретін төрт бүтін сан $x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}$ ($-10^8 \le x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i} \le 10^8$, $0 \le |x_{1,i} - x_{2,i}|, |y_{1,i} - y_{2,i}| \le 5$) берілген.

Шығыс деректер

Әрбір тест жиынтығы үшін жоғарыда анықталғандай $n$ нақты саннан тұратын бір жолды шығарыңыз.

Сіздің жауабыңыз $x$, ал қазылар алқасының жауабы $y$ болсын; сіздің жауабыңыз тек $\frac{|x - y|}{\max(y, 1)} \le 10^{-6}$ шарты орындалғанда ғана дұрыс деп есептеледі.

Мысалдар

Кіріс 1

2
2
1 2
0 0 1 0
1 1 0 1
3
1 2 3
1 0 0 -1
-1 0 0 1
0 1 1 0

Шығыс 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

Ескертпе

Бірінші тест жиынтығы үшін 1-ші метеор моделі мен 2-ші метеор моделінің ең үлкен тартылыс күші олар сәйкесінше $(0.5, 0)$ және $(0.5, 1)$ нүктелеріне жеткенде пайда болады. Бұл кезде жауап $m'_1 m'_2 d_{\min}^2 = 2$ болады.