你的大学正在举办一场名为 IOI 的比赛。作为活动组织者，你想为此制作一条横幅。你准备的横幅可以表示为一个 $3 \times N$ 的网格，其中每个单元格要么印成白色，要么印成黑色。由于打印问题，某些单元格无法印成黑色。

你从一张白色的横幅开始，想要在横幅上打印单词 IOI，具体要求如下：

• 通过打印一个 $3 \times p$ ($p \ge 1$) 的实心黑色矩形来形成第一个字母 I。
• 通过打印一个 $3 \times q$ ($q \ge 3$) 的黑色矩形边框来形成字母 O。
• 通过打印一个 $3 \times r$ ($r \ge 1$) 的实心黑色矩形来形成第二个字母 I。

字母 O 必须形成在两个字母 I 之间，且字母之间必须至少有一列间隔。此外，字母 O 的宽度必须至少是两个字母 I 的宽度之和，即 $q \ge p + r$。所有不属于单词 IOI 的其他单元格必须保持白色。请确定你可以打印出的黑色单元格的最大数量，或者指出打印单词 IOI 是不可能的。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 200\,000$)，表示 $3 \times N$ 网格的大小。接下来的三行，每行包含 $N$ 个字符，表示网格的单元格。这 $3N$ 个字符中的每一个对应一个单元格，要么是 .，要么是 #，分别表示该单元格可以或不可以印成黑色。

输出格式

输出一行，表示你可以打印出的黑色单元格的最大数量。如果无法打印出单词 IOI，则输出 $-1$。

样例

输入 1

7
.......
.......
.......

输出 1

14

说明 1

你可以按以下方式打印你的横幅：

I.OOO.I
I.O.O.I
I.OOO.I

输入 2

6
......
......
......

输出 2

-1

输入 3

12
...#....#...
...##.##....
...#....#...

输出 3

22

说明 3

你可以按以下方式打印你的横幅：

..I#0000#III
..I#0##0#III
..I#0000#III

输入 4

20
#...##............
#...##....#..#..
#...##............

输出 4

39

说明 4

你可以按以下方式打印你的横幅：

#III##0000000000.II
#III##0##....#.0#II
#III##0000000000.II