#include 
using namespace std;

struct node {
    char val;
    node * next;
};
 
struct SLL {
    node * head;
    
    void init() {
        head = NULL;
    }
    
    void insertFirst(char val) {
        node * new_node = new node;
        new_node->val = val;
        
        if(head == NULL) {
            head = new_node;
        }
        else {
            new_node->next = head;
            head = new_node;
        }
    }
    
    void insertLast(char val) {
        node * new_node = new node;
        new_node->val = val;
        
        if(head == NULL) {
            head = new_node;
        }
        else if(head->next == NULL) {
            head->next = new_node;
            new_node->next = NULL;
        }
        else {
            node * tmp = head;
            while(tmp->next != NULL) {
                tmp = tmp->next;
            }
            tmp->next = new_node;
            new_node->next = NULL;
        }
    }
    
    void deleteFirst() {
        if(head != NULL) {
            if(head->next == NULL) {
                delete head;
                head = NULL;
            }
            else {
                node * tmp = head;
                head = head->next;
                delete tmp;
            }
        }
    }
    void deleteLast() {
        if(head != NULL) {
            if(head -> next == NULL) {
                delete head;
                head =  NULL;
            }
            else {
                node * tmp = head;
                while(tmp -> next -> next != NULL) {
                    tmp = tmp->next;
                }
                node * tmp2 = tmp->next;
                delete tmp2;
                tmp->next = NULL;
            }
        }
    }
    
    node * findLastNode(char val) {
        node * tmp = head;
        while(tmp->val != val) {
            tmp = tmp->next;
        }
        return tmp;
    }
    void print() {
        node * tmp = head;
        while(tmp != NULL) {
            cout << tmp->val << " --> ";
            tmp = tmp->next;
        }
        cout << endl;
    }
};
const int max_size = 1000;
struct magacin {
    int idx;
    char niza[max_size];
    
    void init() {
        idx = -1;
    }
    
    bool isEmpty() {
        if(idx == -1) {
            return true;
        }
        else {
            return false;
        }
    }
    
    bool isFull() {
        if(idx == max_size - 1) {
            return true;
        }
        else {
            return false;
        }
    }
    
    int size() {
        return idx + 1;
    }
    
    void push(char element) {
        if(isFull()) {
            cout << "Nema poveke mesto za elementi" << endl;
            return;
        }
        idx++;
        niza[idx] = element;
    }
    void pop() {
        if(isEmpty()) {
            cout << "Stekot e prazen" << endl;
            return;
        }
        idx--;
    }
    
    char top() {
        if(isEmpty()) {
            cout << "Nema elementi vo stekot" << endl;
            return -1;
 
        }
        return niza[idx];
    }
    
    
};
int main()
{

    
    SLL sll;
    sll.init();
    sll.insertLast('i');
    sll.insertLast('s');
    sll.insertLast('p');
    sll.insertLast('i');
    sll.insertLast('t');
    sll.insertLast(' ');
    sll.insertLast('p');
    sll.insertLast('s');
    sll.insertLast('p');
    
    
    char F = ' ';
    
    magacin stack;
    stack.init();
    
    node * last = sll.findLastNode(F);
    
    node * h = sll.head;
    
    SLL rsll;
    rsll.init();
    while(h != last) {
        rsll.insertFirst(h->val);
        stack.push(h->val);
        h = h->next;
    }
    
    stack.push(F);
    
    
    
    
    while(rsll.head != NULL) {
        stack.push(rsll.head->val);
        rsll.deleteFirst();
    }
    
    while(!stack.isEmpty()) {
        cout << stack.top();
        stack.pop();
    }
    cout << endl;
    
    
    return 0;
}

/*
 9
 i
 s
 p
 i
 t
 
 p
 s
 p
 

 
 **/