플로터

새로 산 플로터를 시험해 보려고 바이트아사르는 몇 개의 바이트커브를 그려 보기로 했다.

$n$차 바이트커브는 길이가 각각 $\sqrt{2}$인 선분 $2^n$개로 이루어진다. 첫 번째 선분은 점 $(0, 0)$과 $(1, 1)$을 잇는다. $n$차 바이트커브는 두 글자 $\{L, R\}$로 이루어진 길이 $2^n - 1$의 단어 $L_n$으로 표현된다. 이 단어의 $i$번째 글자는, $i$번째 선분을 그린 직후 펜이 $90°$ 회전하여 다음 선분을 그리기 전에 왼쪽($L$) 또는 오른쪽($R$)으로 직각으로 방향을 바꾼다는 뜻이다.

$L_1$은 글자 $L$ 하나(왼쪽으로 한 번 회전)이고, $L_2 = LLR$(왼쪽 두 번 뒤 오른쪽 한 번)이다. 일반적으로 $L_n$은 $L_{n-1}$로부터 다음과 같이 만든다. $L_{n-1}$의 글자들을 한 칸씩 띄어 쓰고 맨 앞과 맨 뒤에도 빈칸을 하나씩 더 둔 다음, 새로 생긴 빈칸들을 왼쪽부터 $L, R, L, R, \dots$ 순서로 $L$부터 번갈아 채운다. 예를 들어,

$L_2 = LLR \;\longrightarrow\; \_\,L\,\_\,L\,\_\,R\,\_ \;\longrightarrow\; LLRLLRR = L_3,$

같은 방식으로 $L_4 = LLRLLRRLLLRRLRR$이다(아래 그림 참고).

선분 하나를 그리는 데 정확히 $1$초가 걸리고, 펜은 시각 $0$에 $(0, 0)$에서 출발한다. 플로터가 그리는 동안 바이트아사르는 궁금해한다. 주어진 점 $(x, y)$에 펜이 놓이는 시각은 언제인가? 예를 들어 위의 $4$차 바이트커브에서 펜은 $7$초 후와 다시 $11$초 후에 $(-3, -1)$에 놓인다. 바이트아사르의 질문에 답하라.

첫 줄에 두 정수 $n$과 $m$ ($1 \le n, m \le 2000$)이 주어진다. 곡선은 $L_n$이고 질의할 점은 $m$개다. 이어지는 $m$개의 각 줄에는 두 정수 $x_i$와 $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), 곧 $i$번째 질의 점의 좌표가 주어진다. 질의 점이 곡선 위에 있지 않을 수도 있으며, 같은 점이 입력에 두 번 나타나지 않는다.

질의 순서대로 $m$개의 줄을 출력한다. $i$번째 질의에 대해, $n$차 곡선을 그리는 동안 펜이 $(x_i, y_i)$에 놓이는 횟수인 음이 아닌 정수 $k_i$(시각 $0$의 시작 위치도 한 번의 방문으로 센다)를 먼저 출력하고, 이어서 그 $k_i$개의 방문 시각을 그리기 시작한 뒤 초 단위로 오름차순으로 출력한다. 한 줄의 모든 수는 공백 하나로 구분하며, 줄의 앞뒤에는 공백이 없어야 한다.

이 문제가 재미있었다면, 같은 질문을 더 빡빡한 제약에서 다루는 더 어려운 변형을 풀어 보라.