영원히 끝나지 않는 투표

추상적인 투표 절차를 하나 생각해 보자. 예를 들어 Bullet for My Valentine의 2019년 최고의 곡을 뽑는 투표가 이런 절차일 수 있다.

투표에는 $n$명이 참여하고, 투표 대상은 $m$개의 선택지다. 각 사람에게는 선택지 일부가 가장 선호하는 것부터 순서대로 적힌 선호 목록이 있다. 선호 목록에 없는 선택지는 덜 선호하는 정도가 아니라, 그 사람이 받아들이지 않는 선택지다.

투표는 반복으로 진행된다.

첫 번째 반복에서는 모든 사람이 자신의 선호 목록 맨 앞의 선택지에 투표한다. 선택지별 득표 수를 세어 모든 사람에게 공개한다.

그 다음 반복부터는 각 사람이 자신의 선호 목록에 있는 선택지 가운데, 직전 반복에서 득표 수가 가장 많았던 선택지에 투표한다. 그런 선택지가 여러 개면 선호 목록에서 더 앞에 있는 선택지가 이긴다.

매 반복 전에는 직전 반복과 다르게 투표할 사람이 있는지 묻는다. 아무도 없으면 그 반복은 진행하지 않고, 마지막 반복의 결과를 최종 결과로 선언한다. 있으면 위 방식대로 투표하고 득표 수를 다시 세어 공개한다. 이전 반복의 표는 모두 무시된다.

이 절차는 번거롭고, 결과를 알아내는 데 끝이 없을 것처럼 보인다. 이를 증명하기 위해, 적어도 100번의 반복이 진행되도록 $n$, $m$과 선호 목록을 제시하라.

입력은 한 줄이며, 정수 $p$ 하나가 주어진다. 이 값은 필요한 반복 횟수다.

테스트 케이스는 두 개다. 첫 번째 케이스에서는 $p = 2$이고, 두 번째 케이스에서는 $p = 100$이다.

두 정수 $n$과 $m$을 출력한다($1 \le n \le 10^5$; $1 \le m \le 2 \cdot 10^5$). 각각 사람 수와 선택지 수다. 이어서 $n$개의 선호 목록을 출력한다.

각 선호 목록은 목록에 있는 선택지 수 $k_i$($1 \le k_i \le m$)로 시작하고, 이어서 서로 다른 정수 $a_{i,j}$($1 \le a_{i,j} \le m$) $k_i$개를 가장 선호하는 것부터 순서대로 적는다.

모든 $k_i$의 합은 $2 \cdot 10^5$을 넘을 수 없다.

예시 테스트를 보자.

첫 번째 반복에서는 모든 사람이 자신의 목록 맨 앞의 선택지에 투표한다. 따라서 첫 번째 사람은 1번에, 두 번째와 네 번째 사람은 2번에, 세 번째 사람은 5번에 투표한다.

두 번째 반복에서는 2번이 앞서 있으므로, 첫 번째 사람이 1번에서 2번으로 투표를 바꾼다. 나머지 사람은 투표를 그대로 유지한다. 특히 세 번째 사람은 첫 반복에서 5번과 1번이 각각 1표씩 받았지만, 목록에서 5번이 더 앞에 있으므로 계속 5번에 투표한다.

세 번째 반복은 아무도 투표를 바꾸고 싶어 하지 않으므로 진행되지 않는다. 두 번의 반복이 진행되었으므로 $p = 2$ 조건을 만족한다.