import java.io.*;

class UseLists0
{

 public static void main(String [] args) throws IOException
 {
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  List list1,list2;
  String str1,str2;
  System.out.print("Enter list 1: ");
  str1=in.readLine();
  list1=stringToList(str1);
  System.out.print("Enter list 2: ");
  str2=in.readLine();
  list2=stringToList(str2);
  System.out.print("\nList 1 is: ");
  listPrint(list1);
  System.out.print("\nList 2 is: ");
  listPrint(list2);
  System.out.print("\n\nAppending list 1 to list 2 is: ");
  listPrint(append(list1,list2));
  System.out.print("\nMerging list 1 with list 2 is: ");
  listPrint(merge(list1,list2));
  System.out.println();
  
 }

 private static List empty()
 {
  return ArrayList.empty();
 }

 public static List stringToList(String str)
 {
  List list = empty();
  for(int i=str.length()-1;i>=0;i--)
     list=list.cons(new Character(str.charAt(i)));
  return list;
 }

 public static void listPrint(List list)
 {
  Character Ch;
  if(!list.isempty())
     {
      Ch=(Character)(list.head());
      System.out.print(Ch.charValue());
      listPrint(list.tail());
     }
 }

 public static List append(List l1,List l2)
 {
  if(l1.isempty())
     return l2;
  else
     {
      List a=append(l1.tail(),l2);
      return a.cons(l1.head());
     }
 }

 public static List merge(List l1,List l2)
 {
  if(l1.isempty())
     return l2;
  else if(l2.isempty())
     return l1;
  else
     {
      List m=merge(l1.tail(),l2.tail());
      return m.cons(l2.head()).cons(l1.head());
     }
 }

}