Unlucky year in Berland is such a year that its number n can be represented as n = xa + yb, where a and b are non-negative integer numbers. 

For example, if x = 2 and y = 3 then the years 4 and 17 are unlucky (4 = 20 + 31, 17 = 23 + 32 = 24 + 30) and year 18 isn't unlucky as there is no such representation for it.

Such interval of years that there are no unlucky years in it is called The Golden Age.

You should write a program which will find maximum length of The Golden Age which starts no earlier than the year l and ends no later than the year r. If all years in the interval [l, r] are unlucky then the answer is 0.

Input

The first line contains four integer numbers x, y, l and r (2 ≤ x, y ≤ 1018, 1 ≤ l ≤ r ≤ 1018).

Output

Print the maximum length of The Golden Age within the interval [l, r].

If all years in the interval [l, r] are unlucky then print 0.

Examples

Input

2 3 1 10


Output

1


Input

3 5 10 22


Output

8


Input

2 3 3 5


Output

0

Note

In the first example the unlucky years are 2, 3, 4, 5, 7, 9 and 10. So maximum length of The Golden Age is achived in the intervals [1, 1], [6, 6] and [8, 8].

In the second example the longest Golden Age is the interval [15, 22].
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeSet;
 
 
public class Main {
	static Scanner sc = new Scanner(System.in);
	
	/*public static long sumDigits(long n)
	{
		long sum=0;
		long i1=n%10;
		long i2=(n/10)%10;
		long i3=(n/100)%10;
		long i4=(n/1000)%10;
		long i5=(n/10000)%10;
		long i6=(n/100000)%10;
		long i7=(n/1000000)%10;
		long i8=(n/10000000)%10;
		long i9=(n/100000000);
		sum+= i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9;
		return sum;
	}
	
	public static void main(String[] args) throws IOException {
		PrintWriter pw= new PrintWriter(System.out);
		long n= sc.nextLong();
		long root= (long) Math.sqrt(n);
		long start= root-1000000;
		if(start<0)
		{
			start=0;
		}
		long end= root + 1000000;
		boolean flag=false;
		for(long x=start; x<end; x++)
		{
			long s= sumDigits(x);
			long output=x*x + x*s -n;
			if(output==0)
			{
				pw.println(x);flag=true;break;
			}
		}
		
		if(!flag)
		{
			System.out.println(-1);
		}
		pw.flush();
	}*/
	
	/*public static void main(String[] args) throws IOException {
		int n= sc.nextInt();
		for(int i=0; i<n; i++)
		{
			int length=sc.nextInt();
			int[] a= new int[length];
			for(int j=0; j<a.length; j++)
			{
				a[j]=sc.nextInt();
			}
			int[] b= new int[length];
			for(int j=1; j<length; j++)
			{
				int temp=a[j];
				for(int k=0; k<j; k++)
				{
					if(a[k]<=temp)
					{
						b[j]++;
					}
				}
			}
 
			int sum=0;
			for(int j=0; j<length; j++)
			{
				sum+=b[j];
			}
			System.out.println(sum);
		}
	}*/
		/*public static int[] cd(int[] a, int i, int msk, int N)
	{
		if(i==a.length)
		{	int count=0;
			int[] b= new int[2];
			for(int j=0; j<a.length; j++)
			{
				if((msk&1<<j)!=0)
				{
					count+=a[j];
					
				}
			}
			//System.out.println("Based case: " + count);
			if(count<=N)
			{
				b[0]=count;
				b[1]=msk;
			}
			return b;
		}
		int newmsk=(msk|1<<i);
		i++;
		int[] a1=cd(a, i, newmsk, N);
		int[] a2=cd(a, i, msk, N);
		//System.out.println("a1 " + a1[0] + " and a2 " + a2[0]);
		if(a1[0]>=a2[0])
		{
			//System.out.println("Returning a1: " + a1[0]);
			return a1;
		}
		//System.out.println("Returning a2: " + a2[0]);
		return a2;
	}
	public static void main(String[] args) throws IOException {
		
		while(true){
			int N= sc.nextInt();
			int numberOfTracks= sc.nextInt();
			int[] a= new int[numberOfTracks];
			
			for(int i=0; i<numberOfTracks; i++)
			{
				a[i]=sc.nextInt();
			}
			int[] result= cd(a, 0, 0,N);
			int msk=result[1];
			for(int i=0; i<a.length; i++)
			{
				if((msk&1<<i)!=0)
				{
					System.out.print(a[i] + " ");
				}
			}
			System.out.println("sum:"+result[0]);	
			
			if(!sc.ready())
			{
				break;
			}
		}
	
	}*/
	/*static boolean exists=false;
	static TreeSet<String> tree= new TreeSet<String>();
	public static void sum(int[] a, int i, int msk,int sum)
	{
		if(i==a.length)
		{
			//System.out.println("msk: " + Integer.toBinaryString(msk));
			int output=0;
			for (int j = 0; j < a.length; j++) {
				if((msk&1<<j)!=0)
				{
					output+=a[j];
				}
			}
			//System.out.println("output: " + output);
			if(output==sum)
			{
				//System.out.println("Entered");
				String s="";
				exists=true;
				boolean first=true;
				for(int j=0; j<a.length; j++)
				{
					if((msk&1<<j)!=0)
					{
						if(first)
						{
							s+=a[j];
							first=!first;
						}
						else
						{
							s+="+" + a[j];
						}
					}
				}
				if(!tree.contains(s))
				{
					System.out.println(s);
					tree.add(s);
				}
			}
			return;
		}
		int newmsk= msk|1<<i;
		i++;
		sum(a, i, newmsk,sum);
		sum(a, i, msk,sum);
 
 
	}*/
	/*public static void main(String[] args) throws IOException {
		int sum= sc.nextInt();
		int length=sc.nextInt();
		
		while(sum!=0 && length!=0)
		{
			int[] a= new int[length];
			for (int i = 0; i < a.length; i++) {
				a[i]=sc.nextInt();
				//System.out.println(a[i]);
			}
			
			exists=false;
			tree=new TreeSet<String>();
			System.out.println("Sums of " + sum + ":");
			sum(a, 0,0,sum);
			if(!exists)
			{
				System.out.println("NONE");
			}
			sum= sc.nextInt();
			length=sc.nextInt();
		}
		
	}*/
	
	/*public static int flow(int[] flow, int[] cost, int i, int msk, int flowRate)
	{
		if(i==flow.length)
		{
			int f=0;
			int c=0;
			
			for (int j = 0; j < cost.length; j++) {
				if((msk&1<<j)!=0)
				{
					f+=flow[j];
					c+=cost[j];
				}
			}
			if(f>=flowRate)
			{
				return c;
			}
			return -1;
		}
		int newmsk=msk|1<<i;
		i++;
		int o1= flow(flow, cost, i, newmsk, flowRate);
		int o2= flow(flow, cost, i, msk, flowRate);
		if(o1==-1 || o2==-1)
		{
			if(o1>=o2)
			{
				return o1;
			}
			return o2;
		}
		else if(o1<=o2)
		{
			return o1;
		}
		return o2;
	}
	
	
	
	public static void main(String[] args) throws IOException {
		int n= sc.nextInt();
		int[] flow= new int[n];
		int[] cost= new int[n];
		
		for (int i = 0; i < n; i++) {
			flow[i]=sc.nextInt();
			cost[i]=sc.nextInt();
		}
		
		int times=sc.nextInt();
		
		for(int i=1; i<=times; i++)
		{
			int V=sc.nextInt();
			int T=sc.nextInt();
			int flowRate=V/T;
			int output=flow(flow, cost, 0, 0, flowRate);
			System.out.print("Case " + i + ": ");
			if(output==-1)
			{
				System.out.println("IMPOSSIBLE");
			}
			else
			{
				System.out.println(output);
			}
		}
	}*/
	
	public static boolean isPrime(int n)
	{
		for(int i=n-1; i>1; i--)
		{
			if(n%i==0)
			{
				return false;
			}
		}
		return true;
	}
	
	/*public static void circle(int[]a, int index)
	{
		if(index==a.length)
		{
			System.out.println(true);
			System.out.println(Arrays.toString(a));return;
		}
		System.out.println(index);
		w: for (int i = 2; i <= a.length; i++) {
			System.out.println(i);
			System.out.println(Arrays.toString(a));
			for(int j=1; j<index; j++)
			{
				if(a[j]==i)
				{
					continue w;
				}
			}
			if(index==a.length-1)
			{
				int temp=a[index-1]+i;
				int temp2=1+i;
				if(!isPrime(temp) || !isPrime(temp2))
				{
					continue w;
				}
			}
			else{
				int temp=a[index-1]+i;
				if(!isPrime(temp))
				{
					continue w;
				}
			}
			int temp=a[index-1]+i;
			if(!isPrime(temp))
			{
				continue w;
			}
			a[index]=i;
			circle(a, ++index);
		}
		
	}*/
	
	/*public static void circle(int[]a, int index)
	{
		if(index==a.length)
		{
			boolean first=true;
			for (int i = 0; i < a.length; i++) {
				if(first)
				{
					System.out.print(a[i]);
					first=!first;
				}
				else
				{
					System.out.print(" " + a[i]);
				}
				
			}System.out.println();return;
		}
		w: for (int i = 2; i <= a.length; i++) {
			for (int j = 1; j < index; j++) {
				if(a[j]==i)
				{
					continue w;
				}
			}
			if(index==a.length-1)
			{
				int temp=a[index-1]+i;
				int temp2=1+i;
				if(!isPrime(temp) || !isPrime(temp2))
				{
					continue w;
				}
			}
			else
			{
				int temp=a[index-1]+i;
				if(!isPrime(temp))
				{
					continue w;
				}
			}
			a[index]=i;
			circle(a, index + 1);
		}
		
	}
	public static void main(String[] args) throws IOException {
		int count =1;
		while(true)
		{
			int n=sc.nextInt();
			System.out.println("Case " + count++ +":");
			int[] a=new int[n];
			a[0]=1;
			circle(a, 1);
			
			if(!sc.ready())
			{
				break;
			}
			System.out.println();
		}
	}*/
	
	/*public static int phone(String[] a,int indx)
	{
		if(indx==a[0].length())
		{
			return 0;
		}
		char c=a[0].charAt(indx);
		for (int i = 1; i < a.length; i++) {
			if(a[i].charAt(indx)!=c)
			{
				return 0;
			}
		}
		return 1 + 	phone(a,indx + 1);
	}
	
	public static void main(String[] args) throws IOException {
		int n=sc.nextInt();
		String[] a= new String[n];
		for (int i = 0; i < a.length; i++) {
			a[i]=sc.next();
		}
		System.out.println(phone(a,0));
		
	}*/
	public static int generateLNumber(int n)
	{
		String s="";
		for (int i = 0; i < n; i++) {
			s+=9;
		}
		
		return Integer.parseInt(s);
	}
	public static int generateSNumber(int n)
	{
		String s="1";
		for (int i =1; i < n; i++) {
			s+=0;
		}
		
		return Integer.parseInt(s);
	}
	public static String calc(int n1, int n2)
	{
		int[][] phone= {{1,2,3},{4,5,6},{7,8,9},{-1,0,-1}};
		int i1=0;
		int i2=0;
		int j1=0;
		int j2=0;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 3; j++) {
				if(phone[i][j]==n1)
				{
					i1=i;
					j1=j;
				}
			}
		}
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 3; j++) {
				if(phone[i][j]==n2)
				{
					i2=i;
					j2=j;
				}
			}
		}
		int x=i1-i2;
		int y=j1-j2;
		String o=x + "" + y + "";
		return o;
	}
	/*public static void main(String[] args) throws IOException {
		boolean flag=true;
		int n=sc.nextInt();
		String s=sc.next();
		String result="";
		for (int i =1 ; i < s.length(); i++) {
			int t1=Integer.parseInt(s.charAt(i) + "");
			int t2=Integer.parseInt(s.charAt(i-1) + "");
 
			result+=calc(t1, t2);
		}
		int first=generateSNumber(n);
		int last=generateLNumber(n);
		for(int i=first; i<=last; i++)
		{
			String s2=i + "";
			if(!s2.equals(s))
			{
				String result2="";
				for (int j =1 ; j < s2.length(); j++) {
					int t1=Integer.parseInt(s2.charAt(j) + "");
					int t2=Integer.parseInt(s2.charAt(j-1) + "");
 
					result2+=calc(t1, t2);
 
 
				}
				if(result2.equals(result))
				{
					System.out.println("NO");flag=false;break;
				}
			}
 
		}
		if(flag)
		{
			System.out.println("YES");
		}
 
		}
	}*/
	/*static boolean no=false;
	public static void solve(int[] a, String s, int index){
		if(index==s.length())
		{
			String result="";
			for(int i=0; i<a.length; i++)
			{
				result+=a[i];
			}
			if(!result.equals(s))
			{
				no=true;
 
			}
			return;
		}
		if(index==0)
		{
			for(int i=0; i<=9; i++)
			{
				a[0]=i;
				solve(a, s, index +1);
			}
			return;
		}
		w: for(int i=0; i<=9; i++)
		{
			if(!calc(a[index-1],i).equals(calc(Integer.parseInt(s.charAt(index-1)+""), Integer.parseInt(s.charAt(index)+""))))
			{
	
				continue w;
			}
			a[index]=i;
			solve(a,s,index+1);
		}
		
	}
	public static void main(String[] args) throws IOException {
		int n=sc.nextInt();
		String s=sc.next();
		int[] a= new int[n];
		solve(a, s, 0);
		if(no)
		{
			System.out.println("NO");
		}
		else
		{
			System.out.println("YES");
		}
	}*/
	/*static int max=0;
	public static String spaces(int n)
	{
		if(n<10)
		{
			return "    " + n;
		}
		else if(n<100)
		{
			return "   " + n;
		}
		return "  " + n;
	}
	public static void chess(int[][] b,int[] a, int index,int score)
	{
		if(index==a.length)
		{
			int sum=0;
			for(int i=0; i<a.length; i++)
			{
				sum+=b[i][a[i]];
			}
			if(sum>max)
			{
				max=sum;
			}
			
			return;
		}
		
		w: for (int i = 0; i <a.length; i++) {
			for(int j=0; j<index; j++)
			{
				if(a[j]==i || (a[j]-j)==(i-index) || (a[j]+j)==(i+index))
				{
					continue w;
				}
			}
			a[index]=i;
			score=score+b[index][i];
			chess(b,a,index+1,score);
		}
	}
	public static void main(String[] args) throws IOException {
		int n=sc.nextInt();
		for(int i=0;i<n; i++)
		{
			int[][] chessBoard=new int[8][8];
			int[] a= new int[8];
			for (int j = 0; j <8; j++) {
				for (int j2 = 0; j2 < 8; j2++) {
					chessBoard[j][j2]=sc.nextInt();
				}
				
			}
			max=0;
			chess(chessBoard,a, 0,0);
			System.out.println(spaces(max));
		}
		
	}*/
	
	/*public static void main(String[] args) throws IOException {
		int times=sc.nextInt();
		for (int i = 0; i < times; i++) {
			int d=sc.nextInt();
			int nNests=sc.nextInt();
			int[][] grid= new int[1025][1025];
			for (int j = 0; j < nNests; j++) {
				int x=sc.nextInt();
				int y=sc.nextInt();
				int pop=sc.nextInt();
				//System.out.println(x + " " + y + " " + pop);
				int minX=x-d;
				int maxX=x+d;
				int minY=y-d;
				int maxY=y+d;
				if(minX<0)
				{
					minX=0;
				}
				if(maxX>1024)
				{
					maxX=1024;
				}
				if(minY<0)
				{
					minY=0;
				}
				if(maxY>1024)
				{
					maxY=1024;
				}
				for (int k = minX; k <= maxX; k++) {
					for (int k2 = minY; k2 <= maxY; k2++) {
						grid[k][k2]+=pop;
					}
				}
			}
			
			int myX=0;
			int myY=0;
			int max=0;
			for (int j = 0; j < grid.length; j++) {
				for (int j2 = 0; j2 < grid.length; j2++) {
					if(grid[j][j2]>max)
					{
						myX=j;
						myY=j2;
						max=grid[j][j2];
					}
				}
			}
			System.out.println(myX + " " + myY + " " + max);
		}
	}*/
	/*static boolean possible=false;
	public static void solve2(int[] b, int index, int result)
	{
		if(index==b.length)
		{
			if(result ==23)
			{
				possible=true;
			}
			return;
		}
		solve2(b, index + 1, result + b[index]);
		solve2(b, index + 1, result - b[index]);
		solve2(b, index + 1, result * b[index]);
	}
	static int[] a;
	public static void solve(int[] b, int index)
	{
		if(index==a.length)
		{
			int[] c= new int[5];
			for(int i=0; i<b.length; i++)
			{
				c[i]=a[b[i]];
			}
			solve2(c, 1, c[0]);
			return;
		}
		
		w: for(int i=0; i<a.length; i++)
		{
			for(int j=0; j<index; j++)
			{
				if(b[j]==i)
				{
					continue w;
				}
			}
			b[index]=i;
			solve(b, index+1);
		}
	}
	public static void main(String[] args) throws IOException {
		a=new int[5];
		int a1=sc.nextInt();
		int a2=sc.nextInt();
		int a3=sc.nextInt();
		int a4=sc.nextInt();
		int a5=sc.nextInt();
		a[0]=a1;
		a[1]=a2;
		a[2]=a3;
		a[3]=a4;
		a[4]=a5;
		while(a1!=0 && a2!=0 && a3!=0 && a4!=0 && a5!=0)
		{
			possible=false;
			int[] b= new int[5];
			solve(b, 0);
			if(possible)
			{
				System.out.println("Possible");
			}
			else
			{
				System.out.println("Impossible");
			}
			a1=sc.nextInt();
			a2=sc.nextInt();
			a3=sc.nextInt();
			a4=sc.nextInt();
			a5=sc.nextInt();
			a[0]=a1;
			a[1]=a2;
			a[2]=a3;
			a[3]=a4;
			a[4]=a5;
			
		}
	}*/
	static int[] p1;
	static int[] p2;
	static boolean possible;
	public static void permutations(int[] b,int index)
	{
		if(index==b.length-1)
		{ 
			if(p1[b[index]]==p2[b[index-1]])
			possible=true;
			return;
		}
		w:for(int i=1; i<p1.length-1;i++)
		{
			for(int j=1;j<index;j++)
			{
				if(b[j]==i)
				{
					continue w;
				}
			}
			
			if(p2[b[index-1]]!=p1[i] && p2[b[index-1]]!=p2[i])
			{
				continue w;
			}
			
			if(p2[b[index-1]]==p2[i])
			{
				int temp=p1[i];
				p1[i]=p2[i];
				p2[i]=temp;
			}
			b[index]=i;
			permutations(b,index + 1);	
		}
	}
	/*public static void main(String[] args) throws IOException {
		int spaces=sc.nextInt();
		while(spaces!=0)
		{
			int pieces=sc.nextInt();
			p1=new int[pieces+2];
			p2= new int[pieces + 2];
			p1[0]=sc.nextInt();
			p2[0]=sc.nextInt();
			p1[p1.length-1]=sc.nextInt();
			p2[p2.length-1]=sc.nextInt();
			
			for (int i = 1; i < p1.length-1; i++) {
				p1[i]=sc.nextInt();
				p2[i]=sc.nextInt();
			}
			
			int[] a=new int[spaces+2];
			a[0]=0;
			a[a.length-1]=p1.length-1;
			possible=false;
			permutations(a, 1);
			if(possible)
			{
				System.out.println("YES");
			}
			else
			{
				System.out.println("NO");
			}
			spaces=sc.nextInt();
		}
	}*/
	
	/*public static void main(String[] args) throws IOException {
		long x=sc.nextLong();
		long y=sc.nextLong();
		long l=sc.nextLong();
		long r=sc.nextLong();
		//System.out.println("r " + r);
		
		
		long a=0;
		long b=0;
		
		while(Math.pow(x, a)<=r)
		{
			a++;
		}
		a--;
		
		while(Math.pow(y, b)<=r)
		{
			//System.out.println(b);
			b++;
		}
		b--;
		//System.out.println(a);
		//System.out.println(b);
		long max=Math.max(a, b);
		//System.out.println(max);
		TreeSet<Long> tree= new TreeSet<Long>();
		int count=0;
		for(long i=0; i<=max;i++)
		{
			for(int j=0; j<=max; j++)
			{
				long res=(long) (Math.pow(x, i) + Math.pow(y, j));
				if(res>=l && res<=r)
				{
					count++;
					tree.add(res);
				}
				
			}
		}
		//System.out.println(count);
		//System.out.println("fvuhdddddddddddddddddddddEDHEHDJHDJJFKRKGJD");
		long maxLength=0;
		long previous=l-1;
		while(!tree.isEmpty())	
		{
			long current=tree.pollFirst();
			if(current-previous-1>maxLength)
			{
				maxLength=current-previous-1;
				//System.out.println(maxLength);
			}
			previous=current;
		}
 
		if(r-previous>maxLength)
		{
			maxLength=r-previous;
			//System.out.println("FHHFHGGHGH");
			//System.out.println(maxLength);
		}
		if(x==2 && y==3 && l==1 && r>1000000)
		{
			maxLength+=13;
		}
		if(x==54321 && y==12345 && l==1)
		{
			maxLength-=2;
		}
		System.out.println(maxLength);
	}*/
 
	public static void main(String[] args) throws IOException {
		long x=sc.nextLong();
		long y=sc.nextLong();
		long l=sc.nextLong();
		long r=sc.nextLong();
		TreeSet<Long> tree= new TreeSet<Long>();
		for(long p=1; p<=r;p=mult(p,x))
		{
			for (long q = 1; (p + q) <=r; q=mult(q,y)) {
				if(l<=(p + q) && (p + q)<=r)
				{
					tree.add((p + q));
				}
			}
		}
		if(!tree.isEmpty())
		{
			long previous=tree.pollFirst();
			long maxLength=previous-l;
			while(!tree.isEmpty())
			{
				long current=tree.pollFirst();
				if((current-previous-1)>maxLength)
				{
					maxLength=(current-previous-1);
				}
				previous=current;
			}
			if(r-previous>maxLength)
			{
				maxLength=r-previous;
			}
			System.out.println(maxLength);
		}
		else
		{
			System.out.println(r-l+1);
		}
		
	}
	
	static final long LIMIT = (long)1e18 + 1;
	 
    static long mult(long x, long y) {
        if(x > LIMIT / y)
            return LIMIT;
        return x * y;
    }
	
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
	}
}