using System;
using System.Collections.Generic;
namespace Boardmessingaround
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Char> board = new List<char>();
            Console.WriteLine("Hello World!");
            String s = Console.ReadLine();
            foreach(char c in s)
            {
                board.Add(c);
            }
            foreach (char c in board)
            {
                Console.Write(c);
            }
            Console.Write('\n');
            //char input = 's';
            String sol = Solve(board);
            if(sol==null||sol == "?")
            {
                Console.WriteLine("No Solution");
            }
            else
            {
                Console.WriteLine(sol);

            }
            //Console.WriteLine(sol);
           /* while(input != -1)
            {
                Console.WriteLine("Board state");
                PrintBoard(board);
                input = Convert.ToInt32(Console.ReadLine());
                Remove(ref board, input);

            }
            */
            Console.Read();
        }
        public static void PrintBoard(List<char> board)
        {
            foreach (char c in board)
            {
                Console.Write(c);
            }
            Console.Write('\n');

        }
        public static void Remove(ref List<char> board, int i)
        {
            int len = board.Count;
            //error checking
            if(i>= len||i<0|| board[i]== '0')
            {
                Console.WriteLine("Invalid choice");
                Console.WriteLine(i + " , " + len + " " + board[i]);
            }
            else
            {
                board[i] = '.';
                if (i + 1 <len)
                {
                    board[i + 1] = Flip(board[i + 1]);
                }
                if (i -1 >= 0)
                {
                    board[i - 1] = Flip(board[i - 1]);
                }
            }
        }
        public static char Flip(char f)
        {
            if (f == '.') return '.';
            if (f == '0')
            {
                return '1';
            }
            else
            {
                return '0';
            }
        }


        public static String Solve(List<char> board)
        {
            //check valid moves//if solved.
            if (Solved(board))
            {
                return "Solved!";
            }
            List<int> choices = ValidMoves(board);
            String solution ="";
            //loop through each choice
            foreach(int i in choices)
            {
                Console.WriteLine(choices.Count);
                List<char> temp = new List<char>();
                temp.AddRange(board);
                Remove(ref temp, i);
                if (temp.Equals(board))
                {
                    Console.WriteLine("RIP");
                }
                solution = i +' ' + Solve(temp);
                if (solution[solution.Length-1] == '!') return solution;
            }
            //recurssion! Try each solution in order then call previous solution
            //figure out possible starts.
            //No solution found
            return "?";
        }

        //Returns a list of valid moves
        public static List<int> ValidMoves(List<char> board)
        {
            List<int> moves = new List<int>();
            for(int i = 0; i<board.Count; i++)
            {
                if (board[i] == '1')
                {
                    moves.Add(i);
                }
            }
            return moves;
        }

        //Checks if the board is solved.
        public static bool Solved(List<char> board)
        {
            bool solved = true;
            foreach(char c in board)
            {
                if (c != '.') solved = false;
            }
            return solved;
        }

    }
}