다중 다각수

다각수(polygonal number)는 같은 간격으로 놓인 점들을 정다각형 모양으로 배열했을 때 그 점의 개수로 표현할 수 있는 수이다. 아래 그림에 몇 가지 예가 있다.

첫 번째 그림은 삼각수 1, 3, 6, 10의 처음 네 개를 보여 준다. 나머지 세 그림은 각각 사각수, 오각수, 육각수의 처음 네 개를 보여 준다. 일반적으로 그 점들이 정 $k$각형을 이루는 수를 $k$각수($k$-gonal number)라 하며, 따라서 삼각수는 3각수, 사각수는 4각수이다. 이때 $k$를 다각수의 지표(index)라고 부른다. $m$번째 $k$각수는 다음과 같이 주어진다.

$P(k, m) = \frac{(k-2)m^2 - (k-4)m}{2}$

이 문제에서는 서로 다른 둘 이상의 $k$ 값에 대해 $k$각수가 되는 수를 찾는다. 이러한 수를 다중 다각수(poly-polygonal number)라고 부른다.

입력은 여러 개의 문제 인스턴스로 이루어진다. 각 인스턴스는 세 줄로 구성된다.

• 첫째 줄: 이 인스턴스에서 관심 있는 다각수 종류의 개수를 나타내는 음이 아닌 정수 $n$ ($n \le 50$).
• 둘째 줄: $n$개의 정수로, 관심 있는 다각수들의 지표이다. 모두 서로 다르며 증가하는 순서로 주어지고, 각 지표 $k$는 $3 \le k \le 1000$을 만족한다. (이 줄은 80자보다 길 수 있다.)
• 셋째 줄: 다중 다각수를 찾기 시작할 기준이 되는 양의 정수 $s$ ($s \le 10000$).

$n = 0$인 줄이 나오면 입력이 끝난다.

각 문제 인스턴스에 대해, $s$ 이상인 다중 다각수 중 작은 것부터 5개를 출력한다. 각 수는 한 줄에 하나씩 다음 형식을 따른다.

num:k1 k2 k3 ...

여기서 num은 다중 다각수이고, k1, k2, k3, ...는 num이 $k$각수가 되는(주어진 지표들 가운데의) 지표들을 증가하는 순서로 나열한 것이다. 각 지표는 공백 하나로 구분한다. 서로 다른 문제 인스턴스의 출력은 빈 줄 하나로 구분한다. 임의의 다중 다각수의 최댓값은 64비트 부호 있는 정수(long) 범위에 들어감이 보장된다.