1252. Grundy Number and Sprague-Grundy Theorem

In a subtraction game, a pile of n stones allows a move that removes exactly m stones for any m in the given moves set. Compute the Grundy number of the pile of size n, defined recursively as the smallest non-negative integer not among the Grundy numbers of the reachable positions. The input is JSON {n, moves}.

Input: JSON {n, moves}.

Output: Integer — the Grundy number of the position.

Examples

Input: {"n":5,"moves":[1,2,3]}
Output: 1
Explanation: Grundy values cycle with period 4.

Input: {"n":4,"moves":[1,2]}
Output: 1
Explanation: Period-3 cycle.

Input: {"n":0,"moves":[1]}
Output: 0
Explanation: No moves available.

Constraints

• 0<=n<=10^4
• 1<=|moves|<=10

Asked by