Kattis 的抽屉里有很多双漂亮、温暖的针织袜，非常适合冬天穿。这些袜子颜色和种类繁多，全都混在了一起。每天早上，Kattis 都需要挑出一双匹配的袜子。

为了找到匹配的袜子，她只是简单地从抽屉里随机取出单只袜子，直到她凑成了一双匹配的袜子。这可能需要很长时间，例如，当她不断取出右脚袜却找不到匹配的左脚袜时。她需要取出多少只袜子，才能保证一定能凑成一双可以穿的袜子？

Gillie 在他休息的地方之一，摄影：Dwight Sipler (cc by-sa)

输入格式

输入包含： 一行包含一个整数 $n$ ($1 \le n \le 1\,000$)，表示相同袜子的组数。 $n$ 行，每行描述一组相同的袜子，包含以下内容： 一个字符串 $i$，表示该组袜子的类型。类型 $i$ 由 1 到 20 个小写英文字母组成。相同类型的袜子在时尚搭配上被认为是兼容的。 一个字符串 $j$，表示该组袜子的适配类型，为 left（左脚）、right（右脚）或 any（任意脚），表示袜子适合左脚、右脚还是任意脚。 * 一个整数 $k$ ($1 \le k \le 1\,000$)，表示抽屉里该类型和适配方式的袜子数量。

给定类型的袜子，其每种适配方式在输入中最多出现一次。

输出格式

输出 Kattis 为了保证能凑成一双匹配的袜子，最少需要取出的袜子数量。如果根本不可能凑成一双匹配的袜子，则输出 impossible。

样例

样例输入 1

3
fuzzy any 10
wool left 6
wool right 4

样例输出 1

8

样例输入 2

3
sports any 1
black left 6
white right 6

样例输出 2

impossible

样例输入 3

2
warm any 5
warm left 3

样例输出 3

4