This page is still under construction.

Parts of this page are still being built. What you see may change.

Game on Chessboard

Time limit1sMemory limit128 MB

Summary
Given K (p,q)-leapers on an M x N board, decide which player wins the disjunctive sum of impartial games.
Level

Medium7 of 10

Topics
Game theory, Math
Solved
No attempts yet

Problem

You are given an M×NM \times N chessboard. On it sit KK fairy chess pieces called (p,q)(p, q)-leapers (with p<qp < q). Squares are addressed by (row, column), with rows numbered 11 to MM from top to bottom and columns numbered 11 to NN from left to right. Several leapers may occupy the same square.

A (p,q)(p, q)-leaper standing on square (r,c)(r, c) can move to any of the following four squares that lie on the board:

  • (r−q, c+p)(r-q,\ c+p)
  • (r−q, c−p)(r-q,\ c-p)
  • (r+p, c−q)(r+p,\ c-q)
  • (r−p, c−q)(r-p,\ c-q)

In each move the piece steps pp squares along one axis and qq squares along the other, and the length-qq step always points toward a smaller coordinate (upward in rows or leftward in columns). A move that would leave the board is forbidden.

Two players move alternately. On a turn, a player selects one leaper and moves it according to the rules above. The player who has no legal move on their turn loses. Assuming both players play optimally, determine who wins.

Input

The first line contains five integers MM, NN, KK, pp, qq (1≤M,N≤1091 \le M, N \le 10^9, 1≤K≤1051 \le K \le 10^5, 1≤p<q≤201 \le p < q \le 20).

Each of the next KK lines contains two integers rir_i and cic_i, the position of the ii-th leaper (1≤ri≤M1 \le r_i \le M, 1≤ci≤N1 \le c_i \le N).

Output

Print First if the player who moves first wins under optimal play, and Second otherwise.

Examples2

  1. Example 1

    Input
    10 10 2 1 2
    3 7
    7 3
    
    Expected output
    Second
    
  2. Example 2

    Input
    7 5 3 1 3
    2 3
    1 5
    4 3
    
    Expected output
    First