다다스는 모 문제에 사용할 그래프를 만들었다. 이 그래프는 개의 행과 개의 열로 이루어진 격자 모양의 유향 그래프이다. 각 정점은 로 나타내며, , 이다.
상하좌우로 인접한 두 정점 사이에는 정확히 하나의 유향 간선이 존재한다. 즉, 가로나 세로로 인접한 두 정점 사이의 간선은 두 방향 중 정확히 한 방향으로만 존재한다.
다다스가 만든 그래프는 원래 DAG여야 했다. 하지만 그래프를 유심히 살펴보던 모그는 이 그래프에 사이클이 존재한다는 사실을 발견했다!
모그는 다다스에게 문제를 알려 주기 위해, 사이클이 포함된 부분만 직사각형 모양으로 잘라서 보내 주려고 한다. 이왕이면 보내야 할 부분이 작을수록 좋으므로, 모그는 사이클을 포함하는 가장 작은 부분 직사각형을 찾고 싶다.
네 정수 가
을 만족할 때, 가 나타내는 은 다음 정점들과 그 사이의 모든 간선으로 이루어진 유도 부분 그래프이다.
부분 직사각형의 넓이는
로 정의한다.
다행히(?) 모그의 발견은 틀리지 않았으며, 주어진 그래프에는 적어도 하나의 유향 사이클이 존재한다.
모그를 도와 유향 사이클을 포함하는 부분 직사각형 중 넓이가 가장 작은 것을 찾아보자!
넓이가 가장 작은 부분 직사각형이 여러 개라면, 가 사전순으로 가장 작은 것을 구해야 한다.
입력은 다음과 같은 형식으로 주어진다.
case case
각 테스트 케이스마다 한 줄에 정답을 나타내는 네 정수 를 공백으로 구분하여 출력한다.
첫 번째 테스트 케이스에서는 전체 직사각형이 유향 사이클을 이룬다.
두 번째 테스트 케이스에서는 행 부터 , 열 부터 까지의 직사각형이 유향 사이클을 포함한다.
각 케이스는 다음과 같은 형식으로 주어진다.
각 는 길이가 인 문자열이다. 는 와 사이의 간선 방향을 나타낸다.
각 는 길이가 인 문자열이다. 는 와 사이의 간선 방향을 나타낸다.
L 또는 R이다 (, ).U 또는 D이다 (, ).세 번째 테스트 케이스에서는 어떤 더 작은 부분 직사각형도 유향 사이클을 포함하지 않으며, 전체 직사각형이 답이다.