MATGAME - Matrix Game

no tags 

Two players, A and B, play the following game.

  1. First, a matrix M of size N*M is chosen, and filled with non-zero numbers.
  2. Player A starts the game and the players play alternately.
  3. In his turn, a player chooses any row which has at least one non zero number in it. In this row, the left-most non zero number is chosen. Let this number be K. The player subtracts any number between 1 and K inclusive from it.
  4. The game ends when all the numbers in the matrix M are 0.
  5. The player who plays last wins the game.

Given N, M and the initial matrix, determine who wins the game. Assume that both players play optimally.

Input

The first line contains the number of test cases T. Each test case consists of 2 numbers N and M. There follow N lines each having M integers. The jth number on the ith line is the number M[i][j]. There is a blank line between consecutive test cases.

Output

Output T lines, one for each case. Output "FIRST" if player A wins, else output "SECOND".

Constraints

T <= 1000

1 <= N, M <= 50

The initial matrix values are between 1 and 50 inclusive.

Example

Input:
3
2 2
1 1
1 1

1 3
2 1 1

2 2
3 2
3 2

Output:
SECOND
FIRST
SECOND

hide comments
tusharjape: 2018-06-11 10:05:20

Has anyone done this without using Sprague Grundy number? I would like to know an alternative approach.

sxie12: 2017-06-25 23:01:39

@luv_misra Second should win
1 2 3 4 -> 0 2 3 4 First takes one
0 2 3 4 -> 0 1 3 4 Second takes one
0 1 3 4 -> 0 0 3 4 First takes one
0 0 3 4 -> 0 0 1 4 Second takes two
0 0 1 4 -> 0 0 0 4 First takes one
0 0 0 4 -> 0 0 0 0 Second takes four and wins

luv_misra: 2017-06-04 18:08:02

1
1 4
1 2 3 4
in this test case SECOND should not win. But SPOJ says SECOND wins. why?

Last edit: 2017-06-04 18:09:41
Md. Najim Ahmed: 2016-03-19 09:16:53

i dont know much game theory but man... i had fun solving it :v and that even in one attempt ...
nice problem :)
Thumbs Up :D

jkelava6: 2015-06-29 13:21:27

: : still coding -_- :: first player will take 2 in his first move. THEN they both take one. First player wins!

: : still coding -_- :: 2015-03-09 08:54:49

in second test case if each player substracts 1 in his/her turn each time...the answer will be second..?

Utkarsh Saxena: 2014-12-30 12:10:33

uff!!.. my first game theory question.. nice :D

Deepak gupta: 2014-04-17 02:08:58

great problem :)

Shwetank sharad: 2013-07-13 19:01:16

someone please post some more test cases

Varun Jalan: 2010-02-07 07:24:35

just that number..not the whole row


Added by:Varun Jalan
Date:2010-01-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own problem used for Codechef Snackdown