cho.sh

Московские числа

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

Скорее всего, вы знакомы с римскими числами. А также наверняка слышали фразу, что Москва --- это третий Рим. Поэтому мы решили по аналогии с римскими числами придумать их продвинутую версию --- московские числа.

Цифрами московского числа являются заглавные английские буквы от A до Z. Числом является строка из нескольких цифр. Каждой цифре сопоставим значение:

A11H5⋅1035 \cdot 10 ^ {3}O10710 ^ {7}V5⋅10105 \cdot 10 ^ {10}
B55I10410 ^ {4}P5⋅1075 \cdot 10 ^ {7}W101110 ^ {11}
C1010J5⋅1045 \cdot 10 ^ {4}Q10810 ^ {8}X5⋅10115 \cdot 10 ^ {11}
D5050K10510 ^ {5}R5⋅1085 \cdot 10 ^ {8}Y101210 ^ {12}
E100100L5⋅1055 \cdot 10 ^ {5}S10910 ^ {9}Z5⋅10125 \cdot 10 ^ {12}
F500500M10610 ^ {6}T5⋅1095 \cdot 10 ^ {9}  
G10310 ^ {3}N5⋅1065 \cdot 10 ^ {6}U101010 ^ {10}  

Значение числа равно сумме вкладов цифр, из которых оно состоит. Вклад цифры бывает как положительным, так и отрицательным. Если правее цифры в числе нет строго большей цифры, то вклад этой цифры равен её значению. Иначе вклад равен её значению, взятому со знаком минус. 

Например, 

  • <<BBA>> имеет значение 5+5+1=115+5+1=11; 
  • <<BBBC>> имеет значение −5+(−5)+(−5)+10=−5-5+(-5)+(-5)+10=-5;
  • <<ABC>> имеет значение −1+(−5)+10=4-1+(-5)+10=4;
  • <<BAC>> имеет значение −5+(−1)+10=4-5+(-1)+10=4;
  • <<ACA>> имеет значение −1+10+1=10-1+10+1=10.

Вам даны несколько заготовок чисел. Каждая заготовка представляет собой строку из заглавных английских букв и знаков вопроса. Для каждой заготовки необходимо определить, какое максимальное число может получиться, если каждый знак вопроса заменить на цифру московского числа.

입력

В первой строке дано одно целое число tt --- количество заготовок (1≤t≤50,0001 \le t \le 50\\,000).

В следующих tt строках даны строки s_is\_i, состоящие из заглавных английских букв и символов <<?>> --- заготовки для чисел. Сумма длин строк s_is\_i не превышает 300,000300\\,000.

출력

Для каждой заготовки выведите две строки. В первой из них выведите в десятичной системе счисления максимальное значение числа, которое может получиться из этой заготовки. А во второй строке --- саму заготовку, у которой знаки вопроса заменены на буквы английского алфавита таким образом, чтобы достигалось максимальное значение.