아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

체스판 위의 게임

시간 제한1초메모리 제한128 MB

요약
M x N 판 위의 (p, q)-리퍼 K개로 이루어진 게임에서 두 사람이 최적으로 둘 때 승자를 판정한다.
난이도

보통10점 중 7점

유형
게임 이론, 수학
정답자
아직 제출이 없습니다

문제

M×NM \times N 크기의 체스판이 있다. 이 판 위에 (p,q)(p, q)-도약말(단, p<qp < q)이라 불리는 요정 체스 말 KK개가 놓여 있다. 칸은 (행, 열)로 나타내며, 행은 위에서 아래로 11부터 MM까지, 열은 왼쪽에서 오른쪽으로 11부터 NN까지 번호를 매긴다. 여러 말이 같은 칸에 함께 있을 수 있다.

(r,c)(r, c) 칸에 있는 (p,q)(p, q)-도약말은 판 안에 있는 다음 네 칸 중 하나로 이동할 수 있다.

  • (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)

즉 한 번의 이동에서 말은 한 축으로 pp칸, 다른 축으로 qq칸을 움직이며, 길이가 qq인 쪽의 이동은 항상 좌표가 작아지는 방향(행은 위쪽, 열은 왼쪽)을 향한다. 판을 벗어나는 이동은 할 수 없다.

두 사람이 번갈아 이동한다. 자기 차례에 한 명은 말 하나를 골라 위 규칙대로 움직인다. 자기 차례에 어떤 말도 움직일 수 없는 사람이 진다. 두 사람이 모두 최적으로 둔다고 할 때 누가 이기는지 구하라.

입력

첫째 줄에 다섯 정수 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).

다음 KK개의 줄에는 각각 두 정수 rir_i와 cic_i가 주어지며, 이는 ii번째 도약말의 위치이다 (1≤ri≤M1 \le r_i \le M, 1≤ci≤N1 \le c_i \le N).

출력

최적으로 두었을 때 먼저 두는 사람이 이기면 First를, 그렇지 않으면 Second를 출력한다.

예제2

  1. 예제 1

    입력
    10 10 2 1 2
    3 7
    7 3
    
    예상 출력
    Second
    
  2. 예제 2

    입력
    7 5 3 1 3
    2 3
    1 5
    4 3
    
    예상 출력
    First