패션 경찰 (Large)

2016 Code Jam World Finals가 너무 기대된 나머지 뉴욕으로 이사를 왔다. 가져온 옷은 서로 다른 재킷 $J$벌(1번부터 $J$번), 서로 다른 바지 $P$벌(1번부터 $P$번), 서로 다른 셔츠 $S$벌(1번부터 $S$번)이다. 셔츠는 바지보다 적지 않고, 바지는 재킷보다 적지 않다. ($J \le P \le S$)

매일 재킷 하나, 바지 하나, 셔츠 하나를 골라 한 벌의 옷차림으로 입는다. 옷은 매일 밤 전부 빨기 때문에 모든 옷을 매일 입을 수 있다.

뉴욕에서는 패션 경찰이 모든 사람이 매일 무엇을 입는지 항상 지켜보고 기록한다. 완전히 같은 옷차림을 두 번 입은 사실이 드러나면 곧바로 5번가의 패션 감옥으로 끌려가 강제로 스타일을 바꾸게 된다. 이것만은 반드시 피하고 싶다! 같은 두 옷의 조합을 모두 합해 $K$번보다 많이 입은 사실이 드러나도 곧바로 패션 감옥으로 끌려간다. 조합이란 특정 재킷과 특정 바지, 특정 재킷과 특정 셔츠, 또는 특정 바지와 특정 셔츠를 함께 입은 것을 말한다. 예를 들어 옷차림 (재킷 1, 바지 2, 셔츠 3)과 (재킷 1, 바지 1, 셔츠 3)으로 이루어진 집합에서 조합 (재킷 1, 셔츠 3)은 두 번 나타나고, 조합 (바지 1, 셔츠 3)은 한 번만 나타난다.

하루에 한 벌씩 입는다. 패션 감옥에 끌려가지 않고 버틸 수 있는 최대 일수를 구하고, 매일 입을 옷차림 목록을 만들어 보자.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 네 정수 $J$, $P$, $S$, $K$가 담긴 한 줄이다.

제한

• $1 \le T \le 100$
• $1 \le J \le P \le S$
• $1 \le K \le 10$
• $S \le 10$

각 테스트 케이스마다 먼저 Case #x: y 형식의 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 패션 감옥에 끌려가지 않고 버틸 수 있는 최대 일수다. 이어서 y개의 줄에 하루치 옷차림을 재킷, 바지, 셔츠 번호 순서대로 세 정수로 출력한다.

답이 하나로 정해지도록, 옷차림 $(a, b, c)$(재킷 $a$, 바지 $b$, 셔츠 $c$)는 다음 조건을 만족할 때에만 목록에 넣는다.

$(c - a - b + 1) \bmod S < \min(K, S)$

여기서 $\bmod$의 결과는 $0$ 이상 $S - 1$ 이하의 값으로 잡는다. 조건을 만족하는 옷차림을 모두, 사전순(재킷 번호, 바지 번호, 셔츠 번호 순으로 비교)으로 오름차순 정렬해 출력한다. 이 규칙으로 만든 목록은 패션 감옥에 끌려가지 않는 목록 가운데 가장 긴 목록이다.

1번 케이스에서는 패션 경찰이 $K = 10$으로 너그럽게 봐 주지만, 만들 수 있는 옷차림이 하나뿐이므로 패션 감옥을 피할 수 있는 날은 하루뿐이다.

2번 케이스에서 다른 옷차림을 하나라도 더하면 패션 감옥에 끌려간다.

• 1 1 3을 더하면 조합 (재킷 1, 바지 1)을 2번보다 많이 쓰게 된다.
• 1 2 1을 더하면 조합 (재킷 1, 바지 2)를 2번보다 많이 쓰게 된다.

이 케이스에서는 옷차림 5개로 이루어진 어떤 집합도 규칙을 적어도 하나 어긴다.

$J$, $P$, $S$와 달리, 한 옷차림 안의 재킷, 바지, 셔츠 번호가 비내림차순일 필요는 없다.

3번 케이스에서는 재킷과 바지 조합이 하나뿐이라 그 조합을 계속 써야 한다. 따라서 어떤 셔츠를 입든 서로 다른 옷차림을 $K = 2$개보다 많이 만들 수 없다.

4번 케이스에서 최대 크기의 옷차림 집합은 여러 가지이지만, 출력 규칙에 따르면 1 1 1과 1 2 2를 출력해야 한다.