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

class InNode
{
	public InNode(InNode p, InNode c1, InNode c2, int n, int c, int w)
	{
		child = new InNode[2];
		parent = p;
		child[0] = c1;
		child[1] = c2;
		value = n;
		count = c;
		which = w;
	}

	public InNode parent;
	public InNode child[];
	public int value;
	public int count;
	public int which;
}

public class HuffmanInputStream extends FilterInputStream
{
	private InNode ZeroNode;
	private InNode RootNode;
	private InNode EscapeNode;
	private BitInputStream BitIn;
	private int bits;

	private InNode addnode()
	{
		ZeroNode.child[0] = new InNode(ZeroNode,  null, null, 0, 1, 0);
		InNode n = new InNode(ZeroNode, null, null, 0, 0, 1);
		ZeroNode.child[1] = n;
		ZeroNode.count = 1;
		ZeroNode = ZeroNode.child[0];
		return n;
	}

	private void swap(InNode a, InNode b)
	{
		a.parent.child[a.which] = b;
		b.parent.child[b.which] = a;
		
		InNode tn = a.parent;
		a.parent = b.parent;
		b.parent = tn;

		int t = a.which;
		a.which = b.which;
		b.which = t;
	}

	private void update(InNode n)
	{
		while(n != null)
		{
			n.count++;
			if((n.parent != null) && (n.parent.parent != null))
			{
				InNode uncle = n.parent.parent.child[n.parent.which ^ 1];
				if(n.count > uncle.count)
				{
					swap(n, uncle);
				}
			}
			n = n.parent;
		}
	}

	public int readEscape(int bits) throws IOException
	{
		return BitIn.read(bits);
	}

	public int readInt() throws IOException
	{
		InNode n = RootNode;
		int rv;
		while(n.child[0] != null)
		{
			n = n.child[BitIn.readBit()];
		}
		if(n == ZeroNode)
		{
			rv = BitIn.read(bits);
			n = addnode();
			n.value = rv;
		}
		else
		{
			rv = n.value;
		}
		n.count++;
		update(n.parent);
		return rv;
	}
	
	public HuffmanInputStream(InputStream _in, int b) throws IOException
	{
		super(_in);
		bits = b;
		BitIn = new BitInputStream(in);
		RootNode = new InNode(null, null, null, 0, 2, 0);
		ZeroNode = new InNode(RootNode, null, null, 0, 1, 0);
		EscapeNode = new InNode(RootNode, null, null, -1, 1, 1);
		RootNode.child[0] = ZeroNode;
		RootNode.child[1] = EscapeNode;
	}
}