/*
written by- Piyush Golani
language- c++
country- India
College- N.I.T Jamshedpur
*/
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<cctype>
using namespace std;
#define pb push_back
#define all(s) s.begin(),s.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define F(i,a,b) for(int i=a;i>=b;i--)
#define PI 3.1415926535897932384626433832795
#define INF 2000000000
#define BIG_INF 7000000000000000000LL
#define mp make_pair
#define eps 1e-9
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define mod 1000000007
#define mm 10000000
#define pd pair<double,int>
typedef long long LL;
string inttostring(int n)
{
stringstream a;
a<<n;
return a.str();
}
int stringtoint(string A)
{
istringstream a(A);
int p;
a>>p;
return p;
}
//////////////////////////////////////////////////////
class KingdomXCitiesandVillagesAnother {
public:
double determineLength( vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY ) {
int c=cityX.size();
int v=villageX.size();
int nodes=c+v;
double w[nodes][nodes];
f(i,0,c)
{
f(j,0,v)
{
w[i][c+j]=sqrt((LL)(cityX[i]-villageX[j])*(cityX[i]-villageX[j])+(LL)(cityY[i]-villageY[j])*(cityY[i]-villageY[j]));
w[c+j][i]=w[i][c+j];
}
}
f(i,0,v)
{
f(j,0,v)
{
w[c+i][c+j]=sqrt((LL)(villageX[i]-villageX[j])*(villageX[i]-villageX[j])+(LL)(villageY[i]-villageY[j])*(villageY[i]-villageY[j]));
w[c+j][c+i]=w[c+i][c+j];
}
}
priority_queue<pd,vector<pd>,greater<pd> > PQ;
bool visited[nodes];
memset(visited,false,sizeof(visited));
f(i,0,c)
visited[i]=true;
f(i,0,c)
{
f(j,0,v)
{
PQ.push(mp(w[i][c+j],c+j));
}
}
double res=0;
while(!PQ.empty())
{
pd ytk=PQ.top();
PQ.pop();
if(visited[ytk.second]) continue;
res+=ytk.first;
visited[ytk.second]=true;
f(i,0,nodes) if(!visited[i]) PQ.push(mp(w[ytk.second][i],i));
}
return res;
}
};
// BEGIN CUT HERE
namespace moj_harness {
int run_test_case(int);
void run_test(int casenum = -1, bool quiet = false) {
if (casenum != -1) {
if (run_test_case(casenum) == -1 && !quiet) {
cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
}
return;
}
int correct = 0, total = 0;
for (int i=0;; ++i) {
int x = run_test_case(i);
if (x == -1) {
if (i >= 100) break;
continue;
}
correct += x;
++total;
}
if (total == 0) {
cerr << "No test cases run." << endl;
} else if (correct < total) {
cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
} else {
cerr << "All " << total << " tests passed!" << endl;
}
}
static const double MAX_DOUBLE_ERROR = 1e-9; static bool topcoder_fequ(double expected, double result) { if (isnan(expected)) { return isnan(result); } else if (isinf(expected)) { if (expected > 0) { return result > 0 && isinf(result); } else { return result < 0 && isinf(result); } } else if (isnan(result) || isinf(result)) { return false; } else if (fabs(result - expected) < MAX_DOUBLE_ERROR) { return true; } else { double mmin = min(expected * (1.0 - MAX_DOUBLE_ERROR), expected * (1.0 + MAX_DOUBLE_ERROR)); double mmax = max(expected * (1.0 - MAX_DOUBLE_ERROR), expected * (1.0 + MAX_DOUBLE_ERROR)); return result > mmin && result < mmax; } }
double moj_relative_error(double expected, double result) { if (isnan(expected) || isinf(expected) || isnan(result) || isinf(result) || expected == 0) return 0; return fabs(result-expected) / fabs(expected); }
int verify_case(int casenum, const double &expected, const double &received, clock_t elapsed) {
cerr << "Example " << casenum << "... ";
string verdict;
vector<string> info;
char buf[100];
if (elapsed > CLOCKS_PER_SEC / 200) {
sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
info.push_back(buf);
}
if (topcoder_fequ(expected, received)) {
verdict = "PASSED";
double rerr = moj_relative_error(expected, received);
if (rerr > 0) {
sprintf(buf, "relative error %.3e", rerr);
info.push_back(buf);
}
} else {
verdict = "FAILED";
}
cerr << verdict;
if (!info.empty()) {
cerr << " (";
for (int i=0; i<(int)info.size(); ++i) {
if (i > 0) cerr << ", ";
cerr << info[i];
}
cerr << ")";
}
cerr << endl;
if (verdict == "FAILED") {
cerr << " Expected: " << expected << endl;
cerr << " Received: " << received << endl;
}
return verdict == "PASSED";
}
int run_test_case(int casenum__) {
switch (casenum__) {
case 0: {
int cityX[] = {1};
int cityY[] = {1};
int villageX[] = {2,3};
int villageY[] = {1,1};
double expected__ = 2.0;
clock_t start__ = clock();
double received__ = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
return verify_case(casenum__, expected__, received__, clock()-start__);
}
case 1: {
int cityX[] = {1,2};
int cityY[] = {1,1};
int villageX[] = {1,2};
int villageY[] = {2,2};
double expected__ = 2.0;
clock_t start__ = clock();
double received__ = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
return verify_case(casenum__, expected__, received__, clock()-start__);
}
case 2: {
int cityX[] = {0};
int cityY[] = {0};
int villageX[] = {2};
int villageY[] = {2};
double expected__ = 2.8284271247461903;
clock_t start__ = clock();
double received__ = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
return verify_case(casenum__, expected__, received__, clock()-start__);
}
// custom cases
/* case 3: {
int cityX[] = ;
int cityY[] = ;
int villageX[] = ;
int villageY[] = ;
double expected__ = ;
clock_t start__ = clock();
double received__ = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
return verify_case(casenum__, expected__, received__, clock()-start__);
}*/
/* case 4: {
int cityX[] = ;
int cityY[] = ;
int villageX[] = ;
int villageY[] = ;
double expected__ = ;
clock_t start__ = clock();
double received__ = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
return verify_case(casenum__, expected__, received__, clock()-start__);
}*/
/* case 5: {
int cityX[] = ;
int cityY[] = ;
int villageX[] = ;
int villageY[] = ;
double expected__ = ;
clock_t start__ = clock();
double received__ = KingdomXCitiesandVillagesAnother().determineLength(vector <int>(cityX, cityX + (sizeof cityX / sizeof cityX[0])), vector <int>(cityY, cityY + (sizeof cityY / sizeof cityY[0])), vector <int>(villageX, villageX + (sizeof villageX / sizeof villageX[0])), vector <int>(villageY, villageY + (sizeof villageY / sizeof villageY[0])));
return verify_case(casenum__, expected__, received__, clock()-start__);
}*/
default:
return -1;
}
}
}
int main(int argc, char *argv[]) {
if (argc == 1) {
moj_harness::run_test();
} else {
for (int i=1; i<argc; ++i)
moj_harness::run_test(atoi(argv[i]));
}
}
// END CUT HERE
LyoKd3JpdHRlbiBieS0gUGl5dXNoIEdvbGFuaQpsYW5ndWFnZS0gYysrCmNvdW50cnktIEluZGlhCkNvbGxlZ2UtIE4uSS5UIEphbXNoZWRwdXIKKi8KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxzc3RyZWFtPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPGNzdGRsaWI+CiNpbmNsdWRlPGNzdHJpbmc+CiNpbmNsdWRlPG1hcD4KI2luY2x1ZGU8c2V0PgojaW5jbHVkZTxxdWV1ZT4KI2luY2x1ZGU8Y2N0eXBlPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGFsbChzKSBzLmJlZ2luKCkscy5lbmQoKQojZGVmaW5lIGYoaSxhLGIpIGZvcihpbnQgaT1hO2k8YjtpKyspCiNkZWZpbmUgRihpLGEsYikgZm9yKGludCBpPWE7aT49YjtpLS0pCiNkZWZpbmUgUEkgMy4xNDE1OTI2NTM1ODk3OTMyMzg0NjI2NDMzODMyNzk1CiNkZWZpbmUgSU5GIDIwMDAwMDAwMDAKI2RlZmluZSBCSUdfSU5GIDcwMDAwMDAwMDAwMDAwMDAwMDBMTAojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIGVwcyAxZS05CiNkZWZpbmUgc2kobikgc2NhbmYoIiVkIiwmbikKI2RlZmluZSBzbGwobikgc2NhbmYoIiVsbGQiLCZuKQojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CiNkZWZpbmUgbW0gMTAwMDAwMDAKI2RlZmluZSBwZCBwYWlyPGRvdWJsZSxpbnQ+Cgp0eXBlZGVmIGxvbmcgbG9uZyBMTDsKCgpzdHJpbmcgaW50dG9zdHJpbmcoaW50IG4pCnsKICAgIHN0cmluZ3N0cmVhbSBhOwogICAgYTw8bjsKICAgIHJldHVybiBhLnN0cigpOwp9CgppbnQgc3RyaW5ndG9pbnQoc3RyaW5nIEEpCnsKICAgIGlzdHJpbmdzdHJlYW0gYShBKTsKICAgIGludCBwOwogICAgYT4+cDsKICAgIHJldHVybiBwOwp9CgovLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KCmNsYXNzIEtpbmdkb21YQ2l0aWVzYW5kVmlsbGFnZXNBbm90aGVyIHsKcHVibGljOgogICBkb3VibGUgZGV0ZXJtaW5lTGVuZ3RoKCB2ZWN0b3IgPGludD4gY2l0eVgsIHZlY3RvciA8aW50PiBjaXR5WSwgdmVjdG9yIDxpbnQ+IHZpbGxhZ2VYLCB2ZWN0b3IgPGludD4gdmlsbGFnZVkgKSB7CiAgICBpbnQgYz1jaXR5WC5zaXplKCk7CiAgICBpbnQgdj12aWxsYWdlWC5zaXplKCk7CiAgICBpbnQgbm9kZXM9Yyt2OwogICAgZG91YmxlIHdbbm9kZXNdW25vZGVzXTsKICAgIGYoaSwwLGMpCiAgICB7CiAgICAgICAgZihqLDAsdikKICAgICAgICB7CiAgICAgICAgICAgIHdbaV1bYytqXT1zcXJ0KChMTCkoY2l0eVhbaV0tdmlsbGFnZVhbal0pKihjaXR5WFtpXS12aWxsYWdlWFtqXSkrKExMKShjaXR5WVtpXS12aWxsYWdlWVtqXSkqKGNpdHlZW2ldLXZpbGxhZ2VZW2pdKSk7CiAgICAgICAgICAgIHdbYytqXVtpXT13W2ldW2Mral07CiAgICAgICAgfQogICAgfQogICAgZihpLDAsdikKICAgIHsKICAgICAgICBmKGosMCx2KQogICAgICAgIHsKICAgICAgICAgICAgd1tjK2ldW2Mral09c3FydCgoTEwpKHZpbGxhZ2VYW2ldLXZpbGxhZ2VYW2pdKSoodmlsbGFnZVhbaV0tdmlsbGFnZVhbal0pKyhMTCkodmlsbGFnZVlbaV0tdmlsbGFnZVlbal0pKih2aWxsYWdlWVtpXS12aWxsYWdlWVtqXSkpOwogICAgICAgICAgICB3W2Mral1bYytpXT13W2MraV1bYytqXTsKICAgICAgICB9CiAgICB9CiAgICBwcmlvcml0eV9xdWV1ZTxwZCx2ZWN0b3I8cGQ+LGdyZWF0ZXI8cGQ+ID4gUFE7CiAgICBib29sIHZpc2l0ZWRbbm9kZXNdOwogICAgbWVtc2V0KHZpc2l0ZWQsZmFsc2Usc2l6ZW9mKHZpc2l0ZWQpKTsKICAgIGYoaSwwLGMpCiAgICB2aXNpdGVkW2ldPXRydWU7CiAgICBmKGksMCxjKQogICAgewogICAgICAgIGYoaiwwLHYpCiAgICAgICAgewogICAgICAgICAgICBQUS5wdXNoKG1wKHdbaV1bYytqXSxjK2opKTsKICAgICAgICB9CiAgICB9CiAgICBkb3VibGUgcmVzPTA7CiAgICB3aGlsZSghUFEuZW1wdHkoKSkKICAgIHsKICAgICAgICBwZCB5dGs9UFEudG9wKCk7CiAgICAgICAgUFEucG9wKCk7CiAgICAgICAgaWYodmlzaXRlZFt5dGsuc2Vjb25kXSkgY29udGludWU7CiAgICAgICAgcmVzKz15dGsuZmlyc3Q7CiAgICAgICAgdmlzaXRlZFt5dGsuc2Vjb25kXT10cnVlOwogICAgICAgIGYoaSwwLG5vZGVzKSBpZighdmlzaXRlZFtpXSkgUFEucHVzaChtcCh3W3l0ay5zZWNvbmRdW2ldLGkpKTsKICAgIH0KICAgIHJldHVybiByZXM7CiAgIH0KfTsKCi8vIEJFR0lOIENVVCBIRVJFCm5hbWVzcGFjZSBtb2pfaGFybmVzcyB7CiAgICBpbnQgcnVuX3Rlc3RfY2FzZShpbnQpOwoJdm9pZCBydW5fdGVzdChpbnQgY2FzZW51bSA9IC0xLCBib29sIHF1aWV0ID0gZmFsc2UpIHsKCQlpZiAoY2FzZW51bSAhPSAtMSkgewoJCQlpZiAocnVuX3Rlc3RfY2FzZShjYXNlbnVtKSA9PSAtMSAmJiAhcXVpZXQpIHsKCQkJCWNlcnIgPDwgIklsbGVnYWwgaW5wdXQhIFRlc3QgY2FzZSAiIDw8IGNhc2VudW0gPDwgIiBkb2VzIG5vdCBleGlzdC4iIDw8IGVuZGw7CgkJCX0KCQkJcmV0dXJuOwoJCX0KCgkJaW50IGNvcnJlY3QgPSAwLCB0b3RhbCA9IDA7CgkJZm9yIChpbnQgaT0wOzsgKytpKSB7CgkJCWludCB4ID0gcnVuX3Rlc3RfY2FzZShpKTsKCQkJaWYgKHggPT0gLTEpIHsKCQkJCWlmIChpID49IDEwMCkgYnJlYWs7CgkJCQljb250aW51ZTsKCQkJfQoJCQljb3JyZWN0ICs9IHg7CgkJCSsrdG90YWw7CgkJfQoKCQlpZiAodG90YWwgPT0gMCkgewoJCQljZXJyIDw8ICJObyB0ZXN0IGNhc2VzIHJ1bi4iIDw8IGVuZGw7CgkJfSBlbHNlIGlmIChjb3JyZWN0IDwgdG90YWwpIHsKCQkJY2VyciA8PCAiU29tZSBjYXNlcyBGQUlMRUQgKHBhc3NlZCAiIDw8IGNvcnJlY3QgPDwgIiBvZiAiIDw8IHRvdGFsIDw8ICIpLiIgPDwgZW5kbDsKCQl9IGVsc2UgewoJCQljZXJyIDw8ICJBbGwgIiA8PCB0b3RhbCA8PCAiIHRlc3RzIHBhc3NlZCEiIDw8IGVuZGw7CgkJfQoJfQoKCXN0YXRpYyBjb25zdCBkb3VibGUgTUFYX0RPVUJMRV9FUlJPUiA9IDFlLTk7IHN0YXRpYyBib29sIHRvcGNvZGVyX2ZlcXUoZG91YmxlIGV4cGVjdGVkLCBkb3VibGUgcmVzdWx0KSB7IGlmIChpc25hbihleHBlY3RlZCkpIHsgcmV0dXJuIGlzbmFuKHJlc3VsdCk7IH0gZWxzZSBpZiAoaXNpbmYoZXhwZWN0ZWQpKSB7IGlmIChleHBlY3RlZCA+IDApIHsgcmV0dXJuIHJlc3VsdCA+IDAgJiYgaXNpbmYocmVzdWx0KTsgfSBlbHNlIHsgcmV0dXJuIHJlc3VsdCA8IDAgJiYgaXNpbmYocmVzdWx0KTsgfSB9IGVsc2UgaWYgKGlzbmFuKHJlc3VsdCkgfHwgaXNpbmYocmVzdWx0KSkgeyByZXR1cm4gZmFsc2U7IH0gZWxzZSBpZiAoZmFicyhyZXN1bHQgLSBleHBlY3RlZCkgPCBNQVhfRE9VQkxFX0VSUk9SKSB7IHJldHVybiB0cnVlOyB9IGVsc2UgeyBkb3VibGUgbW1pbiA9IG1pbihleHBlY3RlZCAqICgxLjAgLSBNQVhfRE9VQkxFX0VSUk9SKSwgZXhwZWN0ZWQgKiAoMS4wICsgTUFYX0RPVUJMRV9FUlJPUikpOyBkb3VibGUgbW1heCA9IG1heChleHBlY3RlZCAqICgxLjAgLSBNQVhfRE9VQkxFX0VSUk9SKSwgZXhwZWN0ZWQgKiAoMS4wICsgTUFYX0RPVUJMRV9FUlJPUikpOyByZXR1cm4gcmVzdWx0ID4gbW1pbiAmJiByZXN1bHQgPCBtbWF4OyB9IH0KCWRvdWJsZSBtb2pfcmVsYXRpdmVfZXJyb3IoZG91YmxlIGV4cGVjdGVkLCBkb3VibGUgcmVzdWx0KSB7IGlmIChpc25hbihleHBlY3RlZCkgfHwgaXNpbmYoZXhwZWN0ZWQpIHx8IGlzbmFuKHJlc3VsdCkgfHwgaXNpbmYocmVzdWx0KSB8fCBleHBlY3RlZCA9PSAwKSByZXR1cm4gMDsgcmV0dXJuIGZhYnMocmVzdWx0LWV4cGVjdGVkKSAvIGZhYnMoZXhwZWN0ZWQpOyB9CgoJaW50IHZlcmlmeV9jYXNlKGludCBjYXNlbnVtLCBjb25zdCBkb3VibGUgJmV4cGVjdGVkLCBjb25zdCBkb3VibGUgJnJlY2VpdmVkLCBjbG9ja190IGVsYXBzZWQpIHsKCQljZXJyIDw8ICJFeGFtcGxlICIgPDwgY2FzZW51bSA8PCAiLi4uICI7CgoJCXN0cmluZyB2ZXJkaWN0OwoJCXZlY3RvcjxzdHJpbmc+IGluZm87CgkJY2hhciBidWZbMTAwXTsKCgkJaWYgKGVsYXBzZWQgPiBDTE9DS1NfUEVSX1NFQyAvIDIwMCkgewoJCQlzcHJpbnRmKGJ1ZiwgInRpbWUgJS4yZnMiLCBlbGFwc2VkICogKDEuMC9DTE9DS1NfUEVSX1NFQykpOwoJCQlpbmZvLnB1c2hfYmFjayhidWYpOwoJCX0KCgkJaWYgKHRvcGNvZGVyX2ZlcXUoZXhwZWN0ZWQsIHJlY2VpdmVkKSkgewoJCQl2ZXJkaWN0ID0gIlBBU1NFRCI7CgkJCWRvdWJsZSByZXJyID0gbW9qX3JlbGF0aXZlX2Vycm9yKGV4cGVjdGVkLCByZWNlaXZlZCk7CgkJCWlmIChyZXJyID4gMCkgewoJCQkJc3ByaW50ZihidWYsICJyZWxhdGl2ZSBlcnJvciAlLjNlIiwgcmVycik7CgkJCQlpbmZvLnB1c2hfYmFjayhidWYpOwoJCQl9CgkJfSBlbHNlIHsKCQkJdmVyZGljdCA9ICJGQUlMRUQiOwoJCX0KCgkJY2VyciA8PCB2ZXJkaWN0OwoJCWlmICghaW5mby5lbXB0eSgpKSB7CgkJCWNlcnIgPDwgIiAoIjsKCQkJZm9yIChpbnQgaT0wOyBpPChpbnQpaW5mby5zaXplKCk7ICsraSkgewoJCQkJaWYgKGkgPiAwKSBjZXJyIDw8ICIsICI7CgkJCQljZXJyIDw8IGluZm9baV07CgkJCX0KCQkJY2VyciA8PCAiKSI7CgkJfQoJCWNlcnIgPDwgZW5kbDsKCgkJaWYgKHZlcmRpY3QgPT0gIkZBSUxFRCIpIHsKCQkJY2VyciA8PCAiICAgIEV4cGVjdGVkOiAiIDw8IGV4cGVjdGVkIDw8IGVuZGw7CgkJCWNlcnIgPDwgIiAgICBSZWNlaXZlZDogIiA8PCByZWNlaXZlZCA8PCBlbmRsOwoJCX0KCgkJcmV0dXJuIHZlcmRpY3QgPT0gIlBBU1NFRCI7Cgl9CgoJaW50IHJ1bl90ZXN0X2Nhc2UoaW50IGNhc2VudW1fXykgewoJCXN3aXRjaCAoY2FzZW51bV9fKSB7CgkJY2FzZSAwOiB7CgkJCWludCBjaXR5WFtdICAgICAgICAgICAgICAgPSB7MX07CgkJCWludCBjaXR5WVtdICAgICAgICAgICAgICAgPSB7MX07CgkJCWludCB2aWxsYWdlWFtdICAgICAgICAgICAgPSB7MiwzfTsKCQkJaW50IHZpbGxhZ2VZW10gICAgICAgICAgICA9IHsxLDF9OwoJCQlkb3VibGUgZXhwZWN0ZWRfXyAgICAgICAgID0gMi4wOwoKCQkJY2xvY2tfdCBzdGFydF9fICAgICAgICAgICA9IGNsb2NrKCk7CgkJCWRvdWJsZSByZWNlaXZlZF9fICAgICAgICAgPSBLaW5nZG9tWENpdGllc2FuZFZpbGxhZ2VzQW5vdGhlcigpLmRldGVybWluZUxlbmd0aCh2ZWN0b3IgPGludD4oY2l0eVgsIGNpdHlYICsgKHNpemVvZiBjaXR5WCAvIHNpemVvZiBjaXR5WFswXSkpLCB2ZWN0b3IgPGludD4oY2l0eVksIGNpdHlZICsgKHNpemVvZiBjaXR5WSAvIHNpemVvZiBjaXR5WVswXSkpLCB2ZWN0b3IgPGludD4odmlsbGFnZVgsIHZpbGxhZ2VYICsgKHNpemVvZiB2aWxsYWdlWCAvIHNpemVvZiB2aWxsYWdlWFswXSkpLCB2ZWN0b3IgPGludD4odmlsbGFnZVksIHZpbGxhZ2VZICsgKHNpemVvZiB2aWxsYWdlWSAvIHNpemVvZiB2aWxsYWdlWVswXSkpKTsKCQkJcmV0dXJuIHZlcmlmeV9jYXNlKGNhc2VudW1fXywgZXhwZWN0ZWRfXywgcmVjZWl2ZWRfXywgY2xvY2soKS1zdGFydF9fKTsKCQl9CgkJY2FzZSAxOiB7CgkJCWludCBjaXR5WFtdICAgICAgICAgICAgICAgPSB7MSwyfTsKCQkJaW50IGNpdHlZW10gICAgICAgICAgICAgICA9IHsxLDF9OwoJCQlpbnQgdmlsbGFnZVhbXSAgICAgICAgICAgID0gezEsMn07CgkJCWludCB2aWxsYWdlWVtdICAgICAgICAgICAgPSB7MiwyfTsKCQkJZG91YmxlIGV4cGVjdGVkX18gICAgICAgICA9IDIuMDsKCgkJCWNsb2NrX3Qgc3RhcnRfXyAgICAgICAgICAgPSBjbG9jaygpOwoJCQlkb3VibGUgcmVjZWl2ZWRfXyAgICAgICAgID0gS2luZ2RvbVhDaXRpZXNhbmRWaWxsYWdlc0Fub3RoZXIoKS5kZXRlcm1pbmVMZW5ndGgodmVjdG9yIDxpbnQ+KGNpdHlYLCBjaXR5WCArIChzaXplb2YgY2l0eVggLyBzaXplb2YgY2l0eVhbMF0pKSwgdmVjdG9yIDxpbnQ+KGNpdHlZLCBjaXR5WSArIChzaXplb2YgY2l0eVkgLyBzaXplb2YgY2l0eVlbMF0pKSwgdmVjdG9yIDxpbnQ+KHZpbGxhZ2VYLCB2aWxsYWdlWCArIChzaXplb2YgdmlsbGFnZVggLyBzaXplb2YgdmlsbGFnZVhbMF0pKSwgdmVjdG9yIDxpbnQ+KHZpbGxhZ2VZLCB2aWxsYWdlWSArIChzaXplb2YgdmlsbGFnZVkgLyBzaXplb2YgdmlsbGFnZVlbMF0pKSk7CgkJCXJldHVybiB2ZXJpZnlfY2FzZShjYXNlbnVtX18sIGV4cGVjdGVkX18sIHJlY2VpdmVkX18sIGNsb2NrKCktc3RhcnRfXyk7CgkJfQoJCWNhc2UgMjogewoJCQlpbnQgY2l0eVhbXSAgICAgICAgICAgICAgID0gezB9OwoJCQlpbnQgY2l0eVlbXSAgICAgICAgICAgICAgID0gezB9OwoJCQlpbnQgdmlsbGFnZVhbXSAgICAgICAgICAgID0gezJ9OwoJCQlpbnQgdmlsbGFnZVlbXSAgICAgICAgICAgID0gezJ9OwoJCQlkb3VibGUgZXhwZWN0ZWRfXyAgICAgICAgID0gMi44Mjg0MjcxMjQ3NDYxOTAzOwoKCQkJY2xvY2tfdCBzdGFydF9fICAgICAgICAgICA9IGNsb2NrKCk7CgkJCWRvdWJsZSByZWNlaXZlZF9fICAgICAgICAgPSBLaW5nZG9tWENpdGllc2FuZFZpbGxhZ2VzQW5vdGhlcigpLmRldGVybWluZUxlbmd0aCh2ZWN0b3IgPGludD4oY2l0eVgsIGNpdHlYICsgKHNpemVvZiBjaXR5WCAvIHNpemVvZiBjaXR5WFswXSkpLCB2ZWN0b3IgPGludD4oY2l0eVksIGNpdHlZICsgKHNpemVvZiBjaXR5WSAvIHNpemVvZiBjaXR5WVswXSkpLCB2ZWN0b3IgPGludD4odmlsbGFnZVgsIHZpbGxhZ2VYICsgKHNpemVvZiB2aWxsYWdlWCAvIHNpemVvZiB2aWxsYWdlWFswXSkpLCB2ZWN0b3IgPGludD4odmlsbGFnZVksIHZpbGxhZ2VZICsgKHNpemVvZiB2aWxsYWdlWSAvIHNpemVvZiB2aWxsYWdlWVswXSkpKTsKCQkJcmV0dXJuIHZlcmlmeV9jYXNlKGNhc2VudW1fXywgZXhwZWN0ZWRfXywgcmVjZWl2ZWRfXywgY2xvY2soKS1zdGFydF9fKTsKCQl9CgoJCS8vIGN1c3RvbSBjYXNlcwoKLyogICAgICBjYXNlIDM6IHsKCQkJaW50IGNpdHlYW10gICAgICAgICAgICAgICA9IDsKCQkJaW50IGNpdHlZW10gICAgICAgICAgICAgICA9IDsKCQkJaW50IHZpbGxhZ2VYW10gICAgICAgICAgICA9IDsKCQkJaW50IHZpbGxhZ2VZW10gICAgICAgICAgICA9IDsKCQkJZG91YmxlIGV4cGVjdGVkX18gICAgICAgICA9IDsKCgkJCWNsb2NrX3Qgc3RhcnRfXyAgICAgICAgICAgPSBjbG9jaygpOwoJCQlkb3VibGUgcmVjZWl2ZWRfXyAgICAgICAgID0gS2luZ2RvbVhDaXRpZXNhbmRWaWxsYWdlc0Fub3RoZXIoKS5kZXRlcm1pbmVMZW5ndGgodmVjdG9yIDxpbnQ+KGNpdHlYLCBjaXR5WCArIChzaXplb2YgY2l0eVggLyBzaXplb2YgY2l0eVhbMF0pKSwgdmVjdG9yIDxpbnQ+KGNpdHlZLCBjaXR5WSArIChzaXplb2YgY2l0eVkgLyBzaXplb2YgY2l0eVlbMF0pKSwgdmVjdG9yIDxpbnQ+KHZpbGxhZ2VYLCB2aWxsYWdlWCArIChzaXplb2YgdmlsbGFnZVggLyBzaXplb2YgdmlsbGFnZVhbMF0pKSwgdmVjdG9yIDxpbnQ+KHZpbGxhZ2VZLCB2aWxsYWdlWSArIChzaXplb2YgdmlsbGFnZVkgLyBzaXplb2YgdmlsbGFnZVlbMF0pKSk7CgkJCXJldHVybiB2ZXJpZnlfY2FzZShjYXNlbnVtX18sIGV4cGVjdGVkX18sIHJlY2VpdmVkX18sIGNsb2NrKCktc3RhcnRfXyk7CgkJfSovCi8qICAgICAgY2FzZSA0OiB7CgkJCWludCBjaXR5WFtdICAgICAgICAgICAgICAgPSA7CgkJCWludCBjaXR5WVtdICAgICAgICAgICAgICAgPSA7CgkJCWludCB2aWxsYWdlWFtdICAgICAgICAgICAgPSA7CgkJCWludCB2aWxsYWdlWVtdICAgICAgICAgICAgPSA7CgkJCWRvdWJsZSBleHBlY3RlZF9fICAgICAgICAgPSA7CgoJCQljbG9ja190IHN0YXJ0X18gICAgICAgICAgID0gY2xvY2soKTsKCQkJZG91YmxlIHJlY2VpdmVkX18gICAgICAgICA9IEtpbmdkb21YQ2l0aWVzYW5kVmlsbGFnZXNBbm90aGVyKCkuZGV0ZXJtaW5lTGVuZ3RoKHZlY3RvciA8aW50PihjaXR5WCwgY2l0eVggKyAoc2l6ZW9mIGNpdHlYIC8gc2l6ZW9mIGNpdHlYWzBdKSksIHZlY3RvciA8aW50PihjaXR5WSwgY2l0eVkgKyAoc2l6ZW9mIGNpdHlZIC8gc2l6ZW9mIGNpdHlZWzBdKSksIHZlY3RvciA8aW50Pih2aWxsYWdlWCwgdmlsbGFnZVggKyAoc2l6ZW9mIHZpbGxhZ2VYIC8gc2l6ZW9mIHZpbGxhZ2VYWzBdKSksIHZlY3RvciA8aW50Pih2aWxsYWdlWSwgdmlsbGFnZVkgKyAoc2l6ZW9mIHZpbGxhZ2VZIC8gc2l6ZW9mIHZpbGxhZ2VZWzBdKSkpOwoJCQlyZXR1cm4gdmVyaWZ5X2Nhc2UoY2FzZW51bV9fLCBleHBlY3RlZF9fLCByZWNlaXZlZF9fLCBjbG9jaygpLXN0YXJ0X18pOwoJCX0qLwovKiAgICAgIGNhc2UgNTogewoJCQlpbnQgY2l0eVhbXSAgICAgICAgICAgICAgID0gOwoJCQlpbnQgY2l0eVlbXSAgICAgICAgICAgICAgID0gOwoJCQlpbnQgdmlsbGFnZVhbXSAgICAgICAgICAgID0gOwoJCQlpbnQgdmlsbGFnZVlbXSAgICAgICAgICAgID0gOwoJCQlkb3VibGUgZXhwZWN0ZWRfXyAgICAgICAgID0gOwoKCQkJY2xvY2tfdCBzdGFydF9fICAgICAgICAgICA9IGNsb2NrKCk7CgkJCWRvdWJsZSByZWNlaXZlZF9fICAgICAgICAgPSBLaW5nZG9tWENpdGllc2FuZFZpbGxhZ2VzQW5vdGhlcigpLmRldGVybWluZUxlbmd0aCh2ZWN0b3IgPGludD4oY2l0eVgsIGNpdHlYICsgKHNpemVvZiBjaXR5WCAvIHNpemVvZiBjaXR5WFswXSkpLCB2ZWN0b3IgPGludD4oY2l0eVksIGNpdHlZICsgKHNpemVvZiBjaXR5WSAvIHNpemVvZiBjaXR5WVswXSkpLCB2ZWN0b3IgPGludD4odmlsbGFnZVgsIHZpbGxhZ2VYICsgKHNpemVvZiB2aWxsYWdlWCAvIHNpemVvZiB2aWxsYWdlWFswXSkpLCB2ZWN0b3IgPGludD4odmlsbGFnZVksIHZpbGxhZ2VZICsgKHNpemVvZiB2aWxsYWdlWSAvIHNpemVvZiB2aWxsYWdlWVswXSkpKTsKCQkJcmV0dXJuIHZlcmlmeV9jYXNlKGNhc2VudW1fXywgZXhwZWN0ZWRfXywgcmVjZWl2ZWRfXywgY2xvY2soKS1zdGFydF9fKTsKCQl9Ki8KCQlkZWZhdWx0OgoJCQlyZXR1cm4gLTE7CgkJfQoJfQp9CgoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgKmFyZ3ZbXSkgewoJaWYgKGFyZ2MgPT0gMSkgewoJCW1val9oYXJuZXNzOjpydW5fdGVzdCgpOwoJfSBlbHNlIHsKCQlmb3IgKGludCBpPTE7IGk8YXJnYzsgKytpKQoJCQltb2pfaGFybmVzczo6cnVuX3Rlc3QoYXRvaShhcmd2W2ldKSk7Cgl9Cn0KLy8gRU5EIENVVCBIRVJFCgoK