说明

你的大学正在举办一场名为 IOI 的竞赛。作为活动组织者，你想为其制作一条横幅。你准备的横幅可以表示为一个 $3 \times N$ 的网格，每个格子将被印成白色或黑色。由于印刷问题，有些格子不能印成黑色。

你从一条全白的横幅开始，并希望按如下方式在横幅上印出单词 $\texttt{IOI}$。

• 通过印出一个大小为 $3 \times p$（$p \geq 1$）的实心黑色矩形来形成第一个字母 $\texttt{I}$。
• 通过印出一个大小为 $3 \times q$（$q \geq 3$）的矩形边框（即只印边界）来形成字母 $\texttt{O}$。
• 通过印出一个大小为 $3 \times r$（$r \geq 1$）的实心黑色矩形来形成第二个字母 $\texttt{I}$。

字母 $\texttt{O}$ 必须位于两个字母 $\texttt{I}$ 之间，并且字母之间至少要有一列间隔。同时要求字母 $\texttt{O}$ 的宽度至少等于两个字母 $\texttt{I}$ 的宽度之和，即 $q \geq p + r$。所有不属于单词 $\texttt{IOI}$ 的格子必须保持白色。

确定你可以印成黑色的格子的最大数量，或者判断无法印出单词 $\texttt{IOI}$。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 200\;000$），表示 $3 \times N$ 网格的大小。

接下来的三行，每行包含 $N$ 个字符，表示网格的格子。

这 $3N$ 个字符中的每一个对应一个格子，是 $\texttt{.}$ 或 $\texttt{\#}$，分别表示该格子可以或不可以印成黑色。

输出格式

输出一行，表示可以印成黑色的格子的最大数量。

如果无法印出单词 $\texttt{IOI}$，则输出 $-1$。

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

14

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

-1

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

22

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

39

提示

样例 1 解释： 你可以按以下方式印刷横幅。

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

样例 3 解释： 你可以按以下方式印刷横幅。

  ..I#OOOO#III
  ..I#O##O#III
  ..I#OOOO#III

样例 4 解释： 你可以按以下方式印刷横幅。

  #III##OOOOOOOOOOO.II
  #III##O##....#..O#II
  #III##OOOOOOOOOOO.II

翻译由 DeepSeek V3.2 完成