Who Is on First Base

Interview

Time limit2sMemory limit512 MB

Summary

Given nine statements of the form 'player A is' or 'player A is not' the first baseman, and knowing exactly one statement is a lie and exactly one player holds the position, find the player forced to be the first baseman or print -1.

Level: Medium4 of 10
Topics: Brute force, Implementation, Math
Solved: No attempts yet

Problem

On a hot summer day, a mysterious drink arrived in front of the Sunrin baseball team!

"Drink this and cheer up! - To the first baseman ¸"*

The players started arguing over who is the first baseman and who is not. Nine of them are arguing, and it seems that exactly one of the nine is lying! Each player claims one of the following. (For convenience, let us identify the players by their jersey numbers 1, 2, ..., 9.)

1 A: Player A is the first baseman.
0 A: Player A is not the first baseman.

The coach, watching the argument, spoke up in frustration.

"Who's on first, what's the second baseman's name, I don't know the third baseman"

Now you must use logical reasoning, based on the assumption that 'exactly one person is lying' and the fact that 'there is exactly one first baseman', to conclude that a particular player must be the first baseman. Note that it may be impossible to draw such a conclusion from the players' claims alone.

*Who's on first

Input

Nine lines are given. Each line contains either 0 or 1, followed by A. (1 ≤ A ≤ 9)

Output

If logical reasoning lets you uniquely determine the first baseman, print that player's jersey number.

If it is impossible to know who the first baseman is, print -1.

Examples4

Example 1
Input
```
1 2
0 2
1 2
1 2
1 2
0 4
0 4
0 4
0 4
```
Expected output
```
2
```
Example 2
Input
```
0 1
0 1
1 2
0 3
0 4
0 5
0 6
0 7
0 8
```
Expected output
```
9
```
Example 3
Input
```
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
```
Expected output
```
-1
```
Example 4
Input
```
0 1
0 1
0 1
0 1
0 1
0 2
0 3
0 4
0 5
```
Expected output
```
-1
```