G. Игра с фишками
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб решили сыграть в одну игру. У них есть $$$n$$$ кучек, $$$i$$$-я кучка изначально содержит $$$v_i$$$ фишек. Алиса изначально выбирает положительное целое число $$$a$$$ из интервала $$$[1, m]$$$, а Боб выбирает число $$$b$$$ таким же образом.

Затем начинается игра. В свою очередь, Алиса может выбрать любую кучку, содержащую как минимум $$$a$$$ фишек, и удалить из нее ровно $$$a$$$ фишек. Точно так же, в свою очередь, Боб может выбрать любую кучку с не менее $$$b$$$ фишками и удалить из нее ровно $$$b$$$ фишек. Если игрок не может сделать ход, он или она проигрывает.

Если оба игрока играют оптимально, результат в конечном счете зависит от выбора $$$a$$$ и $$$b$$$, а также от того, кто начинает. Рассмотрим пару $$$(a,b)$$$. Всего есть четыре вида игр:

  • Алиса побеждает вне зависимости от того, кто начинает.
  • Боб побеждает вне зависимости от того, кто начинает.
  • Если Алиса начинает, она побеждает. Если Боб начинает, он побеждает. То есть первый игрок побеждает.
  • Если Алиса начинает, Боб побеждает. Если Боб начинает, Алиса побеждает. То есть второй игрок побеждает.

Для всех возможных $$$a$$$ и $$$b$$$ (то есть для каждой пары $$$(a, b)$$$, такой что ($$$1\leq a, b\leq m$$$)) нужно определить, сколько игр будут выиграны Алисой (вне зависимости от того, кто начинает), сколько Бобом (вне зависимости от того, кто начинает), сколько игроком, который начинает игру, и сколько вторым игроком.

Входные данные

Первая строка содержит два целых числа $$$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}$$$) — начальное количество фишек в каждой кучке.

Выходные данные

В первой строке выведите четыре числа $$$w_a$$$, $$$w_b$$$, $$$w_f$$$, $$$w_s$$$ — количество игр, выигранных Алисой, Бобом, первым игроком и вторым игроком соответственно.

Примеры
Входные данные
2 2
4 5
Выходные данные
1 1 1 1
Входные данные
2 20
4 5
Выходные данные
82 82 6 230
Примечание

В первом примере есть всего четыре способа выбрать пару $$$(a,b)$$$.

  • $$$a = b = 1$$$: Не имеет значения с каких кучек забираются фишки — можно сделать всего $$$9$$$ ходов. Первый игрок победит, так как он сделает последний ход.
  • $$$a = b = 2$$$: Второй игрок может выиграть, если всегда будет выбирать ту же кучку, которую первый игрок выбирает, до того момента, когда будет $$$0$$$ и $$$1$$$ фишек в кучках. Так как невозможно выбрать кучку из $$$2$$$ фишками, то первый игрок проигрывает.
  • $$$a = 1$$$ и $$$b = 2$$$:
    • Пусть начинает Алиса. Она может выиграть, забирая одну фишку с кучки с $$$5$$$ фишками, а потом, копируя действия Боба. После следующих четырех ходов игра закончится, так как будет по $$$1$$$ фишке в каждой кучке, и Боб не сможет сделать ход.
    • Пусть начинает Боб. Если он заберет две фишки из второй кучки, то Алиса сможет забрать одну фишку из первой кучки. А потом она всегда может копировать действия Боба. Если же Боб заберет две фишки из первой кучки в свой первый ход, то Алиса может тоже забрать одну от туда. Так как в первой кучке осталась только одна фишка, то Боб вынужден забрать две фишки из второй кучки, оставляя $$$3$$$. Вне зависимости от того, что делает Алиса, она победит.
    Значит, Алиса победит вне зависимости от того, кто начинает.
  • $$$a = 2$$$ и $$$b = 1$$$: Симметрично до предыдущего пункта — поэтому победит Боб.

Во втором примере очень много игр, например при $$$a = 7$$$ и $$$b = 6$$$ игра сразу же закончится, так как никто не может сделать ход — значит, что победил второй игрок. Игры, который закончатся победой для первого игрока: $$$(1, 1)$$$, $$$(1, 4)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(4, 1)$$$ и $$$(5, 5)$$$.