#include <iostream>
#include <stack>
using namespace std;
stack<int> sortst(stack<int> input)
{
	int poped;
	stack<int> temp;
	while (!input.empty())
	{
		poped = input.top();
		input.pop();
		while (!temp.empty() && temp.top() < poped)
		{
			int pop2 = temp.top();
			input.push(pop2);
			temp.pop();
		}
		temp.push(poped);
	}
	return temp;
}
int main() {
	stack<int> input;
	input.push(3);
	input.push(6);
	input.push(1);
	input.push(2);
	input.push(9);
	input = sortst(input);
	while (!input.empty())
	{
		cout << input.top() << ' ';
		input.pop();
	}
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RhY2s+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0YWNrPGludD4gc29ydHN0KHN0YWNrPGludD4gaW5wdXQpCnsKCWludCBwb3BlZDsKCXN0YWNrPGludD4gdGVtcDsKCXdoaWxlICghaW5wdXQuZW1wdHkoKSkKCXsKCQlwb3BlZCA9IGlucHV0LnRvcCgpOwoJCWlucHV0LnBvcCgpOwoJCXdoaWxlICghdGVtcC5lbXB0eSgpICYmIHRlbXAudG9wKCkgPCBwb3BlZCkKCQl7CgkJCWludCBwb3AyID0gdGVtcC50b3AoKTsKCQkJaW5wdXQucHVzaChwb3AyKTsKCQkJdGVtcC5wb3AoKTsKCQl9CgkJdGVtcC5wdXNoKHBvcGVkKTsKCX0KCXJldHVybiB0ZW1wOwp9CmludCBtYWluKCkgewoJc3RhY2s8aW50PiBpbnB1dDsKCWlucHV0LnB1c2goMyk7CglpbnB1dC5wdXNoKDYpOwoJaW5wdXQucHVzaCgxKTsKCWlucHV0LnB1c2goMik7CglpbnB1dC5wdXNoKDkpOwoJaW5wdXQgPSBzb3J0c3QoaW5wdXQpOwoJd2hpbGUgKCFpbnB1dC5lbXB0eSgpKQoJewoJCWNvdXQgPDwgaW5wdXQudG9wKCkgPDwgJyAnOwoJCWlucHV0LnBvcCgpOwoJfQp9