# Mersenne-Twister algorithm

_array = [0 for i in range (624)]
_index = 0
_bitmask1 = (2 ** 32) - 1
_bitmask2 = 2 ** 31
_bitmask3 = (2 ** 31) - 1

def _fill_array():
	global _array
	for i in range (624):
		y = (_array [i] & _bitmask2) + (_array [(i + 1) % 624] & _bitmask3)
		_array [i] = _array [(i + 397) % 624] ^ (y >> 1)
		if y % 2 != 0:
			_array[i] ^= 2567483615
			
def _random_integer ():
	global _index
	global _array
	if _index == 0:
		_fill_array ()
	y = _array [_index]
	y ^= y >> 11
	y ^= (y << 7) & 2636928640
	y ^= (y << 15) & 4022730752
	y ^= y >> 18

	_index = (_index + 1) % 624
	return y

def seed (x = int (_bitmask3 * Math.random ())):
	global _array
	global _bitmask1
	_array [0] = x
	for i in  range (1, 624):
		_array [i] = ((1812433253 * _array [i - 1]) ^ ((_array [i - 1] >> 30) + i)) & _bitmask1

def randint (a, b):
	return a + _random_integer () % (b - a + 1)

def choice (seq):
	return seq [randint (0, len (seq) - 1)]

def random ():
	return _random_integer () / _bitmask3
	
seed ()
