눈 벽

눈싸움에서 굴욕을 당한 스웨덴은 눈 벽을 쌓고 그 비용을 핀란드에게 치르게 하려 한다. 벽의 너비는 $W$이고, 가능한 한 높아야 한다 (엄청나게 높을 거다!).

각 블록의 높이는 1이지만 너비는 블록마다 다를 수 있다. 벽을 쌓을 때 모든 블록은 다음 규칙을 만족해야 한다. 블록 바로 아래 줄에서, 블록의 두 끝점이 놓인 각 위치마다 그 점의 바로 오른쪽과 바로 왼쪽에 블록이 하나씩 있어야 한다. 다만 줄의 시작과 끝에서는 이 규칙이 적용되지 않는다. 대신 모든 줄의 그 자리에 끝점이 있어야 한다.

벽에서 바로 이어지는 두 줄의 같은 위치에 구멍이 있어서는 안 된다. 벽 바로 위의 빈 줄은 계산에 넣지 않는다.

그림 1: 허용되지 않는 벽(왼쪽)과 허용되는 벽(오른쪽)의 예.

첫 줄에 테스트 케이스 번호 $T$, 블록 수 $N$, 벽의 너비 $W$가 정수로 주어진다. 다음 줄에는 각 블록의 너비가 $N$개의 정수로 주어진다.

모든 테스트 케이스는 20887.zip 파일로 받을 수 있다.

첫 줄에 벽의 높이 $H$를 출력한다.

이어서 벽의 각 줄마다 한 줄씩, 총 $H$줄을 출력한다. $i$번째 줄에는 먼저 그 줄의 블록 수 $B$를 쓰고, 이어서 $j$번째 블록의 위치 $P_{i,j}$와 길이 $L_{i,j}$를 쌍으로 $B$개 쓴다.

테스트 케이스 번호 $T$를 입력받아 그 테스트 케이스의 풀이를 출력하는 프로그램만 제출하면 된다.

직접 프로그램을 작성하기 싫다면 http://progolymp.se/uploads/snokaosgen.html을 쓸 수 있다. 그곳에 모든 풀이를 붙여 넣으면 제출할 수 있는 Python 3 프로그램을 받는다.