CF2179G Blackslex and Penguin Migration

[IOI 2025 - Migrations](https://oj.uz/problem/view/IOI25_migrations) This is an interactive problem. The species of penguins that Blackslex is researching lives on an island that is a grid with $ n $ rows and $ n $ columns. Exactly one penguin lives in each one cell of the grid. He labelled each penguin as an integer from $ 1 $ to $ n^2 $ . After some time, some penguins migrated to another cell. After migration, every penguin will still be in some cell on the grid, and every cell contains exactly one penguin. He needs the current position of every penguin. To do so, he can ask a penguin how far another penguin is from it. Formally, for a possible grid $ x $ representing the position of all penguins, denote $ \operatorname{dist}(x, i, j) $ as the Manhattan distance of the penguin $ i $ to the penguin $ j $ in $ x $ $ ^{\text{∗}} $ . There is a hidden grid $ a $ with $ n $ rows and $ n $ columns. You need to find a grid $ b $ that satisfies - $ b $ has $ n $ rows and $ n $ columns. - Each cell of $ b $ contains an integer from $ 1 $ to $ n^2 $ , which is a penguin's label. Each integer will be in a single cell. - For all $ 1 \leq i, j \leq n^2 $ , it holds that $ \operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j) $ . To do so, you may make the following query no more than $ 3n^2 + 150 $ times. - Given $ i $ , $ j $ ( $ 1 \leq i, j \leq n^2 $ ), receive the value of $ \operatorname{dist}(a, i, j) $ . $ ^{\text{∗}} $ Let $ r_i $ , $ c_i $ denote the row and column that the penguin $ i $ is in, and denote the same for $ r_j $ , $ c_j $ , then the Manhattan distance is $ |r_i - r_j| + |c_i - c_j| $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 200 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \leq n \leq 100 $ ) — the size of the island. It is guaranteed that the total sum of all values of $ n $ across all test cases does not exceed $ 500 $ .

N/A

Note that additional lines are for ease of reading. Your solution should not output these additional lines. In the first test case, the grid $ a $ is 1423In the second test case, the grid $ a $ is 913427856The interaction is as follows. ContestantJudgeDescription2Start of the first test case. The island has size $ n=2 $ .? 1 2The contestant asks for the distance of penguin labelled $ 1 $ and $ 2 $ .1The distance of penguin labelled $ 1 $ and $ 2 $ is $ 1 $ .? 1 3The contestant asks for the distance of penguin labelled $ 1 $ and $ 3 $ .2The distance of penguin labelled $ 1 $ and $ 3 $ is $ 2 $ .? 1 4The contestant asks for the distance of penguin labelled $ 1 $ and $ 4 $ .1The distance of penguin labelled $ 1 $ and $ 4 $ is $ 1 $ .? 2 3The contestant asks for the distance of penguin labelled $ 2 $ and $ 3 $ .1The distance of penguin labelled $ 2 $ and $ 3 $ is $ 1 $ .? 2 4The contestant asks for the distance of penguin labelled $ 2 $ and $ 4 $ .2The distance of penguin labelled $ 2 $ and $ 4 $ is $ 2 $ .? 3 4The contestant asks for the distance of penguin labelled $ 3 $ and $ 4 $ .1The distance of penguin labelled $ 3 $ and $ 4 $ is $ 1 $ .!The contestant determined a possible grid $ b $ .3 4Note that the grid need not be exactly the same, but it must hold that $ \operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j) $ for all $ 1 \leq i, j \leq n^2 $ .2 13Start of the second test case. The island has size $ n=3 $ .? 1 8The contestant asks for the distance of penguin labelled $ 1 $ and $ 8 $ .3The distance of penguin labelled $ 1 $ and $ 8 $ is $ 3 $ .!The contestant determined a possible grid $ b $ .9 1 34 2 78 5 6