봇 탐지

평화로운 게임 세상에서 작업장과 봇은 균형을 깨는 악당들이다. 작업장과 봇을 통해서 짧은 시간 내에 높은 레벨로 올라간 사용자가 있다면, 여가 시간에 게임을 즐기면서 레벨을 관리하는 보통의 사용자는 도저히 경쟁이 되지 않기 때문이다. 넥슨의 인기 게임 메이플스토리의 관리자인 당신은 이상한 사용자가 있다는 제보를 받았다. 당신이 할 일은 이 사용자가 사람인지, 아니면 봇인지 구별하는 일이다.

이 게임에서, 플레이어는 상U 하D 좌L 우R 로만 움직일 수 있다. 또 게임 서버에는 모든 사용자의 최근 $n$ 번 이동 기록이 저장되어 있다. 보기에 따라서는 이 이동 기록을 길이가 $n$ 이고, 네 문자 U D L R 로 이루어진 문자열이라고 볼 수도 있다.

봇은 사람 대신 자동으로 게임을 플레이하는 프로그램이며, 가장 간단한 형태는 길이 $m$의 U D L R로 이루어진 문자열을 따라 움직이는 것을 무한히 반복하는 것이다. 이 문자열을 이제부터 루틴이라고 부르자. 루틴대로만 움직이는 봇은 관리자에게 들키기 쉽기 때문에, 발전된 형태의 봇은 $0$번 이상 무작위로 이동하고, 루틴대로 한번 행동한 다음, $0$번 이상 무작위로 이동하고, 다시 루틴대로 한번 행동하고... 를 반복하는 형태로 이루어진다.

만약 사용자가 봇이라면, 루틴의 길이는 이동 기록의 길이보다 작다는 것이 보장되며, 이동 기록에는 루틴에 따른 움직임이 반드시 최소 두 번은 기록된다.

루틴의 길이는 알려져 있지 않고, 무작위로 이동하는 길이도 정해져 있지 않기 때문에, 어떤 사용자가 사람인지 봇인지 판정하는 일은 쉽지 않다. 따라서 다음과 같이 가정해보자. 어떤 사용자가 봇이라면, 전체 이동 기록 중 정해진 루틴을 따라 이동한 기록이 인간인 사용자에 비해서 높을 것이다. 따라서 루틴이 무엇인지는 정확히 알 수 없지만, 전체 이동 기록 중 루틴에 따른 이동 기록, 즉 루틴의 길이를 이 루틴들이 서로 겹쳐지지 않게 나온 횟수로 곱한 값이 최대가 되는 루틴을 찾으면 이 사용자가 사람인지 봇인지 구별하는데 도움이 될 수 있다.

예를 들어 다음 두 기록을 보자.

• $n=30$이고, 어떤 유저의 이동 기록이 UDLRRUUDLRRDUDLRRLUDLRRRUDLRRU이라고 하자. 이 경우 이동 기록을 UDLRR-U-UDLRR-D-UDLRR-L-UDLRR-R-UDLRR-U로 분리해서 본다면 UDLRR의 루틴이 반복됨을 어렵지 않게 알 수 있다. 전체 이동 기록의 길이 $30$ 중 특정한 한 루틴에 따른 이동 기록의 길이가 $5\times 5 = 25$이며, 이로 볼때 높은 확률로 이 유저는 봇이라고 판단할 수 있다. UDLRRU도 전체에서 두 번 나오지만, 이것을 루틴이라고 보면 이 루틴에 따른 이동 기록의 길이는 $6\times 2=12$가 되어 더 짧아진다.
• $n=10$이고, 어떤 유저의 이동 기록이 UDLRRLDULR이라고 한다면, $2$번 이상 반복해서 나타나는 루틴 중 길이가 $1$인 것은 L 또는 R로 이들은 각각 $3$번 나오며, 길이가 $2$인 것은 LR 뿐이다. 전체 이동 기록의 길이 $10$ 중 특정한 한 루틴에 따른 이동 기록의 길이는 최대 $2\times 2 = 4$ 이며, 이로 볼때 높은 확률로 이 유저는 사람이라고 판단할 수 있다.

이 방법을 바탕으로 사용자가 봇인지 아닌지 탐지하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 세 정수 $n$, $a$, $b$가 주어진다. $n$은 이동 기록의 길이이며 ($1 \le n \le 3\,000$), $a$와 $b$는 ($1 \le a < b < n$) 해당 유저가 봇인지 아닌지 판정하기 위한 기준으로, 의미는 출력 형식에서 설명한다.

다음 줄에는 길이 $n$인 문자열이 주어진다. 이 문자열은 네 문자 U D L R 로 이루어져 있다.

출력 형식

출력은 한 줄로 구성되며, 해당 유저가 사람인지, 봇인지, 봇일수도 있고 사람일 수도 있는지를 출력한다. 이를 위해서 입력받은 $a$, $b$ 값을 사용하여 다음과 같이 판정한다.

모든 가능한 루틴마다 루틴에 따른 이동 기록, 즉 루틴의 길이를 이 루틴들이 서로 겹쳐지지 않게 나온 횟수로 곱한 값들의 최대값을 구한다. 이 값을 $n^\prime$ 이라고 하면, 다음과 같이 판단한다.

• 만약 $n^\prime > b$라면 확실히 이 유저는 봇이다.
• 만약 $a \le n^\prime \le b$라면 이 유저는 봇일 수도 있고 사람일 수도 있다.
• 만약 $n^\prime < a$라면 이 유저는 확실히 사람이다.

만약 이 유저가 확실히 봇이라면 $1$, 봇일 수도 있고 사람일 수도 있다면 $2$, 확실히 사람이라면 $3$을 출력한다.

예제

30 20 24
UDLRRUUDLRRDUDLRRLUDLRRRUDLRRU

1

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설