Yet Another Stone Game

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

요약
N개의 돌더미와 K가 주어질 때, 각 차례에 돌이 남은 더미를 최대 K개 골라 돌을 하나씩 가져가며, 선공이 이기는지 후공이 이기는지 판정합니다.
난이도

어려움10점 중 8점

유형
게임 이론, 그리디, 정렬, 조합론
정답자
아직 제출이 없습니다

문제

NN개의 돌더미가 있으며 ii번째 돌더미에는 a_ia\_i개의 돌이 있다. 또한 정수 KK가 주어지며 선공과 후공은 번갈아 가며 다음을 반복한다.

  • 돌이 남아 있는 돌더미 중 최대 KK개를 골라 돌을 11개씩 가져온다. 단, 적어도 하나의 돌더미를 골라야 한다.

자신의 차례에 위 시행을 할 수 없게 되는 쪽이 지게 되고, 상대방이 이기게 된다. 선공이 이길지 후공이 이길지 구해 보자.

입력

첫째 줄에 테스트 케이스의 개수를 나타내는 정수 TT가 주어진다. (1≤T≤100 000)(1\leq T \leq 100\ 000)

각 테스트 케이스의 첫째 줄에 두 정수 NN, KK가 공백으로 구분되어 주어진다. (3≤N≤300 000;N−2≤K≤N)(3 \leq N \leq 300\ 000; N-2 \leq K \leq N)

각 테스트 케이스의 둘째 줄에 NN개의 정수 a_1a\_1, a_2a\_2, ⋯\cdots, a_Na\_N가 공백으로 구분되어 주어진다. (1≤a_i≤109)(1 \leq a\_i \leq 10^9)

모든 테스트 케이스에서 NN의 합은 300 000300\ 000을 넘지 않는다.

출력

각 테스트 케이스 마다 선공이 이긴다면 First, 후공이 이긴다면 Second를 출력한다.

예제1

  1. 예제 1

    입력
    2
    3 1
    1 1 2
    3 3
    1 1 2
    
    예상 출력
    Second
    First