CF1511G Chips on a Board

Alice and Bob have a rectangular board consisting of $ n $ rows and $ m $ columns. Each row contains exactly one chip. Alice and Bob play the following game. They choose two integers $ l $ and $ r $ such that $ 1 \le l \le r \le m $ and cut the board in such a way that only the part of it between column $ l $ and column $ r $ (inclusive) remains. So, all columns to the left of column $ l $ and all columns to the right of column $ r $ no longer belong to the board. After cutting the board, they move chips on the remaining part of the board (the part from column $ l $ to column $ r $ ). They make alternating moves, and the player which cannot make a move loses the game. The first move is made by Alice, the second — by Bob, the third — by Alice, and so on. During their move, the player must choose one of the chips from the board and move it any positive number of cells to the left (so, if the chip was in column $ i $ , it can move to any column $ j < i $ , and the chips in the leftmost column cannot be chosen). Alice and Bob have $ q $ pairs of numbers $ L_i $ and $ R_i $ . For each such pair, they want to determine who will be the winner of the game if $ l = L_i $ and $ r = R_i $ . Note that these games should be considered independently (they don't affect the state of the board for the next games), and both Alice and Bob play optimally.

N/A

N/A