새 트랙

게르 킬케는 포뮬러-Y 경주에 쓸 트랙을 설계하고, 이번에 새 트랙을 만들려고 한다. 트랙을 놓을 평면에 직교좌표계를 잡는데, x축은 오른쪽, y축은 위쪽을 향한다. 트랙은 다음 조건을 모두 만족해야 한다.

• 트랙은 좌표축과 평행한 선분 $n$개로 이루어진 꺾은선이다.
• 꺾은선의 한쪽 끝은 출발점, 반대쪽 끝은 도착점이고, 두 점은 서로 다르다.
• 모든 선분 끝점의 두 좌표는 $3000$ 이하의 양의 정수다.
• 모든 선분의 길이는 0이 아니다.
• 출발점에서 도착점으로 따라갈 때, 한 선분이 끝나고 다음 선분이 시작하는 지점마다 시계 방향으로 90도 꺾는다.
• 어떤 선분의 끝점도 다른 선분 위에 놓이지 않는다. 다만 이웃한 두 선분은 끝점 하나를 공유한다. 특히 서로 다른 두 선분이 길이가 0이 아닌 부분을 공유하는 일은 없다.

교차점은 이웃하지 않은 두 선분에 동시에 속하는 점이다. 게르는 선분이 $n$개이고 교차점이 정확히 $k$개인 트랙을 원한다. 이런 트랙은 $0 \le k \le n_2(n_2 - 1)/2$일 때만 존재하고($n_2 = \lfloor n/2 \rfloor$), 게르는 언제나 이 범위에서 $k$를 고른다.

조건을 만족하는 트랙은 여러 개이므로, 출력 부분의 규칙으로 답을 하나로 정한다. 그 트랙을 구하라.

첫째 줄에 테스트 케이스의 개수 $t$가 주어진다 ($1 \le t \le 10^4$). 다음 $t$개 줄에는 각각 두 정수 $n$과 $k$가 주어진다 ($1 \le n \le 1000$, $0 \le k \le n_2(n_2 - 1)/2$, $n_2 = \lfloor n/2 \rfloor$). $n$은 트랙을 이루는 선분의 개수, $k$는 필요한 교차점의 개수다. 모든 테스트 케이스의 $n$의 합은 $10^4$을 넘지 않는다.

각 테스트 케이스마다 트랙의 꼭짓점 $n + 1$개를 출발점부터 도착점까지 한 줄에 하나씩 출력한다. 각 줄에는 꼭짓점의 x좌표와 y좌표를 공백으로 구분해 적는다. 테스트 케이스는 입력 순서대로 사이에 아무것도 넣지 않고 이어서 출력한다.

출력할 트랙은 아래 규칙으로 만든 트랙이다. $H = \lceil n/2 \rceil$, $V = \lfloor n/2 \rfloor$이라 하자.

$x_0, x_1, \dots, x_H$은 짝수 $i$에 대해 $x_i = 1 + i/2$, 홀수 $i$에 대해 $x_i = 3000 - (i - 1)/2$이다.

$y_0, y_1, \dots, y_V$은 $k$에서 정해진다. $m \le V$이면서 $m(m - 1)/2 \le k$인 가장 큰 정수를 $m$이라 하고, $r = k - m(m - 1)/2$이라 하자. $1 \le q \le m$이면 $c_q = q - 1$, $m + 1 \le V$이면 $c_{m+1} = r$, $m + 1 < q \le V$이면 $c_q = 0$이다. 이때 $y_0, y_1, \dots, y_V$은 $1, 2, \dots, V + 1$의 순열 중 $1$ 이상 $V$ 이하인 모든 $q$에 대해 아래 두 조건을 만족하는 순열이고, 그런 순열은 정확히 하나다.

• $q$가 홀수면 $y_q < y_{q-1}$, $q$가 짝수면 $y_q > y_{q-1}$이다.
• $y_0, y_1, \dots, y_{q-2}$ 중 정확히 $c_q$개가 $y_{q-1}$과 $y_q$ 사이에 양 끝을 빼고 놓인다.

트랙의 $2j$번 꼭짓점은 $(x_j, y_j)$, $2j + 1$번 꼭짓점은 $(x_{j+1}, y_j)$이다. $0$번 꼭짓점부터 $n$번 꼭짓점까지 순서대로 출력한다.

이 트랙은 문제의 조건을 모두 만족하고, 교차점은 정확히 $k$개다.