Chef has bought ten balls of five colours. There are two balls of each colour. Balls of same colour have same weight. Let us enumerate colours by numbers from 1 to 5. Chef knows that all balls, except two (of same colour), weigh exactly one kilogram. He also knows that each of these two balls is exactly 1 kg heavier than other balls.

You need to find the colour which balls are heavier than others. 
To do that, you can use mechanical scales with two weighing pans. As your scales are very accurate, you can know the exact difference of weights of objects from first and second pans. Formally, the scales will give you the difference (signed difference) of weights of the objects put into the first pan and the second pan. See the following examples for details.

- If you put two balls of the same colour on your scales, each ball to one pan, the scales will tell you that difference is "0".
- But if you put into the first pan some balls of total weight 3 kg, and into the second pan of 5 kg, then scales will tell you "-2" because the second pan is 2 kg heavier than first. 
- Similarly, if you put 5 kg weight in first pan and 3 kg in the second pan, then scale will tell you "2" as first pan is 2 kg heavier than second.

-----Input & Output-----
- The interaction process have two phases. At first phase you perform sequence of weighings on the mechanical scales. At the second phase you should output the colour of the heavier balls.
- To use the mechanical scales, you should print "1"(without quotes) and then print two lines, the first line will describe the enumeration of colours of balls on the first pan and second line should that of second pan.
- To describe some pan, you need to print one integer n - the number of balls you put in this pan, followed by n space-separated integers - colours of the balls you put in this pan. 
- Once you have printed required data, you can read from the standard input one integer - the difference of weights of the first and the second pans.
- To output the colour of the heavier balls, you should print "2"(without quotes) and one integer in next line - colour of the heavier balls. 

-----Constraints-----
- Each colour you print should be between 1 and 5.
- In each weighings, you can use at most two balls of same colour.
- Note that you can use scales as much times as you want (even zero).
- Once your program printed the colour of the heavier balls, it should finish its work, i.e. you should exit the program. 
- Do not forget to flush standard output after each line you print.

-----Subtasks-----
- If you output incorrect colour (i.e. colour you printed is not that of heavier balls), your score will be zero.
- Let K will be the number of times you used scales.
- Then your score will be 100/K points.
- Please note that if K equals to zero, your score also will also be 100 points.

-----Example 1-----

Please note that the content in left side denotes output of your program where content in the right side denotes the response of judge which you should read as input. 

Input and Output
1
1 1
1 1	
					0
1
1 1
1 5
					-1
2
5

-----Example 2-----
Input and Output
1
3 1 2 5
0
					4
1
0
1 2
					-1
1
0
1 5
					-2
2
5

-----Explanation-----
In the first example, you first printed :

1
1 1
1 1

This means that you want to use the scale. Each of the first and second pan has one ball of colour 1.
Don't forget to flush the standard output after printing this.

After that you should read the input, the difference of weights between the two pans, in this case, it will be 0. 

Now you printed : 

1
1 1
1 5

It means, that you decided to use scale again. Now first pan contains one ball of colour 1 and the second pan contains one ball of colour 5.

Now, you should read the input, the difference of weights between the two pans, in this case, it will be -1.

Now, you realize that ball of colour 5 is heavier than of colour 1. It means that 5th colour is the colour of heaviest ball. So your print 2 followed by 5 in separate lines and exit your program.

You have used scale total 2 times. Hence your score will be 100/2 = 50.

In the second example, your score will be 100 / 3 = 33.3333333

-----Notes-----

Please note that clearing the output buffer can be done by using fflush(stdout) command or by setting the proper type of buffering at the beginning of the execution - setlinebuf(stdout). Failure to flush the output buffer will result in Time Limit Exceeded verdict.

There are 5 test files. For each of the test file, score you will get is described above. The total sum of scores of your program for all the test files will be displayed on the contest page. This will be considered your final score for the problem. 

Total points awarded for this problem will be equal to (your score) / (best score achieved in the contest) * 100.

Difficulty: interview

Starter code:

Solutions:
import sys

print(1)
print("3 1 1 2")
print("3 3 3 4")
sys.stdout.flush()

d = int(input())
if d==0:
    print(2)
    print(5)
    sys.stdout.flush()
    
elif d==2:
    print(2)
    print(1)
    sys.stdout.flush()
    
elif d==1:
    print(2)
    print(2)
    sys.stdout.flush()
    
elif d==-2:
    print(2)
    print(3)
    sys.stdout.flush()
else:
    print(2)
    print(4)            
    sys.stdout.flush()

import os
from sys import *

print('1')
stdout.flush()
print('4 1 2 2 3')
stdout.flush()
print('4 3 4 4 5')
stdout.flush()
w = int(stdin.readline())
if w == -2:
	print('2')
	stdout.flush()
	print('4')
	stdout.flush()
elif w == -1:
	print('2')
	stdout.flush()
	print('5')
	stdout.flush()
elif w == 0:
	print('2')
	stdout.flush()
	print('3')
	stdout.flush()
elif w == 1:
	print('2')
	stdout.flush()
	print('1')
	stdout.flush()
elif w == 2:
	print('2')
	stdout.flush()
	print('2')
	stdout.flush()
	



# step 1
import sys
import random
balls = list(map(str, list(range(1, 6))))
answered = 1

print('1')
mid = len(balls) / 2
print('3 1 2 2')
print('3 3 3 4')
sys.stdout.flush()
ans = int(input().strip())

if ans == 0:
	# lucky!
	print('2')
	print('5')
	sys.stdout.flush()
if ans == 2:
	print('2')
	print('2')
	sys.stdout.flush()
if ans == 1:
	print('2')
	print('1')
if ans == -1:
	print('2')
	print('4')
if ans == -2:
	print('2')
	print('3')

import sys
print("1")
print("4 1 2 3 3")
print("4 1 4 5 5")
sys.stdout.flush()
d = {0:1,
     1:2,
     2:3,
     -1:4,
     -2:5
     }
v = eval(input())
print("2")
sys.stdout.flush()
print(d[v])

print("1")
print("3 1 2 2")
print("3 3 4 4")
import sys 
d = {1:1,
     2:2,
     -1:3,
     -2:4,
     0:5
     }
sys.stdout.flush()
v = eval(input())
print("2")
print(d[v])

import sys
print(1)
print(4,1,2,2,3)
print(4,1,4,4,5)
sys.stdout.flush()
a=int(input())
if (a==0):
    print(2)
    print(1)
elif (a==2):
    print(2)
    print(2)
elif (a==-2):
    print(2)
    print(4)
elif (a==1):
    print(2)
    print(3)
else:
    print(2)
    print(5)
    


import sys

x = 1
y = 2

print(x)
print("3 1 1 2")
print("3 3 3 4")

sys.stdout.flush()

weight = eval(input())


if(weight == 0):
	print(y)
	print("5")
	sys.stdout.flush()

elif(weight == 2):
	print(y)
	print("1")
	sys.stdout.flush()

elif(weight == 1):
	print(y)
	print("2")
	sys.stdout.flush()

elif(weight == -1):
	print(y)
	print("4")
	sys.stdout.flush()

elif(weight == -2):
	print(y)
	print("3")
	sys.stdout.flush()

import sys
print(1)
print(1,1)
print(1,2)
sys.stdout.flush()
a=int(input())
if (a==1):
    print(2)
    print(1)
    sys.exit()
elif (a==-1):
    print(2)
    print(2)
    sys.exit()
print(1)
print(1,3)
print(1,4)
sys.stdout.flush()
b=int(input())
if (b==1):
    print(2)
    print(3)
elif (b==-1):
    print(2)
    print(4)
else:
    print(2)
    print(5)
    


import sys


print("1")
print("3 1 1 2")
print("3 3 3 4")
sys.stdout.flush()
wt=eval(input())

if(wt==0):
	print("2")
	sys.stdout.flush()
	print("5")
	sys.stdout.flush()

elif(wt<0):
	if wt==-1:
		print("2")
		sys.stdout.flush()
		print("4")
		sys.stdout.flush()
	elif wt==-2:
		print("2")
		sys.stdout.flush()
		print("3")
		sys.stdout.flush()

elif(wt>0):
	if wt==1:
		print("2")
		sys.stdout.flush()
		print("2")
		sys.stdout.flush()
	elif wt==2:
		print("2")
		sys.stdout.flush()
		print("1")
		sys.stdout.flush()

import sys
 
ans = 1
print(1)
sys.stdout.flush()
print(3, 1, 2, 2)
sys.stdout.flush()
print(3, 3, 4, 4)
sys.stdout.flush()
result = int(input())
if result == 1:
	ans = 1
elif result == 2:
	ans = 2
elif result == 0:
	ans = 5
elif result == -1:
	ans = 3
elif result == -2 :
	ans = 4
print(2)
sys.stdout.flush()
print(ans)
sys.stdout.flush() 

import sys
 
ans = 1
print(1)
sys.stdout.flush()
print(4, 1, 4, 2, 2)
sys.stdout.flush()
print(2, 3, 4)
sys.stdout.flush()
result = int(input())
if result == 1:
	ans = 3
elif result == 3:
	ans = 1
elif result == 4:
	ans = 2
elif result == 2:
	print(1)
	sys.stdout.flush()
	print(1, 4)
	sys.stdout.flush()
	print(1, 5)
	sys.stdout.flush()
	r1 = int(input())
	if r1 == -1:
		ans = 5
	elif r1 == 1:
		ans = 4
print(2)
sys.stdout.flush()
print(ans)
sys.stdout.flush() 

import sys
print('1')
sys.stdout.flush()
print('3 1 2 2')
sys.stdout.flush()
print('3 3 4 4')
sys.stdout.flush()
d = int(input())
if d == 2:
    print('2')
    sys.stdout.flush()
    print('2')
    sys.stdout.flush()
elif d == 1:
    print('2')
    sys.stdout.flush()
    print('1')
    sys.stdout.flush()
elif d == -1:
    print('2')
    sys.stdout.flush()
    print('3')
    sys.stdout.flush()
elif d == -2:
    print('2')
    sys.stdout.flush()
    print('4')
    sys.stdout.flush()
else:
    print('2')
    sys.stdout.flush()
    print('5')
    sys.stdout.flush()


import sys
print('1')
sys.stdout.flush()
print('3 1 2 2')
sys.stdout.flush()
print('3 3 4 4')
sys.stdout.flush()
d = int(input())
if d == 2:
    print('2')
    sys.stdout.flush()
    print('2')
    sys.stdout.flush()
elif d == 1:
    print('2')
    sys.stdout.flush()
    print('1')
    sys.stdout.flush()
elif d == -1:
    print('2')
    sys.stdout.flush()
    print('3')
    sys.stdout.flush()
elif d == 1:
    print('2')
    sys.stdout.flush()
    print('4')
    sys.stdout.flush()
else:
    print('2')
    sys.stdout.flush()
    print('5')
    sys.stdout.flush()


import random
n = random.randint(1,5)

d= dict()
d = { 1 : 1, 2:1, 3:1, 4:1, 5:1 }
d[n]=2

import sys

print(1)
sys.stdout.flush()
print('5 1 1 2 2 3')
sys.stdout.flush()
print('5 3 4 4 5 5') 

sum1= 2*(d[1]+d[2]) + d[3]
sum2= 2*(d[4]+d[5]) + d[3]

sys.stdout.flush()

if sum1==sum2:
    print(2)
    sys.stdout.flush()
    print(3)
    sys.exit()
elif sum1<sum2:
    print(1)
    sys.stdout.flush()
    print('1 4')
    sys.stdout.flush()
    print('1 5')
    
    sys.stdout.flush()
    
    if d[4]<d[5]:
        print(2)
        sys.stdout.flush()
        print(5)
        sys.exit()
    else:
        print(2)
        sys.stdout.flush()
        print(4)
        sys.exit()
else:
    print(1)
    sys.stdout.flush()
    print('1 1')
    sys.stdout.flush()
    print('1 2')
    
    sys.stdout.flush()
    
    if d[1]<d[2]:
        print(2)
        sys.stdout.flush()
        print(2)
        sys.exit()
    else:
        print(2)
        sys.stdout.flush()
        print(1)
        sys.exit()

# your code goes here
import sys
d = {0: 3, 1: 4, 2: 1, -1: 5, -2: 2}
print("1")
print("4 1 1 3 4")
print("4 2 2 3 5")
sys.stdout.flush()
ans = int(input())
print("2")
print(d[ans])