#include <iostream>
#include <vector>
using namespace std;

template <class T>
struct Node {
    T element;
    Node<T>* left;
    Node<T>* right;

    Node(const T& e) : element(e), left(nullptr), right(nullptr) {}
};

template <class T>
class BinTree {
public:
    Node<T>* root;
    int height;
    vector<T> arr;

    BinTree() : root(nullptr), height(0) {}
    BinTree(const vector<T>& arrs) : arr(arrs), height(0) {}
    void test() {
        for (auto x : arr) {
            cout << x << " ";
        }
    }
    Node<T>* returnroot() {
        return this->root;
    }

    Node<T>* build(int& index) {
        if (index >= arr.size() || arr[index] == 0) {
            index++;
            return nullptr;
        }

        Node<T>* node = new Node<T>(arr[index]);
        index++;
        node->left = build(index);
        //cout << "build left ";
        node->right = build(index);
        //cout << "build right ";

        return node;
    }

    void buildTree() {
        int index = 0;
        this->root = build(index);
    }

    //تن³ِ
    void preorder(Node<T>* node) {
        if (node == nullptr) return;

        cout << node->element << " ";
        preorder(node->left);
        preorder(node->right);
    }
    void inorder(Node<T>* node) {
        if (node == nullptr) return;

        inorder(node->left);
        cout << node->element << " ";
        inorder(node->right);
    }
    void postorder(Node<T>* node) {
        if (node == nullptr) return;

        postorder(node->left);
        postorder(node->right);
        cout << node->element << " ";
    }
};

int main() {
    int x = 0;
    vector<int> arr;
    int tmp;
    Node<int>* parent;
    while (cin >> tmp) {
        arr.push_back(tmp);
    }
    BinTree<int> tree(arr);
    tree.buildTree();
    //tree.test();
    auto r = tree.root;
    tree.preorder(r);
    cout << endl;
    tree.inorder(r);
    cout << endl;
    tree.postorder(r);
    cout << endl;

    return 0;
}