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

// Data structure to store a Binary Tree node
struct Node
{
	int data;
	Node *left, *right;
};

// Function to create a new binary tree node having given key
Node* newNode(int key)
{
	Node* node = new Node;
	node->data = key;
	node->left = node->right = nullptr;

	return node;
}

// Function to insert given key into the tree
void insert(Node*& root, string level, int key)
{
	// tree is empty
	if (level.length() == 0)
	{
		root = newNode(key);
		return;
	}

	int i = 0;
	Node* ptr = root;
	while (i < level.length() - 1)
	{
		if (level[i++] == 'L')
			ptr = ptr->left;
		else
			ptr = ptr->right;
	}

	if (level[i] == 'L')
		ptr->left = newNode(key);
	else
		ptr->right = newNode(key);
}

// Iterative function to print the diagonal elements of given binary tree
void diagonalPrint(Node* root)
{
	// create an empty queue
	queue<Node*> q;

	// create a sentinel (dummy) node to denote end of a diagonal
	Node* sentinel = newNode(-1);

	// enqueue all nodes of first diagonal in binary tree
	while (root)
	{
		q.push(root);
		root = root->right;
	}

	// enqueue sentinel node at the end of each diagonal
	q.push(sentinel);

	// run till only sentinel is left
	while (q.size() != 1)
	{
		// dequeue front node
		Node* front = q.front();
		q.pop();

		if (front != sentinel)
		{
			// print current node
			cout << front->data << " ";

			// enqueue nodes of next diagonal in binary tree
			Node* node = front->left;
			while (node)
			{
				q.push(node);
				node = node->right;
			}
		}
		else
		{
			// if end of current diagonal is reached, enqueue sentinel node
			// and print newline
			q.push(sentinel);
			cout << endl;
		}
	}
}

// main function
int main()
{
    /* Construct below tree
          1
        /   \
       /     \
      2       3
     /      /  \
    /      /    \
   4      5      6
         / \
        /   \
       7     8
    */

	vector<pair<string, int> > keys =
	{
		 {"", 1}, {"L", 2}, {"R", 3}, {"LL", 4}, {"RL", 5},
		 {"RR", 6}, {"RLL", 7}, {"RLR", 8}
	};

	Node* root = nullptr;

	for (auto pair: keys)
		insert(root, pair.first, pair.second);

	diagonalPrint(root);

	return 0;
}