#include <stdio.h>
#include <string.h>

void read_strings();
void output_strings();
void swap();


#define N 100 // Max number of strings
#define SIZE 100000 //Max size of a string

/* Strings stores a sequence of very large strings */
char Strings[N][SIZE];

/* This function finds the smallest string in the
 * sequence pStr[index], pStr[index+1], ..., pStr[n-1],
 * and returns the index of the smallest string found.
 */
int find_smallest(char *pStr[], int index, int n)
{
	int j;

	j = index; // initial guess of the index of smallest string

	for (int i = index+1; i < n; i++) {
		if (strcmp(pStr[i], pStr[j]) < 0) // a smaller string found
			j = i;
	}

	return j;
}

/* This function sorts the n strings in Strings in lexicographic order.
 * To avoid moving large strings, the sorting is done using pointers
 * in array pStr in the following fashion.
 *
 * Initially pStr[i] points to Strings[i]. Then we change the pointer pStr[0]
 * to point to the smallest string in Strings, say Strings[j]. Simultaneously, pStr[j]
 * is made to point to Strings[0]. So now pStr[0] points to the smallest string, and
 * pStr[1] - pStr[n-1] point to the remaining strings. The same algorithm is repeated
 * for the remaining strings.
 */
void sort_strings(char *pStr[], int n)
{
	int j;

	// Initialize the pointers in pStr
	for (int i = 0; i < n; i++)
		pStr[i] = Strings[i];

	for (int i = 0; i < n-1; i++) {
		j = find_smallest(pStr, i, n); // the index of smallest string in pStr[i] - pStr[n-1]
		swap(pStr+i, pStr+j); // Put pointer to string pStr[j] in pStr[i]
	}
}


int main()
{
	/* This is an array of pointers. Each pointer points to a character (actually a string).
	 * This array is used to sort the large strings stored in Strings.
	 */
	char *pStr[N];
	int n; // The actual number of strings

	read_strings(&n); // read strings
	sort_strings(pStr, n); // sort strings
	output_strings(pStr, n); // output strings
}


/* Reads n, followed by n strings */
void read_strings(int *pn)
{
	scanf("%d", pn);
	for (int i = 0; i < *pn; i++)
		scanf(" %s", Strings[i]);
}

/* Outputs n strings in stored in Strings using the order
 * specified by pointer array pStr.
 */
void output_strings(char *pStr[], int n)
{
	printf("Strings in sorted order are:\n");

	for (int i = 0; i < n; i++)
		printf("%s\n", pStr[i]);
}

/* Swaps values on in pointers a and b.
 * Each of this points to a location which stores a pointer
 * to a string.
 */
void swap(char **a, char **b)
{
	char *c;

	c = *a;
	*a = *b;
	*b = c;
}