꽤 좋은 비율

N개의 이진 숫자로 이루어진 수열이 있다. 0s와 1s의 비율이 딱 알맞은 부분 문자열을 찾고 있지만, 그런 부분 문자열이 존재하지 않을 수도 있으므로 그저 꽤 좋은 것에 만족하려 한다.

1s의 비율이 주어진 비율 F에 가능한 한 가까운 부분 문자열을 찾을 수 있는가? 그러한 부분 문자열이 시작할 수 있는 가장 이른 인덱스를 출력한다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 0 ≤ F ≤ 1 F는 소수점 뒤에 정확히 6개의 숫자를 가진다.

소규모 데이터셋

시간 제한: 240초. 1 ≤ N ≤ 1000.

대규모 데이터셋

시간 제한: 480초. 1 ≤ N ≤ 500,000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 N과 F가 포함된 한 줄로 시작한다. F는 0 이상 1 이하의 소수이며, 소수점 뒤에 정확히 6개의 숫자를 가진다. 다음 줄에는 N개의 숫자가 주어지며, 각 숫자는 0 또는 1이다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 1s의 비율이 F에 가능한 한 가까운 부분 문자열 시작 위치의 0 기반 인덱스이다. 가능한 답이 여러 개라면 올바른 값 중 가장 작은 값을 출력한다.

Case #1에서는 정확히 666667/1000000인 1 비율을 갖는 부분 문자열이 없다. 가능한 가장 가까운 값은 2/3이다. 입력 문자열에는 이를 달성하는 부분 문자열이 5개 있다. 즉, 인덱스 5, 7, 8에서 시작하는 길이 3의 부분 문자열 3개가 있고(101, 101, 011), 인덱스 5과 6에서 시작하는 길이 6의 부분 문자열 두 개도 있다(101011 및 010111). 이 인덱스들 중 가장 작은 것은 5이다.