Background

$\rm hdxrie\$ has recently been writing a pricing system for a newly built interstellar shopping mall.

Problem Description

The shopping mall gathers goods from many planets. However, different planets use different numeral bases, which makes price calculation difficult, so a pricing system is necessary.

Because the deadline given by the client is too tight, $\rm hdxrie\$ asks you to be his assistant. He only needs you to help write a base conversion program; all other system modules will be handled by himself. Can you finish the conversion program within the time limit?

Input Format

The first line contains an integer $n$, where $n$ is the number of item prices that need to be converted.

The next $n$ lines each contain three integers $a, l, r$ and a price string $S$.

$a$ means the price string is a base-$a$ number (it is guaranteed that $a$ is not $-1, 0, 1$). You need to convert it into all bases from $l$ to $r$ (please automatically skip the cases where the base is $-1, 0, 1$).

Since prices are real numbers, there may be fractional parts. If a fractional part is repeating, we will enclose the repeating cycle in <,>.

If it is not a repeating decimal, there will be no angle brackets. If there is no fractional part, there will be no decimal point. It is guaranteed that there will not be a case where there are no digits between the angle brackets.

It is guaranteed that both the repeating cycle and the non-repeating part before it are the shortest possible. For example, in base $10$, $0.123123\cdots$ will be given as $0.$<$123$>. Inputs like $0.1$<$231$> or $0.$<$123123$> will not appear.

For positive base $a$, it is guaranteed that the repeating cycle will not be $a-1$. For example, in base $10$, an input like $0.$<$9$> will not appear. But for negative bases, there is no such restriction.

To make conversion easier, when using a positive base to represent a negative number, a minus sign is added before the price. But since a negative base can represent both positive and negative numbers, a minus sign is not allowed for negative bases.

It is required that every digit in any base is non-negative. Values greater than $9$ are written using uppercase letters in increasing order.

Output Format

For each price that needs to be converted, output the price string converted to each base in the given range, in increasing order of the base (please automatically skip the cases where the base is $-1, 0, 1$).

You must also strictly follow the requirements described above for the input format when outputting each price string.

2
10 2 4 72451
-3 -4 2 123456

10001101100000011
10200101101
101230003
2021
122000
10001001
-10000111

2
8 2 2 176336030760401.6
30 35 36 HQA9MBFD3SEC.<GAR85DJ2LO>

1111110011011110000011000111110000100000001.11
39SAWRJ5CPP7.<J36CPFVSM9>
2EMEUXKKZHA0.<JMWQ6>

1
-26 -6 -6 1PMMK.<L15>

1213400.<511>

Hint

• For $5\%$ of the testdata, there is no fractional part, and $1≤n≤20,2≤a≤36,2≤l≤r≤36$.

• For $15\%$ of the testdata, there is no fractional part, and $1≤n≤100,2≤|a|≤36,-36≤l≤r≤36$.

• For another $15\%$ of the testdata, both before and after conversion are terminating decimals, and $1≤n≤550,2≤a≤36,2≤l≤r≤36$.

• For another $20\%$ of the testdata, $1≤n≤550,2≤a≤36,2≤l≤r≤36$.

• For $100\%$ of the testdata, $1≤n≤550,2≤|a|≤36,-36≤l≤r≤36$.

It is guaranteed that in all testdata, the absolute value of the price will not exceed $2^{63}-1$, and the length of the fractional-part string (before and after conversion) will not exceed $\left\lfloor\log_{|a|}2^{62}\right\rfloor$ ($a$ is the base; the parentheses are not counted in the length).

Translated by ChatGPT 5