Расшифровка генома берляндского мамонта подходит к концу!
Одна из немногих оставшихся задач — восстановление нераспознанных нуклеотидов в найденной цепочке s. Каждый нуклеотид кодируется прописной буквой латинского алфавита: 'A', 'C', 'G' или 'T'. Нераспознанный нуклеотид кодируется знаком вопроса '?'. Таким образом, s — это строка, состоящая из букв 'A', 'C', 'G', 'T' и символов '?'.
Известно, что в расшифрованном геноме берляндского мамонта количества нуклеотидов каждого из четырех видов равны между собой.
Требуется расшифровать геном и заменить каждый нераспознанный нуклеотид на один из четырёх так, чтобы количества нуклеотидов каждого из четырёх типов стали равны между собой.
Выходные данные
Если расшифровать геном возможно, выведите его расшифровку. Если существует много вариантов расшифровки, то выведите любой из них. Если искомой замены не существует, то выведите три знака равно подряд «===» (без кавычек).
Примечание
В первом примере можно заменить первый знак вопроса на букву 'A', второй знак вопроса на букву 'G', в третий — на букву 'T', тогда каждого нуклеотида в геноме будет по 2.
Во втором примере геном уже корректно расшифрован и каждого нуклеотида в нём ровно по одному.
В третьем и четвертом примерах корректно расшифровать геном невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
AG?C??CT
|
AGACGTCT
|
|
2
|
4
AGCT
|
AGCT
|
|
3
|
6
????G?
|
===
|
|
4
|
4
AA??
|
===
|