Chef and New Game

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has found a new game and now he wants you to help him to get as much points as possible.
Rules of the game: There are different types of game pieces  geometric shapes composed of some amount of square blocks. In the picture below you can see all the types of figures and enumeration.
The playing field is 10 cells width and 10 cells height. On each step of the game you are given exactly three game pieces. After that you need to put each of them to the game field such that after your move no two figures on the field are overlapped(you cannot rotate figures). If your move results in one or more horizontal or/and vertical lines of 10 units without gaps, those lines disappear. Notice that you put these three figures one by one and if you place the first figure and there are some lines ready to disappear, then they will disappear and only after that you place other figures.
The game ends when you can't put no more figures on the game field.
Input
Each line of input contains three integers figure_{1}, figure_{2} , figure_{3} denoting the type of the figures appeared on this step. If the game has ended  in the next line of input will be "1 1 1".
Interaction with the judge
In each step you should read from the standard input all information about figures that appear in this step. After receiving this input, you should print one line containing nine spaceseparated parameters id_{1}, r_{1}, c_{1}, id_{2}, r_{2}, c_{2}, id_{3}, r_{3} and c_{3}. Integers {id_{1}, id_{2}, id_{3}} is the permutation of {1, 2, 3} and denote the order in which you will put these three figures. Integer r_{i} denotes the number of the row of the lowest block of id_{i}^{th} figure after you put it and c_{i} denotes the number of the column of the leftmost block of id_{i}^{th} figure after you put it. The rows are numbered from 1 to 10 from top to bottom and columns are numbered from 1 to 10 from left to right. Remember to flush the output after every line you print.
To finish the game(if you don't know where to put figures or it's impossible to put some figures) you need to output "1" for figures you don't know where to put. For example, if on some move you don't know how to place all three figures, you need to output nine '1"s as describing of all three figures. But if you can place, for example, only second figure, you need to output next numbers: "2 r_{1} c_{1} 1 1 1 1 1 1". When judge reads "1"s as describing of some figure, it means that the game ends at this step and then judge will output only "1 1 1" as sign of finishing the game.
Constraints
 1 ≤ figure_{i} ≤ 19
 Total amount of steps of the game does not exceed 5 * 10^{4}
Scoring
 For each test case, your score will be the sum of areas(amount of square blocks figure consists) of figures that you correctly place in the playing field. Your goal is to maximise this score.
 Also there are some bonuses: if after your move exactly x row(s) and y column(s) will disappear  your score for this test will be increased by x^{2} + y^{2} + 5 * x *y and by 500 if after your move the field will be empty.
 Your total score for the problem will be the sum of scores on all the test cases.
 Your solution will be tested only on 20% of the test files during the contest and will be rejudged against 100% after the end of competition.
 The game ends when you output "1"s as describing of placing some figure(what means you want to finish the game) or total number of moves reached 5 * 10^{4}. In both cases the judge will output "1 1 1" as a sing of finishing of the game.
 You will get WA verdict if you output incorrect data or some figures overlap. Incorrect data means that there is no way to put this figure at the place you output or you output completely incorrect data: id_{i} ∉ {1, 2, 3}, {id_{1}, id_{2}, id_{3}} is not the permutation of {1, 2, 3}, r ∉ [1..10] or c ∉ [1..10].
 If you passed all 5 * 10^{4} steps of the game, the next line of input will be "1 1 1" and your result will be the score you got.
Test data generation
For each test file the probabilities of appearing each figure are manually chosen.
Example
Input: 8 3 11 6 14 12 5 10 11 5 7 11 16 19 1 1 1 1 Output: 3 6 5 2 2 2 1 10 8 1 4 8 2 6 1 3 7 2 1 5 8 3 4 8 2 6 8 3 9 8 2 10 7 1 1 6 3 10 8 2 8 3 1 1 1
Explanation
In this test case your score will be 74 = 66 (for areas of figures) + 8 (bonus score).
On the fifth move the player decided to finish the game and output three "1"s as the describing of placing the last figure on this move.
Author:  antoniuk1 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/CHNWGM 
Tags  antoniuk1, challenge, june16 
Date Added:  1102015 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 