A higher resolution is required to access the IDE
- 40
Statement
Goal
In a game of Nim, two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. The goal of the normal game is to be the player to remove the last object.In the Misère Nim variant of the game, the player who takes the last object loses.
Given a list of starting game positions, for each position find all possible moves that will ensure your victory.
Input
Line 1: Two space separated Integers N and K.
N is the number of heaps; it is shared between all of the following positions.
K is number of positions.
Next K Lines: N space separated integers Mi, the number of objects in each heap.
N is the number of heaps; it is shared between all of the following positions.
K is number of positions.
Next K Lines: N space separated integers Mi, the number of objects in each heap.
Output
K lines: Solutions for each board position, in the order they were given.
If the position has no winning moves, its solution is the wordCONCEDE .
If the position has winning moves, its solution is a line of one or more space-separated moves. Each move is a colon-separated pair of integers i: a, where:
- i is the number of the heap to remove objects from: 1 ≤i ≤ N.
- a is the amount of objects to take: 1 ≤ a ≤ Mi.
Moves must be sorted by heap number i first, number of objects a second.
If the position has no winning moves, its solution is the word
If the position has winning moves, its solution is a line of one or more space-separated moves. Each move is a colon-separated pair of integers i
- i is the number of the heap to remove objects from: 1 ≤i ≤ N.
- a is the amount of objects to take: 1 ≤ a ≤ Mi.
Moves must be sorted by heap number i first, number of objects a second.
Constraints
1 ≤ N ≤ 3
1 ≤ Mi ≤ 50
1 ≤ K ≤ 5
The positions are provided in ascending order of initial heap size.
1 ≤ Mi ≤ 50
1 ≤ K ≤ 5
The positions are provided in ascending order of initial heap size.
Example
Input
1 3 5 1 7
Output
1:4 CONCEDE 1:6
A higher resolution is required to access the IDE