405997: GYM102215 C Jumps on a Circle

There are p points on the circle numbered from 0 to (p - 1) in a way that from the point 0 you can move to the point 1, from the point 1 — to the point 2, and so on, and from the point (p - 1) you can move to the point 0.

A chip is initially placed at the point 0. It starts to jump around the circle, first moving 1 point forward, then 2 points forward, then 3 points forward and so on.

How many unique points (including the start one) will be visited by a chip after n moves?

The input has two integers p and n (1 ≤ p ≤ 10⁷, 0 ≤ n ≤ 10¹⁸) — the number of points on a circle and the number of moves.

Output a single integer — the number of unique points visited by a chip.

3 10

2

5 3

3

8 1000000000000000000

8