A145355.星环巡检

$Sherry$ 为科技节设计了一个星环展区。展区中有 $n$ 个展台围成一圈，按照顺时针方向编号为 $1\sim n$。

巡检机器人一开始站在第 $p$ 个展台。之后它会进行 $q$ 次巡检，每次巡检时：

1. 先记录当前所在展台；
2. 然后顺时针移动 $k$ 个展台。

请你计算，机器人一共记录过多少个不同的展台。

第一行输入四个整数 $n,k,p,q$，分别表示展台数量、每次移动的步数、初始位置和巡检次数。

输出一个整数，表示机器人记录过的不同展台数量。

样例解释1

机器人记录的展台编号依次为：

3 7 11 3 7 11 ...

所以只会记录到 $3$ 个不同的展台。

数据范围

$1\le n,k\le 10^9$

$1\le p\le n$

$1\le q\le 10^{18}$