import java.io.*;
import java.util.*;

public class Scanner
{
   public Scanner(InputStream in)
   {
      this.in = new BufferedReader(new InputStreamReader(in));
      currentLineStart = -1; 
   }

   public Scanner(Reader in)
   {
      this.in = new BufferedReader(in);
      currentLineStart = -1; 
   }

   private void readNextLine()
   {
      try
      {
         currentLine = in.readLine();
         currentLineStart = 0;
         nextTokenStart = 0;
         currentToken = null;
      }
      catch (IOException ex)
      {
         currentLine = null;
         lastException = ex;
      }
   }

   private void readNextToken()
   {
      if (in == null) throw new IllegalStateException("scanner is closed");
      if (currentToken != null)
         return;
      if (currentLineStart == -1) readNextLine();
      if (currentLine == null)
         return;
      boolean done;
      while (nextTokenStart == currentLine.length())
      {
         readNextLine();
         if (currentLine == null)
            return;
         while (nextTokenStart < currentLine.length()
               && Character.isWhitespace(currentLine.charAt(nextTokenStart)))
         {
            nextTokenStart++;
         }
      }
      int end = nextTokenStart;
      while (end < currentLine.length()
            && !Character.isWhitespace(currentLine.charAt(end)))
      {
         end++;
      }
      currentToken = currentLine.substring(nextTokenStart, end);
      currentLineStart = end;
      nextTokenStart = end;
      while (nextTokenStart < currentLine.length()
            && Character.isWhitespace(currentLine.charAt(nextTokenStart)))
      {
         nextTokenStart++;
      }
   }

   private String consumeToken()
   {
      if (currentToken == null) return null;
      String r = currentToken;
      currentToken = null;
      return r;
   }

   public int nextInt()
   {
      if (!hasNext()) throw new NoSuchElementException("end of input");
      if (!hasNextInt()) throw new InputMismatchException("next item is not an integer");
      return Integer.parseInt(consumeToken());
   }

   public boolean hasNextInt()
   {
      readNextToken();
      if (currentToken == null)
         return false;
      try
      {
         Integer.parseInt(currentToken);
         return true;
      }
      catch (NumberFormatException ex)
      {
         return false;
      }
   }

   public double nextDouble()
   {
      if (!hasNext()) throw new NoSuchElementException("end of input");
      if (!hasNextDouble()) throw new InputMismatchException("next item is not a double");
      return Double.parseDouble(consumeToken());
   }

   public boolean hasNextDouble()
   {
      readNextToken();
      if (currentToken == null)
         return false;
      try
      {
         Double.parseDouble(currentToken);
         return true;
      }
      catch (NumberFormatException ex)
      {
         return false;
      }
   }

   public String next()
   {
      if (!hasNext()) throw new NoSuchElementException("end of input");
      return consumeToken();
   }

   public boolean hasNext()
   {
      readNextToken();
      return currentToken != null;
   }

   public String nextLine()
   {      
      if (!hasNextLine()) throw new NoSuchElementException("end of input");
      String r = currentLine.substring(currentLineStart);
      currentLineStart = -1; 
      return r;
   }   
   
   public boolean hasNextLine()
   {
      if (currentLineStart == -1) readNextLine();
      return currentLine != null;
   }

   public void close()
   {
      if (in == null) return;      
      try
      {
         in.close();
      }
      catch (IOException ex)
      {
         lastException = ex;
      }
      in = null;
   }

   public IOException ioException() { return lastException; }

   private BufferedReader in;
   private String currentLine;
   private String currentToken;
   private int currentLineStart;
   private int nextTokenStart;
   private IOException lastException;
}

class InputMismatchException extends RuntimeException
{
   public InputMismatchException() {}
   public InputMismatchException(String reason) { super(reason); }
}