시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB97312440.000%

문제

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

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

A $1$ H $5 \cdot 10 ^ {3}$ O $10 ^ {7}$ V $5 \cdot 10 ^ {10}$
B $5$ I $10 ^ {4}$ P $5 \cdot 10 ^ {7}$ W $10 ^ {11}$
C $10$ J $5 \cdot 10 ^ {4}$ Q $10 ^ {8}$ X $5 \cdot 10 ^ {11}$
D $50$ K $10 ^ {5}$ R $5 \cdot 10 ^ {8}$ Y $10 ^ {12}$
E $100$ L $5 \cdot 10 ^ {5}$ S $10 ^ {9}$ Z $5 \cdot 10 ^ {12}$
F $500$ M $10 ^ {6}$ T $5 \cdot 10 ^ {9}$    
G $10 ^ {3}$ N $5 \cdot 10 ^ {6}$ U $10 ^ {10}$    

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

Например, 

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

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

입력

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

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

출력

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

서브태스크

번호배점제한
16

$S \le 1000$, $s_i$ не содержит <<?>>

29

$S \le 3 \cdot 10^5$, $s_i$ не содержит <<?>>

340

$S \le 1000$ & $s_i$ содержит не более трёх <<?>>

420

$S \le 1000$

525

$S \le 3 \cdot 10^5$

예제 입력 1

4
BBBC
????
A?B?C?D
YYYYY?

예제 출력 1

-5
BBBC
20000000000000
ZZZZ
15000000000034
AZBZCZD
6000000000000
YYYYYY

채점 및 기타 정보

  • 예제는 채점하지 않는다.