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 figure1, figure2 , figure3 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 space-separated parameters id1, r1, c1, id2, r2, c2, id3, r3 and c3. Integers {id1, id2, id3} is the permutation of {1, 2, 3} and denote the order in which you will put these three figures. Integer ri denotes the number of the row of the lowest block of idith figure after you put it and ci denotes the number of the column of the leftmost block of idith 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 r1 c1 -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 ≤ figurei ≤ 19
- Total amount of steps of the game does not exceed 5 * 104 

-----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 x2 + y2 + 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 re-judged 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 * 104. 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: idi ∉ {1, 2, 3},  {id1, id2, id3} is not the permutation of {1, 2, 3}, r ∉ [1..10] or c ∉ [1..10].
- If you passed all 5 * 104 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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '\nimport fileinput\nimport sys\nfrom collections import Counter\nfrom math import sqrt\n\ndef get_input():\n    return [line for line in fileinput.input()]\n\nclass NewGame2:\n    N = 10\n    map = [[0 for i2 in range(0, N)] for j2 in range(0, N)]\n    score = 0\n    moves = 0\n    debug = False\n\n    def __init__(self):\n        pass\n\n    def play(self, pieces):\n        clear = False\n        clear = True\n        if self.moves > 3:\n            return \'-1 -1 -1 -1 -1 -1 -1 -1 -1\'\n\n        res = self.getMoves(pieces)\n\n        placed = 0\n\n        gameOver = False\n        for i in range(0, len(res)):\n            if res[i] == -1:\n                gameOver = True\n\n        if not gameOver:\n            clearRows = 0\n            clearColumns = 0\n\n            for i in range(0, len(res), 3):\n                p = self.defi[pieces[res[i]-1]]\n                posy = res[i+1] - len(p)\n                posx = res[i+2] - 1\n\n                for py in range(0, len(p)):\n                    for px in range(0, len(p[0])):\n                        if p[py][px] > 0:\n                            self.map[posy+py][posx+px] = pieces[res[i]-1] +1;\n                            placed += 1\n\n                # clear\n                rows = [False for i in range(0, self.N)]\n                columns = [False for i in range(0, self.N)]\n\n                for y in range(0, self.N):\n                    fill = 0\n                    for x in range(0, self.N):\n                        if self.map[y][x] > 0:\n                            fill += 1\n                    if fill == self.N:\n                        rows[y] = True\n                        clearRows += 1\n\n                for x in range(0, self.N):\n                    fill = 0\n                    for y in range(0, self.N):\n                        if self.map[y][x] > 0:\n                            fill += 1\n                    if fill == self.N:\n                        columns[y] = True\n                        clearColumns += 1\n\n                for y in range(0, self.N):\n                    for x in range(0, self.N):\n                        if (rows[y] or columns[x]) and clear:\n                            self.map[y][x] = 0\n\n            size = 0\n            for y in range(0, self.N):\n                for x in range(0, self.N):\n                    if self.map[y][x] > 0:\n                        size += 1\n\n            if size == 0:\n                self.score += 500\n\n            self.score += placed\n            self.score += clearColumns * clearColumns + clearRows * clearRows + (5 * clearRows * clearColumns)\n            self.moves += 1\n\n        output = "";\n        for i in range(0, len(res)):\n            if (i > 0):\n                output += " "\n\n            output += str(res[i])\n\n        return output\n\n    def getMoves(self, pieces):\n        res = [-1 for i in range(0, 9)]\n        tMap = [[0 for i2 in range(0, self.N)] for j2 in range(0, self.N)]\n\n        for y in range(0, self.N):\n            for x in range(0, self.N):\n                tMap[y][x] = self.map[y][x]\n\n        for i in range(0, len(pieces)):\n            p = self.defi[pieces[i]]\n\n            found_move = False\n            for y in range(0, self.N):\n                for x in range(0, self.N):\n                    if not found_move:\n                        valid = True\n                        for py in range(0, len(p)):\n                            for px in range(0, len(p[0])):\n                                if valid and (y+py >= self.N or x+px >= self.N or (p[py][px] > 0 and tMap[y+py][x+px] != 0)):\n                                    valid = False\n                                    break\n                        if (valid):\n                            for py in range(0, len(p)):\n                                for px in range(0, len(p[0])):\n                                    if (p[py][px] > 0):\n                                        tMap[y+py][x+px] = pieces[i] +1\n\n                            res[i*3 + 0] = i+1\n                            res[i*3 + 1] = y+len(p)\n                            res[i*3 + 2] = x+1\n                            found_move = True\n                            break\n\n        return res\n\n    defi = [\n        [\n            [1],\n        ],\n        [\n            [1],\n            [1],\n        ],\n        [\n            [1, 1],\n        ],\n        [\n            [1],\n            [1],\n            [1],\n        ],\n        [\n            [1, 1, 1],\n        ],\n        [\n            [1],\n            [1],\n            [1],\n            [1],\n        ],\n        [\n            [1, 1, 1, 1],\n        ],\n        [\n            [1],\n            [1],\n            [1],\n            [1],\n            [1],\n        ],\n        [\n            [1, 1, 1, 1, 1],\n        ],\n        [\n            [1, 1],\n            [1, 1],\n        ],\n        [\n            [1, 1, 1],\n            [1, 1, 1],\n            [1, 1, 1],\n        ],\n        [\n            [1, 1, 1],\n            [0, 0, 1],\n            [0, 0, 1],\n        ],\n        [\n            [0, 0, 1],\n            [0, 0, 1],\n            [1, 1, 1],\n        ],\n        [\n            [1, 0, 0],\n            [1, 0, 0],\n            [1, 1, 1],\n        ],\n        [\n            [1, 1, 1],\n            [1, 0, 0],\n            [1, 0, 0],\n        ],\n        [\n            [1, 1],\n            [1, 0],\n        ],\n        [\n            [1, 1],\n            [0, 1],\n        ],\n        [\n            [0, 1],\n            [1, 1],\n        ],\n        [\n            [1, 0],\n            [1, 1],\n        ],\n    ]\n\n\nclass JUNE16:\n    def __init__(self):\n        self.CHNWGM()\n\n    def CHNWGM(self):\n        game = NewGame2()\n        while True:\n            a = [int(x)-1 for x in input().split()]\n            if a[0] < 0 or a[1] < 0 or a[2] < 0:\n                return\n            print(game.play(a))\n\n            sys.stdout.flush()\n            sys.stdin.flush()\n\n\ndef __starting_point():\n    JUNE16()\n\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: