오래된 컴퓨터에서 그림판을 사용하고 있다. 그림판의 화면은 픽셀이라 부르는 칸을 가진 격자 모양이다. 가장 왼쪽 아래 픽셀의 좌표를 (1, 1)로 하고, 오른쪽으로 a번째 위쪽으로 b번째 픽셀의 좌표를 (a, b)로 한 다. 초기 화면에는 수직, 수평 변을 가진 N개의 직사각형들이 그려져 있다. 직사각형은 이 구역안에 포함된 픽셀들로 표현된다.

N개의 직사각형에 M개의 이동 명령이 수행될 것이다. 직사각형의 이동은 동, 서, 남, 북의 4방향과 북동, 북서, 남동, 남서(수평축과 45도 방향) 4방향으로 이루어진다. 또한 이동 거리 d가 주어진다. 다시 말해서, 이동 명령은 방향과 거리로 주어진다. 구체적으로, 직사각형의 가장 왼쪽, 아래 모서리 픽셀의 좌표가 (a, b) 라 하면, 동, 북, 서, 남 방향으로 거리 d만큼의 이동은 모서리가 각각 (a+d, b), (a, b+d), (a−d, b), (a, b−d) 가 된다. 또한 북동, 북서, 남서, 남동 방향으로 거리 d만큼의 이동은 각각 (a + d, b + d), (a − d, b + d), (a − d, b − d), (a + d, b − d)가 된다.

화면에서 직사각형 R의 거리 d만큼 이동은 초기 위치를 포함해서 R이 거리 1 만큼 이동할 때마다 R의 모습을 순서대로 빠르게 나타냄으로서 구현된다. 하지만 우리의 컴퓨터는 아주 오래 되어서 R의 이동 시 렉이 심하게 걸린다. 결과적으로 R의 이동에서 그리게 되는 모든 R의 모습이 화면에 그대로 남아있게 된다. 따라서 R이 거리 d만큼 이동하면, d개의 직사각형들이 새롭게 화면에 만들어진다. 예를 들어, 직사각형이 북동방향으로 거리 3만큼 이동하면, 3개의 직사각형들이 만들어져서 총 4개의 직사각형이 화면 위에 남게 된다. 물론, 이동 후에는 북동 방향 끝에 있는 직사각형이 R 이 된다.

M개의 이동 명령을 수행한 후 Q개의 질의가 주어질 것이다. 각 질의는 평면 상의 픽셀 p로 주어진다. 질의에 대한 대답으로 픽셀 p를 포함하는 직사각형들의 개수를 출력한다.

#5067 upload 15 done 3 how_to_reg 2 call_split Subtarea

렉 timer 8s memory 1024MB

#5067
Subtarea

렉 8s 1024MB