import std.algorithm, std.array, std.container, std.range, std.bitmanip; import std.numeric, std.math, std.bigint, std.random, core.bitop; import std.string, std.regex, std.conv, std.stdio, std.typecons; alias Tuple!(int[][], "board", int, "visited") qItem; void main() { auto aij = iota(4).map!(_ => readln.split.map!(to!int).array).array; auto bij = iota(4).map!(i => iota(4).map!(j => (i * 4 + j + 1).to!int).array).array; bij[3][3] = 0; auto qi = new DList!(qItem); qi.insert(qItem(bij.dupDeep, 0)); while (!qi.empty) { auto q = qi.front, cij = q.board, visited = q.visited; qi.removeFront; if (cmp(aij, cij)) { writeln("YES"); return; } auto p = find0(cij); foreach (sib; sibPoints) { auto np = p + sib; if (np.x < 0 || np.x >= 4 || np.y < 0 || np.y >= 4) continue; if (visited.bitTest(cij[np.y][np.x])) continue; auto dij = cij.dupDeep; swap(dij[p.y][p.x], dij[np.y][np.x]); qi.insert(qItem(dij, visited.bitSet(dij[p.y][p.x]))); } } writeln("NO"); } bool cmp(int[][] aij, int[][] bij) { return aij.zip(bij).all!("a[0] == a[1]"); } int[][] dupDeep(int[][] aij) { return aij.map!(a => a.dup).array; } point find0(int[][] aij) { foreach (int i, ai; aij) foreach (int j, a; ai) if (a == 0) return point(j, i); assert(0); } struct Point(T) { T x, y; point opBinary(string op)(point rhs) { static if (op == "+") return point(x + rhs.x, y + rhs.y); else static if (op == "-") return point(x - rhs.x, y - rhs.y); } } alias Point!int point; alias Point!real rpoint; const auto sibPoints = [point(-1, 0), point(0, -1), point(1, 0), point(0, 1)]; template BitOp(T) { bool bitTest(T n, size_t i) { return (n & (1.to!T << i)) != 0; } T bitSet(T n, size_t i) { return n | (1.to!T << i); } T bitReset(T n, size_t i) { return n & ~(1.to!T << i); } T bitComp(T n, size_t i) { return n ^ (1.to!T << i); } int bsf(T n) { return core.bitop.bsf(n.to!ulong); } int bsr(T n) { return core.bitop.bsr(n.to!ulong); } int popcnt(T n) { return core.bitop.popcnt(n.to!ulong); } } mixin BitOp!(int);