4. Problémy s počítaním

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahni (liahen.ksp.sk). Keď budeš riešiť sadu loops_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Paulinke na [email protected]

Dávid má mladšiu sestru a ako dobrý súrodenec jej pomáha s úlohami. Napríklad dnes sa vrátila zo školy s tým, že sa učili deliť deviatimi.

Dávid jej preto začal vymýšľať rôzne cvičenia, po chvíli však zistil, že to tak trochu nezvládol. Čísla, ktoré napísal neboli deliteľné deviatimi. Zobral teda gumu a vymazal z nich niekoľko cifier, aby svoju chybu napravil. Lenže tri úmorné roky na matfyze si vybrali svoju daň – Dávid zistil, že zabudol deliť deviatimi¹!

Úloha

Na vstupe dostanete číslo, v ktorom sú niektoré cifry nahradené otáznikmi. Nahraďte tieto otázniky ciframi tak, aby výsledné číslo bolo deliteľné deviatimi a bolo najmenšie možné.

Formát vstupu

Na vstupe dostanete reťazec cifier a otáznikov. Na začiatku čísla nebudú prebytočné nuly.

Formát výstupu

Na výstup vypíšte číslo deliteľné deviatimi, ktoré vzniklo zo zadaného reťazca nahradením znakov ? ciframi 0 až 9. Toto číslo nemôže začínať nulami.

Hodnotenie

Úloha má 15 testovacích sád, za každú viete získať jeden bod.

Podrobnejšie, pre jednotlivé sady platia nasledovné obmedzenia:

Príklady

Input:

99?

Output:

990

Input:

?00?

Output:

1008

Číslo nemôže začínať nulou, preto je výstup 0009 alebo 0000 nesprávny.

Input:

?

Output:

0