У Паши много хомяков, и он устраивает им зарядку. Сегодня на зарядку пришли n хомяков (n — четное). Хомяки выстроились в ряд, при этом каждый хомяк либо сел, либо встал.
Паше для очередного упражнения нужно, чтобы ровно 
хомяков стояли, а остальные сидели. За одну минуту Паша может заставить некоторого хомяка либо сесть, либо встать. Сколько минут ему понадобится, чтобы добиться требуемого, если он будет действовать оптимально?
Выходные данные
В первой строке выведите единственное целое число — минимальное требуемое количество минут. Во второй строке выведите строку описывающее положение хомяков, после того как Паша выполнит требуемые действия. Если существует несколько оптимальных положений, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
xxXx
|
1
XxXx
|
|
2
|
2
XX
|
1
xX
|
|
3
|
6
xXXxXx
|
0
xXXxXx
|