#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

const int N = 5005;

int n;
int x[N], t[N];
int d[N][N];

int dist(int i, int j) {
	if (i == j) {
		return 0;
	}
	if (d[i][j] != -1) {
		return d[i][j];
	}
	return d[i][j] = getDistance(i, j);
}

}

void findLocation(int n1, int first, int location[], int stype[]) {
	n = n1;
	for (int i = 0; i < n; ++i) {
		t[i] = -1;
	}
	x[0] = first;
	t[0] = 1;
	if (n == 1) {
		location[0] = first;
		stype[0] = 1;
		return;	
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			d[i][j] = -1;
		}
	}
	int mn = 1;
	for (int i = 2; i < n; ++i) {
		if (dist(0, i) < dist(0, mn)) {
			mn = i;
		}
	}
	vector<int> l, r;
	for (int i = 1; i < n; ++i) {
		if (i != mn) {
			if (dist(0, mn) + dist(mn, i) == dist(0, i)) {
				l.push_back(i);
			} else {
				r.push_back(i);
			}
		}
	}
	sort(l.begin(), l.end(), [&](int i, int j) {
		return dist(mn, i) < dist(mn, j);
	});
	sort(r.begin(), r.end(), [&](int i, int j) {
		return dist(mn, i) < dist(mn, j);
	});
	int szl = l.size(), szr = r.size();
	x[mn] = x[0] + dist(0, mn);
	t[mn] = 2;
	for (int i = 0; i < szr; ++i) {
		for (int j = i + 1; j < szr; ++j) {
			if (dist(0, r[i]) + dist(r[i], r[j]) == dist(0, r[j])) {
				t[r[i]] = 2;
				x[r[i]] = x[0] + dist(0, r[i]);
				t[r[j]] = 1;
				x[r[j]] = x[r[i]] - dist(r[i], r[j]);
			}
		}
	}
	for (int i = 0; i < szr; ++i) {
		if (t[r[i]] == -1) {
			t[r[i]] = 2;
			x[r[i]] = x[0] + dist(0, r[i]);
		}
	}
	for (int i = 0; i < szl; ++i) {
		for (int j = i + 1; j < szl; ++j) {
			if (dist(mn, l[i]) + dist(l[i], l[j]) == dist(mn, l[j])) {
				t[l[i]] = 1;
				x[l[i]] = x[mn] - dist(mn, l[i]);
				t[l[j]] = 2;
				x[l[j]] = x[l[i]] + dist(l[i], l[j]);
			}
		}
	}
	for (int i = 0; i < szl; ++i) {
		if (t[l[i]] == -1) {
			t[l[i]] = 1;
			x[l[i]] = x[mn] - dist(mn, l[i]);
		}
	}
	for (int i = 0; i < n; ++i) {
		location[i] = x[i];
		stype[i] = t[i];
	}
}