Mister B and Boring Game

题意翻译

Mister B 和电脑在玩游戏。两个人轮流向字符串 $s$ 的末尾添加字符，Mister B 先开始。 开始时，字符串 $s$ 包含按顺序的前 $a$ 个字母，例如 $a=5$ 时 $s=\texttt{abcde}$。 Mister B 每次向字符串 $s$ 的末尾添加任意的 $b$ 个字符。电脑每次取出 $s$ 的长度为 $a$ 的后缀，并将前 $a$ 个没有在后缀中出现的字母按顺序组成字符串 $t$，再把 $t$ 加入 $s$ 的末尾。例如，$a=4$，后缀为 $\texttt{bfdd}$，则 $t=\texttt{aceg}$。 求 $s$ 的第 $l$ 到第 $r$ 个字符中，最少有多少个不同的字符。（含第 $l$ 个和第 $r$ 个字符，字符从 $1$ 开始标号）

题目描述

Sometimes Mister B has free evenings when he doesn't know what to do. Fortunately, Mister B found a new game, where the player can play against aliens. All characters in this game are lowercase English letters. There are two players: Mister B and his competitor. Initially the players have a string $ s $ consisting of the first $ a $ English letters in alphabetical order (for example, if $ a=5 $ , then $ s $ equals to "abcde"). The players take turns appending letters to string $ s $ . Mister B moves first. Mister B must append exactly $ b $ letters on each his move. He can arbitrary choose these letters. His opponent adds exactly $ a $ letters on each move. Mister B quickly understood that his opponent was just a computer that used a simple algorithm. The computer on each turn considers the suffix of string $ s $ of length $ a $ and generates a string $ t $ of length $ a $ such that all letters in the string $ t $ are distinct and don't appear in the considered suffix. From multiple variants of $ t $ lexicographically minimal is chosen (if $ a=4 $ and the suffix is "bfdd", the computer chooses string $ t $ equal to "aceg"). After that the chosen string $ t $ is appended to the end of $ s $ . Mister B soon found the game boring and came up with the following question: what can be the minimum possible number of different letters in string $ s $ on the segment between positions $ l $ and $ r $ , inclusive. Letters of string $ s $ are numerated starting from $ 1 $ .

输入输出格式

输入格式

First and only line contains four space-separated integers: $ a $ , $ b $ , $ l $ and $ r $ ( $ 1<=a,b<=12 $ , $ 1<=l<=r<=10^{9} $ ) — the numbers of letters each player appends and the bounds of the segment.

输出格式

Print one integer — the minimum possible number of different letters in the segment from position $ l $ to position $ r $ , inclusive, in string $ s $ .

输入输出样例

输入样例 #1

1 1 1 8

输出样例 #1

2

输入样例 #2

4 2 2 6

输出样例 #2

3

输入样例 #3

3 7 4 6

输出样例 #3

1

说明

In the first sample test one of optimal strategies generate string $ s= $ "abababab...", that's why answer is $ 2 $ . In the second sample test string $ s= $ "abcdbcaefg..." can be obtained, chosen segment will look like "bcdbc", that's why answer is $ 3 $ . In the third sample test string $ s= $ "abczzzacad..." can be obtained, chosen, segment will look like "zzz", that's why answer is $ 1 $ .