<|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; you can move only within the same class.
- 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) = 120 comparisons; overall constant time and trivial memory usage.

4) C++ implementation with detailed comments
```cpp
#include <bits/stdc++.h>
using namespace std;

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

    // Read the 4x4 grid (16 integers in total).
    vector<int> a(16);
    for (int i = 0; i < 16; ++i) {
        if (!(cin >> a[i])) return 0; // Handle empty input defensively.
    }

    // Find the position of the blank (0).
    int zero_idx = -1;
    for (int i = 0; i < 16; ++i) {
        if (a[i] == 0) {
            zero_idx = i;
            break;
        }
    }

    // Compute the Manhattan distance from the blank to its target (row=3, col=3).
    // Current coordinates of blank:
    int r = zero_idx / 4, c = zero_idx % 4;
    int d = (3 - r) + (3 - c);

    // Treat the blank as the largest tile for inversion counting.
    a[zero_idx] = 16;

    // Count inversions I: number of pairs (i < j) with a[i] > a[j].
    int inv = 0;
    for (int i = 0; i < 16; ++i) {
        for (int j = i + 1; j < 16; ++j) {
            if (a[i] > a[j]) ++inv;
        }
    }

    // Solvable iff (inv + d) is even.
    cout << (((inv + d) & 1) == 0 ? "YES\n" : "NO\n");
    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()
```