CF1599H.Hidden Fortress

This is an interactive problem!

As part of your contribution in the Great Bubble War, you have been tasked with finding the newly built enemy fortress. The world you live in is a giant $10^9 \times 10^9$ grid, with squares having both coordinates between $1$ and $10^9$.

You know that the enemy base has the shape of a rectangle, with the sides parallel to the sides of the grid. The people of your world are extremely scared of being at the edge of the world, so you know that the base doesn't contain any of the squares on the edges of the grid (the $x$ or $y$ coordinate being $1$ or $10^9$).

To help you locate the base, you have been given a device that you can place in any square of the grid, and it will tell you the manhattan distance to the closest square of the base. The manhattan distance from square $(a, b)$ to square $(p, q)$ is calculated as $|a−p|+|b−q|$. If you try to place the device inside the enemy base, you will be captured by the enemy. Because of this, you need to make sure to never place the device inside the enemy base.

Unfortunately, the device is powered by a battery and you can't recharge it. This means that you can use the device at most $40$ times.

这是一个交互式问题！

作为“伟大气泡战争”的一员，你的任务是定位敌方新建的堡垒。你所生活的世界是一个巨大的 $10^9 \times 10^9$ 网格，其中每个格子的横纵坐标均在 $1$ 到 $10^9$ 之间（含端点）。

你已知敌方基地呈矩形，且其边与网格的边平行。由于你所在世界的人们极度恐惧身处世界边缘，因此你知道该基地不包含任何位于网格边缘的格子（即横坐标或纵坐标为 $1$ 或 $10^9$ 的格子）。

为协助你定位基地，你被配备了一台设备：可将其放置于网格中任意一个格子上，设备将返回该格子到基地中最近格子的曼哈顿距离。格子 $(a, b)$ 到格子 $(p, q)$ 的曼哈顿距离定义为 $|a−p|+|b−q|$。若你将设备放置于敌方基地内部，你将被敌方俘获。 因此，你必须确保绝不在敌方基地内部放置设备。

不幸的是，该设备由电池供电，且无法充电。这意味着你最多只能使用该设备 40 次。

The input contains the answers to your queries.

输入包含您查询的答案。