Problem D
Knitpicking

Gillie in one of his resting places By Dwight Sipler (cc by-sa)

To find matching socks, she simply randomly takes single socks out of the drawer until she has a matching pair. It may take a long time, for example when she keeps drawing right socks without a matching left one. How long does she need to keep drawing socks until she is guaranteed to have a pair to wear?

Input

The input consists of:

• One line with an integer $n$ ($1\le n\le 1000$), the number of groups of identical socks.

• $n$ lines, each describing a group of identical socks with the following:

  • A string $i$, the type of the socks in the group. The type $i$ consists of between $1$ and $20$ lowercase English letters. Socks with the same type are considered compatible for fashion purposes.

  • A string $j$, the fit of the socks in the group, which is either left, right or any, indicating whether the socks fit on the left foot, the right foot or any foot.

  • An integer $k$ ($1\le k\le 1000$), the number of socks in the drawer that are of this type and fit.

A given fit of a given type of sock appears at most once in the input.

Output

Output the minimum number of socks Kattis needs to draw to be guaranteed to get a matching pair. If it is not possible to get a matching pair at all, output impossible.

3
fuzzy any 10
wool left 6
wool right 4

8

3
sports any 1
black left 6
white right 6

impossible

2
warm any 5
warm left 3

4