20211번 - 게임 개발자 영우

문제

게임 개발자가 꿈인 영우는 컴퓨터게임설계 수업의 과제로 RPG 게임을 개발했다. 영우가 만든 RPG 게임은 다음의 단계들을 순차적으로 수행하며 진행된다.

• 1단계 : 시작하기 전 이번 게임에서 사용할 특수 파라미터 x, y를 플레이어가 임의로 정한다. 단, x와 y는 양의 정수이어야 한다.
• 2단계 : 게임을 시작하면 플레이어는 레벨이 0이고 보유 경험치가 0점인 상태로 시작한다.
• 3단계 : 우선 플레이어는 동전을 하나 던진다. 동전을 던져서 나온 면에 따라서 일반 또는 에픽 몬스터의 사냥에 도전하고, 사냥 결과에 따라 경험치를 획득한다.
  • 동전 앞면이 나온 경우 : 일반 몬스터 사냥에 도전한다. 일반 몬스터는 언제나 사냥에 성공하여 경험치를 3점 획득한다.
  • 동전 뒷면이 나온 경우 : 에픽 몬스터 사냥에 도전한다. 에픽 몬스터는 강력하므로 사냥에 실패할 수도 있다. 이때 게임 내부적으로는, 플레이어의 현재 보유 경험치에 따라 사냥 성공 여부가 결정된다. 만약 보유 경험치가 0 또는 짝수였다면, 사냥에 성공하여 경험치를 5점 획득한다. 만약 보유 경험치가 홀수였다면, 사냥에 실패하여 경험치를 1점 획득한다.
• 4단계 : 플레이어의 보유 경험치를 체크한다. 만약 보유 경험치가 x점 이상이라면 레벨업 이벤트가 발동되어, 레벨이 1 상승하고 보유 경험치는 0점으로 초기화된다. 이때 보유하고 있던 경험치가 x점을 초과해 아무리 많이 있었어도, 레벨이 여러번 오르거나 남는 경험치가 보존되지는 않는다.
• 5단계 : 플레이어의 레벨을 체크한다. 만약 현재 레벨이 y라면 게임이 즉시 클리어되고 플레이어는 더이상 게임을 진행할 수 없다. 레벨 y가 아니라면 3단계로 돌아가서 다시 동전을 던지고, 레벨 y가 될 때까지 이 과정을 반복한다. 레벨 y가 되기 전에는 절대 게임이 클리어되거나 종료되지 않는다.

영우는 이 게임을 이미 클리어했고 그 당시의 게임 진행 기록을 남겼다. 영우의 진행 기록에는 게임이 시작될 때부터 클리어 될 때까지 수행한 동전 던지기의 결과가 차례대로 나와있다. 하지만, 그 외에 다른 정보들은 깜빡하고 전혀 기록하지 않았다! 특히 이 게임에서 중요한 요소인 특수 파라미터 x, y를 어떤 값으로 정했는지도 기록하지 않았다.

영우는 디버깅을 위해 게임 진행 기록을 온전히 복원하고 싶어졌다. 이를 위해서는 영우가 게임에서 사용한 x, y의 값을 추정할 필요가 있다. 다행히도 우리는 영우가 만든 게임의 알고리즘을 알고 있기에, 이를 참고하여 x, y 값으로 가능한 것들이 무엇이 있는지 알아낼 수 있다.

영우의 게임 진행 기록을 보고 해당 게임에서 사용되었을 특수 파라미터 값 (x, y) 쌍으로 가능한 것들을 게임의 알고리즘에 근거하여 모두 찾아내보자.

입력

첫째 줄에는 게임 시작부터 클리어까지 플레이어가 동전을 던진 횟수를 의미하는 정수 N(1 ≤ N ≤ 32,000)이 주어진다.

둘째 줄에는 게임 시작부터 클리어까지 동전을 던져서 나온 면이 공백 없이 던진 순서대로 N개 주어진다. 앞면이 나온 경우는 H, 뒷면이 나온 경우는 T로 표현한다.

출력

첫째 줄에는 해당 게임에서 사용되었을 특수 파라미터 (x, y) 쌍으로 가능한 것의 개수 K를 출력한다.

둘째 줄부터 K개의 줄에 걸쳐서 가능한 (x, y) 쌍을 한 줄에 하나씩 출력한다. 각 줄에는 양의 정수 x와 y를 하나의 공백을 사이에 두고 출력한다.

만약 가능한 (x, y) 쌍이 여러 개라면, (x, y) 쌍들을 x의 오름차순으로 출력하되 x의 값이 동일한 쌍들 간에는 y의 오름차순으로 출력한다.

제한

힌트