Нека е даден цел број N. Ваша задача е да смените точно една цифра во бројот така што после промената ќе добиете број делив со 3 кој е најголем можен.
Да повториме, мора да се смени една цифра во влезниот број.

Напишете програма што го пресметува новиот број, кој е со следните карактеристики:
1. Тој се разликува од влезниот број во точно една цифра.
2. Тој се дели со 3.
3. Тој треба да е најголемиот можен број од сите оние кои ги исполнуваат точките 1 и 2.

Влез

Во првиот ред од влезот е даден бројот N (0 ≤ N < 10¹⁰¹, односно 0 ≤ N < 10^101).
Во тест случаи за 60% од поените N ≤ 1 000 000 000.

Излез

Отпечатете го бараниот број, без водечки нули (ако ги има).

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
123

излез
723

влез
999

излез
996