题目描述

$n$ 个钟表正在进行转动...

每个钟表的指针有四个方向，上（U），下（D），左（L），右（R）。

每一秒，每个钟表的指针都会顺时针旋转 $90$ 度，即按照 $U - R - D - L - U -...$ 的顺序进行旋转。

每一秒，你都可以选择暂停一个钟表，让该钟表上的指针在这一秒不转动。当然，你也可以选择不暂停钟表（即让所有钟表的指针转动）。

第 $0$ 秒时，第 $i$ 个钟表的指针方向为 $s_i$。江桥希望让这些钟表的指针以最快的时间全部指向上方。

请你帮他求出，最早第几秒可以使得所有钟表的指针都指向上方。

输入格式

第一行两个正整数 $n$，表示钟表数量。

接下来一行一个长度为 $n$ 的字符串，表示初始时每个钟表的指针方向。

输出格式

一个整数，表示最早第几秒所有钟表的指针会指向上方。

4
URDL

6

样例解释

数据规模与约定

下发文件

下发文件对应子任务 $1,4$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 10^6,s_i \in \{U,D,L,R\}$。