Trò chơi lấy sỏi tổng quát (Generalized Take-Away Game)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Trên bàn có $N$ viên sỏi và một tập hợp

$$A=\{a_1,a_2,\ldots,a_K\}$$

gồm $K$ số nguyên dương đôi một phân biệt.

Hai người chơi luân phiên thực hiện nước đi. Người đi trước thực hiện lượt đầu tiên.

Trong mỗi lượt, người chơi phải chọn một giá trị $a_i\in A$ và lấy đúng $a_i$ viên sỏi, với điều kiện số viên được lấy không vượt quá số viên hiện còn trên bàn.

Nếu đến lượt một người chơi mà không tồn tại nước đi hợp lệ, người đó thua. Do đó, người lấy được viên sỏi cuối cùng sẽ thắng.

Cả hai người đều chơi tối ưu.

Hãy xác định người đi trước có chiến lược bảo đảm chiến thắng hay không.

• Nếu người đi trước thua, hãy in LOSE.
• Nếu người đi trước thắng, hãy in WIN và số viên nhỏ nhất mà người đó có thể lấy ở nước đầu tiên để vẫn bảo đảm chiến thắng.

Input

Dòng đầu chứa hai số nguyên $N$ và $K$.

Dòng thứ hai chứa $K$ số nguyên dương đôi một phân biệt

$$a_1,a_2,\ldots,a_K,$$

biểu diễn các số lượng sỏi được phép lấy trong một lượt.

Thứ tự các giá trị $a_i$ trong dữ liệu vào là tùy ý.

Output

Nếu người đi trước không thể bảo đảm chiến thắng, in:

LOSE

Nếu người đi trước có chiến lược bảo đảm chiến thắng:

• dòng đầu in WIN;
• dòng thứ hai in số viên nhỏ nhất có thể lấy ở nước đầu tiên mà vẫn bảo đảm chiến thắng.

Subtask

• Subtask 1 — 10%: $0\le N\le 22$; $1\le K\le 8$; $1\le a_i\le 10^7$; các $a_i$ đôi một phân biệt. Time Limit : $0.5$ giây.
• Subtask 2 — 15%: $0\le N\le 10^7$; $K=1$; $1\le a_1\le 10^7$. Time Limit : $0.5$ giây.
• Subtask 3 — 15%: $0\le N\le 10^7$; $1\le K\le 50$; $A=\{1,2,\ldots,K\}$. Time Limit : $0.5$ giây.
• Subtask 4 — 25%: $0\le N\le 10^5$; $1\le K\le 50$; $1\le a_i\le 10^7$; các $a_i$ đôi một phân biệt. Time Limit : $1.5$ giây.
• Subtask 5 — 35%: $0\le N\le 10^7$; $1\le K\le 50$; $1\le a_i\le 10^7$; các $a_i$ đôi một phân biệt. Time Limit : $8.0$ giây.

Ví dụ

Ví dụ 1

Input

10 3
1 2 3

Output

WIN
2

Giải thích

Người đi trước có thể lấy $2$ viên, làm số sỏi còn lại bằng $8$.

Từ trạng thái có $8$ viên, dù người đến lượt lấy $1$, $2$ hay $3$ viên thì đối phương vẫn có thể đáp lại để duy trì lợi thế và cuối cùng lấy viên sỏi cuối cùng.

Lấy $1$ viên ở nước đầu tiên không bảo đảm chiến thắng, trong khi lấy $2$ viên thì có. Vì vậy $2$ là nước thắng nhỏ nhất.

Ví dụ 2

Input

12 3
1 2 3

Output

LOSE

Giải thích

Ở lượt đầu tiên, người chơi chỉ có thể lấy $1$, $2$ hoặc $3$ viên, tương ứng để lại $11$, $10$ hoặc $9$ viên.

Trong cả ba trường hợp, người chơi thứ hai đều có thể bảo đảm chiến thắng nếu tiếp tục chơi tối ưu.

Vì không tồn tại nước đi đầu tiên giúp người đi trước bảo đảm chiến thắng, kết quả là LOSE.

Ví dụ 3

Input

7 2
2 5

Output

LOSE

Giải thích

Người đi trước chỉ có hai lựa chọn:

• lấy $2$ viên, còn lại $5$ viên; người chơi thứ hai có thể lấy đúng $5$ viên và thắng;
• lấy $5$ viên, còn lại $2$ viên; người chơi thứ hai có thể lấy đúng $2$ viên và thắng.

Do mọi nước đi hợp lệ đều cho phép người chơi thứ hai lấy hết số sỏi còn lại, người đi trước thua.