题面描述

给定一个 $N\times N$ 的网格，给定两条网格上的路径（保证路径和格线重合），求夹在路径中的最大正方形的大小（正方形的边必须与格线平行）。

例如下图（样例1）：

棕色部分是夹在两条路径中的部分，能取出的最大正方形边长为 $4$。

输入格式

第一行一个正整数 $N$ 表示网格大小。

第二行一个长度为 $2N$ 的只包含 $\texttt{R,D}$ 的字符串，$\texttt{R}$，表示向右移动一格，$\texttt{D}$ 表示向下移动一格。保证路径从左上出发，到右下结束。

第三行一个长度为 $2N$ 的字符串表示第二条路径。保证第二条路径不存在在第一条路径下方的部分。

输出格式

输出一行一个整数表示答案。

Samples

10
DDDDRRDDDDRRRDRDRRRR
RRDRDRRRDDRRDDDDRDRD

4

6
DDDDDDRRRRRR
RDRRDDDRRRDD

3

数据范围与约定

保证 $2 \le N\le 10^6$。

本题共 $50$ 个测试点。

对于测试点 $1\sim 5$，保证 $N\le 10$。

对于测试点 $6\sim 15$，保证 $N\le 100$。

对于测试点 $16\sim 30$，保证 $N\le 5000$。

对于测试点 $31 \sim 50$，无特殊限制。