Alice and Bob decided to play one ultimate game. They have $$$n$$$ piles, the $$$i$$$-th pile initially contain $$$v_i$$$ chips. Alice selects a positive integer $$$a$$$ from interval $$$[1, m]$$$, and Bob selects a number $$$b$$$ the same way.
Then the game starts. In her turn, Alice can select any pile containing at least $$$a$$$ chips, and remove exactly $$$a$$$ chips from it. Similarly, in his turn, Bob can choose any pile with at least $$$b$$$ chips, and remove exactly $$$b$$$ chips from it. If a player cannot make a move, he or she loses.
If both players play optimally, the outcome ultimately depends on the choice of $$$a$$$ and $$$b$$$, and on the starting player. Consider a fixed pair $$$(a,b)$$$. There are four types of games:
Among all choices of $$$a$$$ and $$$b$$$ (i.e. for each pair $$$(a, b)$$$ such that $$$1\leq a, b\leq m$$$), determine how many games are won by Alice (regardless of who starts), how many are won by Bob (regardless of who starts), how many are won by the first player, and how many are won by the second player.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 100, 1 \leq m \leq 10^5$$$) — the number of piles, and the upper bound on the number of chips allowed to be taken in one turn, respectively.
The second line contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$1 \leq v_i \leq 10^{18}$$$) — the starting number of chips in each pile.
Print a single line containing four integers $$$w_a$$$, $$$w_b$$$, $$$w_f$$$, $$$w_s$$$ — the number of games won by Alice, Bob, the first player, the second player, respectively.
2 2
4 5
1 1 1 1
2 20
4 5
82 82 6 230
In the first sample, there are a total of four choices for the tuple $$$(a,b)$$$.
In the second sample, a lot of games, e.g. $$$a = 7$$$ and $$$b = 6$$$, end without anybody being able to remove single chip — which counts as a win for the second player. The games won for the first player are $$$(1, 1)$$$, $$$(1, 4)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(4, 1)$$$, and $$$(5, 5)$$$.
Name |
---|