Subtraction Game Oracle

Difficulty: 1800 6000 ms 128 MB

dp games

A single pile of n stones; a move removes exactly s stones for some s in the allowed set S; last to move wins. For each query n, print the winner.

Input: the first line has |S| and Q; the second line has the set S; each of the next Q lines has a pile size n.

Output: one line per query: FIRST or SECOND.

Constraints:

• 1 ≤ |S| ≤ 10
• 1 ≤ Q ≤ 10⁴
• 0 ≤ n ≤ 10⁴
• 1 ≤ s ≤ 20

Sample Tests

2 3
1 2
0
3
4

SECOND
SECOND
FIRST

1 1
2
5

SECOND

Read the Editorial