13205번 - 비밀번호

스포츠, 특히 프로야구에서 ‘비밀번호’ 라 함은 암흑기의 등수를 지칭하는 말이다. 예를 들어, 한국 프로야 구의 롯데 자이언츠는 2001년부터 2007년까지 매년 8등, 8등, 8등, 8등, 5등, 7등, 7등을 순서대로 찍으며 ‘8-8-8-8-5-7-7’ 이라는 비밀번호를 작성하였다. 또한, 같은 리그의 LG 트윈스는 2003년부터 2012 년까지 ‘6-6-6-8-5-8-7-6-6-7’ 이라는 비밀번호를 작성하였고, 한화 이글스는 2008년부터 현재까지 ‘5-8-8-6-8-9-9-6’ 이라는 비밀번호를 작성하고 있다.

비밀번호를 한국 프로야구 뿐만 아니라 모든 스포츠의 프로 리그에 확장시키기 위해, 다음과 같이 ‘비밀번호’ 를 정의하였다.

1. 비밀번호는 암흑기의 등수를 순서대로 나열한 다음, 그 등수 사이에 하이픈 ( ‘-’ )을 넣은 형태이다. 예를 들어, 8등, 11등, 7등, 6등을 순서대로 한 경우 ‘8-11-7-6’ 이 비밀번호가 된다.
2. 비밀번호에 등장하는 숫자는 (해당 리그의 팀 수)의 절반보다 큰 수여야 한다. 예를 들어, 8팀 혹은 9팀이 있는 리그에서는 5 이상의 숫자로만 이루어져야 한다.
3. 비밀번호의 길이는 L₁ 이상 L₂ 이하이다. 비밀번호의 후보가 여러 개가 될 수 있는데, 비밀번호를 읽을 때 임팩트가 강렬할 수 있도록 내림차순으로 가장 빠른 것을 선택한다. 예를 들어, 8팀이 있는 리그에서 8등, 7등, 2등, 8등, 7등, 7등을 했고, L₁ = 2 L₂ = 3인 경우, ‘8-7-7’ 이 비밀번호가 된다. 만약, 8등, 7등, 2등, 7등, 7등, 7등을 한 경우라면 ‘8-7’ 이 비밀번호가 된다.

K 팀이 있는 스포츠 리그가 있다. 이 스포츠 리그에 있는 팀의 N 년 동안 등수가 주어졌을 때, 이 팀의 비밀번호와 이 팀의 비밀번호가 반복된 횟수를 알아내자.

첫 번째 줄에 테스트 케이스의 수 T 가 주어진다.

각 테스트 케이스의 첫 번째 줄에 네 개의 정수 K, N, L₁, L₂ 가 순서대로 공백으로 분리되어 주어진다. (1 ≤ K ≤ 100, 000, 1 ≤ N ≤ 200, 000, 1 ≤ L₁ ≤ L₂ ≤ N)

각 테스트 케이스의 두 번째 줄에 이 팀의 N 년간 등수 정보인 N 개의 정수가 주어진다. i번째에 주어지는 정수 R_i 는 i번째 해의 등수를 의미한다. (1 ≤ R_i ≤ K)

각 테스트 케이스마다 두 줄을 출력한다.

각 테스트 케이스에 대해 첫 번째 줄에 비밀번호를 출력하고, 두 번째 줄에 비밀번호가 등장하는 횟수를 출력한다.