D. Dots and Boxes?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Talia and Terra are playing a variant of dots and boxes. Just as in the original version, you are given an $$$n$$$ by $$$m$$$ grid of dots, and Talia and Terra will take turns connecting two cardinally adjacent dots with a segment. In this version, once a region is fully enclosed by a set of segments, all cells that aren't possessed yet in that region are possessed by the person who placed the last segment enclosing the region. Once a cell is possessed, neither player may place any more segments connecting two corners of that cell. Once a player cannot place a segment, they lose the game.

To make the game more interesting, some segments will already be added to the board before the game even begins. It is guaranteed that no set of segments initially on the game board will enclose a region. If Talia makes the first move, and both Talia and Terra play optimally, who will win the game?

Input

The first line of input will consist of two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n, m \leq 500$$$) — the number of rows and columns of the grid of dots.

The following $$$2n-1$$$ lines will each consist of $$$2m-1$$$ characters denoting the initial state of the board. For each $$$i$$$ ($$$1 \leq i \leq n$$$) and $$$j$$$ ($$$1 \leq j \leq m$$$):

  • The character on the $$$2i-1$$$ row and $$$2j-1$$$ column will be a '*', representing a dot.
  • If $$$j \lt m$$$, the character on the $$$2i-1$$$ row and $$$2j$$$ column will be a '-' if there is a segment connecting dots (i, j) and (i, j+1), and '.' otherwise.
  • If $$$i \lt n$$$, the character on the $$$2i$$$ row and $$$2j-1$$$ column will be a '|' if there is a segment connecting dots (i, j) and (i+1, j), and '.' otherwise.
  • If $$$i \lt n$$$ and $$$j \lt m$$$, the character on the $$$2i$$$ row and $$$2j$$$ will be a '.', corresponding to the empty cell.

It is guaranteed that no set of segments initially on the game board will enclose a region.

Output

Output "Talia" (without quotes) if Talia wins the game; otherwise, output "Terra" (without quotes). The output is case sensitive.

Examples
Input
2 3
*.*.*
.....
*.*.*
Output
Talia
Input
5 5
*-*-*-*-*
|.|.....|
*.*-*.*.*
|...|.|.|
*.*-*-*.*
|...|...|
*.*-*.*.*
|.|...|.|
*.*-*-*.*
Output
Terra