Bounded Nim

Difficulty: 2100 4000 ms 128 MB

math games

N piles; a move removes between 1 and K stones from ONE pile; last to move wins. Determine the winner under perfect play.

Input: the first line has N and K; the second line has the N pile sizes.

Output: FIRST or SECOND.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ 100
• 0 ≤ piles ≤ 10⁹

Sample Tests

2 2
4 5

FIRST

1 3
3

FIRST

Read the Editorial