<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

139. Help Needed!

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


Little Johnny likes puzzles a lot! Just a few days ago, he found out about the 'traditional' 4x4 puzzle. For this puzzle, you have all the numbers from 0 to 15 arranged in 4 rows and 4 columns. You are allowed to switch two adjacent elements (horizontally or vertically), only if one of them has the value 0. The purpose of the puzzle is to reach the following final state:

                             1  2  3  4
                             5  6  7  8
                             9 10 11 12
                            13 14 15  0

Given the initial state of the puzzle, you have to decide whether there exists a sequence of moves which brings the puzzle into the final state.


Input

The input will consist of  4 lines, each of them containing 4 integers, describing the initial state of the puzzle.


Output

For every initial state, you should print "YES" if the final state can be reached after several moves or "NO", if such a thing is impossible.


Sample Input #1

1 2 3 4
5 6 7 8
9 10 11 0
13 14 15 12
Sample Output #1

YES
Sample Input #2

2 1 3 4
5 6 7 8
9 10 11 12
0 13 14 15
Sample Output #2

NO
Author	: Mugurel Ionut Andreica
Resource	: SSU::Online Contester Fall Contest #2
Date	: Fall 2002

<|response|>
1) Abridged problem statement
- You’re given a 4x4 sliding puzzle with tiles 0..15 (0 is the blank). A legal move swaps 0 with an adjacent tile (up/down/left/right).
- Target configuration:
  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15  0
- Input: 4 lines, each with 4 integers (the initial board).
- Output: YES if the target is reachable from the initial board; otherwise NO.

2) Key observations
- The 15-puzzle’s states split into exactly two parity classes (Johnson & Story, 1879); you can move only within the same class. Since we only need YES/NO and not the minimum number of moves, no search (A*, BFS) is required.
- A simple invariant decides solvability:
  - Flatten the board row-wise and temporarily replace 0 by 16 (treat blank as the largest tile).
  - Let I be the inversion count: number of pairs (i < j) with a[i] > a[j].
  - Let d be the Manhattan distance of the blank to the target corner (3,3), i.e., d = (3 - r) + (3 - c).
- Each legal move flips both:
  - the parity of I (inversions with 0→16), and
  - the parity of d (blank distance to bottom-right).
- In the target state, I = 0 and d = 0 (both even). Therefore the initial configuration is solvable iff (I + d) is even.
- This is equivalent to the classical rule for even-width boards (like 4x4): (inversions ignoring 0) + (blank row counted from bottom, 1-based) is odd.

3) Full solution approach
- Read the 16 numbers row-wise into an array a.
- Locate the blank (value 0): its index p gives row r = p / 4, column c = p % 4.
- Compute d = (3 - r) + (3 - c).
- Replace a[p] = 16 (treat the blank as the largest tile).
- Compute I = count of pairs (i < j) with a[i] > a[j] over all 16 elements.
- If (I + d) % 2 == 0, print YES; else print NO.

Complexity: Counting inversions among 16 elements is O(16^2) comparisons; overall constant time and trivial memory usage.

4) C++ implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

vector<int> a;

void read() {
    a.resize(16);
    cin >> a;
}

int inversions(vector<int>& arr) {
    int count = 0;
    for(int i = 0; i < arr.size(); i++) {
        for(int j = i + 1; j < arr.size(); j++) {
            if(arr[i] > arr[j]) {
                count++;
            }
        }
    }
    return count;
}

void solve() {
    // The standard solution would be to do A* or some other search algorithm,
    // which is sufficiently fast for 4x4, but interestingly Johnson & Story in
    // 1879 proved that there are only two equivalence classes in the 15 puzzle
    // - essentially based on the parity of the permutation achieved by the rows
    // of the table. This makes the problem easier to solve, as we are only
    // interested in YES/NO rather than least number of steps.
    // More can be found in these two sources:
    // - https://www.jstor.org/stable/2369492?origin=crossref&seq=1
    // -
    // https://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/15-puzzle.pdf
    //
    // The sources describe one way of showing the fact there are two
    // equivalence classes, but there is also arguably a simpler explanation.
    // Let's consider the permutation given by replacing 0 with 16, and going
    // row by row, each row starting from the left. This means that the original
    // grid's permutation is the identity and so even. Let's say we made some
    // operations to the grid and now 16 is on position i. The operations we can
    // perform are swap i with i-1,i+1, i+n, and i-n. Let's consider how the
    // number of inversions changes - there are effectively 2 x 2 symmetric
    // cases:
    //
    //    1) We swap i with i-1 or i+1. Trivially i is the largest element, so
    //       the number of inversions will change with either +1 or -1. In both
    //       cases with 1 mod 2.
    //
    //    2) We swap i with i-n or i+n. This case is slightly more
    //       complicated as we have n-1 elements between the two we are swapping and 
    //       j =def= i-n or i+n is not the "largest element" to make the number
    //       of inversions predictable. WLOG, we will assume that j = i-n, and that
    //       in p[j+1:i] there are exactly k elements that are less than p[j]. This 
    //       means there are n-1-k elements greater than p[j]. The inversions with p[j]
    //       as part of them will change with exactly n-2k-1. However, p[i] = 16 will also
    //       now contribute to more inversions - n to be precise. This means that overall
    //       the inversions change by 2n-2k-1, which mod 2 actually also ends up being 1.
    //
    // Therefore, we showed that the parity of the inversions (permutation) changes every
    // time we move the 16. This gives us the invariant that the parity of number of moves 
    // of 16 is always the same as the parity of the permutation as this is the case in the 
    // initial permutation, or it's enough to check that:
    //     
    //    manhattan_distance((n-1,n-1), (i / 4, i % 4)) = parity(p) mod 2

    int sum = 0;
    for(int i = 0; i < 16; i++) {
        if(a[i] == 0) {
            sum = (3 - i / 4) + (3 - i % 4);
            a[i] = 16;
            break;
        }
    }

    sum += inversions(a);

    cout << (sum % 2 == 0 ? "YES" : "NO") << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5) Python implementation with detailed comments
```python
import sys

def main():
    # Read all integers. The problem has a single 4x4 board (16 numbers).
    data = sys.stdin.read().strip().split()
    if len(data) < 16:
        return
    vals = list(map(int, data[:16]))

    # Locate the blank (0).
    zero_idx = vals.index(0)
    r, c = divmod(zero_idx, 4)

    # Manhattan distance from blank to bottom-right corner (3,3).
    d = (3 - r) + (3 - c)

    # Replace 0 with 16 (the largest) to compute inversion count consistently.
    vals[zero_idx] = 16

    # Count inversions among all 16 positions.
    inv = 0
    for i in range(16):
        ai = vals[i]
        for j in range(i + 1, 16):
            if ai > vals[j]:
                inv += 1

    # Solvable iff parity(inv + d) is even.
    print("YES" if (inv + d) % 2 == 0 else "NO")

if __name__ == "__main__":
    main()
```
