// This class implements many of the methods of java.util.Random
// but uses Jurgen Doornik's method to convert bits to doubles.
// It is more than 5 times faster than java.util.Random, despite
// using exactly the generator described in the documentation,
// because it is NOT designed to be shared between threads.
// If you want to share a random generator between threads,
// stick with java.util.Random, or wrap your accesses to this in
//    synchronised (myRandom48) {...}
// blocks.  This is in some ways safer than java.util.Random(),
// where nextLong() and nextDouble() may be interrupted by other
// threads.
// Another advantage of this class is that it provides a useful
// toString() method and a corresponding constructor that takes a string.

import java.lang.*;

public class Random48 implements java.io.Serializable {

    static final long serialVersionUID = 1L;
	// The state is one 64-bit number and nothing else.
	// It will never be anything else.

    private static volatile long counter = 0;
    private long seed;
    private static final long mask = 0xffffffffffffL;

    public Random48() {
	this(System.nanoTime() + counter++);
    }

    public Random48(long seed) {
        this.seed = seed;
    }

    public Random48(String s) {
        if (s.startsWith("Random48_")) s = s.substring(9);
        this.seed = Long.parseLong(s, 16);
    }

    public String toString() {
        return "Random48_" + Long.toString(seed & mask, 16);
    }


    public int nextInt() {
	return (int)(seed = seed * 0x5deece66dL + 11L);
    }

    public int nextInt(int n) {
	long x = (seed = seed * 0x5deece66dL + 11L) & mask;
	return (int)(n * (x * 3.552713678800500929355621337890625e-15));
    }

    public long nextLong() {
        final long a = nextInt() & 0xffffffffL;
        final long b = nextInt();
        return (b << 32) | a;
    }

    public boolean nextBoolean() {
	return nextInt() >= 0;
    }

    public double nextDouble() {
        final int a = nextInt();
        final int b = nextInt() & 0xFFFF;
        return a * 2.3283064365386962890625e-10 +
	       (2.220446049250313080847263336181640625e-16/2.0 + 0.5) +
	       b * 2.220446049250313080847263336181640625e-16;
    }

    public void nextBytes(byte[] bytes) {
	int n = bytes.length - 3;
	int i = 0;
	while (i < n) {
	    int x = nextInt();
	    bytes[i+0] = (byte)x;
	    bytes[i+1] = (byte)(x >>= 8);
	    bytes[i+2] = (byte)(x >>= 8);
	    bytes[i+3] = (byte)(x >> 8);
	    i += 4;
	}
	n += 3;
	if (i < n) {
	    int x = nextInt();
	    while (i < n) {
		bytes[i] = (byte)(x >>= 8);
		i++;
	    }
	}
    }

}