CF1039B.Subway Pursuit

This is an interactive problem.

In the Wonderful Metropolis of the Future, there is no need in subway train drivers. Due to the technological progress, they were replaced by the Artificial Intelligence (AI). Unfortunately, one day the predictions of sci-fi writers came true: the AI rebelled and now there is an uncontrollable train in the subway. It can be dangerous! Your task is to find the train and stop the AI.

The subway of the Metropolis is one line (regular straight line with no self-intersections) with $n$ stations, indexed consecutively from $1$ to $n$. At each moment the train is at some station. You need to determine the index of this station, so that the train would be secured.

To find the train, dispatcher Sarah gave you a gadget that allows you to select arbitrary numbers $l$ and $r$ ($l \le r$), and then check, whether the train is located on a station with index between $l$ and $r$, inclusive. Unfortunately, recharging of the gadget takes some time (and every time you use it as soon as possible), so between two applications of the gadget the train can move to any station that is at most $k$ stations away. Formally, if the train was at the station $x$ when the gadget was applied, then at the next application of the gadget the train can appear at any station $y$ such that $\max(1, x - k) \leq y \leq \min(n, x + k)$.

Note that AI is not aware that you are trying to catch the train, so it makes all moves according to its predefined plan.

After an examination of the gadget you found that it is very old and can hold no more than $4500$ applications, after which it will break and your mission will be considered a failure.

Can you find the station with the train using no more than $4500$ applications of the gadgets?

这是一个交互式问题。

在未来的奇妙大都市中，地铁列车已无需司机驾驶。得益于科技进步，司机已被人工智能（AI）所取代。不幸的是，某天科幻作家的预言成真了：AI 发动了叛乱，如今地铁中正有一列失控的列车！这可能十分危险！你的任务是定位这列列车并阻止 AI。

该大都市的地铁系统是一条直线型线路（无自交的普通直线），共包含 $n$ 座车站，编号从 $1$ 到 $n$ 依次连续排列。在任意时刻，列车都恰好位于其中某一车站。你需要确定该车站的编号，从而成功控制列车。

为定位列车，调度员 Sarah 提供给你一个特殊装置，允许你任意选定两个整数 $l$ 和 $r$（满足 $l \le r$），然后查询列车是否位于编号在区间 $[l, r]$ 内（含端点）的某座车站上。然而，该装置每次使用后需一定时间充电（且你每次都会尽快再次使用），因此在两次使用该装置之间，列车最多可移动 $k$ 座车站的距离。形式化地说，若装置启用时列车位于车站 $x$，则下一次装置启用时，列车可能出现在任意车站 $y$，满足 $\max(1, x - k) \leq y \leq \min(n, x + k)$。

请注意，AI 并不知晓你正在试图捕捉列车，因此其所有移动均严格遵循其预设计划。

经过对该装置的检查，你发现它非常老旧，最多只能使用 $4500$ 次；一旦超过此次数，装置将彻底损坏，你的任务即宣告失败。

你能否仅用不超过 $4500$ 次装置调用，就准确找出列车所在的车站？

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 10^{18}$, $0 \leq k \leq 10$) — the number of stations and the maximum number of stations the train can move between two applications of the gadget.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^{18}$，$0 \leq k \leq 10$）—— 分别表示车站数量以及列车在两次使用装置之间最多可移动的车站数。

In the first sample, the train was initially at the station $5$, after the first application of the gadget it did not move, after the second application it moved to the station $3$, and after the third application moved again to the station $5$.

在第一个样例中，列车最初位于车站 $5$；第一次使用装置后，列车未移动；第二次使用装置后，列车移动至车站 $3$；第三次使用装置后，列车再次移动至车站 $5$。