// include
#include <algorithm>
#include <sstream>
#include <queue>
#include <iostream>
#include <cmath>
#include <string>

using namespace std;

// 数値を文字列に変換する
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

// repetition
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

const int Target     = 4; // 目的の値
const int PitcherNum = 3;  // ピッチャーの数
const int PitcherMax[PitcherNum] = {8, 5, 3}; // 各ピッチャーの最大値

// 終了条件を満たすか調べる
bool check(int *Pitchers)
{
    REP(i, PitcherNum)
        if (Pitchers[i] == Target) return true;
    return false;
}

// 現在の状態を保持する構造体
struct Status
{
    int p[3];
    int cnt;
    string ret;
};

// 幅優先で解く
Status SolveBFS()
{
    bool flag[PitcherMax[0]+1][PitcherMax[1]+1][PitcherMax[2]+1]; // ある状態になった事があるかを保持する（この処理がないと無限ループ）

    // 配列の初期化
    REP(i, PitcherMax[0]+1)
        REP(j, PitcherMax[1]+1)
            REP(k, PitcherMax[2]+1)
                flag[i][j][k] = false;

    queue<Status> bfs; // 幅優先用のキュー

    Status state;
    state.p[0] = PitcherMax[0];
    state.p[1] = 0;
    state.p[2] = 0;
    state.cnt = 0;
    state.ret = toString(state.p[0]) + " " + toString(state.p[1]) + " " + toString(state.p[2]) + "\n";
    bfs.push(state); // 初期状態をキューに追加

    while (!bfs.empty()) // キューが空になるまでループ
    {
        state = bfs.front(); bfs.pop(); // キューの先頭から要素を一つ取り出す
        if (check(state.p)) break; // 終了条件を満たしていれば終わる
        if (flag[state.p[0]][state.p[1]][state.p[2]]) continue; // 訪れたことがあるならスキップ
        else flag[state.p[0]][state.p[1]][state.p[2]] = true; // 訪れたことがないなら、フラグを立てる

        Status newState; // 次の状態
        REP (i, PitcherNum)
        {
            REP (j, PitcherNum)
            {
                if (i == j) continue; // 同じピッチャーに移すことはないからスキップ (例：８のピッチャー -> ８のピッチャー)

                // 中身を移す処理
                newState.p[i] = max(state.p[i] - (PitcherMax[j] - state.p[j]), 0);
                newState.p[j] = min(state.p[j] + state.p[i], PitcherMax[j]);
                newState.p[3 - i - j] = state.p[3 - i - j];

                // 移動した回数を1増やす
                newState.cnt = state.cnt + 1;

                // ピッチャーの状態遷移をメモする
                newState.ret = state.ret + toString(newState.p[0]) + " " + toString(newState.p[1]) + " " + toString(newState.p[2]) + "\n";

                // ピッチャーの中身が移動していない場合はスキップする
                if (newState.p[i] == state.p[i]) continue;

                // キューに状態を追加
                bfs.push(newState);
            }
        }
    }
    if (check(state.p)) return state;
    else
    {
        state.cnt = -1;
        state.ret = "目的の値になりませんでした";
        return state;
    }
}

int main()
{
    Status result = SolveBFS();

    cout << "目的の値: " << Target << endl;
    cout << "移動回数: " << result.cnt << endl;
    cout << "ピッチャーの状態遷移:" << endl;
    cout << result.ret << endl;

    return 0;
}