Minimum Stone Merging Cost

Uncle Fang participates in a mall game where a line of workers each has several piles of stones. For the worker at position \(i\), the number of stones in the \(j\)-th pile is equal to the \(j\)-th digit of \(i\) when expressed in base \(K\). Uncle Fang is given two integers \(L\) and \(R\) and must, for every worker at positions in the interval \([L, R]\), merge all the stone piles into one single pile.

In one operation, he may choose any two piles in front of the same worker and move some stones from one pile to the other. The cost of moving \(x\) stones a distance of \(d\) is \(x \times d\), where the distance \(d\) is the absolute difference between the indices of the two piles. Merging is performed by repeatedly moving stones between piles until only one pile remains for each worker.

The task is to compute the minimum total cost needed to merge the stones for all workers with positions from \(L\) to \(R\) (inclusive). For each worker, if his stone piles (given by the digits \(d_1, d_2, \dots, d_m\) of his position \(i\) in base \(K\)) are to be merged into a single pile located at index \(c\) (where \(1 \le c \le m\)), the cost incurred is:

[ Cost = \sum_{j=1}^{m} d_j \times |j - c|. ]

The optimal cost for that worker is the minimum value of the above sum when \(c\) varies from \(1\) to \(m\). The overall answer is the sum of the optimal costs for all workers in the range \([L, R]\).

Example: In base \(10\), consider the worker at position 12312. His stone piles are \([1, 2, 3, 1, 2]\). If he merges all stones into the third pile, the cost is computed as:

[ 1\times|1-3| + 2\times|2-3| + 3\times|3-3| + 1\times|4-3| + 2\times|5-3| = 1\times2 + 2\times1 + 3\times0 + 1\times1 + 2\times2 = 9. ]

Thus, the minimum cost for this worker is \(9\).

inputFormat

The input consists of a single line containing three space‐separated integers: \(K\), \(L\), and \(R\). Here, \(K\) is the numeral system base, and \(L\) and \(R\) (with \(L \le R\)) define the range of positions of the workers.

If only two integers are provided, assume \(K = 10\) by default.

outputFormat

Output a single integer representing the minimum total cost required to merge the stones into one pile for each worker in positions \([L, R]\).

sample

10 12312 12312

9