struct random
{
    static const LL multiplier = 25214903917LL;
    static const LL addend = 11LL;
    static const LL mask = 281474976710655LL;

    LL seed;

    random()
    {
        seed = 3905348978240129619LL;
    }

    void setSeed(LL newSeed)
    {
        seed = newSeed;
    }

    int nextBits(int bits)
    {
        seed = (seed * multiplier + addend) & mask;
        return int(seed >> (48 - bits));
    }

    int nextInt(int n)
    {
        if ((n & (-n)) == n)
            return int((n * LL(nextBits(31))) >> 31);
        int bits, val;
        do
        {
            bits = nextBits(31);
            val = bits % n;
        }
        while (bits - val + (n - 1) < 0);
        return val;
    }
};