Description

Tenshi is very lucky to be chosen as the angel who holds the Key of Wisdom. Before officially taking office, she must take an oath like the other newly elected angels.

During the oath ceremony, each angel states her mission, and their speech scripts are placed in $n$ treasure boxes arranged in a circle. These boxes are numbered clockwise as $1, 2, \cdots, n - 1, n$.

At the beginning, the angels stand next to the box numbered $n$. Each of them holds a number that indicates the box containing her script is the $k$-th one clockwise starting from box $1$. For example: there are $7$ boxes, and if the number in Tenshi’s hand is $9$, then the box containing her script is $2$. Now the angels start to search for their scripts according to the numbers they hold; whoever finds it first will speak first.

Tenshi finds hers immediately and goes on stage first: “I will lead everyone to open the gate to NOI ...” After Tenshi finishes her oath, other angels go on stage one after another. However, one angel cannot find her script for a long time. It turns out that the number $m$ in her hand is very large, and after circling for a long time she still cannot find the box she wants.

Please help this angel find the index of the box she is looking for.

Input Format

The first line contains a positive integer $n$, and the second line contains a positive integer $m$.

Output Format

Output a single line: the index of the box the angel is looking for.

7
9

2

11
108

9

Hint

For 100% of the testdata, $2 \le n \le 10^8$, $2 \le m \le 10^{1000}$.

Translated by ChatGPT 5