Алиса и Боб решили сыграть в одну игру. У них есть \(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\))) нужно определить, сколько игр будут выиграны Алисой (вне зависимости от того, кто начинает), сколько Бобом (вне зависимости от того, кто начинает), сколько игроком, который начинает игру, и сколько вторым игроком.
Выходные данные
В первой строке выведите четыре числа \(w_a\), \(w_b\), \(w_f\), \(w_s\) — количество игр, выигранных Алисой, Бобом, первым игроком и вторым игроком соответственно.
Примечание
В первом примере есть всего четыре способа выбрать пару \((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)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
4 5
|
1 1 1 1
|
|
2
|
2 20
4 5
|
82 82 6 230
|