GOST 28147-89 is a standard symmetric encryption based on a Feistel network.



The structure of the algorithm consists of three levels:

   encryption modes - simple replacement, application range, imposing a range of feedback and authentication code generation;
   cycles - 32-З, 32-Р and 16-З, is a repetition of the main step;
   main step, a function that takes a 64-bit block of text and one of the eight 32-bit encryption key elements, and uses the replacement table (8x16 matrix of 4-bit values), and returns encrypted block.


Task

Implement the main step of this encryption algorithm.




 
k8 = [	14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7 ] 
k7 = [	15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10 ]
k6 = [	10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8 ]
k5 = [	 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15 ]
k4 = [	 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9 ]
k3 = [	12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11 ]
k2 = [	 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1 ]
k1 = [	13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7 ]
 
k87 = [0] * 256
k65 = [0] * 256
k43 = [0] * 256
k21 = [0] * 256
 
def kboxinit():
	for i in range(256):
		k87[i] = k8[i >> 4] << 4 | k7[i & 15]
		k65[i] = k6[i >> 4] << 4 | k5[i & 15]
		k43[i] = k4[i >> 4] << 4 | k3[i & 15]
		k21[i] = k2[i >> 4] << 4 | k1[i & 15]
 
def f(x):
	x = ( k87[x>>24 & 255] << 24 | k65[x>>16 & 255] << 16 |
	      k43[x>> 8 & 255] <<  8 | k21[x & 255] )
	return x<<11 | x>>(32-11)