#include <bits/stdc++.h>
using namespace std;

class Solution {
    int *arr;      // Pointer to dynamically allocated array
    int size;      // Size of the array
    int top1;      // Top pointer for stack 1
    int top2;      // Top pointer for stack 2

public:
    // Constructor to initialize array and stack pointers
    Solution(int n) {
        size = n;
        // Allocate array of given size
        arr = new int[n];
        // Stack 1 starts empty before index 0
        top1 = -1;
        // Stack 2 starts empty after last index
        top2 = size;
    }

    // Function to push element into stack 1
    void push1(int x) {
        // Check if there is free space between the two stacks
        if (top1 + 1 < top2) {
            // Move top pointer of stack 1 forward
            top1++;
            // Insert the element at the new top position
            arr[top1] = x;
        } else {
            // No space left for stack 1
            cout << "Stack Overflow on Stack 1\n";
        }
    }

    // Function to push element into stack 2
    void push2(int x) {
        // Check if there is free space between the two stacks
        if (top2 - 1 > top1) {
            // Move top pointer of stack 2 backward
            top2--;
            // Insert the element at the new top position
            arr[top2] = x;
        } else {
            // No space left for stack 2
            cout << "Stack Overflow on Stack 2\n";
        }
    }

    // Function to pop element from stack 1
    int pop1() {
        // Check if stack 1 is empty
        if (top1 == -1) {
            // Print underflow message for stack 1
            cout << "Stack Underflow on S