비밀번호

스포츠, 특히 프로야구에서 "비밀번호"는 암흑기에 기록한 등수를 순서대로 이어 붙여 부르는 말이다. 한국 프로야구의 롯데 자이언츠는 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_1$ 이상 $L_2$ 이하이다.

조건을 만족하는 후보가 여럿이면 읽었을 때 임팩트가 가장 크도록 등수 수열이 사전순으로 가장 큰 것을 고른다. 두 후보는 앞에서부터 등수를 하나씩 수의 크기로 비교하고, 처음으로 등수가 갈리는 자리에서 더 큰 등수를 가진 쪽이 크다. 한쪽이 다른 쪽의 앞부분과 끝까지 같으면 더 긴 쪽이 크다. 팀이 8개인 리그에서 8등, 7등, 2등, 8등, 7등, 7등을 기록하고 $L_1 = 2$, $L_2 = 3$이면 비밀번호는 8-7-7이다. 같은 조건에서 8등, 7등, 2등, 7등, 7등, 7등을 기록했다면 비밀번호는 8-7이다.

$K$개 팀이 있는 리그에서 뛰는 어느 팀의 $N$년치 등수가 주어진다. 이 팀의 비밀번호와, 그 비밀번호가 $N$년치 등수 기록에 등장하는 횟수를 구하라. 서로 겹치는 등장도 각각 센다.

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

각 테스트 케이스의 첫 줄에 네 정수 $K$, $N$, $L_1$, $L_2$가 공백으로 구분되어 주어진다. ($1 \le K \le 100000$, $1 \le N \le 200000$, $1 \le L_1 \le L_2 \le N$)

각 테스트 케이스의 둘째 줄에 이 팀의 $N$년치 등수인 정수 $N$개가 주어진다. $i$번째 정수 $R_i$는 $i$번째 해의 등수이다. ($1 \le R_i \le K$)

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

첫 줄에는 비밀번호를 출력하고, 둘째 줄에는 그 비밀번호가 등수 기록에 등장하는 횟수를 출력한다. 조건을 만족하는 비밀번호가 하나도 없으면 첫 줄에 -1을, 둘째 줄에 0을 출력한다.