Each cell of a grid contains one apple. Rows are numbered from to from top to bottom, and columns from to from left to right.
You may eat all apples one at a time in any order. Initially, every apple has tastiness 100. Eating an apple earns its current tastiness as points. Afterwards, the tastiness of every uneaten apple at Manhattan distance at most 2 from the apple just eaten is multiplied by 0.9.
The Manhattan distance between and is . Tastiness values are never rounded or truncated during updates.
You want to maximize the total points earned. If your output lists every cell exactly once, the total points earned become your judge score directly. The nominal full score is , but there is no score cap: you can receive more than points. A score of at least receives AC. Judging uses the exact total rather than a rounded display value. An invalid order receives points.
All judge testcases have . The value is used only in the example, which shows an order with the maximum total. The -point AC threshold applies to the actual judge testcases.
The first line contains an integer .
Print lines describing the eating order. On line , print the row and column of the -th apple to eat, separated by a space.
This order scores , the optimum for the grid. Only is used in judge testcases.
Every cell must occur exactly once. Find an order with as large a total score as possible. Do not print the score itself.