격자의 각 칸에 사과가 하나씩 있다. 행은 위에서 아래로, 열은 왼쪽에서 오른쪽으로 부터 까지 번호가 붙어 있다.
당신은 사과 개를 원하는 순서대로 하나씩 먹을 수 있다. 처음에는 모든 사과의 맛있음이 100이다. 사과를 먹으면 그 순간의 맛있음만큼 점수를 얻는다. 그 후, 아직 먹지 않은 사과 중 방금 먹은 사과와 맨해튼 거리가 2 이하인 모든 사과의 맛있음이 각각 0.9배가 된다.
두 칸 , 의 맨해튼 거리는 이다. 맛있음을 갱신할 때 반올림하거나 버리지 않는다.
사과를 먹었을 때 얻는 점수의 합이 최대가 되도록 순서를 정하고자 한다. 출력한 순서가 모든 칸을 정확히 한 번씩 포함하면, 사과를 먹으면서 얻은 점수의 합을 그대로 채점 점수로 받는다. 기준 만점은 점이지만 점수에 상한은 없으며, 이를 초과하는 점수도 그대로 받을 수 있다. 점수가 점 이상이면 AC로 판정한다. 채점에는 반올림한 값이 아닌 정확한 합계를 사용한다. 잘못된 순서를 출력하면 점이다.
실제 채점 데이터는 모두 이다. 은 예제에만 사용되며, 예제에서는 점수 합이 최대인 순서를 제시한다. 위의 AC 기준 점은 실제 채점 데이터에 적용된다.
첫째 줄에 정수 이 주어진다.
개의 줄에 걸쳐 사과를 먹을 순서를 출력한다. 번째 줄에는 번째로 먹을 사과의 행 번호 와 열 번호 를 공백으로 구분하여 출력한다.
이 예제 순서의 점수 합은 이며, 격자의 최댓값이다. 실제 채점 데이터는 만 사용한다.
각 칸은 정확히 한 번씩 나타나야 한다. 가능한 순서 중 점수의 합이 최대가 되는 순서를 찾아라. 점수 자체는 출력하지 않는다.