// $Id: ackermann.java,v 1.4 2000/10/07 08:41:43 doug Exp $
// http://www.bagley.org/~doug/shootout/

public class ackermann {

    public static void main(String args[]) {
    int NUM = Integer.parseInt(args[0]);
    System.out.print("Ack(3," + NUM + "): " + Ack(3, NUM) + "\n");
    }

    public static int Ack(int M, int N) {
    if (M == 0) return( N + 1 );
    if (N == 0) return( Ack(M - 1, 1) );
    return( Ack(M - 1, Ack(M, (N - 1))) );
    }

}

// $Id: ary3.java,v 1.2 2001/05/31 20:17:42 doug Exp $
// http://www.bagley.org/~doug/shootout/

// this program is modified from:
//   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
// Timing Trials, or, the Trials of Timing: Experiments with Scripting
// and User-Interface Languages</a> by Brian W. Kernighan and
// Christopher J. Van Wyk.

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

public class ary3 {
    public static void main(String args[]) {
    int i, j, k, n = Integer.parseInt(args[0]);
    int x[] = new int[n];
    int y[] = new int[n];

    for (i = 0; i < n; i++)
        x[i] = i + 1;
    for (k = 0; k < 1000; k++ )
        for (j = n-1; j >= 0; j--)
        y[j] += x[j];

    System.out.println(y[0] + " " + y[n-1]);
    }
}

// $Id: wc.java,v 1.2 2001/05/31 22:56:19 doug Exp $
// http://www.bagley.org/~doug/shootout/
// with help from Dirus@programmer.net

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

// this program modified from:
//   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
// Timing Trials, or, the Trials of Timing: Experiments with Scripting
// and User-Interface Languages</a> by Brian W. Kernighan and
// Christopher J. Van Wyk.

public class wc {
    public static void main(String[] args) {
        int nl = 0, nw = 0, nc = 0;

        try {
            byte[] buff = new byte[4096];
            boolean inword = false;
            int length;

            while ((length = System.in.read(buff)) != -1) {
                nc += length;
                for(int i = 0; i < length; i++) {
                    char c = (char)buff[i];
                    if (c == '\n')
                        ++nl;
                    if (Character.isWhitespace(c))
                        inword = false;
                    else if (inword == false) {
                        ++nw;
                        inword = true;
                    }
                }
            }
        } catch (IOException e) {
            System.err.println(e);
            return;
        }
        System.out.println(Integer.toString(nl) + " " +
                           Integer.toString(nw) + " " +
                           Integer.toString(nc));
    }
}

// $Id: echo.java,v 1.4 2001/06/01 12:40:29 doug Exp $
// http://www.bagley.org/~doug/shootout/
// author: Dirus@programmer.net

import java.io.*;
import java.net.*;

public class echo {
    public static void main(String[] args) throws Exception {
    int iIterations = 1;
    try {
        iIterations = Integer.parseInt(args[0]);
    } catch(Exception e) { }

    EchoServer esServer = new EchoServer(0);
    new EchoClient(InetAddress.getLocalHost(), esServer.getPort(), iIterations);
    }
}

class EchoClient extends Thread {
    private static final String GREETING = "Hello there sailor\n";
    private final InetAddress inetaServer;
    private final int         iPort;
    private final int         iIterations;

    public EchoClient(InetAddress inetaServer, int iPort, int iIterations) {
    this.inetaServer = inetaServer;
    this.iPort = iPort;
    this.iIterations = iIterations;
    start();
    }

    public void run() {
    Socket socketFromServer = null;
    try {
        socketFromServer = new Socket(inetaServer, iPort);
        BufferedReader in = new BufferedReader(new InputStreamReader(socketFromServer.getInputStream()));
        OutputStream out = socketFromServer.getOutputStream();

        byte[] bytesOut = GREETING.getBytes();
        String strIn = GREETING.trim();
        for(int i = 0; i < iIterations; ++i) {
        out.write(bytesOut);
        out.flush();
        String strRead = in.readLine();
        if(!strRead.equals(strIn))
            throw new RuntimeException("client: \"" + strIn + "\" ne \"" + strRead + "\"");
        }
    } catch(Exception e) {
        e.printStackTrace();
    }

    try {
        socketFromServer.close();
    } catch(Exception e) { }
    }
}

class EchoServer extends Thread {
    private static final int   BUFFER_SIZE = 1024;
    private final ServerSocket ssAccepting;
    private final int          iPort;

    public EchoServer(int iPort) throws IOException {
    ssAccepting = new ServerSocket(iPort);
    this.iPort = ssAccepting.getLocalPort();
    start();
    }

    public final int getPort() {
    return iPort;
    }

    public void run() {
    byte bytesIn[] = new byte[BUFFER_SIZE];
    try {
        Socket socketClient = ssAccepting.accept();
        InputStream in = socketClient.getInputStream();
        OutputStream out = socketClient.getOutputStream();
        int iLength, iCount = 0;
        while ((iLength = in.read(bytesIn)) != -1) {
        out.write(bytesIn, 0, iLength);
        out.flush();
        iCount += iLength;
        }
        System.out.println("server processed " + iCount + " bytes");
    } catch (Exception e) {
        e.printStackTrace();
    }
    }
}

// $Id: except.java,v 1.1 2000/12/17 17:58:23 doug Exp $
// http://www.bagley.org/~doug/shootout/
// Collection class code is from my friend Phil Chu, Thanks Phil!

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

class Lo_Exception extends Exception {
    int num = 0;
    public Lo_Exception(int num) {
    this.num = num;
    }
    public String toString() {
    return "Lo_Exception, num = " + this.num;
    }
}

class Hi_Exception extends Exception {
    int num = 0;
    public Hi_Exception(int num) {
    this.num = num;
    }
    public String toString() {
    return "Hi_Exception, num = " + this.num;
    }
}

public class except {
    static int Lo = 0;
    static int Hi = 0;

    public static void main(String args[]) throws IOException {
    int n = Integer.parseInt(args[0]);

    for (int i=0; i<n; i++) {
        some_function(i);
    }
    System.out.println("Exceptions: HI=" + Hi + " / LO=" + Lo);
    }

    public static void some_function(int n) {
    try {
        hi_function(n);
    } catch (Exception e) {
        System.out.println("We shouldn't get here: " + e);
    }
    }

    public static void hi_function(int n) throws Hi_Exception, Lo_Exception {
    try {
        lo_function(n);
    } catch (Hi_Exception e) {
        Hi++;
    }
    }

    public static void lo_function(int n) throws Hi_Exception, Lo_Exception {
    try {
        blowup(n);
    } catch (Lo_Exception e) {
        Lo++;
    }
    }

    public static void blowup(int n) throws Hi_Exception, Lo_Exception {
    if ((n % 2) == 0) {
        throw new Lo_Exception(n);
    } else {
        throw new Hi_Exception(n);
    }
    }
}

// $Id: fibo.java,v 1.2 2000/12/24 19:10:50 doug Exp $
// http://www.bagley.org/~doug/shootout/

public class fibo {
    public static void main(String args[]) {
    int N = Integer.parseInt(args[0]);
    System.out.println(fib(N));
    }
    public static int fib(int n) {
    if (n < 2) return(1);
    return( fib(n-2) + fib(n-1) );
    }
}

// $Id: hash.java,v 1.3 2001/03/02 02:17:29 doug Exp $
// http://www.bagley.org/~doug/shootout/

// this program is modified from:
//   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
// Timing Trials, or, the Trials of Timing: Experiments with Scripting
// and User-Interface Languages</a> by Brian W. Kernighan and
// Christopher J. Van Wyk.

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

public class hash {

    public static void main(String args[]) throws IOException {
    int n = Integer.parseInt(args[0]);
    int i, c;
    String s = "";
    Integer ii;
    // the original program used:
    // Hashtable ht = new Hashtable();
    // John Olsson points out that Hashtable is for synchronized access
    // and we should use instead:
    HashMap ht = new HashMap();

    c = 0;
    for (i = 1; i <= n; i++)
        ht.put(Integer.toString(i, 16), new Integer(i));
    for (i = 1; i <= n; i++)
        // The original code converted to decimal string this way:
        // if (ht.containsKey(i+""))
        if (ht.containsKey(Integer.toString(i, 10)))
        c++;

    System.out.println(c);
    }
}

// $Id: hash2.java,v 1.3 2001/05/31 20:37:44 doug Exp $
// http://www.bagley.org/~doug/shootout/

import java.util.*;

class Val {
    int val;
    Val(int init) { val = init; }
}

public class hash2 {
    public static void main(String args[]) {
    int n = Integer.parseInt(args[0]);
    HashMap hash1 = new HashMap(10000);
    HashMap hash2 = new HashMap(n);

    for(int i = 0; i < 10000; i++)
        hash1.put("foo_" + Integer.toString(i, 10), new Val(i));
    for(int i = 0; i < n; i++) {
        Iterator it = hash1.entrySet().iterator();
        while(it.hasNext()) {
            Map.Entry h1 = (Map.Entry)it.next();
            String key = (String)h1.getKey();
            int v1 = ((Val)h1.getValue()).val;
            if (hash2.containsKey(key))
                ((Val)hash2.get(key)).val += v1;
            else
                hash2.put(key, new Val(v1));
        }
    }

    System.out.print(((Val)hash1.get("foo_1")).val    + " " +
                     ((Val)hash1.get("foo_9999")).val + " " +
                     ((Val)hash2.get("foo_1")).val    + " " +
                     ((Val)hash2.get("foo_9999")).val + "\n");
    }
}

// $Id: heapsort.java,v 1.6 2001/05/08 02:46:59 doug Exp $
// http://www.bagley.org/~doug/shootout/

import java.text.*;
import java.lang.reflect.Array;

public class heapsort {

    public static final long IM = 139968;
    public static final long IA =   3877;
    public static final long IC =  29573;

    public static void main(String args[]) {
    int N = Integer.parseInt(args[0]);
    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(10);
    nf.setMinimumFractionDigits(10);
    nf.setGroupingUsed(false);
    double []ary = (double[])Array.newInstance(double.class, N+1);
    for (int i=1; i<=N; i++) {
        ary[i] = gen_random(1);
    }
    heapsort(N, ary);
    System.out.print(nf.format(ary[N]) + "\n");
    }

    public static long last = 42;
    public static double gen_random(double max) {
    return( max * (last = (last * IA + IC) % IM) / IM );
    }

    public static void heapsort(int n, double ra[]) {
    int l, j, ir, i;
    double rra;

    l = (n >> 1) + 1;
    ir = n;
    for (;;) {
        if (l > 1) {
        rra = ra[--l];
        } else {
        rra = ra[ir];
        ra[ir] = ra[1];
        if (--ir == 1) {
            ra[1] = rra;
            return;
        }
        }
        i = l;
        j = l << 1;
        while (j <= ir) {
        if (j < ir && ra[j] < ra[j+1]) { ++j; }
        if (rra < ra[j]) {
            ra[i] = ra[j];
            j += (i = j);
        } else {
            j = ir + 1;
        }
        }
        ra[i] = rra;
    }
    }
}

// $Id: hello.java,v 1.1 2001/06/17 22:00:34 doug Exp $
// http://www.bagley.org/~doug/shootout/

public class hello {
    public static void main(String args[]) {
    System.out.print("hello world\n");
    }
}

// $Id: lists.java,v 1.1 2001/01/14 18:13:15 doug Exp $
// http://www.bagley.org/~doug/shootout/

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

public class lists {
    static int SIZE = 10000;

    public static void main(String args[]) {
    int n = Integer.parseInt(args[0]);
    int result = 0;
    for (int i = 0; i < n; i++) {
        result = test_lists();
    }
    System.out.println(result);
    }
    public static int test_lists() {
    int result = 0;
    // create a list of integers (Li1) from 1 to SIZE
    LinkedList Li1 = new LinkedList();
    for (int i = 1; i < SIZE+1; i++) {
        Li1.addLast(new Integer(i));
    }
    // copy the list to Li2 (not by individual items)
    LinkedList Li2 = new LinkedList(Li1);
    LinkedList Li3 = new LinkedList();
    // remove each individual item from left side of Li2 and
    // append to right side of Li3 (preserving order)
    while (! Li2.isEmpty()) {
        Li3.addLast(Li2.removeFirst());
    }
    // Li2 must now be empty
    // remove each individual item from right side of Li3 and
    // append to right side of Li2 (reversing list)
    while (! Li3.isEmpty()) {
        Li2.addLast(Li3.removeLast());
    }
    // Li3 must now be empty
    // reverse Li1
    LinkedList tmp = new LinkedList();
    while (! Li1.isEmpty()) {
        tmp.addFirst(Li1.removeFirst());
    }
    Li1 = tmp;
    // check that first item is now SIZE
    if (((Integer)Li1.getFirst()).intValue() != SIZE) {
        System.err.println("first item of Li1 != SIZE");
        return(0);
    }
    // compare Li1 and Li2 for equality
    if (! Li1.equals(Li2)) {
        System.err.println("Li1 and Li2 differ");
        System.err.println("Li1:" + Li1);
        System.err.println("Li2:" + Li2);
        return(0);
    }
    // return the length of the list
    return(Li1.size());
    }
}

// $Id: matrix.java,v 1.3 2001/05/27 14:52:57 doug Exp $
// http://www.bagley.org/~doug/shootout/
// modified to use a little less memory by Thomas Holenstein

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

public class matrix {
    static int SIZE = 30;

    public static void main(String args[]) {
    int n = Integer.parseInt(args[0]);
    int m1[][] = mkmatrix(SIZE, SIZE);
    int m2[][] = mkmatrix(SIZE, SIZE);
    int mm[][] = new int[SIZE][SIZE];
    for (int i=0; i<n; i++) {
        mmult(SIZE, SIZE, m1, m2, mm);
    }
    System.out.print(mm[0][0]);
    System.out.print(" ");
    System.out.print(mm[2][3]);
    System.out.print(" ");
    System.out.print(mm[3][2]);
    System.out.print(" ");
    System.out.println(mm[4][4]);
    }

    public static int[][] mkmatrix (int rows, int cols) {
    int count = 1;
    int m[][] = new int[rows][cols];
    for (int i=0; i<rows; i++) {
        for (int j=0; j<cols; j++) {
        m[i][j] = count++;
        }
    }
    return(m);
    }

    public static void mmult (int rows, int cols, 
                          int[][] m1, int[][] m2, int[][] m3) {
    for (int i=0; i<rows; i++) {
        for (int j=0; j<cols; j++) {
        int val = 0;
        for (int k=0; k<cols; k++) {
            val += m1[i][k] * m2[k][j];
        }
        m3[i][j] = val;
        }
    }
    }
}

// $Id: methcall.java,v 1.3 2000/12/24 22:04:51 doug Exp $
// http://www.bagley.org/~doug/shootout/
// Collection class code is from my friend Phil Chu, Thanks Phil!

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

class Toggle {
    boolean state = true;
    public Toggle(boolean start_state) {
    this.state = start_state;
    }
    public boolean value() {
    return(this.state);
    }
    public Toggle activate() {
    this.state = !this.state;
    return(this);
    }
}

class NthToggle extends Toggle {
    int count_max = 0;
    int counter = 0;

    public NthToggle(boolean start_state, int max_counter) {
    super(start_state);
    this.count_max = max_counter;
    this.counter = 0;
    }
    public Toggle activate() {
    this.counter += 1;
    if (this.counter >= this.count_max) {
        this.state = !this.state;
        this.counter = 0;
    }
    return(this);
    }
}

public class methcall {
    public static void main(String args[]) throws IOException {
    int n = Integer.parseInt(args[0]);

    boolean val = true;
    Toggle toggle = new Toggle(val);
    for (int i=0; i<n; i++) {
        val = toggle.activate().value();
    }
    System.out.println((val) ? "true" : "false");

    val = true;
    NthToggle ntoggle = new NthToggle(true, 3);
    for (int i=0; i<n; i++) {
        val = ntoggle.activate().value();
    }
    System.out.println((val) ? "true" : "false");
    }
}

// $Id: nestedloop.java,v 1.1 2000/12/30 21:42:57 doug Exp $
// http://www.bagley.org/~doug/shootout/

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

public class nestedloop {
    public static void main(String args[]) throws IOException {
    int n = Integer.parseInt(args[0]);
    int x = 0;
    for (int a=0; a<n; a++)
        for (int b=0; b<n; b++)
        for (int c=0; c<n; c++)
            for (int d=0; d<n; d++)
            for (int e=0; e<n; e++)
                for (int f=0; f<n; f++)
                x++;
    System.out.println(x);
    }
}

// $Id: objinst.java,v 1.2 2000/12/24 22:04:57 doug Exp $
// http://www.bagley.org/~doug/shootout/
// Collection class code is from my friend Phil Chu, Thanks Phil!

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

class Toggle {
    boolean state = true;
    public Toggle(boolean start_state) {
    this.state = start_state;
    }
    public boolean value() {
    return(this.state);
    }
    public Toggle activate() {
    this.state = !this.state;
    return(this);
    }
}

class NthToggle extends Toggle {
    int count_max = 0;
    int counter = 0;

    public NthToggle(boolean start_state, int max_counter) {
    super(start_state);
    this.count_max = max_counter;
    this.counter = 0;
    }
    public Toggle activate() {
    this.counter += 1;
    if (this.counter >= this.count_max) {
        this.state = !this.state;
        this.counter = 0;
    }
    return(this);
    }
}

public class objinst {
    public static void main(String args[]) throws IOException {
    int n = Integer.parseInt(args[0]);
    Toggle toggle1 = new Toggle(true);
    for (int i=0; i<5; i++) {
        System.out.println((toggle1.activate().value()) ? "true" : "false");
    }
    for (int i=0; i<n; i++) {
        Toggle toggle = new Toggle(true);
    }

    System.out.println("");
    
    NthToggle ntoggle1 = new NthToggle(true, 3);
    for (int i=0; i<8; i++) {
        System.out.println((ntoggle1.activate().value()) ? "true" : "false");
    }
    for (int i=0; i<n; i++) {
        NthToggle toggle = new NthToggle(true, 3);
    }
    }
}

// $Id: prodcons.java,v 1.1 2000/12/20 13:41:33 doug Exp $
// http://www.bagley.org/~doug/shootout/
// Producer-Consumer Example by Bill Lear
// Adapted from http://java.sun.com/docs/books/tutorial/essential/threads

public class prodcons {
    private class CubbyHole {
        private int m_contents;
        private boolean m_available = false;

        public synchronized int get() {
            while (m_available == false) {
                try {
                    wait();
                } catch (InterruptedException e) { }
            }
            m_available = false;
            notifyAll();
            return m_contents;
        }

        public synchronized void put(int value) {
            while (m_available == true) {
                try {
                    wait();
                } catch (InterruptedException e) { }
            }
            m_contents = value;
            m_available = true;
            notifyAll();
        }
    }

    private class Producer extends Thread {
        private CubbyHole m_cubbyhole;
        private int m_count;

        public Producer(CubbyHole c, int count) {
            m_cubbyhole = c;
            m_count = count;
        }

        public void run() {
            for (int i = 0; i < m_count; i++) {
                m_cubbyhole.put(i);
                ++m_produced;
            }
        }
    }

    private class Consumer extends Thread {
        private CubbyHole m_cubbyhole;
        private int m_count;

        public Consumer(CubbyHole c, int count) {
            m_cubbyhole = c;
            m_count = count;
        }

        public void run() {
            int value = 0;
            for (int i = 0; i < m_count; i++) {
                value = m_cubbyhole.get();
                ++m_consumed;
            }
        }
    }

    public void run() {
        m_producer.start();
        m_consumer.start();
        try { m_producer.join(); } catch (InterruptedException e) { }
        try { m_consumer.join(); } catch (InterruptedException e) { }
        System.out.println(m_produced + " " + m_consumed);
    }

    public prodcons(int count) {
        CubbyHole m_cubbyhole = new CubbyHole();
        m_producer = new Producer(m_cubbyhole, count);
        m_consumer = new Consumer(m_cubbyhole, count);
    }

    public static void main(String[] args) {
        int count = 1;
        try { count = Integer.parseInt(args[0]); } catch (Exception e) { }
        new prodcons(count).run();
    }

    private Producer m_producer;
    private Consumer m_consumer;
    private int m_produced = 0;
    private int m_consumed = 0;
}

// $Id: random.java,v 1.10 2001/05/08 01:51:39 doug Exp $
// http://www.bagley.org/~doug/shootout/

import java.text.*;

public class random {

    public static final long IM = 139968;
    public static final long IA = 3877;
    public static final long IC = 29573;

    public static void main(String args[]) {
    int N = Integer.parseInt(args[0]);
    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(9);
    nf.setMinimumFractionDigits(9);
    nf.setGroupingUsed(false);
    double result = 0;
    while (N-- > 0) {
        result = gen_random(100);
    }
    System.out.println(nf.format(result));
    }

    public static long last = 42;
    public static double gen_random(double max) {
    return( max * (last = (last * IA + IC) % IM) / IM );
    }
}

// $Id: regexmatch.java,v 1.2 2003/10/13 16:50:21 tomk Exp $
// http://www.bagley.org/~doug/shootout/
// contributed by Tom Kludy

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

public class regexmatch {

  public static void main(String args[])
  throws IOException, PatternSyntaxException {

    int n = (args.length > 0) ? Integer.parseInt(args[0]) : 1;
    LinkedList lines = new LinkedList();
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String line;
    while( (line = in.readLine()) != null )
      lines.addLast(line);
    in.close();

    Pattern pattern = Pattern.compile(
      "(?:^|[^\\d\\(])"+           // must be preceeded by non-digit
      "(?:\\((\\d\\d\\d)\\)|(\\d\\d\\d))"+// area code is 3 digits (match 1&2)
      "[ ]"+                       // area code followed by one space
      "(\\d\\d\\d)"+               // match 3: prefix of 3 digits
      "[ -]"+                      // separator is either space or dash
      "(\\d\\d\\d\\d)"+            // match 4: last 4 digits
      "(?:\\D|$)"                  // must be followed by a non-digit
      );

    int count = 0;
    while(--n >= 0) {
      for (ListIterator li = lines.listIterator(); li.hasNext();) {
        Matcher matcher = pattern.matcher((String)li.next());
        if (matcher.find()) {
          StringBuffer num = new StringBuffer("(");
          String areaCode = matcher.group(1);
          if ( areaCode == null )
            areaCode = matcher.group(2);
          num.append(areaCode).append(") ").append(matcher.group(3))
             .append("-").append(matcher.group(4));
          if ( n == 0 )
            System.out.println(++count + ": " + num);
        }
      }
    }
  }
}

// $Id: reversefile.java,v 1.2 2001/05/31 22:41:04 doug Exp $
// http://www.bagley.org/~doug/shootout/
// author: Dirus@programmer.net

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

public class reversefile {
    public static void main(String[] args) {
        ArrayList al = new ArrayList(4096);

        try {
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            String strLine;
            while((strLine = in.readLine()) != null)
                al.add(strLine);
            in.close();
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(1);
        }

        String strArray[] = new String[al.size()];
        al.toArray(strArray);

        for(int i = strArray.length - 1; i >= 0; i--)
            System.out.println(strArray[i]);
    }
}

// $Id: sieve.java,v 1.8 2001/05/06 04:37:45 doug Exp $
// http://www.bagley.org/~doug/shootout/

public class sieve {
    public static void main(String args[]) {
    int NUM = Integer.parseInt(args[0]);
    boolean [] flags = new boolean[8192 + 1];
    int count = 0;
    while (NUM-- > 0) {
        count = 0;
        for (int i=2; i <= 8192; i++) {
        flags[i] = true;
        }
        for (int i=2; i <= 8192; i++) {
        if (flags[i]) {
            // remove all multiples of prime: i
            for (int k=i+i; k <= 8192; k+=i) {
            flags[k] = false;
            }
            count++;
        }
        }
    }  
    System.out.print("Count: " + count + "\n");
    }
}

// $Id: spellcheck.java,v 1.2 2000/12/20 14:29:31 doug Exp $
// http://www.bagley.org/~doug/shootout/

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

public class spellcheck {
    public static void main(String args[]) throws IOException {
    int n = Integer.parseInt(args[0]);
    HashMap dict = new HashMap();
    String word;

    try {
        BufferedReader in = new BufferedReader(new FileReader("Usr.Dict.Words"));
        while ((word = in.readLine()) != null) {
        dict.put(word, new Integer(1));
        }
        in.close();
        } catch (IOException e) {
            System.err.println(e);
            return;
        }
    
    try {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        while ((word = in.readLine()) != null) {
        if (!dict.containsKey(word)) {
            System.out.println(word);
        }
        }
        } catch (IOException e) {
            System.err.println(e);
            return;
        }
    }
}

// $Id: moments.java,v 1.2 2001/01/05 01:35:56 doug Exp $
// http://www.bagley.org/~doug/shootout/

import java.io.*;
import java.util.*;
import java.text.*;
import java.lang.Math;

public class moments {
    public static void main(String[] args) {
    String line;
    Vector nums = new Vector();
    double num, sum = 0.0;
    double mean = 0.0;
    double average_deviation = 0.0;
    double standard_deviation = 0.0;
    double variance = 0.0;
    double skew = 0.0;
    double kurtosis = 0.0;
    double median = 0.0;
    double deviation = 0.0;
    int i, n, mid = 0;

        try {
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            while ((line = in.readLine()) != null) {
        num = Double.parseDouble(line);
        sum += num;
        nums.add(new Double(num));
            }
        } catch (IOException e) {
            System.err.println(e);
            return;
        }

    n = nums.size();
    mean = sum/n;
    for (i=0; i<n; i++) {
        deviation = ((Double)nums.get(i)).doubleValue() - mean;
        average_deviation += Math.abs(deviation);
        variance += Math.pow(deviation,2);
        skew += Math.pow(deviation,3);
        kurtosis += Math.pow(deviation,4);
    }
    average_deviation /= n;
    variance /= (n - 1);
    standard_deviation = Math.sqrt(variance);
    if (variance != 0.0) {
        skew /= (n * variance * standard_deviation);
        kurtosis = kurtosis/(n * variance * variance) - 3.0;
    }
    
    Collections.sort(nums);

    mid = (n/2);
    median = (n % 2 != 0) ?
        ((Double)nums.get(mid)).doubleValue() :
        (((Double)nums.get(mid)).doubleValue() +
         ((Double)nums.get(mid-1)).doubleValue())/2;
    
    NumberFormat nf = NumberFormat.getInstance();
    nf.setMaximumFractionDigits(13);
    nf.setGroupingUsed(false);
    nf.setMaximumFractionDigits(6);
    nf.setMinimumFractionDigits(6);

    System.out.println("n:                  " + n);
    System.out.println("median:             " + nf.format(median));
    System.out.println("mean:               " + nf.format(mean));
    System.out.println("average_deviation:  " + nf.format(average_deviation));
    System.out.println("standard_deviation: " + nf.format(standard_deviation));
    System.out.println("variance:           " + nf.format(variance));
    System.out.println("skew:               " + nf.format(skew));
    System.out.println("kurtosis:           " + nf.format(kurtosis));
    }
}

// $Id: strcat.java,v 1.6 2001/06/28 15:36:52 doug Exp $
// http://www.bagley.org/~doug/shootout/
// Pelle Nilsson suggested we also illustrate StringBuffer
// since it is the preferred method for concatenating 
// strings in Java

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

public class strcat {
    public static void main(String args[]) throws IOException {
    int n = Integer.parseInt(args[0]);
    String hello = "hello\n";
    StringBuffer stringBuffer = new StringBuffer(32);

        for (int i=0; i<n; i++) {
            stringBuffer.append(hello);
    }

        System.out.println(stringBuffer.toString().length());
    }
}

// $Id: sumcol.java,v 1.2 2000/10/07 08:41:44 doug Exp $
// http://www.bagley.org/~doug/shootout/

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

public class sumcol {
    public static void main(String[] args) {
    int sum = 0;
    String line;
        try {
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            while ((line = in.readLine()) != null) {
        sum = sum + Integer.parseInt(line);
            }
        } catch (IOException e) {
            System.err.println(e);
            return;
        }
    System.out.println(Integer.toString(sum));
    }
}

// $Id: wordfreq.java,v 1.3 2000/12/17 21:40:53 doug Exp $
// http://www.bagley.org/~doug/shootout/
// Collection class code is from my friend Phil Chu, Thanks Phil!

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

class Counter {
    int count = 1; 
}

public class wordfreq {

    public static void main(String[] args) {
    wf();
    }

    public static String padleft(String s,int n,char c) {
        int len = s.length();
        if( len>=n ) return s;
        char[] buf = new char[n];
        for( int i=0;i<n-len;i++ ) buf[i]=c;
        s.getChars(0,len,buf,n-len);
        return new String(buf);
    }
  
    public static void wf() {
        HashMap map = new HashMap();
        try {
            Reader r = new BufferedReader(new InputStreamReader(System.in));
            StreamTokenizer st = new StreamTokenizer(r);
            st.lowerCaseMode(true);
            st.whitespaceChars( 0, 64 );
            st.wordChars(65, 90);
            st.whitespaceChars( 91, 96 );
            st.wordChars(97, 122);
            st.whitespaceChars( 123, 255 );
            int tt = st.nextToken();
            while (tt != StreamTokenizer.TT_EOF) {
                if (tt == StreamTokenizer.TT_WORD) {
                    if (map.containsKey(st.sval)) {
                        ((Counter)map.get(st.sval)).count++;
                    } else {
                        map.put(st.sval, new Counter());
                    }
                }
                tt = st.nextToken();
            }
        } catch (IOException e) {
            System.err.println(e);
            return;
        }

        Collection entries = map.entrySet();
    // flatten the entries set into a vector for sorting
    Vector rev_wf = new Vector(entries); 

        // Sort the vector according to its value
        Collections.sort(rev_wf, new Comparator() {
        public int compare(Object o1, Object o2) {
            // First sort by frequency
            int c = ((Counter)((Map.Entry)o2).getValue()).count - ((Counter)((Map.Entry)o1).getValue()).count;
            if (c == 0) { // Second sort by lexicographical order
            c = ((String)((Map.Entry)o2).getKey()).compareTo((String)((Map.Entry)o1).getKey());
            }
            return c;
        }
        }
             );

        Iterator it = rev_wf.iterator();
    Map.Entry ent;
    String word;
    int count;
        while(it.hasNext()) {
            ent = (Map.Entry)it.next();
        word = ((String)ent.getKey());
        count = ((Counter)ent.getValue()).count;
        System.out.println(padleft(Integer.toString(count),7,' ') + "\t" + word);
        }
    }
}