일천광년

시간 제한3.9초메모리 제한1000 MB

요약

거리 N의 양 끝에 x와 y만큼의 사랑이 있을 때, 매 단계 더 작은 쪽을 안쪽으로 한 칸 옮기는 과정을 천문학적인 시간만큼 반복한 뒤 사랑이 남아 있는 위치와 양을 구한다.

문제

일천광년 앞으로

끊기지 않을 실로 이어줄래

그 소매에 사랑을 숨겨보고파

— 一千光年 - iyowa

미쿠는 모래의 행성에, 플라워는 모래의 행성으로부터 $N\ \text{km}$ 떨어진 푸른 행성에 살고 있다. 미쿠와 플라워는 어느 날, 넘치는 사랑을 서로에게 전하기로 했다!

모래의 행성에서 푸른 행성 방향으로 $i\ \text{km}$ 떨어진 위치에 있는 사랑의 양은 $L\_i$ 로 표현되며, 초기에는 $L\_0=x$ , $L\_N=y$ , $L\_j = 0$ ( $1 \leq j < N$ )이다.

미쿠와 플라워는 $1$ 의 시간이 지날 때마다 다음과 같이 서로를 향해 사랑을 옮긴다.

$L\_i \neq 0$ 을 만족하는 $i$ 중에서 $i$ 의 최솟값과 최댓값을 각각 $l$ 과 $r$ , 이때의 $\min(L\_l,L\_r)$ 을 $M$ 이라고 하자.
$r-l>1$ 인 경우, $L\_l$ 과 $L\_r$ 의 값을 $M$ 만큼 감소시키고, $L\_{l+1}$ 과 $L\_{r-1}$ 의 값을 $M$ 만큼 증가시킨다.
$r-l \leq 1$ 인 경우, 옮겼을 때 서로의 뜨거운 사랑이 너무 가까워져 미쿠미쿠해지므로♪ 사랑 옮기기를 중단한다.

미쿠와 플라워는 여러 상황에서 사랑이 어디에 도달할지 궁금해졌다. $39^{39^{39}}$ 의 시간이 지났을 때, $Q$ 개의 상황에 대해 사랑이 존재하는 위치와 사랑의 양을 구해 주자!

첫 번째 줄에 상황의 수 $Q$ 가 주어진다.

두 번째 줄부터 $Q+1$ 번째 줄까지 각 줄에 양의 정수 $N$ , $x$ , $y$ 가 공백으로 구분되어 주어진다.

주어진 $Q$ 개의 각 상황에 대해, 첫 번째 줄에 사랑이 존재하는 위치의 수를 출력한다.

두 번째 줄부터는 모든 사랑이 존재하는 위치에 대해, 각 줄에 모래의 행성에 가까운 순으로 모래의 행성으로부터 사랑이 존재하는 위치까지의 거리와 사랑의 양을 공백으로 구분하여 출력한다.

이 문제는 노래 일천광년 (一千光年)을 모티브로 하였다.

예제 1

입력

예상 출력

예제 2

입력

예상 출력