Bluetooth

/problems/bluetooth/file/statement/en/img-0001.jpg
Harald Bluetooth depicted in the 17th century.

King Harold of Denmark (c. 998–1098) wants to eat an apple to celebrate the founding of the town Lund. Harold’s teeth are in terrible condition; some are missing, some are rotten and discoloured, earning him the nickname “Bluetooth.”

Harold can chew the apple on the left or the right side of his mouth. Chewing with rotten teeth causes terrible pain, so he cannot chew on a side containing a blue tooth. He needs at least one tooth in both the upper and the lower jaw on the same side to be able to chew on that side.

As Harold’s chief advisor and reluctant dentist, you have a complete overview of his dental problems. Can you help him decide on which side to chew, or if apples are too hard to handle?

Input

The first line of input is an integer $n$, the number of Harold’s dental problems, where $1\leq n\leq 32$. Each of the following $n$ lines describes a dental problem. A dental problem consists of a space separated tooth and a condition, »m« (for »missing«) or »b« (for »blue«). No tooth will appear more than once in the problem description. Teeth are described using the nomenclature created by your dentist colleague Victor Haderup:

\includegraphics[width=0.5\textwidth ]{img/dental-en.pdf}

Harald has at least one blue tooth. A tooth cannot be both missing and blue.

Output

The integer $0$ if Harold can chew the apple with the left side. The integer $1$ if Harold can chew the apple with the right side. The integer $2$ if you recommend soup.

Scoring

Group

Points

Limits

1

19

$n = 1$

2

81

$1\leq n\leq 32$

Sample Input 1 Sample Output 1
1
-5 b
1
Sample Input 2 Sample Output 2
9
8- m
7- m
6- m
5- m
4- m
3- m
2- m
1- b
+3 m
0
Sample Input 3 Sample Output 3
9
8- m
7- m
6- m
5- m
4- m
3- m
2- m
1- m
+3 b
2
Sample Input 4 Sample Output 4
15
6+ b
+2 m
+3 m
+4 m
+5 m
+6 m
+7 m
+8 m
-1 m
-2 m
-3 m
-4 m
-5 m
-6 m
-7 m
0