#BT05. 互质通行证

互质通行证

互质通行证

编号从 LL 到 RR 的通行证中,只有编号与 NN 互质的通行证可以使用。

请找到可以使用的最大编号。若一个也没有,输出 -1。

两个正整数互质,当且仅当它们的最大公约数为 11。

输入格式

一行三个整数 N,L,RN,L,R。

输出格式

一行一个整数,表示答案。

数据范围

  • 1≤N≤10181\le N\le 10^{18}。
  • 1≤L≤R≤10181\le L\le R\le 10^{18}。
  • R−L≤200000R-L\le 200000。

样例 1

6 2 8
7

样例 2

6 8 10
-1