16128번 - 스눕시티

카젤은 도시 운영 게임을 플레이하고 있다. 이 게임에서는 2^N × 2^N 크기의 땅에 다양한 오브젝트를 배치할 수 있다. 땅에는 격자가 그려져 있고, 모든 오브젝트는 격자에 맞춰서 배치해야 한다. 즉 한 오브젝트가 차지하는 영역이 어떤 격자칸과 일부만 겹쳐서는 안 된다. 오브젝트는 원하는 방향을 향하도록 회전시켜서 배치할 수도 있다.

이 게임에는 매 시간마다 금화를 생산하는 건물 오브젝트와 도시의 아름다움 수치를 늘려 주는 꽃밭 오브젝트가 있다. 그 중 가장 효율이 좋은 건물 오브젝트는 1 × 1 정사각형 세 개가 ㄱ자 모양으로 변을 맞대고 있는 모양의 영역을 차지하며, 가장 효율이 좋은 꽃밭 오브젝트는 1 × 1 정사각형 모양의 영역을 차지한다. 카젤은 금화를 많이 벌고 싶어서 꽃밭 오브젝트는 한 개만 놓고 나머지 영역을 전부 건물 오브젝트로 채우기로 했다.

카젤은 분할정복 알고리즘을 공부한 적이 있기 때문에 꽃밭 오브젝트를 하나 배치했을 때 건물을 어떻게 배치해야 하는지도 잘 알고 있다.

1. 땅을 2^N-1 × 2^N-1 크기의 영역 4개로 분할한다. 이때 한 개의 영역은 꽃밭 오브젝트가 한 칸을 차지하고 있고, 나머지 세 영역은 비어 있을 것이다.
2. 건물 오브젝트를 비어 있는 세 개의 영역에 한 칸씩 걸치도록 가운데에 배치한다.
3. 각각의 영역에 오브젝트가 차지하고 있는 칸이 한 칸씩 있게 되므로 각 영역에 대해 같은 방법으로 건물을 배치하면 된다.

8 × 8 크기의 땅의 6번째 줄 2번째 칸에 꽃밭을 배치하는 경우

하지만 도시에 건물만 가득 차 있으면 너무 삭막해 보이므로, 게임에서는 꽃밭의 사용을 권장하기 위해 일일 퀘스트를 도입했다. 매일 아침 격자칸을 한 칸 지정해 주고, 해당 격자칸에 꽃밭을 배치하면 큰 보상을 주기로 한 것이다. 카젤은 일일 퀘스트를 깨고 싶었지만, 건물을 없앴다가 다시 짓는 것은 시간이 아주 오래 걸리기 때문에 어려움에 처했다.

그나마 다행인 점은 건물을 제자리에서 회전시키는 데에는 시간이 걸리지 않는다는 점이다. 유저는 건물 하나를 선택하고 해당 건물을 포함하는 2 × 2 정사각형 영역의 중심을 기준으로 시계 또는 반시계 방향으로 90도씩 회전시킬 수 있다. 물론 건물을 회전시켰을 때 다른 오브젝트가 차지하고 있는 영역과 겹치는 경우는 회전시킬 수 없다.

건물 회전의 예시

카젤은 일일 퀘스트가 주어지면 기존의 꽃밭을 삭제하고 건물들을 열심히 회전시켜서 지정된 위치를 빈 칸으로 만든 뒤, 그 위치에 새로 꽃밭을 배치해서 퀘스트를 완료하려고 한다. 비록 건물을 회전시키는 데에 시스템상으로 시간이 걸리지는 않지만, 건물을 클릭하고 회전 버튼을 누르는 것은 너무 귀찮은 작업이기에 카젤은 되도록 적은 횟수의 회전으로 퀘스트를 완료하고 싶어한다.

최초의 꽃밭의 위치와 이후 M일간 일일 퀘스트로 지정된 격자칸들이 주어질 때, 카젤이 모든 일일 퀘스트를 순서대로 완료할 수 있는지, 가능하다면 최소 몇 번의 회전이 필요한지 구해 보자.

첫 줄에 땅의 크기를 의미하는 정수 N과 일일 퀘스트가 주어지는 날의 수를 의미하는 정수 M(1 ≤ N ≤ 40, 1 ≤ M ≤ 100,000)이 주어진다. 땅의 크기는 2^N × 2^N임에 유의하라.

둘째 줄에 최초의 꽃밭의 위치를 의미하는 두 개의 정수 a, b(1 ≤ a, b ≤ 2^N)가 주어진다. 이는 땅에 그려진 격자의 a번째 줄 b번째 칸에 꽃밭 오브젝트가 있음을 의미한다.

세 번째 줄부터 M개의 줄에 걸쳐 각 줄에 각 날짜마다 일일 퀘스트로 주어진 칸의 위치를 의미하는 두 개의 정수가 둘째 줄과 같은 형식으로 주어진다.

카젤이 M일간의 일일 퀘스트를 모두 순서대로 완료할 수 있다면 첫 줄에 모든 퀘스트를 완료하기 위해 필요한 최소 회전 횟수를 출력한다. 만약 불가능하다면 첫 줄에 WA Machine을 출력한다.

첫 번째 예시는 건물이 하나뿐이며, 첫 날에는 시계 방향으로 한 번, 둘째 날에는 시계 또는 반시계 방향으로 두 번 회전시키면 된다.

두 번째 예시의 최초의 건물과 꽃밭의 배치는 다음과 같다.

1일차 일일 퀘스트는 아래와 같은 방법으로 완료할 수 있다.

2일차 일일 퀘스트는 아래와 같은 방법으로 완료할 수 있다.