CF1033G.Chip Game

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:

• Alice wins, regardless of who starts.
• Bob wins, regardless of who starts.
• If Alice starts, she wins. If Bob starts, he wins. We say that the first player wins.
• If Alice starts, Bob wins. If Bob starts, Alice wins. We say that the second player wins.

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.

爱丽丝和鲍勃决定玩一场终极游戏。他们有 $n$ 堆石子，其中第 $i$ 堆初始包含 $v_i$ 颗石子。爱丽丝从区间 $[1, m]$ 中选择一个正整数 $a$，鲍勃同样方式选择一个数 $b$。

随后游戏开始。在自己的回合中，爱丽丝可任选一堆至少含有 $a$ 颗石子的石堆，并从中恰好移除 $a$ 颗石子；类似地，在自己的回合中，鲍勃可任选一堆至少含有 $b$ 颗石子的石堆，并从中恰好移除 $b$ 颗石子。若某玩家无法进行任何操作，则该玩家判负。

若双方均采取最优策略，则游戏结果最终取决于 $a$ 和 $b$ 的取值，以及起始玩家。考虑固定的数对 $(a,b)$。共有四类游戏：

• 无论谁先手，爱丽丝均获胜。
• 无论谁先手，鲍勃均获胜。
• 若爱丽丝先手，则她获胜；若鲍勃先手，则他获胜。我们称“先手玩家获胜”。
• 若爱丽丝先手，则鲍勃获胜；若鲍勃先手，则爱丽丝获胜。我们称“后手玩家获胜”。

对所有可能的 $a$ 和 $b$ 的选择（即对所有满足 $1\leq a, b\leq m$ 的数对 $(a, b)$），分别统计：

• 爱丽丝必胜（无论谁先手）的游戏个数；
• 鲍勃必胜（无论谁先手）的游戏个数；
• 先手玩家必胜的游戏个数；
• 后手玩家必胜的游戏个数。

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.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 100$，$1 \leq m \leq 10^5$）—— 分别表示堆的数量以及每次操作允许取走的筹码数量的上限。

第二行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$（$1 \leq v_i \leq 10^{18}$）—— 表示每堆初始的筹码数量。

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.

输出一行，包含四个整数 $w_a$、$w_b$、$w_f$、$w_s$ —— 分别表示 Alice、Bob、先手玩家、后手玩家获胜的局数。

In the first sample, there are a total of four choices for the tuple $(a,b)$.

• $a = b = 1$: It does not matter from which pile the chips are removed — there are $9$ turns to be made, and the first player also makes the last, and hence he wins.
• $a = b = 2$: The second player may win by always selecting the same pile as the first before there are $0$ and $1$ chips in the piles. Since it is impossible to remove $2$ chips from any of them, the first player loses.
• $a = 1$ and $b = 2$:
  • Suppose Alice starts. She can win by removing a single chip from the pile with $5$ chips and then copying Bob's decision. After the next four turns, the game ends with $1$ chip in each pile and Bob unable to make a move.
  • Suppose Bob starts. If he removes two chips from second pile, Alice counters by removing a chip from the first pile. From then on, she can always copy Bob's decision and win. If Bob removes two chips from the first pile in his first turn, Alice can also remove one. As the first pile only has one chip left, Bob is forced to remove two chips from the second pile, leaving $3$. Regardless of what Alice does, she wins.Hence, Alice wins no matter who starts.
• $a = 2$ and $b = 1$: This is symmetric with the previous case — hence Bob always wins.

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)$.

在第一个样例中，元组 $(a,b)$ 共有四种可能的选择。

• $a = b = 1$：从哪一堆取走筹码并不重要——总共需进行 $9$ 轮操作，且先手玩家也执行最后一轮操作，因此他获胜。
• $a = b = 2$：后手玩家可在两堆筹码数量变为 $0$ 和 $1$ 之前，始终选择与先手玩家相同的那一堆进行操作。由于此时无法从任一堆中取走 $2$ 枚筹码，先手玩家失败。
• $a = 1$ 且 $b = 2$：
  • 假设 Alice 先手。她可通过从含 $5$ 枚筹码的那堆中取走 $1$ 枚筹码取胜，随后模仿 Bob 的每一步操作。再经过四轮后，游戏结束，每堆各剩 $1$ 枚筹码，而 Bob 无法继续操作。
  • 假设 Bob 先手。若他在第一轮从第二堆取走 $2$ 枚筹码，则 Alice 可从第一堆取走 $1$ 枚筹码作为回应；此后她总能模仿 Bob 的操作并获胜。若 Bob 在第一轮从第一堆取走 $2$ 枚筹码，则 Alice 同样可取走 $1$ 枚；此时第一堆仅剩 $1$ 枚筹码，Bob 被迫从第二堆取走 $2$ 枚筹码，使第二堆剩余 $3$ 枚。无论 Alice 如何操作，她都将获胜。因此，无论谁先手，Alice 均获胜。
• $a = 2$ 且 $b = 1$：此情况与上一情形对称——故 Bob 总是获胜。

在第二个样例中，许多对局（例如 $a = 7$ 且 $b = 6$）会以双方均无法取走 $1$ 枚筹码而告终——这被计为后手玩家获胜。先手玩家获胜的对局有：$(1, 1)$、$(1, 4)$、$(2, 3)$、$(3, 2)$、$(4, 1)$ 和 $(5, 5)$。