Index Into an Infinite String

You are given an alphabet (can be lower or uppercase) string s and two integers i and j where i < j. Let’s say p is an infinite string of s repeating forever. Return the substring of p from indexes [i, j).

Constraints

• 1 ≤ n ≤ 100,000 where n is the length of `s
• 0 ≤ i < j < 2 ** 31

https://binarysearch.com/problems/Index-Into-an-Infinite-String

Examples

Example 1

Input

• s = tiger
• i = 6
• j = 8

Output

• answer = ig

Example 2

Input

• s = hi
• i = 2
• j = 6

Output

• answer = hihi

Solution