34080번 - 일천광년

문제

일천광년 앞으로

끊기지 않을 실로 이어줄래

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

— 一千光年 - 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ドル \leq Q \leq 393939$
• 1ドル \leq N \leq 9460730472580800$
• 1ドル \leq x, y \leq 10^9$
• 1ドル \leq N \times x \times y \leq 10^{18}$

노트

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

[フレーム]