Problem name: Impas

Problem ID: 19005

Problem setter: Vlad Dascalu

Problem input: standard input

Problem output: standard output

Background:

On a 4x4 yellow board, 4 pieces are originally placed as below:

                     
                     
    O   O            
    O   O            

Problem:

John (the first player) and Vlad (the second) play this game according to the following rules. The first player can move the pieces only up, and the 2nd player only to the right. The pieces can't jump one over another. The players move one by one. The first player starts the game. There is no restriction regarding the number of spaces a piece can travel, except the fact that pieces can't go beyond the board's limits. When a player can't move, the game ends. The winner is the one that made the last move.

Input data:

One digit, 1 for the first player or 2 for the second, representing the player that must move next.

4 lines, each one with 4 binary digits, representing the board configuration. A piece is represented by 1, and an empty space by 0.

Output data:

1 if the current player always wins (with optimal strategy), 0 otherwise.

Example:

input:

1
0000
0000
1100
1100

output:

0

Restrictions:

1