Signal Tower Strengths

On a line there are \(10^{999}+1\) equally spaced points, indexed from \(0\) to \(10^{999}\). A signal tower is built on each point. Tower \(0\) (at the leftmost point) is the TV broadcasting station and is configured with a huge signal strength of \(10^{30}\). The signal in this problem propagates only from left to right.

The propagation rule is as follows: a tower with signal strength \(x\) can transmit its signal up to a distance of \(\lfloor\frac{x-1}{k}\rfloor\) to its right. For any tower with index \(i\) (\(1 \le i \le 10^{999}\)), its signal strength is set by the following procedure:

1. Find the closest tower to its left, say tower \(j\) (with \(0 \le j < i\)), for which its signal can reach tower \(i\), i.e. the condition \[ i - j \le \left\lfloor\frac{f(j)-1}{k}\right\rfloor. \]
2. Set the signal strength of tower \(i\) as the distance between these two towers, i.e. \(f(i)=i-j\).

For example, when \(k=2\), the strengths for towers \(1\) through \(5\) are \(1,2,3,1,5\) respectively.

Your task is: given \(k\) and an index \(n\), determine the signal strength of tower \(n\). All formulas must be written in LaTeX format.

inputFormat

The input consists of a single line containing two integers \(k\) and \(n\) (with \(1 \le k \le 10^9\) and \(1 \le n \le 10^5\)). Tower indices start from \(0\) and tower \(0\) always has strength \(10^{30}\). You are to compute the strength of tower \(n\).

Note: The constraints on \(n\) have been chosen so that a simulation using an efficient stack algorithm will pass.

outputFormat

Output a single integer: the signal strength of tower \(n\).

sample

2 5

5