최고의 펫 만들기

Petya는 멀티플레이어 컴퓨터 게임을 한다. 게임에서 Petya를 나타내는 영웅은 최대 세 마리의 펫을 가질 수 있다.

각 펫에는 공격력과 방어력을 담당하는 여덟 개의 매개변수가 있다. 각 매개변수는 $1$부터 $999$까지의 정수이다. $500$보다 큰 수는 주로 공격력을 올리고, 작은 수는 방어력에 좋다. 일반적으로 각 매개변수가 $500$에서 어느 쪽으로든 더 멀리 벗어날수록 더 좋다. 또한 각 펫에는 외형을 결정하는 여덟 개의 유전 매개변수가 있다. 마지막으로 각 펫에는 이름이 있다.

플레이어가 게임 상점에서 펫을 사기로 하면 이름만 고를 수 있다. 그 뒤 알고리즘이 실행되어 능력 매개변수와 유전 매개변수를 무작위로 정한다. Petya는 이미 펫 한 마리를 샀지만 만족하지 못했다. 능력 매개변수가 평범했기 때문이다. 그는 다음번에는 무슨 수를 써서라도 강한 펫을 얻기로 굳게 마음먹었다. 그런데 어떻게 해야 할까?

조사 끝에 Petya는 스크립트 언어 XyzzyLang으로 작성된 펫 생성 코드를 손에 넣었다. 코드는 다음과 같다.

CreateRandomPet (Name):
    Seed := Now xor Hash (Name) xor Salt
    return Pet:
        Pet.Name := Name
        for I := 1, 2, ..., 8:
            Pet.Power[I] := GenerateRandomPower
        for J := 1, 2, ..., 8:
            Pet.Gene[J] := Random mod 5

Hash (String):
    Result := 0
    for I := 1, 2, ..., String.Length:
        Result := Result * 31 + String[I].AsciiCode
    return Result

Random:
    Seed := Seed * 1234567893 + 151515151
    return Seed

GenerateRandomPower:
    Result := 500
    for I := 1, 2, ..., 10000:
        Result := Result + Random mod 3 - 1
    return Result

Petya는 이 언어를 처음 접했지만, 프로그램의 모든 수가 정수이고 모든 계산이 $2^{31}$을 법으로 수행된다는 것은 이미 알아냈다. 코드에서 보듯이 펫의 매개변수는 세 수 $\mathrm{Now}$, $\mathrm{Hash} (\mathrm{Name})$, $\mathrm{Salt}$로 완전히 결정된다. Petya는 함수 $\mathrm{Now}$가 현재 시각을 유닉스 타임스탬프 형식(1970년 1월 1일부터 지난 초의 수)으로 반환한다는 것을 안다. 함수 $\mathrm{Hash}$는 문자의 ASCII 코드(A-Z는 65-90, a-z는 97-122)를 사용한다. 그러나 Petya는 수 $\mathrm{Salt}$의 값을 어디에서도 찾지 못했다.

Petya가 보기에 펫의 품질은 능력 매개변수가 $500$에서 벗어난 정도의 평균, 즉 절댓값 차 $|500 -$Power[I]$|$의 합을 $8$로 나눈 값이다. 유전 매개변수는 고려하지 않는다.

Petya는 다음 펫에 쓸 좋은 이름을 이미 생각해 두었고, 시각 $\mathrm{Start}$에 펫을 만들고 싶어 한다. 하지만 강한 펫을 얻기 위해 $0$초부터 $\mathrm{Wait}$초까지 기다릴 수 있다. 이 조건에서 가능한 한 품질이 높은 펫을 얻으려면 Petya가 정확히 언제 구매해야 하는지 구하시오.

이 문제의 모든 테스트에서 수 $\mathrm{Salt}$는 $0$부터 $2^{31} - 1$까지의 같은 비밀값이다. 예제는 Petya가 처음 산 펫을 보여 준다.

첫째 줄에 두 정수 $\mathrm{Start}$와 $\mathrm{Wait}$가 주어지고, 이어서 단어 $\mathrm{Name}$이 주어진다($1\,535\,814\,000 \le \mathrm{Start} \le 2\,000\,000\,000$, $0 \le \mathrm{Wait} \le 120$). 단어 $\mathrm{Name}$의 길이는 $1$부터 $20$까지이며, 영문 대문자와 소문자만 포함할 수 있다.

첫째 줄에 정수 하나와 실수 하나를 출력한다. 정수는 최고의 펫을 생성할 시각이고, 실수는 그 펫의 품질이다. 품질은 가능한 한 정확하게 출력한다. 둘째 줄에는 생성된 펫의 능력 매개변수 여덟 개를 순서대로 출력한다. 셋째 줄에는 펫의 유전 매개변수 여덟 개를 순서대로 출력한다.

최대 품질을 가진 펫을 여러 마리 생성할 수 있다면, 더 이른 시각에 생성할 수 있는 펫을 출력한다.