Problem: 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≤ a, b≤ 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. 

Input

The first line contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 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, ..., v_n (1 ≤ v_i ≤ 10^{18}) — the starting number of chips in each pile.

Output

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. 

Examples

Input

2 2
4 5


Output

1 1 1 1


Input

2 20
4 5


Output

82 82 6 230

Note

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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  int n, m;
  std::cin >> n >> m;
  std::vector<int64_t> v(n);
  for (int64_t& x : v) std::cin >> x;
  int64_t wa = 0, wb = 0, wf = 0, wz = 0;
  for (int a = 1; a <= m; ++a) {
    auto grundyvalue = 1 & std::count_if(begin(v), end(v), [a](int64_t x) {
                         return (x / a) & 1;
                       });
    ++(grundyvalue ? wf : wz);
  }
  for (int sum = 3; sum < 2 * m; ++sum) {
    int mina = std::max(1, sum - m);
    int maxa = std::min(m, (sum - 1) / 2);
    assert(mina <= maxa);
    assert(mina < sum - mina);
    assert(maxa < sum - maxa);
    auto v1 = v;
    for (auto& x : v1) x %= sum;
    std::sort(begin(v1), end(v1));
    {
      int a1 = mina - 1;
      auto const a1_ok = [&](int a) {
        if (a > maxa) return false;
        int const b = sum - a;
        auto n_atleast_a =
            std::count_if(begin(v1), end(v1), [&](int x) { return x >= a; });
        auto n_atleast_b =
            std::count_if(begin(v1), end(v1), [&](int x) { return x >= b; });
        return n_atleast_a > n_atleast_b;
      };
      for (int step = 1 << 20; step; step >>= 1)
        if (a1_ok(a1 + step)) a1 += step;
      int const cnt = a1 - mina + 1;
      for (int a = mina; a <= a1; ++a) assert(a1_ok(a));
      assert(cnt >= 0);
      wa += cnt;
      wb += cnt;
      mina = a1 + 1;
    }
    {
      int a1 = maxa + 1;
      auto const a1_ok = [&](int a) {
        if (a < mina) return false;
        auto n_atleast_a =
            std::count_if(begin(v1), end(v1), [&](int x) { return x >= a; });
        return n_atleast_a == 0;
      };
      for (int step = 1 << 20; step; step >>= 1)
        if (a1_ok(a1 - step)) a1 -= step;
      int const cnt = maxa - a1 + 1;
      for (int a = a1; a <= maxa; ++a) assert(a1_ok(a));
      assert(cnt >= 0);
      wz += 2 * cnt;
      maxa = a1 - 1;
    }
    {
      int a1 = mina - 1;
      auto const a1_ok = [&](int a) {
        if (a > maxa) return false;
        auto n_atleast_2a = std::count_if(begin(v1), end(v1),
                                          [&](int x) { return x >= 2 * a; });
        return n_atleast_2a >= 2;
      };
      for (int step = 1 << 20; step; step >>= 1)
        if (a1_ok(a1 + step)) a1 += step;
      int const cnt = a1 - mina + 1;
      for (int a = mina; a <= a1; ++a) assert(a1_ok(a));
      assert(cnt >= 0);
      wa += cnt;
      wb += cnt;
      mina = a1 + 1;
    }
    {
      int a1 = mina - 1;
      auto const a1_ok = [&](int a) {
        if (a > maxa) return false;
        auto n_atleast_2a = std::count_if(begin(v1), end(v1),
                                          [&](int x) { return x >= 2 * a; });
        return n_atleast_2a == 1;
      };
      for (int step = 1 << 20; step; step >>= 1)
        if (a1_ok(a1 + step)) a1 += step;
      int const cnt = a1 - mina + 1;
      for (int a = mina; a <= a1; ++a) assert(a1_ok(a));
      assert(cnt >= 0);
      {
        int minb = sum - a1, maxb = sum - mina;
        assert(maxb - minb + 1 >= 0);
        int n_atleast_b = 0;
        for (auto i = v1.size(); i--;) {
          auto const v1_i = v1[i];
          int const minb1 = int(v1_i + 1);
          for (int b = minb1; b <= maxb; ++b)
            assert(n_atleast_b == std::count_if(begin(v1), end(v1),
                                                [&](int x) { return x >= b; }));
          int const cnt1 = std::max(0, maxb - std::max(minb, minb1) + 1);
          if (n_atleast_b % 2 != 0) {
            wf += 2 * cnt1;
          } else {
            wa += cnt1;
            wb += cnt1;
          }
          ++n_atleast_b;
          maxb -= cnt1;
          if (minb > maxb) break;
        };
        assert(maxb - minb + 1 >= 0);
        if (minb <= maxb) {
          int const cnt1 = maxb - minb + 1;
          if (n_atleast_b % 2 != 0) {
            wf += 2 * cnt1;
          } else {
            wa += cnt1;
            wb += cnt1;
          }
        }
      }
      mina = a1 + 1;
    }
    assert(maxa - mina + 1 >= 0);
    int minb = sum - maxa, maxb = sum - mina;
    assert(maxb - minb + 1 >= 0);
    int n_atleast_b = 0;
    for (auto i = v1.size(); i--;) {
      auto const v1_i = v1[i];
      int const minb1 = int(v1_i + 1);
      for (int b = minb1; b <= maxb; ++b)
        assert(n_atleast_b == std::count_if(begin(v1), end(v1),
                                            [&](int x) { return x >= b; }));
      int const cnt = std::max(0, maxb - std::max(minb, minb1) + 1);
      (n_atleast_b & 1 ? wf : wz) += 2 * cnt;
      ++n_atleast_b;
      maxb -= cnt;
      if (minb > maxb) break;
    };
    assert(maxb - minb + 1 >= 0);
    if (minb <= maxb) {
      int const cnt = maxb - minb + 1;
      (n_atleast_b & 1 ? wf : wz) += 2 * cnt;
    }
  }
  std::cout << wa << ' ' << wb << ' ' << wf << ' ' << wz << '\n';
}