Paper Cut Game
Source: aizu

Paper Cut Game
Problem Statement

There is a sheet of paper consisting of a grid with $N$ rows $M$ and columns. Two players participate in a game with this paper.

Each player alternates moves, performing exactly one of the following actions on their turn.

Cut the paper vertically along one of the grid lines to split the paper into two, and keep only the part with more cells. If both parts have the same number of cells, keep only one of them.
Cut the paper horizontally along one of the grid lines to split the paper into two, and keep only the part with more cells. If both parts have the same number of cells, keep only one of them.

The player who is unable to make a move loses, while the other player wins. Given the size of the paper, determine the winner, assuming both players play optimally.

You have $T$ test cases to solve.

Input

The input consists of a multiple test case of the following format.

$T$
$case_1$
$\vdots$
$case_T$


The first line contains an integer $T$ between $1$ and $200,000$, inclusive.

The $(i+1)$-th line corresponds to the $i$-th test case. Each line contains two integers, $N$ and $M$, representing the height and width of the paper, respectively. Both $N$ and $M$ are between $1$ and $10^{18}$, inclusive.

Output

Print $T$ lines. For each test case, the $i$-th line should contain First if the first player wins in the $i$-th test case, and Second otherwise.

Sample Input
5
1 1
1 2
3 3
7 3
999999999999999999 1000000000000000000

Sample Output
Second
First
Second
Second
First


C++ solution:
// AOJ #3640 Paper Cut Game
// 2025.4.19

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)

ll Cin() {
    ll n = 0; int c = gc();
    do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
    return n;
}

void Couts(const string &s) {
    for (char c : s) pc(c);
    pc('\n');
}

ll g(ll x) {
    while (x & 1) {
        if (x == 1) return 0;
        x = (x - 1) >> 1;
    }
    return x >> 1;
}

int main() {
    int T = Cin();
    while (T--) {
        ll n = Cin(), m = Cin();
        ll gn = g(n);
        ll gm = g(m);
        Couts((gn ^ gm)? "First": "Second");
    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanLines)
	scanner.Scan()
	T, _ := strconv.Atoi(scanner.Text())

	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	for i := 0; i < T; i++ {
		scanner.Scan()
		line := scanner.Text()
		parts := strings.Fields(line)
		if len(parts) < 2 {
			continue
		}
		n, _ := strconv.ParseUint(parts[0], 10, 64)
		m, _ := strconv.ParseUint(parts[1], 10, 64)

		gn := grundy(n)
		gm := grundy(m)

		if gn^gm != 0 {
			fmt.Fprintln(writer, "First")
		} else {
			fmt.Fprintln(writer, "Second")
		}
	}
}

func grundy(x uint64) uint64 {
	for x&1 != 0 {
		if x == 1 {
			return 0
		}
		x = (x - 1) >> 1
	}
	return x >> 1
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }

    static long g(long x) {
        while ((x & 1) != 0) {
            if (x == 1) return 0;
            x = (x - 1) >> 1;
        }
        return x >> 1;
    }

    public static void main(String[] args) {
        FastReader reader = new FastReader();
        int T = reader.nextInt();
        StringBuilder output = new StringBuilder();
        while (T-- > 0) {
            long n = reader.nextLong();
            long m = reader.nextLong();
            long gn = g(n);
            long gm = g(m);
            if ((gn ^ gm) != 0) {
                output.append("First\n");
            } else {
                output.append("Second\n");
            }
        }
        System.out.print(output);
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

let inputLines = [];
let currentLine = 0;

rl.on('line', (line) => {
    inputLines.push(line);
});

rl.on('close', () => {
    solve();
});

function solve() {
    const T = parseInt(inputLines[0], 10);
    const results = [];
    
    for (let i = 1; i <= T; i++) {
        const [nStr, mStr] = inputLines[i].split(' ');
        const n = BigInt(nStr);
        const m = BigInt(mStr);
        const gn = computeGrundy(n);
        const gm = computeGrundy(m);
        const xor = gn ^ gm;
        results.push(xor !== 0n ? 'First' : 'Second');
    }
    
    console.log(results.join('\n'));
}

function computeGrundy(x) {
    let xVal = x;
    while (xVal % 2n === 1n) {
        if (xVal === 1n) {
            return 0n;
        }
        xVal = (xVal - 1n) / 2n;
    }
    return xVal / 2n;
}

Python solution:
import sys

def g(x):
    while x & 1:
        if x == 1:
            return 0
        x = (x - 1) >> 1
    return x >> 1

def solve():
    input = sys.stdin
    T = int(input.readline())
    for _ in range(T):
        line = input.readline()
        while line.strip() == '':
            line = input.readline()
        n, m = map(int, line.strip().split())
        gn = g(n)
        gm = g(m)
        if gn ^ gm:
            print("First")
        else:
            print("Second")

solve()

Ruby solution:
def g(x)
  while x & 1 == 1
    return 0 if x == 1
    x = (x - 1) >> 1
  end
  x >> 1
end

def solve
  input = $stdin.read.split
  t = input.shift.to_i
  output = []
  t.times do
    n = input.shift.to_i
    m = input.shift.to_i
    gn = g(n)
    gm = g(m)
    output << ((gn ^ gm) != 0 ? "First" : "Second")
  end
  puts output.join("\n")
end

solve