\(N\)개의 돌무더기가 있다. 한 번의 차례에 한 무더기를 골라 정해진 이동 집합 \(S\)에 속하는 개수만큼만 돌을 가져갈 수 있다(\(S\)의 각 원소 \(s\)에 대해 정확히 \(s\)개를 가져갈 수 있고, 가져간 뒤 남는 돌이 음수가 되면 안 된다). 더 이상 어떤 무더기에서도 합법적으로 가져갈 수 없는 사람이 진다.

선공이 이기면 선공, 후공이 이기면 후공을 출력하라. (Sprague–Grundy: 각 무더기의 그런디 수를 구한 뒤 XOR한다.)

\(1 \le N \le 100{,}000\)
\(1 \le K \le 50\), \(1 \le s_i \le 50\)
\(1 \le a_i \le 100{,}000\)

첫 줄에 무더기 수 \(N\).
둘째 줄에 이동 집합 크기 \(K\).
셋째 줄에 이동 집합 \(s_1, \dots, s_K\).
넷째 줄에 \(a_1, \dots, a_N\).

선공 또는 후공을 출력한다.

riseoj 작성

출처 Original