b

// div1 easy
import java.util.ArrayList;

public class AlmostFibonacciKnapsack {
  public static int MX = 90;
  public static long[] arr;
  static {
    arr = new long[MX];
    arr[1] = 2;
    arr[2] = 3;
    for (int i = 3; i < arr.length; i++) {
      arr[i] = arr[i-1] + arr[i-2] - 1;
    }
  }

  public int[] getIndices(long x) {
    ArrayList<Integer> ans = new ArrayList<>();
    while (x > 0) {
      if (x == 2) {
        ans.add(1);
        break;
      }
      if (x == 3) {
        ans.add(2);
        break;
      }
      for (int i = 1; i+1 < arr.length; i++) {
        if (arr[i+1] > x) {
          if (arr[i]+1 == x) {
            ans.add(i-1);
            ans.add(i-2);
            x -= arr[i-1];
            x -= arr[i-2];
          } else {
            ans.add(i);
            x -= arr[i];
          }
          break;
        }
      }
    }
    int[] res = new int[ans.size()];
    for (int i = 0; i < ans.size(); i++) res[i] = ans.get(i);
    return res;
  }
}

// div1 med
import java.util.ArrayList;
import java.util.Arrays;

public class AllGraphCuts {
  public int[] findGraph(int[] x) {
    int n = 0;
    while(n*n < x.length) n++;
    int[][] d = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        d[i][j] = x[i*n+j];
      }
    }

    for (int i = 0; i < n; i++) {
      if (d[i][i] != 0)return new int[]{-1};
      for (int j = 0; j < n; j++) {
        if (d[i][j] != d[j][i]) return new int[]{-1};
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          if (i != j && d[i][j] < Math.min(d[i][k], d[k][j]))
            return new int[]{-1};
        }
      }
    }

    // A max spanning tree will satisfy the conditions
    int[] prev = new int[n];
    int[] max = new int[n];;
    max[0] = 1 << 30;
    boolean[] vis = new boolean[n];
    int[] ans = new int[n-1];
    int aid = 0;
    for (int i = 0; i < n; i++) {
      int idx = 0, mx = -1;
      for (int j = 0; j < n; j++) {
        if (!vis[j] && max[j] > mx) {
          mx = max[j];
          idx = j;
        }
      }
      vis[idx] = true;
      if (i > 0) {
        ans[aid++] = d[idx][prev[idx]] * n * n + idx * n + prev[idx];
      }
      for (int j = 0; j < n; j++) {
        if (!vis[j] && d[idx][j] > max[j]) {
          max[j] = d[idx][j];
          prev[j] = idx;
        }
      }
    }
    return ans;
  }
}

// div1 hard (by subscriber)
public class AlienSkiSlopes {
    int n;
    int[][] H;
    int[] ans;
    int bad;

    int[][] e;
    int[] q, f;

    int[] was;

    boolean kun(int x) {
        if (f[x] == 1) return false;
        f[x] = 1;
        for (int i = 0; i < n; i++) if (e[x][i] == 1 && q[i] == -1) {
            q[i] = x;
            return true;
        }
        for (int i = 0; i < n; i++) if (e[x][i] == 1 && kun(q[i])) {
            q[i] = x;
            return true;
        }
        return false;
    }

    void dfs(int x) {
        if (was[x] == 1) return;
        was[x] = 1;
        for (int i = 0; i < n; i++) if (e[x][i] == 1) dfs(q[i]);
    }

    boolean cut() {
        for (int i = 0; i < n; i++) {
            int ma = -1;
            for (int j = 0; j < n; j++) ma = Math.max(ma,  H[i][j]);
            if (ma < 0) {
                bad = 1;
                return false;
            }
            for (int j = 0; j < n; j++) if (H[i][j] == ma) e[i][j] = 1; else e[i][j] = 0;
        }
        for (int i = 0; i < n; i++) q[i] = -1;
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) f[j] = 0;
            if (kun(i)) res++;
        }
        if (res == n) return false;

        for (int i = 0; i < n; i++) was[i] = 0;
        for (int i = 0; i < n; i++) {
            boolean ok = false;
            for (int j = 0; j < n; j++) if (q[j] == i) ok = true;
            if (!ok) {
                dfs(i);
                //break;
            }
        }

        int[] was2 = new int[n];
        for (int i = 0; i < n; i++) if (was[i] == 1) for (int j = 0; j < n; j++) if (e[i][j] == 1) was2[j] = 1;

        int c = (int) 1e9 + 1;
        for (int i = 0; i < n; i++) if (was[i] == 1) {
            int ma = -1;
            for (int j = 0; j < n; j++) ma = Math.max(ma,  H[i][j]);

            for (int j = 0; j < n; j++) if (H[i][j] < ma && was2[j] == 0) c = Math.min(c,  ma - H[i][j]);
        }

        for (int i = 0; i < n; i++) f[i] = 0;

        for (int i = 0; i < n; i++) if (was[i] == 1) for (int j = 0; j < n; j++) if (e[i][j] == 1) f[j] = 1;

        for (int i = 0; i < n; i++) if (f[i] == 1) {
            ans[i] += c;
            for (int j = 0; j < n; j++) H[j][i] -= c;
        }
        return true;
    }

    public int[] raise(int[] h) {
        n = 1;
        while (n * n < h.length) n++;

        H = new int[n][n];
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) H[i][j] = h[i * n + j];
        ans = new int[n];

        e = new int[n][n];
        q = new int[n];
        f = new int[n];
        was = new int[n];

        bad = 0;
        for(;;) {
            if (!cut()) break;
        }
        if (bad == 1) return new int[]{-1};

        return ans;
    }
}