Finding LITS Tetrominoes

In the popular game Tetris, there are seven tetrominoes but here we only focus on the four classic ones: L, I, T and S (the LITS pieces). Each tetromino is composed of four squares of equal size. You are given an N×N grid, where each cell contains either 0 or 1. A cell with 1 means that there is a square in that cell. Your task is to determine whether it is possible to select four disjoint groups of cells (each of size 4) from those marked 1 such that each group (when appropriately rotated by any multiple of 90°; flipping is not allowed) forms one of the four tetromino shapes: L, I, T, and S. No square may be used in more than one tetromino.

Note on Rotations: For each tetromino, only rotations (by 0°, 90°, 180°, and 270°) are allowed. For example, the canonical forms (with coordinates relative to an origin) for each type can be taken as:

• L: The canonical L is given by \(\{(0,0), (1,0), (2,0), (2,1)\}\). Its rotations (after proper normalization) are:
  0°: \(\{(0,0), (1,0), (2,0), (2,1)\}\)
  90°: \(\{(0,0), (0,1), (0,2), (1,0)\}\)
  180°: \(\{(0,0), (0,1), (1,1), (2,1)\}\)
  270°: \(\{(0,2), (1,0), (1,1), (1,2)\}\)
• I: The canonical I is \(\{(0,0), (1,0), (2,0), (3,0)\}\), with rotation 90° as \(\{(0,0), (0,1), (0,2), (0,3)\}\). (The 180° and 270° rotations repeat these two forms.)
• T: The canonical T is \(\{(0,0), (0,1), (0,2), (1,1)\}\). Its rotations can be computed similarly.
• S: The canonical S is \(\{(0,1), (0,2), (1,0), (1,1)\}\). Its 90° rotation becomes \(\{(0,0), (1,0), (1,1), (2,1)\}\). (There are 2 unique orientations.)

Your program should output "YES" if such a selection exists and "NO" otherwise.

inputFormat

The first line contains an integer N, the size of the grid (N×N).
Each of the next N lines contains N space-separated integers (each 0 or 1) representing the grid.

outputFormat

Output a single line with either "YES" if the grid contains four disjoint tetromino placements – one each corresponding to L, I, T, and S (allowing rotations but no flips) – or "NO" otherwise.

sample

5
1 0 1 1 1
1 0 1 1 1
1 1 0 0 1
0 1 0 0 1
1 1 1 0 0

YES