I. The Tale of the Fisherman and the Fish
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A fisherman is fishing in the ocean when he encounters a fish in his net. The fish suddenly starts pleading for its freedom. Because the fisherman was feeling a bit generous, he decides to play a game with the fish. The fisherman has some stones, each with some value. After agreeing to some order of stones in a line, the fish and the fisherman take turns taking stones from the left side: the fish takes the first stone, followed by the fisherman taking the second stone, followed by the fish taking the third stone. A player's score at the end is the sum total of values on all the stones they took, and the winner is the player with the larger score (equal value is a tie).

The fisherman already put the stones in some order, but the fish is allowed to rearrange the stones. The fish is not too strong out of the water, so it needs your help! The fish will perform a left cyclic shift on some contiguous subarray of the stones, and then you must answer what the result of the game will be after each query. Note that these updates persist between queries.

A left cyclic shift on some subarray $$$[a_l, a_{l+1}, \dots, a_{r - 1}, a_r]$$$ replaces that subarray with the array $$$[a_{l+1}, \dots, a_{r - 1}, a_r, a_l]$$$ in the original array.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^5$$$) — the number of stones and the number of cyclic shifts performed by the fish, respectively.

The next line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the values of the stones in the original order by the fisherman.

Each of the following $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \lt r \leq n$$$) — the left and right endpoints of the subarray

Output

For each query, output "FISH" (without quotes) if the fish will win, "MAN" (without quote) if the fisherman will win, and "TIE" if they will tie.

Example
Input
4 3
1 2 3 4
1 2
3 4
1 3
Output
TIE
FISH
MAN
Note

After the first query, the stones are ordered $$$[2, 1, 3, 4]$$$. The fish gets a score of $$$2 + 3 = 5$$$ and the fisherman gets a score of $$$1 + 4 = 5$$$, so they tie.

After the second query, the stones are ordered $$$[2, 1, 4, 3]$$$. The fish gets a score of $$$2 + 4 = 6$$$ and the fisherman gets a score of $$$1 + 3 = 4$$$, so the fish wins.

After the third query, the stones are ordered $$$[1, 3, 2, 4]$$$. The fish gets a score of $$$1 + 2 = 3$$$ and the fisherman gets a score of $$$3 + 4 = 7$$$, so the fisherman wins.