Ideone.com

download

copy

/*  An example of how to compile and use the checker:
 *    $ g++ checker.cpp -o checker
 *    $ checker < yourOutput.txt
 *
 *  The checker reads the test case from the standard input (stdin) and
 *  prints an informative message with the results of the heuristics to
 *  the standard ouput (stdout).
 *
 *
 *  # Description of the solutions.
 *
 *  0. 'struct CorrectSolution' implements the intended solution using
 *     matroid intersection, which is described in the editorial of CNNCT2.
 *
 *  1. 'struct Solution1' implements the following randomized heuristic:
 *        a) Select a random permutation of the edges;
 *        b) Start with both graphs empty and consider the edges one by one
 *           in the selected order;
 *        c) If the considered edge can be added to both graphs without
 *           creating any cycles - add it, otherwise discard it;
 *        d) If at the end of the process 'k' edges were added to the
 *           graphs, update the answer with the value of '2 * n - 2 - k';
 *        e) Repeat steps (a) through (d) '30000000 / m' times and return
 *           the best (minimal) answer found.
 *
 *  2. 'struct Solution2' implements the following randomized heuristic:
 *        a) Select a random permutation of the edges;
 *        b) Start with both graphs empty and consider the edges one by one
 *           in the selected order;
 *        c) If the considered edge connects two different connected
 *           components in at least one of the graph - add it, otherwise
 *           discard it;
 *        d) Denote the list of added edges with 'L', preserving order;
 *        e) Consider each edge from the list 'L', if it is a bridge in at
 *           least of the graphs - move it to the beginning of the list 'L',
 *           otherwise leave it at its previous position;
 *        f) If the size of the list 'L' is 'k' and all the 'k' edges were
 *           moved during step (e), return 'k' as the answer;
 *        g) Otherwise, go back to step (b) using the list 'L' instead of
 *           the initial permutation generated during step (a);
 *        h) Repeat steps (a) through (g) until the total size of the graphs
 *           (vertices + edges) considered during step (b) reaches 20000000
 *           and return the best answer found;
 *
 *  3. 'struct Solution3' implements the following randomized heuristic:
 *        a) Start with a parameter 'ee = 1.0';
 *        b) Select a random permutation of the edges 'P';
 *        c) Execute steps (b) and (c) from the solution (1) using the per-
 *           mutation 'P' and denote the number of added edges with 'curr';
 *        d) Select a pair of permutation elements 'x' and 'y' at random;
 *           and swap the edges 'P[x]' and 'P[y]';
 *        e) Execute steps (b) and (c) from the solution (1) using the per-
 *           mutation 'P' and denote the number of added edges with 'cnt';
 *        f) If 'cnt > curr' go to step (i);
 *        g) Otherwise with probability 'pow(ee, curr - cnt)' go to step (i);
 *        h) Otherwise swap the edges 'P[x]' and 'P[y]' back and go to
 *           step (j);
 *        i) Update 'ee := ee * 0.991' and update the answer with the value
 *           '2 * n - 2 - cnt';
 *        j) Finish one iteration;
 *        k) Repeat the steps (c) through (j) '6000000 / m' times on each
 *           iteration using the permutations 'P' obtained after the
 *           previous iteration;
 *        l) Steps (a) through (k) are repeated 5 times and the best answer
 *           found is returned.
 *
 *  4. 'struct Solution4' implements the following randomized heuristic:
 *        a) Start with a parameter 'ee = 1.0';
 *        b) Select a random spanning tree in the first graph and consider
 *           these edges to be initially enabled and all other - disabled;
 *        c) Count the number of connected components in the second graph,
 *           including only enabled edges, and denote the count with 'curr';
 *        d) Choose an edge 'x' at random among currently disabled edges;
 *        e) Choose an edge 'y' at random from the path connecting the
 *           endpoints of 'x' in the tree formed by enabled edges;
 *        f) Mark edge 'x' as disabled and edge 'y' as enabled;
 *        g) Count the number of connected components in the second graph,
 *           including only enabled edges, and denote the count with 'cnt';
 *        h) If 'cnt < curr' go to step (k);
 *        i) Otherwise with probability 'pow(ee, cnt - curr)' go to step (k);
 *        j) Otherwise mark the edge 'x' as enabled and edge 'y' as disabled,
 *           reverting the step (f) and go to the step (l);
 *        k) Update 'ee := ee * 0.988' and update the answer with the value
 *           'n - 1 + cnt - 1';
 *        l) Finish one iteration;
 *        m) Repeat the steps (c) through (l) '300000 / m' times on each
 *           itertion using the enabled edges obtained after the previous
 *           iteration;
 *        n) Steps (a) through (m) are repeated 50 times with the two graphs
 *           in their original order and 50 times with the graphs being
 *           swapped. The best answer found is returned.
 */
 
#include <vector>
 
using namespace std;
 
extern "C" {
	int scanf(const char*, ...);
	int printf(const char*, ...);
	void exit(int);
	double pow(double, double);
}
 
const unsigned seed = 0x12345678;
 
//////////////////////////////////////////////////////////////////////////
// The part below is an exact copy from the checker used on the server! //
 
struct random_t {
	unsigned state;
	random_t() : state(seed) { }
	unsigned next() {
		state ^= state << 13;
		state ^= state >> 17;
		state ^= state << 5;
		return state;
	}
	void permute(int* permutation, int n) {
		for (int k = 0; k < n; k++) {
			permutation[k] = k;
			int p = next() % (k + 1);
			int tmp = permutation[p];
			permutation[p] = k;
			permutation[k] = tmp;
		}
	}
};
 
const int MX = 300;
 
struct DSU {
	int p[MX];
 
	void init(int n) {
		for (int i = 0; i < n; i++) p[i] = i;
	}
 
	int get(int v) {
		if (p[v] != v) p[v] = get(p[v]);
		return p[v];
	}
 
	void merge(int u, int v) {
		u = get(u);
		v = get(v);
		p[u] = v;
	}
};
 
int n, m;
int u1[MX], v1[MX], u2[MX], v2[MX];
 
struct Graph {
	int lastEdge[MX], ee;
	struct { int v, id, next; } e[2 * MX];
 
	void init() {
		ee = 0;
		for (int i = 0; i < n; i++) lastEdge[i] = -1;
	}
 
	void addEdge(int u, int v, int id) {
		e[ee].v = v;
		e[ee].id = id;
		e[ee].next = lastEdge[u];
		lastEdge[u] = ee++;
 
		e[ee].v = u;
		e[ee].id = id;
		e[ee].next = lastEdge[v];
		lastEdge[v] = ee++;
	}
 
	bool vis[MX];
	int up[MX], dep[MX];
	bool* bridge;
 
	void dfs(int v, int edgeToParent, int depth) {
		vis[v] = true;
		dep[v] = depth;
		up[v] = depth;
		for (int i = lastEdge[v]; i != -1; i = e[i].next) {
			if (e[i].id == edgeToParent) continue;
 
			int u = e[i].v;
			if (vis[u] == false) {
				dfs(u, e[i].id, depth + 1);
				if (up[u] > depth) bridge[e[i].id] = true;
			}
 
			if (up[u] < up[v]) up[v] = up[u];
		}
	}
 
	void markBridges(bool* isBridge) {
		for (int i = 0; i < n; i++) vis[i] = false;
 
		bridge = isBridge;
		dfs(0, -1, 0);
	}
};
 
int getBothAcyclic(int* permutation) {
	static DSU dsu1, dsu2;
 
	dsu1.init(n);
	dsu2.init(n);
 
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		int e = permutation[i];
		int x1 = dsu1.get(u1[e]);
		int y1 = dsu1.get(v1[e]);
		if (x1 == y1) continue;
		int x2 = dsu2.get(u2[e]);
		int y2 = dsu2.get(v2[e]);
		if (x2 != y2) {
			cnt++;
			dsu1.merge(x1, y1);
			dsu2.merge(x2, y2);
		}
	}
 
	return cnt;
}
 
struct ExchangeGraph {
	vector<int> G[MX];
 
	void clear() {
		for (int i = 0; i < m; i++) G[i].clear();
	}
 
	void addEdge(int u, int v) {
		G[u].push_back(v);
	}
 
	bool findAugmentalPath(vector<int> from, vector<int> to, bool* enabled) {
		vector<int> par(m, -1), dist(m), queue;
		for (size_t i = 0; i < from.size(); i++) {
			int v = from[i];
			queue.push_back(v);
			par[v] = -2;
			dist[v] = 0;
		}
 
		for (size_t i = 0; i < queue.size(); i++) {
			int v = queue[i];
			for (size_t j = 0; j < G[v].size(); j++) {
				int u = G[v][j];
				if (par[u] == -1) {
					queue.push_back(u);
					par[u] = v;
					dist[u] = dist[v] + 1;
				}
			}
		}
 
		int target = -1;
		for (size_t i = 0; i < to.size(); i++) {
			int v = to[i];
			if (par[v] == -1) continue;
			if (target == -1 || dist[v] < dist[target]) target = v;
		}
 
		if (target != -1) {
			while (target != -2) {
				enabled[target] = not enabled[target];
				target = par[target];
			}
 
			return true;
		}
 
		return false;
	}
};
 
struct CorrectSolution {
	ExchangeGraph exchangeGraph;
	bool enabled[MX];
 
	int solve() {
		for (int i = 0; i < m; i++) enabled[i] = true;
 
		int ans = m;
		while (true) {
			exchangeGraph.clear();
 
			vector<int> Y1 = getNonBridges(u1, v1);
			vector<int> Y2 = getNonBridges(u2, v2);
 
			if (exchangeGraph.findAugmentalPath(Y1, Y2, enabled)) {
				ans--;
				continue;
			}
 
			for (int e = 0; e < m; e++) {
				if (enabled[e]) continue;
 
				enabled[e] = true;
 
				vector<int> edgesTo = getNonBridges(u1, v1);
				vector<int> edgesFrom = getNonBridges(u2, v2);
 
				enabled[e] = false;
 
				for (size_t i = 0; i < edgesTo.size(); i++) {
					exchangeGraph.addEdge(e, edgesTo[i]);
				}
				for (size_t i = 0; i < edgesFrom.size(); i++) {
					exchangeGraph.addEdge(edgesFrom[i], e);
				}
			}
 
			if (exchangeGraph.findAugmentalPath(Y1, Y2, enabled)) {
				ans--;
			}
			else {
				break;
			}
		}
 
		return ans;
	}
 
	Graph G;
	bool isBridge[MX];
	vector<int> getNonBridges(int* u, int* v) {
		G.init();
		for (int i = 0; i < m; i++) {
			if (enabled[i]) {
				G.addEdge(u[i], v[i], i);
				isBridge[i] = false;
			}
		}
 
		G.markBridges(isBridge);
 
		vector<int> result;
		for (int i = 0; i < m; i++) {
			if (enabled[i] && isBridge[i] == false) {
				result.push_back(i);
			}
		}
 
		return result;
	}
};
 
struct Solution1 {
	int permutation[MX];
 
	double solve(int correct) {
		const int limit = 30000000 / m;
 
		random_t rnd;
		for (int it = 1; it <= limit; it++) {
			rnd.permute(permutation, m);
			int cnt = getBothAcyclic(permutation);
			int ans = 2 * (n - 1 - cnt) + cnt;
			if (ans == correct) return it / (double)limit;
		}
 
		return -1;
	}
};
 
struct Solution2 {
	int permutation[MX], selected[MX], timeSpent;
	bool isBridge[MX];
 
	double solve(int correct) {
		const int limit = 20000000;
		timeSpent = 0;
 
		random_t rnd;
 
		while (timeSpent < limit) {
			rnd.permute(permutation, m);
			int ans = solveOne(m);
			if (ans == correct) return timeSpent / (double)limit;
		}
 
		return -1;
	}
 
	DSU dsu1, dsu2;
	int solveOne(int cnt) {
		timeSpent += n + cnt;
 
		dsu1.init(n);
		dsu2.init(n);
 
		int used = 0;
		for (int i = 0; i < cnt; i++) {
			int e = permutation[i];
			int x1 = dsu1.get(u1[e]);
			int y1 = dsu1.get(v1[e]);
			int x2 = dsu2.get(u2[e]);
			int y2 = dsu2.get(v2[e]);
			if (x1 != y1 || x2 != y2) {
				selected[used++] = e;
				isBridge[e] = false;
				dsu1.merge(x1, y1);
				dsu2.merge(x2, y2);
			}
		}
 
		getBridges(used, u1, v1);
		getBridges(used, u2, v2);
 
		int bridges = 0;
		for (int i = 0; i < used; i++) {
			int e = selected[i];
			if (isBridge[e]) {
				permutation[bridges++] = e;
			}
		}
 
		for (int i = 0, j = bridges; i < used; i++) {
			int e = selected[i];
			if (isBridge[e] == false) {
				permutation[j++] = e;
			}
		}
 
		if (bridges == used) return used;
		return solveOne(used);
	}
 
	Graph G;
	void getBridges(int cnt, int* u, int* v) {
		G.init();
		for (int i = 0; i < cnt; i++) {
			int e = selected[i];
			G.addEdge(u[e], v[e], e);
		}
 
		G.markBridges(isBridge);
	}
};
 
struct Solution3 {
	random_t rnd;
 
	double solve(int correct) {
		if (m == n - 1) return 0;
 
		for (int it = 0; it < 5; it++) {
			double result = solveOne(correct);
			if (result < -0.5) continue;
			return (it + result) / 5;
		}
 
		return -1;
	}
 
	int permutation[MX];
	double solveOne(int correct) {
		const int limit = 6000000 / m;
 
		rnd.permute(permutation, m);
 
		double ee = 1.0;
		int best = getBothAcyclic(permutation), curr = best;
		for (int it = 1; it <= limit; it++) {
			int x, y;
			do {
				x = rnd.next() % m;
				y = rnd.next() % m;
			} while (x == y);
 
			int tmp = permutation[x];
			permutation[x] = permutation[y];
			permutation[y] = tmp;
 
			int cnt = getBothAcyclic(permutation);
			if (cnt > curr || rnd.next() < (1LL << 32) * pow(ee, curr - cnt)) {
				curr = cnt;
				ee *= 0.991;
				if (cnt > best) best = cnt;
			}
			else {
				tmp = permutation[x];
				permutation[x] = permutation[y];
				permutation[y] = tmp;
			}
 
			int ans = 2 * (n - 1 - best) + best;
			if (ans == correct) return it / (double)limit;
		}
 
		return -1;
	}
};
 
struct Solution4 {
	random_t rnd;
 
	double solve(int correct) {
		if (m == n - 1) return 0;
 
		for (int it = 0; it < 100; it++) {
			double result = solveOne(correct, it < 50);
			if (result < -0.5) continue;
			return (it + result) / 100;
		}
 
		return -1;
	}
 
	int *u1, *v1, *u2, *v2;
	int permutation[MX];
	bool enabled[MX];
	DSU dsu;
 
	void getrandom_tSubst(int& x, int& y) {
		int k = rnd.next() % (m - n + 1);
		for (int i = 0; i < m; i++) {
			if (enabled[i] == false) {
				if (k == 0) y = i;
				else k--;
			}
		}
 
		rnd.permute(permutation, m);
 
		dsu.init(n);
		dsu.merge(u1[y], v1[y]);
		for (int i = 0; i < m; i++) {
			int e = permutation[i];
			if (enabled[e]) {
				int a = dsu.get(u1[e]);
				int b = dsu.get(v1[e]);
				if (a == b) x = e;
				dsu.merge(a, b);
			}
		}
	}
 
	int countComponents() {
		dsu.init(n);
		for (int i = 0; i < m; i++) {
			if (enabled[i] == false) continue;
			dsu.merge(u2[i], v2[i]);
		}
 
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			if (dsu.get(i) == i) cnt++;
		}
 
		return cnt;
	}
 
	double solveOne(int correct, bool swapGraphs) {
		const int limit = 300000 / m;
 
		if (swapGraphs) {
			u1 = ::u2;
			v1 = ::v2;
			u2 = ::u1;
			v2 = ::v1;
		}
		else {
			u1 = ::u1;
			v1 = ::v1;
			u2 = ::u2;
			v2 = ::v2;
		}
 
		rnd.permute(permutation, m);
 
		dsu.init(n);
		for (int i = 0; i < m; i++) {
			int x = dsu.get(u1[i]);
			int y = dsu.get(v1[i]);
			if (x != y) {
				dsu.merge(x, y);
				enabled[i] = true;
			}
			else {
				enabled[i] = false;
			}
		}
 
		double ee = 1.0;
		int best = countComponents(), curr = best;
		for (int it = 1; it <= limit; it++) {
			int x, y;
			getrandom_tSubst(x, y);
 
			enabled[x] = false;
			enabled[y] = true;
 
			int cnt = countComponents();
			if (cnt < curr || rnd.next() < (1LL << 32) * pow(ee, cnt - curr)) {
				curr = cnt;
				ee *= 0.988;
				if (cnt < best) best = cnt;
			}
			else {
				enabled[x] = true;
				enabled[y] = false;
			}
 
			int ans = n - 1 + best - 1;
			if (ans == correct) return it / (double)limit;
		}
 
		return -1;
	}
};
 
// The part above is an exact copy from the checker used on the server! //
//////////////////////////////////////////////////////////////////////////
 
void invalidInput() {
	printf("%s\n", "Invalid input!");
	exit(0);
}
 
int failed = 0;
void process(int id, double result) {
	printf("Solution #%d: ", id);
	if (result < -0.5) {
		printf("%s\n", "produced an incorrect answer (success).");
		failed++;
	}
	else {
		if (result < 0) result = 0;
		if (result > 1) result = 1;
		printf("produced a correct answer using %6.2f%% of the time limit (failure).\n", 100 * result);
	}
}
 
int main() {
	if (scanf("%d %d", &n, &m) != 2) invalidInput();
	if (n < 2 || n > MX) invalidInput();
	if (m < n - 1 || m > MX) invalidInput();
	for (int i = 0; i < m; i++) {
		if (scanf("%d %d", u1 + i, v1 + i) != 2) invalidInput();
		if (u1[i] < 1 || u1[i] > n) invalidInput();
		if (v1[i] < 1 || v1[i] > n) invalidInput();
		u1[i]--;
		v1[i]--;
	}
	for (int i = 0; i < m; i++) {
		if (scanf("%d %d", u2 + i, v2 + i) != 2) invalidInput();
		if (u2[i] < 1 || u2[i] > n) invalidInput();
		if (v2[i] < 1 || v2[i] > n) invalidInput();
		u2[i]--;
		v2[i]--;
	}
 
	DSU dsu1, dsu2;
	dsu1.init(n);
	dsu2.init(n);
	for (int i = 0; i < m; i++) {
		dsu1.merge(u1[i], v1[i]);
		dsu2.merge(u2[i], v2[i]);
	}
 
	for (int i = 0; i < n; i++) {
		if (dsu1.get(i) != dsu1.get(0)) invalidInput();
		if (dsu2.get(i) != dsu2.get(0)) invalidInput();
	}
 
	printf("The input is valid! N = %d; M = %d.\n\n", n, m);
 
	CorrectSolution sol;
	int correct = sol.solve();
 
	Solution1 sol1;
	process(1, sol1.solve(correct));
 
	Solution2 sol2;
	process(2, sol2.solve(correct));
 
	Solution3 sol3;
	process(3, sol3.solve(correct));
 
	Solution4 sol4;
	process(4, sol4.solve(correct));
 
	int score = 21 * failed;
	if (failed > 0) score += 2400 / (m < 100 ? 100 : m) - 8;
	printf("\nScore: %d points.\n", score);
 
	return 0;
}

LyogIEFuIGV4YW1wbGUgb2YgaG93IHRvIGNvbXBpbGUgYW5kIHVzZSB0aGUgY2hlY2tlcjoKICogICAgJCBnKysgY2hlY2tlci5jcHAgLW8gY2hlY2tlcgogKiAgICAkIGNoZWNrZXIgPCB5b3VyT3V0cHV0LnR4dAogKgogKiAgVGhlIGNoZWNrZXIgcmVhZHMgdGhlIHRlc3QgY2FzZSBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCAoc3RkaW4pIGFuZAogKiAgcHJpbnRzIGFuIGluZm9ybWF0aXZlIG1lc3NhZ2Ugd2l0aCB0aGUgcmVzdWx0cyBvZiB0aGUgaGV1cmlzdGljcyB0bwogKiAgdGhlIHN0YW5kYXJkIG91cHV0IChzdGRvdXQpLgogKgogKgogKiAgIyBEZXNjcmlwdGlvbiBvZiB0aGUgc29sdXRpb25zLgogKgogKiAgMC4gJ3N0cnVjdCBDb3JyZWN0U29sdXRpb24nIGltcGxlbWVudHMgdGhlIGludGVuZGVkIHNvbHV0aW9uIHVzaW5nCiAqICAgICBtYXRyb2lkIGludGVyc2VjdGlvbiwgd2hpY2ggaXMgZGVzY3JpYmVkIGluIHRoZSBlZGl0b3JpYWwgb2YgQ05OQ1QyLgogKgogKiAgMS4gJ3N0cnVjdCBTb2x1dGlvbjEnIGltcGxlbWVudHMgdGhlIGZvbGxvd2luZyByYW5kb21pemVkIGhldXJpc3RpYzoKICogICAgICAgIGEpIFNlbGVjdCBhIHJhbmRvbSBwZXJtdXRhdGlvbiBvZiB0aGUgZWRnZXM7CiAqICAgICAgICBiKSBTdGFydCB3aXRoIGJvdGggZ3JhcGhzIGVtcHR5IGFuZCBjb25zaWRlciB0aGUgZWRnZXMgb25lIGJ5IG9uZQogKiAgICAgICAgICAgaW4gdGhlIHNlbGVjdGVkIG9yZGVyOwogKiAgICAgICAgYykgSWYgdGhlIGNvbnNpZGVyZWQgZWRnZSBjYW4gYmUgYWRkZWQgdG8gYm90aCBncmFwaHMgd2l0aG91dAogKiAgICAgICAgICAgY3JlYXRpbmcgYW55IGN5Y2xlcyAtIGFkZCBpdCwgb3RoZXJ3aXNlIGRpc2NhcmQgaXQ7CiAqICAgICAgICBkKSBJZiBhdCB0aGUgZW5kIG9mIHRoZSBwcm9jZXNzICdrJyBlZGdlcyB3ZXJlIGFkZGVkIHRvIHRoZQogKiAgICAgICAgICAgZ3JhcGhzLCB1cGRhdGUgdGhlIGFuc3dlciB3aXRoIHRoZSB2YWx1ZSBvZiAnMiAqIG4gLSAyIC0gayc7CiAqICAgICAgICBlKSBSZXBlYXQgc3RlcHMgKGEpIHRocm91Z2ggKGQpICczMDAwMDAwMCAvIG0nIHRpbWVzIGFuZCByZXR1cm4KICogICAgICAgICAgIHRoZSBiZXN0IChtaW5pbWFsKSBhbnN3ZXIgZm91bmQuCiAqCiAqICAyLiAnc3RydWN0IFNvbHV0aW9uMicgaW1wbGVtZW50cyB0aGUgZm9sbG93aW5nIHJhbmRvbWl6ZWQgaGV1cmlzdGljOgogKiAgICAgICAgYSkgU2VsZWN0IGEgcmFuZG9tIHBlcm11dGF0aW9uIG9mIHRoZSBlZGdlczsKICogICAgICAgIGIpIFN0YXJ0IHdpdGggYm90aCBncmFwaHMgZW1wdHkgYW5kIGNvbnNpZGVyIHRoZSBlZGdlcyBvbmUgYnkgb25lCiAqICAgICAgICAgICBpbiB0aGUgc2VsZWN0ZWQgb3JkZXI7CiAqICAgICAgICBjKSBJZiB0aGUgY29uc2lkZXJlZCBlZGdlIGNvbm5lY3RzIHR3byBkaWZmZXJlbnQgY29ubmVjdGVkCiAqICAgICAgICAgICBjb21wb25lbnRzIGluIGF0IGxlYXN0IG9uZSBvZiB0aGUgZ3JhcGggLSBhZGQgaXQsIG90aGVyd2lzZQogKiAgICAgICAgICAgZGlzY2FyZCBpdDsKICogICAgICAgIGQpIERlbm90ZSB0aGUgbGlzdCBvZiBhZGRlZCBlZGdlcyB3aXRoICdMJywgcHJlc2VydmluZyBvcmRlcjsKICogICAgICAgIGUpIENvbnNpZGVyIGVhY2ggZWRnZSBmcm9tIHRoZSBsaXN0ICdMJywgaWYgaXQgaXMgYSBicmlkZ2UgaW4gYXQKICogICAgICAgICAgIGxlYXN0IG9mIHRoZSBncmFwaHMgLSBtb3ZlIGl0IHRvIHRoZSBiZWdpbm5pbmcgb2YgdGhlIGxpc3QgJ0wnLAogKiAgICAgICAgICAgb3RoZXJ3aXNlIGxlYXZlIGl0IGF0IGl0cyBwcmV2aW91cyBwb3NpdGlvbjsKICogICAgICAgIGYpIElmIHRoZSBzaXplIG9mIHRoZSBsaXN0ICdMJyBpcyAnaycgYW5kIGFsbCB0aGUgJ2snIGVkZ2VzIHdlcmUKICogICAgICAgICAgIG1vdmVkIGR1cmluZyBzdGVwIChlKSwgcmV0dXJuICdrJyBhcyB0aGUgYW5zd2VyOwogKiAgICAgICAgZykgT3RoZXJ3aXNlLCBnbyBiYWNrIHRvIHN0ZXAgKGIpIHVzaW5nIHRoZSBsaXN0ICdMJyBpbnN0ZWFkIG9mCiAqICAgICAgICAgICB0aGUgaW5pdGlhbCBwZXJtdXRhdGlvbiBnZW5lcmF0ZWQgZHVyaW5nIHN0ZXAgKGEpOwogKiAgICAgICAgaCkgUmVwZWF0IHN0ZXBzIChhKSB0aHJvdWdoIChnKSB1bnRpbCB0aGUgdG90YWwgc2l6ZSBvZiB0aGUgZ3JhcGhzCiAqICAgICAgICAgICAodmVydGljZXMgKyBlZGdlcykgY29uc2lkZXJlZCBkdXJpbmcgc3RlcCAoYikgcmVhY2hlcyAyMDAwMDAwMAogKiAgICAgICAgICAgYW5kIHJldHVybiB0aGUgYmVzdCBhbnN3ZXIgZm91bmQ7CiAqCiAqICAzLiAnc3RydWN0IFNvbHV0aW9uMycgaW1wbGVtZW50cyB0aGUgZm9sbG93aW5nIHJhbmRvbWl6ZWQgaGV1cmlzdGljOgogKiAgICAgICAgYSkgU3RhcnQgd2l0aCBhIHBhcmFtZXRlciAnZWUgPSAxLjAnOwogKiAgICAgICAgYikgU2VsZWN0IGEgcmFuZG9tIHBlcm11dGF0aW9uIG9mIHRoZSBlZGdlcyAnUCc7CiAqICAgICAgICBjKSBFeGVjdXRlIHN0ZXBzIChiKSBhbmQgKGMpIGZyb20gdGhlIHNvbHV0aW9uICgxKSB1c2luZyB0aGUgcGVyLQogKiAgICAgICAgICAgbXV0YXRpb24gJ1AnIGFuZCBkZW5vdGUgdGhlIG51bWJlciBvZiBhZGRlZCBlZGdlcyB3aXRoICdjdXJyJzsKICogICAgICAgIGQpIFNlbGVjdCBhIHBhaXIgb2YgcGVybXV0YXRpb24gZWxlbWVudHMgJ3gnIGFuZCAneScgYXQgcmFuZG9tOwogKiAgICAgICAgICAgYW5kIHN3YXAgdGhlIGVkZ2VzICdQW3hdJyBhbmQgJ1BbeV0nOwogKiAgICAgICAgZSkgRXhlY3V0ZSBzdGVwcyAoYikgYW5kIChjKSBmcm9tIHRoZSBzb2x1dGlvbiAoMSkgdXNpbmcgdGhlIHBlci0KICogICAgICAgICAgIG11dGF0aW9uICdQJyBhbmQgZGVub3RlIHRoZSBudW1iZXIgb2YgYWRkZWQgZWRnZXMgd2l0aCAnY250JzsKICogICAgICAgIGYpIElmICdjbnQgPiBjdXJyJyBnbyB0byBzdGVwIChpKTsKICogICAgICAgIGcpIE90aGVyd2lzZSB3aXRoIHByb2JhYmlsaXR5ICdwb3coZWUsIGN1cnIgLSBjbnQpJyBnbyB0byBzdGVwIChpKTsKICogICAgICAgIGgpIE90aGVyd2lzZSBzd2FwIHRoZSBlZGdlcyAnUFt4XScgYW5kICdQW3ldJyBiYWNrIGFuZCBnbyB0bwogKiAgICAgICAgICAgc3RlcCAoaik7CiAqICAgICAgICBpKSBVcGRhdGUgJ2VlIDo9IGVlICogMC45OTEnIGFuZCB1cGRhdGUgdGhlIGFuc3dlciB3aXRoIHRoZSB2YWx1ZQogKiAgICAgICAgICAgJzIgKiBuIC0gMiAtIGNudCc7CiAqICAgICAgICBqKSBGaW5pc2ggb25lIGl0ZXJhdGlvbjsKICogICAgICAgIGspIFJlcGVhdCB0aGUgc3RlcHMgKGMpIHRocm91Z2ggKGopICc2MDAwMDAwIC8gbScgdGltZXMgb24gZWFjaAogKiAgICAgICAgICAgaXRlcmF0aW9uIHVzaW5nIHRoZSBwZXJtdXRhdGlvbnMgJ1AnIG9idGFpbmVkIGFmdGVyIHRoZQogKiAgICAgICAgICAgcHJldmlvdXMgaXRlcmF0aW9uOwogKiAgICAgICAgbCkgU3RlcHMgKGEpIHRocm91Z2ggKGspIGFyZSByZXBlYXRlZCA1IHRpbWVzIGFuZCB0aGUgYmVzdCBhbnN3ZXIKICogICAgICAgICAgIGZvdW5kIGlzIHJldHVybmVkLgogKgogKiAgNC4gJ3N0cnVjdCBTb2x1dGlvbjQnIGltcGxlbWVudHMgdGhlIGZvbGxvd2luZyByYW5kb21pemVkIGhldXJpc3RpYzoKICogICAgICAgIGEpIFN0YXJ0IHdpdGggYSBwYXJhbWV0ZXIgJ2VlID0gMS4wJzsKICogICAgICAgIGIpIFNlbGVjdCBhIHJhbmRvbSBzcGFubmluZyB0cmVlIGluIHRoZSBmaXJzdCBncmFwaCBhbmQgY29uc2lkZXIKICogICAgICAgICAgIHRoZXNlIGVkZ2VzIHRvIGJlIGluaXRpYWxseSBlbmFibGVkIGFuZCBhbGwgb3RoZXIgLSBkaXNhYmxlZDsKICogICAgICAgIGMpIENvdW50IHRoZSBudW1iZXIgb2YgY29ubmVjdGVkIGNvbXBvbmVudHMgaW4gdGhlIHNlY29uZCBncmFwaCwKICogICAgICAgICAgIGluY2x1ZGluZyBvbmx5IGVuYWJsZWQgZWRnZXMsIGFuZCBkZW5vdGUgdGhlIGNvdW50IHdpdGggJ2N1cnInOwogKiAgICAgICAgZCkgQ2hvb3NlIGFuIGVkZ2UgJ3gnIGF0IHJhbmRvbSBhbW9uZyBjdXJyZW50bHkgZGlzYWJsZWQgZWRnZXM7CiAqICAgICAgICBlKSBDaG9vc2UgYW4gZWRnZSAneScgYXQgcmFuZG9tIGZyb20gdGhlIHBhdGggY29ubmVjdGluZyB0aGUKICogICAgICAgICAgIGVuZHBvaW50cyBvZiAneCcgaW4gdGhlIHRyZWUgZm9ybWVkIGJ5IGVuYWJsZWQgZWRnZXM7CiAqICAgICAgICBmKSBNYXJrIGVkZ2UgJ3gnIGFzIGRpc2FibGVkIGFuZCBlZGdlICd5JyBhcyBlbmFibGVkOwogKiAgICAgICAgZykgQ291bnQgdGhlIG51bWJlciBvZiBjb25uZWN0ZWQgY29tcG9uZW50cyBpbiB0aGUgc2Vjb25kIGdyYXBoLAogKiAgICAgICAgICAgaW5jbHVkaW5nIG9ubHkgZW5hYmxlZCBlZGdlcywgYW5kIGRlbm90ZSB0aGUgY291bnQgd2l0aCAnY250JzsKICogICAgICAgIGgpIElmICdjbnQgPCBjdXJyJyBnbyB0byBzdGVwIChrKTsKICogICAgICAgIGkpIE90aGVyd2lzZSB3aXRoIHByb2JhYmlsaXR5ICdwb3coZWUsIGNudCAtIGN1cnIpJyBnbyB0byBzdGVwIChrKTsKICogICAgICAgIGopIE90aGVyd2lzZSBtYXJrIHRoZSBlZGdlICd4JyBhcyBlbmFibGVkIGFuZCBlZGdlICd5JyBhcyBkaXNhYmxlZCwKICogICAgICAgICAgIHJldmVydGluZyB0aGUgc3RlcCAoZikgYW5kIGdvIHRvIHRoZSBzdGVwIChsKTsKICogICAgICAgIGspIFVwZGF0ZSAnZWUgOj0gZWUgKiAwLjk4OCcgYW5kIHVwZGF0ZSB0aGUgYW5zd2VyIHdpdGggdGhlIHZhbHVlCiAqICAgICAgICAgICAnbiAtIDEgKyBjbnQgLSAxJzsKICogICAgICAgIGwpIEZpbmlzaCBvbmUgaXRlcmF0aW9uOwogKiAgICAgICAgbSkgUmVwZWF0IHRoZSBzdGVwcyAoYykgdGhyb3VnaCAobCkgJzMwMDAwMCAvIG0nIHRpbWVzIG9uIGVhY2gKICogICAgICAgICAgIGl0ZXJ0aW9uIHVzaW5nIHRoZSBlbmFibGVkIGVkZ2VzIG9idGFpbmVkIGFmdGVyIHRoZSBwcmV2aW91cwogKiAgICAgICAgICAgaXRlcmF0aW9uOwogKiAgICAgICAgbikgU3RlcHMgKGEpIHRocm91Z2ggKG0pIGFyZSByZXBlYXRlZCA1MCB0aW1lcyB3aXRoIHRoZSB0d28gZ3JhcGhzCiAqICAgICAgICAgICBpbiB0aGVpciBvcmlnaW5hbCBvcmRlciBhbmQgNTAgdGltZXMgd2l0aCB0aGUgZ3JhcGhzIGJlaW5nCiAqICAgICAgICAgICBzd2FwcGVkLiBUaGUgYmVzdCBhbnN3ZXIgZm91bmQgaXMgcmV0dXJuZWQuCiAqLwoKI2luY2x1ZGUgPHZlY3Rvcj4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpleHRlcm4gIkMiIHsKCWludCBzY2FuZihjb25zdCBjaGFyKiwgLi4uKTsKCWludCBwcmludGYoY29uc3QgY2hhciosIC4uLik7Cgl2b2lkIGV4aXQoaW50KTsKCWRvdWJsZSBwb3coZG91YmxlLCBkb3VibGUpOwp9Cgpjb25zdCB1bnNpZ25lZCBzZWVkID0gMHgxMjM0NTY3ODsKCi8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vCi8vIFRoZSBwYXJ0IGJlbG93IGlzIGFuIGV4YWN0IGNvcHkgZnJvbSB0aGUgY2hlY2tlciB1c2VkIG9uIHRoZSBzZXJ2ZXIhIC8vCgpzdHJ1Y3QgcmFuZG9tX3QgewoJdW5zaWduZWQgc3RhdGU7CglyYW5kb21fdCgpIDogc3RhdGUoc2VlZCkgeyB9Cgl1bnNpZ25lZCBuZXh0KCkgewoJCXN0YXRlIF49IHN0YXRlIDw8IDEzOwoJCXN0YXRlIF49IHN0YXRlID4+IDE3OwoJCXN0YXRlIF49IHN0YXRlIDw8IDU7CgkJcmV0dXJuIHN0YXRlOwoJfQoJdm9pZCBwZXJtdXRlKGludCogcGVybXV0YXRpb24sIGludCBuKSB7CgkJZm9yIChpbnQgayA9IDA7IGsgPCBuOyBrKyspIHsKCQkJcGVybXV0YXRpb25ba10gPSBrOwoJCQlpbnQgcCA9IG5leHQoKSAlIChrICsgMSk7CgkJCWludCB0bXAgPSBwZXJtdXRhdGlvbltwXTsKCQkJcGVybXV0YXRpb25bcF0gPSBrOwoJCQlwZXJtdXRhdGlvbltrXSA9IHRtcDsKCQl9Cgl9Cn07Cgpjb25zdCBpbnQgTVggPSAzMDA7CgpzdHJ1Y3QgRFNVIHsKCWludCBwW01YXTsKCQoJdm9pZCBpbml0KGludCBuKSB7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHBbaV0gPSBpOwoJfQoJCglpbnQgZ2V0KGludCB2KSB7CgkJaWYgKHBbdl0gIT0gdikgcFt2XSA9IGdldChwW3ZdKTsKCQlyZXR1cm4gcFt2XTsKCX0KCQoJdm9pZCBtZXJnZShpbnQgdSwgaW50IHYpIHsKCQl1ID0gZ2V0KHUpOwoJCXYgPSBnZXQodik7CgkJcFt1XSA9IHY7Cgl9Cn07CgppbnQgbiwgbTsKaW50IHUxW01YXSwgdjFbTVhdLCB1MltNWF0sIHYyW01YXTsKCnN0cnVjdCBHcmFwaCB7CglpbnQgbGFzdEVkZ2VbTVhdLCBlZTsKCXN0cnVjdCB7IGludCB2LCBpZCwgbmV4dDsgfSBlWzIgKiBNWF07CgkKCXZvaWQgaW5pdCgpIHsKCQllZSA9IDA7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIGxhc3RFZGdlW2ldID0gLTE7Cgl9CgkKCXZvaWQgYWRkRWRnZShpbnQgdSwgaW50IHYsIGludCBpZCkgewoJCWVbZWVdLnYgPSB2OwoJCWVbZWVdLmlkID0gaWQ7CgkJZVtlZV0ubmV4dCA9IGxhc3RFZGdlW3VdOwoJCWxhc3RFZGdlW3VdID0gZWUrKzsKCQkKCQllW2VlXS52ID0gdTsKCQllW2VlXS5pZCA9IGlkOwoJCWVbZWVdLm5leHQgPSBsYXN0RWRnZVt2XTsKCQlsYXN0RWRnZVt2XSA9IGVlKys7Cgl9CgkKCWJvb2wgdmlzW01YXTsKCWludCB1cFtNWF0sIGRlcFtNWF07Cglib29sKiBicmlkZ2U7CgkKCXZvaWQgZGZzKGludCB2LCBpbnQgZWRnZVRvUGFyZW50LCBpbnQgZGVwdGgpIHsKCQl2aXNbdl0gPSB0cnVlOwoJCWRlcFt2XSA9IGRlcHRoOwoJCXVwW3ZdID0gZGVwdGg7CgkJZm9yIChpbnQgaSA9IGxhc3RFZGdlW3ZdOyBpICE9IC0xOyBpID0gZVtpXS5uZXh0KSB7CgkJCWlmIChlW2ldLmlkID09IGVkZ2VUb1BhcmVudCkgY29udGludWU7CgkJCQoJCQlpbnQgdSA9IGVbaV0udjsKCQkJaWYgKHZpc1t1XSA9PSBmYWxzZSkgewoJCQkJZGZzKHUsIGVbaV0uaWQsIGRlcHRoICsgMSk7CgkJCQlpZiAodXBbdV0gPiBkZXB0aCkgYnJpZGdlW2VbaV0uaWRdID0gdHJ1ZTsKCQkJfQoJCQkKCQkJaWYgKHVwW3VdIDwgdXBbdl0pIHVwW3ZdID0gdXBbdV07CgkJfQoJfQoJCgl2b2lkIG1hcmtCcmlkZ2VzKGJvb2wqIGlzQnJpZGdlKSB7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHZpc1tpXSA9IGZhbHNlOwoJCQoJCWJyaWRnZSA9IGlzQnJpZGdlOwoJCWRmcygwLCAtMSwgMCk7Cgl9Cn07CgppbnQgZ2V0Qm90aEFjeWNsaWMoaW50KiBwZXJtdXRhdGlvbikgewoJc3RhdGljIERTVSBkc3UxLCBkc3UyOwoJCglkc3UxLmluaXQobik7Cglkc3UyLmluaXQobik7CgkKCWludCBjbnQgPSAwOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIHsKCQlpbnQgZSA9IHBlcm11dGF0aW9uW2ldOwoJCWludCB4MSA9IGRzdTEuZ2V0KHUxW2VdKTsKCQlpbnQgeTEgPSBkc3UxLmdldCh2MVtlXSk7CgkJaWYgKHgxID09IHkxKSBjb250aW51ZTsKCQlpbnQgeDIgPSBkc3UyLmdldCh1MltlXSk7CgkJaW50IHkyID0gZHN1Mi5nZXQodjJbZV0pOwoJCWlmICh4MiAhPSB5MikgewoJCQljbnQrKzsKCQkJZHN1MS5tZXJnZSh4MSwgeTEpOwoJCQlkc3UyLm1lcmdlKHgyLCB5Mik7CgkJfQoJfQoJCglyZXR1cm4gY250Owp9CgpzdHJ1Y3QgRXhjaGFuZ2VHcmFwaCB7Cgl2ZWN0b3I8aW50PiBHW01YXTsKCQoJdm9pZCBjbGVhcigpIHsKCQlmb3IgKGludCBpID0gMDsgaSA8IG07IGkrKykgR1tpXS5jbGVhcigpOwoJfQoKCXZvaWQgYWRkRWRnZShpbnQgdSwgaW50IHYpIHsKCQlHW3VdLnB1c2hfYmFjayh2KTsKCX0KCQoJYm9vbCBmaW5kQXVnbWVudGFsUGF0aCh2ZWN0b3I8aW50PiBmcm9tLCB2ZWN0b3I8aW50PiB0bywgYm9vbCogZW5hYmxlZCkgewoJCXZlY3RvcjxpbnQ+IHBhcihtLCAtMSksIGRpc3QobSksIHF1ZXVlOwoJCWZvciAoc2l6ZV90IGkgPSAwOyBpIDwgZnJvbS5zaXplKCk7IGkrKykgewoJCQlpbnQgdiA9IGZyb21baV07CgkJCXF1ZXVlLnB1c2hfYmFjayh2KTsKCQkJcGFyW3ZdID0gLTI7CgkJCWRpc3Rbdl0gPSAwOwoJCX0KCQkKCQlmb3IgKHNpemVfdCBpID0gMDsgaSA8IHF1ZXVlLnNpemUoKTsgaSsrKSB7CgkJCWludCB2ID0gcXVldWVbaV07CgkJCWZvciAoc2l6ZV90IGogPSAwOyBqIDwgR1t2XS5zaXplKCk7IGorKykgewoJCQkJaW50IHUgPSBHW3ZdW2pdOwoJCQkJaWYgKHBhclt1XSA9PSAtMSkgewoJCQkJCXF1ZXVlLnB1c2hfYmFjayh1KTsKCQkJCQlwYXJbdV0gPSB2OwoJCQkJCWRpc3RbdV0gPSBkaXN0W3ZdICsgMTsKCQkJCX0KCQkJfQoJCX0KCQkKCQlpbnQgdGFyZ2V0ID0gLTE7CgkJZm9yIChzaXplX3QgaSA9IDA7IGkgPCB0by5zaXplKCk7IGkrKykgewoJCQlpbnQgdiA9IHRvW2ldOwoJCQlpZiAocGFyW3ZdID09IC0xKSBjb250aW51ZTsKCQkJaWYgKHRhcmdldCA9PSAtMSB8fCBkaXN0W3ZdIDwgZGlzdFt0YXJnZXRdKSB0YXJnZXQgPSB2OwoJCX0KCQkKCQlpZiAodGFyZ2V0ICE9IC0xKSB7CgkJCXdoaWxlICh0YXJnZXQgIT0gLTIpIHsKCQkJCWVuYWJsZWRbdGFyZ2V0XSA9IG5vdCBlbmFibGVkW3RhcmdldF07CgkJCQl0YXJnZXQgPSBwYXJbdGFyZ2V0XTsKCQkJfQoJCQkKCQkJcmV0dXJuIHRydWU7CgkJfQoJCQoJCXJldHVybiBmYWxzZTsKCX0KfTsKCnN0cnVjdCBDb3JyZWN0U29sdXRpb24gewoJRXhjaGFuZ2VHcmFwaCBleGNoYW5nZUdyYXBoOwoJYm9vbCBlbmFibGVkW01YXTsKCQoJaW50IHNvbHZlKCkgewoJCWZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSBlbmFibGVkW2ldID0gdHJ1ZTsKCQkKCQlpbnQgYW5zID0gbTsKCQl3aGlsZSAodHJ1ZSkgewoJCQlleGNoYW5nZUdyYXBoLmNsZWFyKCk7CgkJCQoJCQl2ZWN0b3I8aW50PiBZMSA9IGdldE5vbkJyaWRnZXModTEsIHYxKTsKCQkJdmVjdG9yPGludD4gWTIgPSBnZXROb25CcmlkZ2VzKHUyLCB2Mik7CgkJCQoJCQlpZiAoZXhjaGFuZ2VHcmFwaC5maW5kQXVnbWVudGFsUGF0aChZMSwgWTIsIGVuYWJsZWQpKSB7CgkJCQlhbnMtLTsKCQkJCWNvbnRpbnVlOwoJCQl9CgkJCQoJCQlmb3IgKGludCBlID0gMDsgZSA8IG07IGUrKykgewoJCQkJaWYgKGVuYWJsZWRbZV0pIGNvbnRpbnVlOwoJCQkJCgkJCQllbmFibGVkW2VdID0gdHJ1ZTsKCQkJCQoJCQkJdmVjdG9yPGludD4gZWRnZXNUbyA9IGdldE5vbkJyaWRnZXModTEsIHYxKTsKCQkJCXZlY3RvcjxpbnQ+IGVkZ2VzRnJvbSA9IGdldE5vbkJyaWRnZXModTIsIHYyKTsKCQkJCQoJCQkJZW5hYmxlZFtlXSA9IGZhbHNlOwoJCQkJCgkJCQlmb3IgKHNpemVfdCBpID0gMDsgaSA8IGVkZ2VzVG8uc2l6ZSgpOyBpKyspIHsKCQkJCQlleGNoYW5nZUdyYXBoLmFkZEVkZ2UoZSwgZWRnZXNUb1tpXSk7CgkJCQl9CgkJCQlmb3IgKHNpemVfdCBpID0gMDsgaSA8IGVkZ2VzRnJvbS5zaXplKCk7IGkrKykgewoJCQkJCWV4Y2hhbmdlR3JhcGguYWRkRWRnZShlZGdlc0Zyb21baV0sIGUpOwoJCQkJfQoJCQl9CgkJCQoJCQlpZiAoZXhjaGFuZ2VHcmFwaC5maW5kQXVnbWVudGFsUGF0aChZMSwgWTIsIGVuYWJsZWQpKSB7CgkJCQlhbnMtLTsKCQkJfQoJCQllbHNlIHsKCQkJCWJyZWFrOwoJCQl9CgkJfQoJCQoJCXJldHVybiBhbnM7Cgl9CgkKCUdyYXBoIEc7Cglib29sIGlzQnJpZGdlW01YXTsKCXZlY3RvcjxpbnQ+IGdldE5vbkJyaWRnZXMoaW50KiB1LCBpbnQqIHYpIHsKCQlHLmluaXQoKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IG07IGkrKykgewoJCQlpZiAoZW5hYmxlZFtpXSkgewoJCQkJRy5hZGRFZGdlKHVbaV0sIHZbaV0sIGkpOwoJCQkJaXNCcmlkZ2VbaV0gPSBmYWxzZTsKCQkJfQoJCX0KCQkKCQlHLm1hcmtCcmlkZ2VzKGlzQnJpZGdlKTsKCQkKCQl2ZWN0b3I8aW50PiByZXN1bHQ7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIHsKCQkJaWYgKGVuYWJsZWRbaV0gJiYgaXNCcmlkZ2VbaV0gPT0gZmFsc2UpIHsKCQkJCXJlc3VsdC5wdXNoX2JhY2soaSk7CgkJCX0KCQl9CgkJCgkJcmV0dXJuIHJlc3VsdDsKCX0KfTsKCnN0cnVjdCBTb2x1dGlvbjEgewoJaW50IHBlcm11dGF0aW9uW01YXTsKCQoJZG91YmxlIHNvbHZlKGludCBjb3JyZWN0KSB7CgkJY29uc3QgaW50IGxpbWl0ID0gMzAwMDAwMDAgLyBtOwoJCQoJCXJhbmRvbV90IHJuZDsKCQlmb3IgKGludCBpdCA9IDE7IGl0IDw9IGxpbWl0OyBpdCsrKSB7CgkJCXJuZC5wZXJtdXRlKHBlcm11dGF0aW9uLCBtKTsKCQkJaW50IGNudCA9IGdldEJvdGhBY3ljbGljKHBlcm11dGF0aW9uKTsKCQkJaW50IGFucyA9IDIgKiAobiAtIDEgLSBjbnQpICsgY250OwoJCQlpZiAoYW5zID09IGNvcnJlY3QpIHJldHVybiBpdCAvIChkb3VibGUpbGltaXQ7CgkJfQoJCQoJCXJldHVybiAtMTsKCX0KfTsKCnN0cnVjdCBTb2x1dGlvbjIgewoJaW50IHBlcm11dGF0aW9uW01YXSwgc2VsZWN0ZWRbTVhdLCB0aW1lU3BlbnQ7Cglib29sIGlzQnJpZGdlW01YXTsKCQoJZG91YmxlIHNvbHZlKGludCBjb3JyZWN0KSB7CgkJY29uc3QgaW50IGxpbWl0ID0gMjAwMDAwMDA7CgkJdGltZVNwZW50ID0gMDsKCQkKCQlyYW5kb21fdCBybmQ7CgkJCgkJd2hpbGUgKHRpbWVTcGVudCA8IGxpbWl0KSB7CgkJCXJuZC5wZXJtdXRlKHBlcm11dGF0aW9uLCBtKTsKCQkJaW50IGFucyA9IHNvbHZlT25lKG0pOwoJCQlpZiAoYW5zID09IGNvcnJlY3QpIHJldHVybiB0aW1lU3BlbnQgLyAoZG91YmxlKWxpbWl0OwoJCX0KCQkKCQlyZXR1cm4gLTE7Cgl9CgkKCURTVSBkc3UxLCBkc3UyOwoJaW50IHNvbHZlT25lKGludCBjbnQpIHsKCQl0aW1lU3BlbnQgKz0gbiArIGNudDsKCQkKCQlkc3UxLmluaXQobik7CgkJZHN1Mi5pbml0KG4pOwoJCQoJCWludCB1c2VkID0gMDsKCQlmb3IgKGludCBpID0gMDsgaSA8IGNudDsgaSsrKSB7CgkJCWludCBlID0gcGVybXV0YXRpb25baV07CgkJCWludCB4MSA9IGRzdTEuZ2V0KHUxW2VdKTsKCQkJaW50IHkxID0gZHN1MS5nZXQodjFbZV0pOwoJCQlpbnQgeDIgPSBkc3UyLmdldCh1MltlXSk7CgkJCWludCB5MiA9IGRzdTIuZ2V0KHYyW2VdKTsKCQkJaWYgKHgxICE9IHkxIHx8IHgyICE9IHkyKSB7CgkJCQlzZWxlY3RlZFt1c2VkKytdID0gZTsKCQkJCWlzQnJpZGdlW2VdID0gZmFsc2U7CgkJCQlkc3UxLm1lcmdlKHgxLCB5MSk7CgkJCQlkc3UyLm1lcmdlKHgyLCB5Mik7CgkJCX0KCQl9CgkJCgkJZ2V0QnJpZGdlcyh1c2VkLCB1MSwgdjEpOwoJCWdldEJyaWRnZXModXNlZCwgdTIsIHYyKTsKCQkKCQlpbnQgYnJpZGdlcyA9IDA7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCB1c2VkOyBpKyspIHsKCQkJaW50IGUgPSBzZWxlY3RlZFtpXTsKCQkJaWYgKGlzQnJpZGdlW2VdKSB7CgkJCQlwZXJtdXRhdGlvblticmlkZ2VzKytdID0gZTsKCQkJfQoJCX0KCQkKCQlmb3IgKGludCBpID0gMCwgaiA9IGJyaWRnZXM7IGkgPCB1c2VkOyBpKyspIHsKCQkJaW50IGUgPSBzZWxlY3RlZFtpXTsKCQkJaWYgKGlzQnJpZGdlW2VdID09IGZhbHNlKSB7CgkJCQlwZXJtdXRhdGlvbltqKytdID0gZTsKCQkJfQoJCX0KCQkKCQlpZiAoYnJpZGdlcyA9PSB1c2VkKSByZXR1cm4gdXNlZDsKCQlyZXR1cm4gc29sdmVPbmUodXNlZCk7Cgl9CgkKCUdyYXBoIEc7Cgl2b2lkIGdldEJyaWRnZXMoaW50IGNudCwgaW50KiB1LCBpbnQqIHYpIHsKCQlHLmluaXQoKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IGNudDsgaSsrKSB7CgkJCWludCBlID0gc2VsZWN0ZWRbaV07CgkJCUcuYWRkRWRnZSh1W2VdLCB2W2VdLCBlKTsKCQl9CgkJCgkJRy5tYXJrQnJpZGdlcyhpc0JyaWRnZSk7Cgl9Cn07CgpzdHJ1Y3QgU29sdXRpb24zIHsKCXJhbmRvbV90IHJuZDsKCQoJZG91YmxlIHNvbHZlKGludCBjb3JyZWN0KSB7CgkJaWYgKG0gPT0gbiAtIDEpIHJldHVybiAwOwoJCQoJCWZvciAoaW50IGl0ID0gMDsgaXQgPCA1OyBpdCsrKSB7CgkJCWRvdWJsZSByZXN1bHQgPSBzb2x2ZU9uZShjb3JyZWN0KTsKCQkJaWYgKHJlc3VsdCA8IC0wLjUpIGNvbnRpbnVlOwoJCQlyZXR1cm4gKGl0ICsgcmVzdWx0KSAvIDU7CgkJfQoJCQoJCXJldHVybiAtMTsKCX0KCQoJaW50IHBlcm11dGF0aW9uW01YXTsKCWRvdWJsZSBzb2x2ZU9uZShpbnQgY29ycmVjdCkgewoJCWNvbnN0IGludCBsaW1pdCA9IDYwMDAwMDAgLyBtOwoJCQoJCXJuZC5wZXJtdXRlKHBlcm11dGF0aW9uLCBtKTsKCQkKCQlkb3VibGUgZWUgPSAxLjA7CgkJaW50IGJlc3QgPSBnZXRCb3RoQWN5Y2xpYyhwZXJtdXRhdGlvbiksIGN1cnIgPSBiZXN0OwoJCWZvciAoaW50IGl0ID0gMTsgaXQgPD0gbGltaXQ7IGl0KyspIHsKCQkJaW50IHgsIHk7CgkJCWRvIHsKCQkJCXggPSBybmQubmV4dCgpICUgbTsKCQkJCXkgPSBybmQubmV4dCgpICUgbTsKCQkJfSB3aGlsZSAoeCA9PSB5KTsKCQkJCgkJCWludCB0bXAgPSBwZXJtdXRhdGlvblt4XTsKCQkJcGVybXV0YXRpb25beF0gPSBwZXJtdXRhdGlvblt5XTsKCQkJcGVybXV0YXRpb25beV0gPSB0bXA7CgkJCQoJCQlpbnQgY250ID0gZ2V0Qm90aEFjeWNsaWMocGVybXV0YXRpb24pOwoJCQlpZiAoY250ID4gY3VyciB8fCBybmQubmV4dCgpIDwgKDFMTCA8PCAzMikgKiBwb3coZWUsIGN1cnIgLSBjbnQpKSB7CgkJCQljdXJyID0gY250OwoJCQkJZWUgKj0gMC45OTE7CgkJCQlpZiAoY250ID4gYmVzdCkgYmVzdCA9IGNudDsKCQkJfQoJCQllbHNlIHsKCQkJCXRtcCA9IHBlcm11dGF0aW9uW3hdOwoJCQkJcGVybXV0YXRpb25beF0gPSBwZXJtdXRhdGlvblt5XTsKCQkJCXBlcm11dGF0aW9uW3ldID0gdG1wOwoJCQl9CgkJCQoJCQlpbnQgYW5zID0gMiAqIChuIC0gMSAtIGJlc3QpICsgYmVzdDsKCQkJaWYgKGFucyA9PSBjb3JyZWN0KSByZXR1cm4gaXQgLyAoZG91YmxlKWxpbWl0OwoJCX0KCQkKCQlyZXR1cm4gLTE7Cgl9Cn07CgpzdHJ1Y3QgU29sdXRpb240IHsKCXJhbmRvbV90IHJuZDsKCQoJZG91YmxlIHNvbHZlKGludCBjb3JyZWN0KSB7CgkJaWYgKG0gPT0gbiAtIDEpIHJldHVybiAwOwoJCQoJCWZvciAoaW50IGl0ID0gMDsgaXQgPCAxMDA7IGl0KyspIHsKCQkJZG91YmxlIHJlc3VsdCA9IHNvbHZlT25lKGNvcnJlY3QsIGl0IDwgNTApOwoJCQlpZiAocmVzdWx0IDwgLTAuNSkgY29udGludWU7CgkJCXJldHVybiAoaXQgKyByZXN1bHQpIC8gMTAwOwoJCX0KCQkKCQlyZXR1cm4gLTE7Cgl9CgkKCWludCAqdTEsICp2MSwgKnUyLCAqdjI7CglpbnQgcGVybXV0YXRpb25bTVhdOwoJYm9vbCBlbmFibGVkW01YXTsKCURTVSBkc3U7CgkKCXZvaWQgZ2V0cmFuZG9tX3RTdWJzdChpbnQmIHgsIGludCYgeSkgewoJCWludCBrID0gcm5kLm5leHQoKSAlIChtIC0gbiArIDEpOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CgkJCWlmIChlbmFibGVkW2ldID09IGZhbHNlKSB7CgkJCQlpZiAoayA9PSAwKSB5ID0gaTsKCQkJCWVsc2Ugay0tOwoJCQl9CgkJfQoJCQoJCXJuZC5wZXJtdXRlKHBlcm11dGF0aW9uLCBtKTsKCQkKCQlkc3UuaW5pdChuKTsKCQlkc3UubWVyZ2UodTFbeV0sIHYxW3ldKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IG07IGkrKykgewoJCQlpbnQgZSA9IHBlcm11dGF0aW9uW2ldOwoJCQlpZiAoZW5hYmxlZFtlXSkgewoJCQkJaW50IGEgPSBkc3UuZ2V0KHUxW2VdKTsKCQkJCWludCBiID0gZHN1LmdldCh2MVtlXSk7CgkJCQlpZiAoYSA9PSBiKSB4ID0gZTsKCQkJCWRzdS5tZXJnZShhLCBiKTsKCQkJfQoJCX0KCX0KCQoJaW50IGNvdW50Q29tcG9uZW50cygpIHsKCQlkc3UuaW5pdChuKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IG07IGkrKykgewoJCQlpZiAoZW5hYmxlZFtpXSA9PSBmYWxzZSkgY29udGludWU7CgkJCWRzdS5tZXJnZSh1MltpXSwgdjJbaV0pOwoJCX0KCQkKCQlpbnQgY250ID0gMDsKCQlmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewoJCQlpZiAoZHN1LmdldChpKSA9PSBpKSBjbnQrKzsKCQl9CgkJCgkJcmV0dXJuIGNudDsKCX0KCQoJZG91YmxlIHNvbHZlT25lKGludCBjb3JyZWN0LCBib29sIHN3YXBHcmFwaHMpIHsKCQljb25zdCBpbnQgbGltaXQgPSAzMDAwMDAgLyBtOwoJCQoJCWlmIChzd2FwR3JhcGhzKSB7CgkJCXUxID0gOjp1MjsKCQkJdjEgPSA6OnYyOwoJCQl1MiA9IDo6dTE7CgkJCXYyID0gOjp2MTsKCQl9CgkJZWxzZSB7CgkJCXUxID0gOjp1MTsKCQkJdjEgPSA6OnYxOwoJCQl1MiA9IDo6dTI7CgkJCXYyID0gOjp2MjsKCQl9CgkJCgkJcm5kLnBlcm11dGUocGVybXV0YXRpb24sIG0pOwoJCQoJCWRzdS5pbml0KG4pOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CgkJCWludCB4ID0gZHN1LmdldCh1MVtpXSk7CgkJCWludCB5ID0gZHN1LmdldCh2MVtpXSk7CgkJCWlmICh4ICE9IHkpIHsKCQkJCWRzdS5tZXJnZSh4LCB5KTsKCQkJCWVuYWJsZWRbaV0gPSB0cnVlOwoJCQl9CgkJCWVsc2UgewoJCQkJZW5hYmxlZFtpXSA9IGZhbHNlOwoJCQl9CgkJfQoJCQoJCWRvdWJsZSBlZSA9IDEuMDsKCQlpbnQgYmVzdCA9IGNvdW50Q29tcG9uZW50cygpLCBjdXJyID0gYmVzdDsKCQlmb3IgKGludCBpdCA9IDE7IGl0IDw9IGxpbWl0OyBpdCsrKSB7CgkJCWludCB4LCB5OwoJCQlnZXRyYW5kb21fdFN1YnN0KHgsIHkpOwoJCQkKCQkJZW5hYmxlZFt4XSA9IGZhbHNlOwoJCQllbmFibGVkW3ldID0gdHJ1ZTsKCQkJCgkJCWludCBjbnQgPSBjb3VudENvbXBvbmVudHMoKTsKCQkJaWYgKGNudCA8IGN1cnIgfHwgcm5kLm5leHQoKSA8ICgxTEwgPDwgMzIpICogcG93KGVlLCBjbnQgLSBjdXJyKSkgewoJCQkJY3VyciA9IGNudDsKCQkJCWVlICo9IDAuOTg4OwoJCQkJaWYgKGNudCA8IGJlc3QpIGJlc3QgPSBjbnQ7CgkJCX0KCQkJZWxzZSB7CgkJCQllbmFibGVkW3hdID0gdHJ1ZTsKCQkJCWVuYWJsZWRbeV0gPSBmYWxzZTsKCQkJfQoJCQkKCQkJaW50IGFucyA9IG4gLSAxICsgYmVzdCAtIDE7CgkJCWlmIChhbnMgPT0gY29ycmVjdCkgcmV0dXJuIGl0IC8gKGRvdWJsZSlsaW1pdDsKCQl9CgkJCgkJcmV0dXJuIC0xOwoJfQp9OwoKLy8gVGhlIHBhcnQgYWJvdmUgaXMgYW4gZXhhY3QgY29weSBmcm9tIHRoZSBjaGVja2VyIHVzZWQgb24gdGhlIHNlcnZlciEgLy8KLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KCnZvaWQgaW52YWxpZElucHV0KCkgewoJcHJpbnRmKCIlc1xuIiwgIkludmFsaWQgaW5wdXQhIik7CglleGl0KDApOwp9CgppbnQgZmFpbGVkID0gMDsKdm9pZCBwcm9jZXNzKGludCBpZCwgZG91YmxlIHJlc3VsdCkgewoJcHJpbnRmKCJTb2x1dGlvbiAjJWQ6ICIsIGlkKTsKCWlmIChyZXN1bHQgPCAtMC41KSB7CgkJcHJpbnRmKCIlc1xuIiwgInByb2R1Y2VkIGFuIGluY29ycmVjdCBhbnN3ZXIgKHN1Y2Nlc3MpLiIpOwoJCWZhaWxlZCsrOwoJfQoJZWxzZSB7CgkJaWYgKHJlc3VsdCA8IDApIHJlc3VsdCA9IDA7CgkJaWYgKHJlc3VsdCA+IDEpIHJlc3VsdCA9IDE7CgkJcHJpbnRmKCJwcm9kdWNlZCBhIGNvcnJlY3QgYW5zd2VyIHVzaW5nICU2LjJmJSUgb2YgdGhlIHRpbWUgbGltaXQgKGZhaWx1cmUpLlxuIiwgMTAwICogcmVzdWx0KTsKCX0KfQoKaW50IG1haW4oKSB7CglpZiAoc2NhbmYoIiVkICVkIiwgJm4sICZtKSAhPSAyKSBpbnZhbGlkSW5wdXQoKTsKCWlmIChuIDwgMiB8fCBuID4gTVgpIGludmFsaWRJbnB1dCgpOwoJaWYgKG0gPCBuIC0gMSB8fCBtID4gTVgpIGludmFsaWRJbnB1dCgpOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIHsKCQlpZiAoc2NhbmYoIiVkICVkIiwgdTEgKyBpLCB2MSArIGkpICE9IDIpIGludmFsaWRJbnB1dCgpOwoJCWlmICh1MVtpXSA8IDEgfHwgdTFbaV0gPiBuKSBpbnZhbGlkSW5wdXQoKTsKCQlpZiAodjFbaV0gPCAxIHx8IHYxW2ldID4gbikgaW52YWxpZElucHV0KCk7CgkJdTFbaV0tLTsKCQl2MVtpXS0tOwoJfQoJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIHsKCQlpZiAoc2NhbmYoIiVkICVkIiwgdTIgKyBpLCB2MiArIGkpICE9IDIpIGludmFsaWRJbnB1dCgpOwoJCWlmICh1MltpXSA8IDEgfHwgdTJbaV0gPiBuKSBpbnZhbGlkSW5wdXQoKTsKCQlpZiAodjJbaV0gPCAxIHx8IHYyW2ldID4gbikgaW52YWxpZElucHV0KCk7CgkJdTJbaV0tLTsKCQl2MltpXS0tOwoJfQoJCglEU1UgZHN1MSwgZHN1MjsKCWRzdTEuaW5pdChuKTsKCWRzdTIuaW5pdChuKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CgkJZHN1MS5tZXJnZSh1MVtpXSwgdjFbaV0pOwoJCWRzdTIubWVyZ2UodTJbaV0sIHYyW2ldKTsKCX0KCQoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKCQlpZiAoZHN1MS5nZXQoaSkgIT0gZHN1MS5nZXQoMCkpIGludmFsaWRJbnB1dCgpOwoJCWlmIChkc3UyLmdldChpKSAhPSBkc3UyLmdldCgwKSkgaW52YWxpZElucHV0KCk7Cgl9CgkKCXByaW50ZigiVGhlIGlucHV0IGlzIHZhbGlkISBOID0gJWQ7IE0gPSAlZC5cblxuIiwgbiwgbSk7CgkKCUNvcnJlY3RTb2x1dGlvbiBzb2w7CglpbnQgY29ycmVjdCA9IHNvbC5zb2x2ZSgpOwoJCglTb2x1dGlvbjEgc29sMTsKCXByb2Nlc3MoMSwgc29sMS5zb2x2ZShjb3JyZWN0KSk7CgkKCVNvbHV0aW9uMiBzb2wyOwoJcHJvY2VzcygyLCBzb2wyLnNvbHZlKGNvcnJlY3QpKTsKCQoJU29sdXRpb24zIHNvbDM7Cglwcm9jZXNzKDMsIHNvbDMuc29sdmUoY29ycmVjdCkpOwoJCglTb2x1dGlvbjQgc29sNDsKCXByb2Nlc3MoNCwgc29sNC5zb2x2ZShjb3JyZWN0KSk7CgkKCWludCBzY29yZSA9IDIxICogZmFpbGVkOwoJaWYgKGZhaWxlZCA+IDApIHNjb3JlICs9IDI0MDAgLyAobSA8IDEwMCA/IDEwMCA6IG0pIC0gODsKCXByaW50ZigiXG5TY29yZTogJWQgcG9pbnRzLlxuIiwgc2NvcmUpOwoJCglyZXR1cm4gMDsKfQo=

Success #stdin #stdout 3.72s 4416KB

stdin

copy

MjIyIDI1NQoxNSA5NAo2IDMxCjI1IDY0CjEzMiAxNDAKNzggMTM5CjYyIDE1MQoyNCA1NQoxMDAgMTc4CjExOCAyMjAKMTYgNDkKMTIyIDEyNAo4OSAxNDcKMTc5IDMyCjI3IDgyCjM0IDkzCjUzIDE2Nwo1MiAxMzAKMzIgNzkKMTEgNDAKOTEgMTk5CjE0IDE3NAozMSA1MAo5OSAxMTMKMjEgMTQyCjQyIDg5CjE4OCAyMTEKMzkgMTc0CjE4IDg1CjM2IDEyOAoxNjAgMjEyCjMxIDU3CjM2IDQyCjEwOCAxNDUKNCA1CjgwIDkwCjM4IDIwNAoxNSAxOAoyNiAxMgozIDg0CjExNCAxMjUKMTcxIDE5NAoyOSA5MgoxIDIKMzEgOTEKMTIgMTgwCjEzNiAxNTgKNTcgMTM4CjggNjEKMTEgMzQKMTczIDIyMQo1MiA2Mgo2OCAxODUKMTAwIDE0OAoxOTYgNjkKMTE0IDEzNgoyNiAxMDgKMTUgMjAwCjk0IDE2NQo1MSA4MAoxMyAxMDYKMTg4IDE3MQo2IDEzCjEwMyAyOAoxMjkgMTM3CjE0IDMyCjE1IDIzCjE1IDEwNwo1NCAxMzMKMTYgNDMKMTMgMzYKMTMxIDE3Nwo4MyAxNzkKNzIgOTUKMTMgMzgKMjIgMTY4CjYxIDE2OQo2MiA2NQozOSAxMjAKNzkgMTE5CjE0OCAyMDgKMzkgNDgKMTQwIDIwMAo2NiAxNzIKOCAxNQo0MyA3MQo4MCA4NgoyMDAgMTQ2CjYgMTAKMTgyIDE5MAoxNiA2MwoxIDQKMTIgMjA3CjY0IDc3CjIyIDU2CjUxIDEwMAoxMCAxMzIKMjUgNzMKMTkgMzAKMjYgNzYKNSA3MgoxODQgMjA1CjExMCAxMTIKMjMgMTU2CjEzIDI0CjE2IDIxCjEgMwo2MCA2Ngo5MSAxMDQKOSA0Ngo4IDE5CjEyMiAyMTgKMTUxIDIxOQozIDM1CjQ2IDEwMQoyNSA5OQoxNyA0NQozNSA1MwoxNDAgMTY0CjE5MiAyMDkKMTc5IDI3CjEzNCAxNjMKMTkgMTQ5Cjg2IDE4MQo3MiAxNTMKNjIgMTE4CjIzIDUxCjE2NSAxNDUKNjggMTQ0CjQgNgoxNzIgMjEwCjUgNDcKMTMwIDE0CjE1MSAxOTEKODMgMTg2CjM3IDI0CjE4NyAyMTQKODUgMTQxCjg5IDE0Ngo1NSAxNTkKMTQgODgKMiAxNzEKMjQgMTI2CjU2IDc0CjY1IDgzCjkgMTUyCjExIDEyCjM3IDEwMgoxMDMgMTI3CjEzMSAxNTAKNTIgOTgKMTIxIDE5MgoxMTQgMTYxCjcgMzkKOCAyMgozNyAxMTQKMTMgMTI5CjE1MCAyMjIKMTAgMTEKNjAgNTcKMTA1IDIxNAo0MiA2OAo3IDY3CjggOQoxMyA3OAoxOTQgMjA2CjMgMTQKMTQ0IDE3Mwo1IDcKMjMgMTM5Cjc0IDExNQoxNSAyOAo0NyAyMDMKMTUwIDgzCjQ4IDUyCjE4IDE4Mwo5IDEwMgo0MCAxMzAKMjQgMTA5CjcwIDc1CjUzIDE4MAoxNjUgMTc1Cjk5IDE4MAo5OCAxMTEKMTIgMjkKODEgMTc2CjEgNDQKNDIgMTkxCjE2IDI2CjcgMjcKMTA2IDE2MQo2OCAxOTgKMTI3IDE5MgoxMiAxNDMKNTIgMTEzCjc3IDExMAoxMjEgMTY2CjUwIDIxNgoyMCAxMTcKMTAxIDExNgoyOCAxMzAKMTkgMTU1CjEzIDEzMQo4MiA5NgoxOCAxMDMKNjEgMTY4CjQ3IDIwMgo5NyAxODkKMTM5IDE4OAo4IDE1OQo3IDE3CjUzIDU4CjE0IDE2CjE3NCAxODQKNDkgMTIzCjQ5IDgxCjI5IDM3CjkgNTQKMTU0IDE5NQozNSA4NwoyNSAzMwoxMCAxNjIKMTI2IDE4Mgo2NCAxNTEKMTc4IDIxNwoyOSAxMjIKNTggMTU3CjE3MyAyMDEKNTYgMTU3CjE0OSAxOTYKMiA4CjIxIDI1CjE3NyAxOTcKMzUgMTIxCjEyNiAxNzAKNTIgNzkKMjkgMTg3CjIyIDQxCjU1IDE5MwoxOSAxMzUKNDUgMjE1CjEzNyAxNgoxMjIgMjAxCjIyIDYwCjExIDg3CjgyIDE2MAo1MiAyMDkKMTIgMTU0CjU3IDk3CjMgNjkKNzAgMTA1CjU4IDU5CjExIDcwCjkgMjAKMjYgMjEzCjExMSAxMzQKOTAgMjE3CjU5IDE5Nwo5MiAxNDEKNDAgODgKMTY2IDIwMwozNSAxMjEKNiAxOAo3MiA5Nwo4OCAxMDkKOTYgMTI4CjYxIDE0NwoxOTAgMjE1CjE0MCAyMTMKMjcgMTk1CjExNyAxMzIKNjcgMTc1CjE0IDMyCjI2IDEzMAoxMjAgMTg0CjEyMSAxNTUKMjMgMzQKOTYgMTM3CjM0IDQzCjI0IDE2MQoxNjcgMTg2CjEgMTUzCjI5IDE1MgoxOCAxMTIKOTkgMjA4CjIgNDUKMiAzCjMgMTczCjc4IDIxOQo2IDE5CjIzIDM4CjQwIDgxCjczIDkxCjcyIDEzNQo4MSAxNzUKNiAxMgoxOSA3MAo0NSAxNDUKODQgMTM2CjE4OSA0Ngo5NSAxNjAKMTM3IDkwCjE2MyAxOTgKMSA1NQozIDM3Cjk3IDE0NgoxOCAzNQo0NyA5OQoyIDcKMSAyCjMyIDEyNAoyIDE0MAoyMCAxOTYKMjkgOTAKMTcxIDIyMQo0MSAxNzQKMTQxIDE3OQo3MSA3Mwo3MiAxNTEKMTE2IDIyMAoxNDMgMTYKOSA1MwoyNCAxNTMKMTAgMTcKMTIgMTM0CjEyNiAxMzkKMTUzIDE2NQozNSA0NwoyMTEgNTcKOSAyNQoxNjAgMTcyCjIxNSAxNDIKNzQgODgKMzUgNzYKNjEgNjQKNjMgMTUwCjQgMjEKODUgMjE4CjEwMiAyMDEKOSAyMAozOSA4MgozMyA0NAo2MSA2OQozNiA1MgoxNTUgMjAwCjIgMTEKMzIgNjEKMTAwIDE1Nwo0NCAxNjIKNTAgMjA5CjE4IDE4NwoxMDkgMTgwCjMgMTE3CjEyIDEzMwo2OSAxMDIKMTM0IDUKNTEgMTkyCjE3OSA4MAo4IDE2NwoxOSAxMTYKNTggMTA2CjEzNiAxMDEKMjE5IDY5CjQgOTQKNjEgMTc1CjEgNzQKMTU5IDIwNQo3MyAxOTQKNzQgMTQzCjQgMTUKMTU3IDE5OQo2IDIyCjEgMTkzCjQ4IDc4CjU3IDEwMwoxNyAxODIKMzAgNjUKMzQgOTMKOSAyNwoxNCAxNzAKMTUgNDgKMzIgMTA3CjEgOQo0OSAyMTQKODYgMTQwCjEwOCAxOAoxMjggNzkKOCA2MAo1OCAxMDEKMTg4IDIwNAo3MyAxNjkKMzggNTcKNCAxMjkKNjEgNDIKOTggMTU2CjEgMTAKMzcgNDIKNjYgMTEwCjEwIDI0CjEwNiAxMjcKMTI3IDIxMgoyOCAzNgozIDQKMTUgMTc4CjI2IDgwCjYxIDExNAo3MyA3NQoxNjcgMjE2CjEyMCAxNzYKMiAxMwoxOCAxNjQKMTQzIDE5MgoxMzggMTU5CjEzOSAxNDgKNjggMTg4CjU4IDE2OAo2NCA3OQoxIDI5CjYwIDkyCjYgOAoyNCAyNgoyIDU0CjM3IDUxCjI4IDMzCjI3IDgxCjMxIDQ5CjggMTM4CjI0IDIxMQoxNjYgMTgxCjgyIDEyMwo3OSAxMDQKOSA4MwoxMCAzMQoxODEgMjQKOTAgMTcxCjI4IDE3NwoxIDUKMzEgODQKMTE1IDE1OAoxNiA2NgoyIDExOAo3NiAxMDUKNyA2MwoxMSAyMDcKMTM5IDE5MQoyNCAxMjAKOTAgMTI1CjE5OSAxMDAKMjMgMTEzCjcwIDE4Mwo2NCAxMjYKMTA4IDExOQo0OSA5OAoxMCA4NQo5OCAxNjYKMiA2CjM1IDQwCjggOTUKMzQgNTAKODYgMTI5CjIxIDI4CjE0IDcyCjM2IDg3CjEzOCAyMDAKNTYgMTY4CjI0IDMwCjE5OCAzMQoxMzEgMTM2CjExMSAxOQoyMyA3MQo2OSA5NgoyMSAyMDIKMTQxIDE0NAoxOSA1OAo4MCAxMjIKMTggMzkKMTA1IDExMQozOSA1NgoxMDkgMTg5CjcgMTYKMjkgMTMxCjEzIDU5CjQgMTQKMTQxIDE2Mwo1MCA2OAo4NCA4OQoxMDggMTE1CjM5IDQ2Cjc4IDE0Mgo2NSAyMTAKNDIgMTAwCjQ2IDY3CjMxIDE0Mgo4NyAxOTAKNDEgNzcKNDIgODYKNDggNjIKMTIgMjMKMjIgMjIyCjE0MiAxODUKOTUgMTU0CjE2IDEwOAozNSA0MQoxMTMgMTY2CjE0MiAxNDkKMjkgMjgKMTEzIDIwNgo5OCAxMjUKMTAgNTUKNTcgMjAxCjEwMyAxMTIK

stdout

copy

The input is valid! N = 222; M = 255.

Solution #1: produced an incorrect answer (success).
Solution #2: produced an incorrect answer (success).
Solution #3: produced an incorrect answer (success).
Solution #4: produced an incorrect answer (success).

Score: 85 points.

https://ideone.com/kCRpT1

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language