#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
#include <tuple>
#include <numeric>
#include <utility>
#include <array>
using namespace std;

namespace {
  using Integer = long long; //__int128;
  template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}
  template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
  template<class T> istream& operator ,  (istream& is, T& val){ return is >> val;}
  template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}
  template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
  template<class T> ostream& operator ,  (ostream& os, const T& val){ return os << " " << val;}

  template<class H> void print(const H& head){ cout << head; }
  template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
  template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }

  template<class H> void eprint(const H& head){ cerr << head; }
  template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
  template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }

  class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator   end(){ return range_iterator(  end_, step_); } };

  inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }
  constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
  constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
  constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }

  inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed

  mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());

  template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str(); }

  inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }
}

#define dump(x) eprintln(__LINE__, ":", #x, "=", x);

namespace timer{
  using namespace chrono;
  steady_clock::time_point start_time;

  unsigned long long begin_time;
  unsigned long long get_cycle();
  void init();
  double get_sec_per_cycle();
  double get();

  unsigned long long get_cycle(){
    unsigned int low, high;
    __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
    return ((unsigned long long)low) | ((unsigned long long)high << 32);
  }

  void init(){
    start_time = steady_clock::now();
    begin_time = get_cycle();
  }

  double get_sec_per_cycle(){
    auto end_time = steady_clock::now();
    double elapsed = duration_cast<nanoseconds>(end_time - start_time).count() * 1e-9;
    return elapsed / (get_cycle() - begin_time);
  }

  double get(){
    static double sec_per_cycle = get_sec_per_cycle();
    return (double)(get_cycle() - begin_time) * sec_per_cycle;
  }
};

struct xor_shift{
  uint32_t x;
  uint32_t y;
  uint32_t z;
  uint32_t w;

  xor_shift(uint32_t seed = 88675123) : x(123456789), y(362436069), z(521288629), w(seed){
    for(int i=0; i<100; i++) next();
  }
  
  // [0..2^32)
  inline uint32_t next() {
    uint32_t t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
  }

  uint32_t operator () () {
    return next();
  }

  // [0, range)
  int operator () (int range){
    return (((long long)next()) * range) >> 32 ;
  }

  // [0, 1.0]
  double prob(){
    return (next()&0xfffffff) * 3.7252903123397e-9; // 0xfffffff = 268,435,455 = 2^28-1
  }

  // [first, last)
  template<class RandomIt>
  RandomIt operator() (RandomIt first, RandomIt last){
    int d = last - first;
    assert(d>0);
    return first + (*this)(d);
  }

  template<class T>
  T& operator()(vector<T>& v){
    return *(*this)(v.begin(), v.end());
  }

  template<class RandomIt>
  void shuffle (RandomIt first, RandomIt last){
    for(;first != last; ++first){
      auto itr = (*this)(first, last);
      swap(*first, *itr);
    }
  }
};

xor_shift rng(114);

constexpr int types = 26;
constexpr int max_days = 400;

struct AliasMethod{
  int n;
  vector<double> values;
  vector<double> thresholds;
  vector<int> low;
  vector<int> high;

  void init(vector<double> v){
    n = v.size();
    values = v;
    thresholds.resize(v.size());
    low.resize(v.size());
    high.resize(v.size());
  // }

  // AliasMethod(vector<double> v)
  //  : n(v.size()), values(v), thresholds(v.size()), low(v.size()), high(v.size())
  // {
    double s = accumulate(values.begin(), values.end(), 0.0);
    s = 1.0 / s;
    for(auto& x: values){
      x = x * s * n;
    }

    vector<int> small, big, one;
    for(int i=0; i<n; i++){
      if(values[i] > 1.0){
        big.push_back(i);
      }else if(values[i] < 1.0){
        small.push_back(i);
      }else{
        one.push_back(i);
      }
    }

    for(int i=0; i<n; i++){
      if(one.size()){
        int a = one.back();
        one.pop_back();
        thresholds[i] = 1.0;
        low[i] = a;
        high[i] = a;
        values[a] = 0.0;
      }else if(small.size() && big.size()){
        int a = small.back();
        small.pop_back();
        int b = big.back();
        big.pop_back();

        thresholds[i] = values[a];
        low[i] = a;
        high[i] = b;
        values[b] -= 1.0 - values[a];
        values[a] = 0.0;
        if(values[b] > 1.0){
          big.push_back(b);
        }else if(values[b] == 1.0){
          one.push_back(a);
        }else if(values[b] > 0.0){
          small.push_back(b);
        }
      }else{
        swap(one, big.size() ? big : small);
        i--;
      }
    }
  }

  int get(double p){
    assert(0.0 <= p && p < 1.0);
    p *= n;
    int i = p;
    p -= i;
    assert(0.0 <= p && p < 1.0);
    if(thresholds[i] > p){
      return low[i];
    }else{
      return high[i];
    }
  }
};


template<class T = int>
class BinaryIndexedTree_1_indexed{
  void init(const vector<T> &A){
    for(int i=0; i<N; i++){
      add(i+1, A[i]);
    }
  }
  
public:
  vector<T> tree;
  int N;
  
  BinaryIndexedTree_1_indexed(): tree(max_days+1, 0), N(max_days){}

  BinaryIndexedTree_1_indexed(const int n) : tree(n+1,0), N(n){
    
  }
  
  BinaryIndexedTree_1_indexed(const vector<T> &A) : tree(A.size()+1,0), N(A.size()){
    init(A);
  }

  //caution : position "i" must be 1-indexed
  void add(int i, const T x){
    while(i <= N){
      tree[i] += x;
      i += i & -i;
    }
  }

  //update node i to zero
  void to_zero(const int i){
    T val = get_at(i);
    add(i, -val);
  }

  //get sums [0,i]
  T get_sum(int i){
    T ret=0;
    while(i>0){
      ret += tree[i];
      i -= i & -i;
    }
    return ret;
  }

  //get sums [from,to]
  T get_sums_range(const int from, const int to){
    return get_sum(to) - get_sum(from-1);
  }

  //get at [i]
  T get_at(const int i){
    return get_sum(i) - get_sum(i-1);
  }

  int lower_bound(T val){
    if(val<=0) return 0;
    int x = 0;
    int k = 1;
    while((k<<1) <= N) k<<=1;
    
    for( ; k>0; k>>=1){
      if( x+k <= N && tree[x+k] < val ){
        val -= tree[x+k];
        x += k;
      }
    }
    return x+1;
  }

  void print(){
    for(int i=0; i<=N; i++){
      cerr << tree[i] << " ";
    }
    cerr << endl;
  }
};


struct Problem{
  int d;
  vector<int> c;
  vector<vector<int>> s;
};

long long calc_score(Problem& p, vector<int>& t, int t_offset){
  long long res = 0;
  vector<int> last(types, -1);

  for(int i=0; i<p.d; i++){
    int tt = t[i] - t_offset;
    res += p.s[i][tt];
    last[tt] = i;
    for(int j=0; j<types; j++){
      res -= p.c[j] * (i - last[j]);
    }
    // println(res);
  }

  return res;
}

struct ListNode{
  int next;
  int prev;
};

struct List{
  array<ListNode, max_days + 10> data;
  ListNode& operator[] (int at){
    return data[at + 1];
  }
};
  
template<class T, size_t N>
struct my_array{
  array<T, N> data;
  T& operator [] (int at){
    return data[at+1];
  }
};

struct State {
  vector<List> d_list;
  vector<my_array<int, max_days + 10>> d_list_prev;
  vector<int> t;
  long long score;
};

State construct(Problem& p, vector<int> t){
  State s;
  s.t = t;
  s.d_list.resize(types + 1);
  s.d_list_prev.resize(types + 1);
  for(int j=0; j<=types; j++){
    s.d_list[j][-1].next = p.d;
    s.d_list[j][p.d].prev = -1;
    s.d_list_prev[j][-1] = -1;
  }
  for(int day=0; day<p.d; day++){
    for(int j=0; j<=types; j++){
      s.d_list_prev[j][day] = s.d_list_prev[j][day-1];
    }
    int t = s.t[day];
    s.d_list_prev[t][day] = day;
    int last = s.d_list[t][p.d].prev;
    // connext last - day - end
    s.d_list[t][last].next = day;
    s.d_list[t][day].prev = last;
    s.d_list[t][day].next = p.d;
    s.d_list[t][p.d].prev = day;
  }
  s.score = calc_score(p, s.t, 0);
  return s;
}

State init(Problem& p){
  State s;
  vector<int> t(p.d);
  for(int i=0; i<p.d; i++){
    t[i] = rng(types);
  }
  return construct(p, t);
};

inline long long pena_len(int d_len){
  return ((0ll + d_len-1) * d_len) >> 1;
}

long long get_diff(Problem& p, State& s, int day, int new_t){
  long long res = 0;
  int old_t = s.t[day];
  if(old_t == new_t) return 0;
  res -= p.s[day][old_t];
  res += p.s[day][new_t];
  {
    int prev = s.d_list[old_t][day].prev;
    int next = s.d_list[old_t][day].next;

    int l0 = day - prev;
    int l1 = next - day;
    int l2 = next - prev;
    res += -p.c[old_t] * (pena_len(l2) - pena_len(l0) - pena_len(l1));
  }
  {
    int prev = s.d_list_prev[new_t][day];
    int next = s.d_list[new_t][prev].next;

    int l0 = day - prev;
    int l1 = next - day;
    int l2 = next - prev;
    res += -p.c[new_t] * (-pena_len(l2) + pena_len(l0) + pena_len(l1));
  }
  return res;
}

long long get_diff_swap(Problem& p, State& s, int day1, int day2){
  if(day1 > day2) swap(day1, day2);

  long long res = 0;
  int a_t = s.t[day1];
  int b_t = s.t[day2];
  if(a_t == b_t) return 0;

  res -= p.s[day1][a_t];
  res += p.s[day2][a_t];

  res -= p.s[day2][b_t];
  res += p.s[day1][b_t];

  for(int d0 = day1, d1 = day2, t=a_t, _=0; _<1; _++){
    int prev = s.d_list[t][d0].prev;
    int next = s.d_list[t][d0].next;
    int l0 = d0 - prev;
    int l1 = next - d0;
    int l2 = next - prev;

    int prev_ = s.d_list_prev[t][d1];
    int next_ = s.d_list[t][prev_].next;
    if(prev_ == d0){
      prev_ = prev;
      int l4 = next_ - d1;
      int l5 = d1 - prev_;
      res += -p.c[t] * (-pena_len(l0) - pena_len(l1) + pena_len(l4) + pena_len(l5));
    }else{
      int l3 = next_ - prev_;
      int l4 = d1 - prev_;
      int l5 = next_ - d1;
      res += -p.c[t] * (-pena_len(l0) - pena_len(l1) + pena_len(l2));
      res += -p.c[t] * (-pena_len(l3) + pena_len(l4) + pena_len(l5));
    }
  }
  for(int d0 = day1, d1 = day2, t=b_t, _=0; _<1; _++){
    int prev = s.d_list[t][d1].prev;
    int next = s.d_list[t][d1].next;
    int l0 = d1 - prev;
    int l1 = next - d1;
    int l2 = next - prev;

    int prev_ = s.d_list_prev[t][d0];
    int next_ = s.d_list[t][prev_].next;
    if(next_ == d1){
      next_ = next;
      int l4 = next_ - d0;
      int l5 = d0 - prev_;
      res += -p.c[t] * (-pena_len(l0) - pena_len(l1) + pena_len(l4) + pena_len(l5));
    }else{
      int l3 = next_ - prev_;
      int l4 = d0 - prev_;
      int l5 = next_ - d0;
      res += -p.c[t] * (-pena_len(l0) - pena_len(l1) + pena_len(l2));
      res += -p.c[t] * (-pena_len(l3) + pena_len(l4) + pena_len(l5));
    }
  }
  return res;
}


void update(Problem& p, State& s, int day, int new_t){
  int old_t = s.t[day];
  if(old_t == new_t) return;

  {
    int prev = s.d_list[old_t][day].prev;
    int next = s.d_list[old_t][day].next;
    s.d_list[old_t][prev].next = next;
    s.d_list[old_t][next].prev = prev;
    for(int i=day; i<next; i++){
      s.d_list_prev[old_t][i] = prev;
    }
  }
  {
    int prev = s.d_list_prev[new_t][day];
    int next = s.d_list[new_t][prev].next;

    s.d_list[new_t][prev].next = day;
    s.d_list[new_t][day].prev = prev;
    s.d_list[new_t][day].next = next;
    s.d_list[new_t][next].prev = day;

    for(int i=day; i<next; i++){
      s.d_list_prev[new_t][i] = day;
    }
  }

  s.t[day] = new_t;
}

// #define D_CHAIN
#define D_FENWICK
// #define D_BIT

struct State_v2 {
  vector<List> d_list;
  #ifdef D_CHAIN
  vector<vector<int>> d_chain;
  #endif
  #ifdef D_FENWICK
  vector<BinaryIndexedTree_1_indexed<int>> d_bit;
  #endif
  #ifdef D_BIT
  vector<array<long long, 10>> d_bit;
  #endif

  vector<int> t;
  long long score;

  int get_last(int day, int t){
    #ifdef D_CHAIN
    for(int i=d_chain[t].size()-1; i>=0; i--){
      if(d_chain[t][i] < day) return d_chain[t][i];
    }
    return -1;
    #endif

    #ifdef D_FENWICK
    int s = d_bit[t].get_sum(day + 3);
    return d_bit[t].lower_bound(s) - 3;
    #endif

    #ifdef D_BIT
    day += 3;
    for(int k=day>>6; k>=0; k--){
      if(d_bit[t][k] == 0) continue;
      if(k == day>>6){
        int r = day & 63;
        long long mask = (1ll<<r) - 1;
        mask &= d_bit[t][k];
        if(mask == 0) continue;
        int res = 63 - __builtin_clzll(mask);
        if(res >= (day & 63)) continue;
        res += k << 6;
        return res - 3;
      }else{
        int res = 63 - __builtin_clzll(d_bit[t][k]);
        res += k << 6;
        return res - 3;
      }
    }
    return -1;
    #endif
  }

  void put(int day, int t){
    int last = get_last(day, t);
    int next = d_list[t][last].next;
    d_list[t][last].next = day;
    d_list[t][day].prev = last;
    d_list[t][day].next = next;
    d_list[t][next].prev = day;
    this->t[day] = t;

    #ifdef D_CHAIN
    d_chain[t].push_back(day);
    for(int i=d_chain[t].size()-1; i>0; i--){
      if(d_chain[t][i-1] > d_chain[t][i]){
        swap(d_chain[t][i-1], d_chain[t][i]);
      }else{
        break;
      }
    }
    #endif

    #ifdef D_FENWICK
    d_bit[t].add(day + 3, 1);
    #endif

    #ifdef D_BIT
    d_bit[t][(day+3)>>6] ^= (1ll << ((day+3) & 63));
    #endif
  }

  void erase(int day){
    int t = this->t[day];
    int prev = d_list[t][day].prev;
    int next = d_list[t][day].next;
    d_list[t][prev].next = next;
    d_list[t][next].prev = prev;

    #ifdef D_CHAIN
    for(int i=0; i+1<d_chain[t].size(); i++){
      if(d_chain[t][i] != day) continue;
      swap(d_chain[t][i], d_chain[t][i+1]);
    }
    d_chain[t].pop_back();
    #endif

    #ifdef D_FENWICK
    d_bit[t].add(day + 3, -1);
    #endif

    #ifdef D_BIT
    d_bit[t][(day+3)>>6] ^= (1ll << ((day+3) & 63));
    #endif
  }
};


State_v2 construct_v2(Problem& p, vector<int> t){
  State_v2 s;
  s.t = t;
  s.d_list.resize(types + 1);

  #ifdef D_CHAIN
  s.d_chain.resize(types + 1);
  #endif

  #ifdef D_FENWICK
  s.d_bit.resize(types + 1, {});
  #endif

  #ifdef D_BIT
  s.d_bit.resize(types + 1, {});
  #endif

  for(int j=0; j<=types; j++){
    s.d_list[j][-1].next = p.d;
    s.d_list[j][p.d].prev = -1;

    #ifdef D_CHAIN
    s.d_chain[j].push_back(-1);
    s.d_chain[j].push_back(p.d);
    #endif

    #ifdef D_FENWICK
    s.d_bit[j].add(-1 + 3, 1);
    s.d_bit[j].add(p.d + 3, 1);
    #endif

    #ifdef D_BIT
    s.d_bit[j][(-1+3)>>6] ^= (1ll << ((-1+3) & 63));
    s.d_bit[j][(p.d+3)>>6] ^= (1ll << ((p.d+3) & 63));
    #endif
  }
  for(int day=0; day<p.d; day++){
    int t = s.t[day];
    s.put(day, t);
  }
  s.score = calc_score(p, s.t, 0);
  return s;
}

long long get_diff(Problem& p, State_v2& s, int day, int new_t){
  long long res = 0;
  int old_t = s.t[day];
  if(old_t == new_t) return 0;
  res -= p.s[day][old_t];
  res += p.s[day][new_t];
  {
    int prev = s.d_list[old_t][day].prev;
    int next = s.d_list[old_t][day].next;

    int l0 = day - prev;
    int l1 = next - day;
    int l2 = next - prev;
    res += -p.c[old_t] * (pena_len(l2) - pena_len(l0) - pena_len(l1));
  }
  {
    int prev = s.get_last(day, new_t);
    int next = s.d_list[new_t][prev].next;

    int l0 = day - prev;
    int l1 = next - day;
    int l2 = next - prev;
    res += -p.c[new_t] * (-pena_len(l2) + pena_len(l0) + pena_len(l1));
  }
  return res;
}

long long get_diff_swap(Problem& p, State_v2& s, int day1, int day2){
  if(day1 > day2) swap(day1, day2);

  long long res = 0;
  int a_t = s.t[day1];
  int b_t = s.t[day2];
  if(a_t == b_t) return 0;

  res -= p.s[day1][a_t];
  res += p.s[day2][a_t];

  res -= p.s[day2][b_t];
  res += p.s[day1][b_t];

  for(int d0 = day1, d1 = day2, t=a_t, _=0; _<1; _++){
    int prev = s.d_list[t][d0].prev;
    int next = s.d_list[t][d0].next;
    int l0 = d0 - prev;
    int l1 = next - d0;
    int l2 = next - prev;

    int prev_ = s.get_last(d1, t);
    int next_ = s.d_list[t][prev_].next;
    if(prev_ == d0){
      prev_ = prev;
      int l4 = next_ - d1;
      int l5 = d1 - prev_;
      res += -p.c[t] * (-pena_len(l0) - pena_len(l1) + pena_len(l4) + pena_len(l5));
    }else{
      int l3 = next_ - prev_;
      int l4 = d1 - prev_;
      int l5 = next_ - d1;
      res += -p.c[t] * (-pena_len(l0) - pena_len(l1) + pena_len(l2));
      res += -p.c[t] * (-pena_len(l3) + pena_len(l4) + pena_len(l5));
    }
  }
  for(int d0 = day1, d1 = day2, t=b_t, _=0; _<1; _++){
    int prev = s.d_list[t][d1].prev;
    int next = s.d_list[t][d1].next;
    int l0 = d1 - prev;
    int l1 = next - d1;
    int l2 = next - prev;

    int prev_ = s.get_last(d0, t);
    int next_ = s.d_list[t][prev_].next;
    if(next_ == d1){
      next_ = next;
      int l4 = next_ - d0;
      int l5 = d0 - prev_;
      res += -p.c[t] * (-pena_len(l0) - pena_len(l1) + pena_len(l4) + pena_len(l5));
    }else{
      int l3 = next_ - prev_;
      int l4 = d0 - prev_;
      int l5 = next_ - d0;
      res += -p.c[t] * (-pena_len(l0) - pena_len(l1) + pena_len(l2));
      res += -p.c[t] * (-pena_len(l3) + pena_len(l4) + pena_len(l5));
    }
  }
  return res;
}


void update(Problem& p, State_v2& s, int day, int new_t){
  int old_t = s.t[day];
  if(old_t == new_t) return;
  s.erase(day);
  s.put(day, new_t);
}

double coef = 0.0013;

// minimize
template<class RNG>
struct SimulatedAnnealing{
  RNG* rng;

  bool accept(double diff, double itr){
    if(diff < 0) return true;
    double T = max(0.9, 1.8 - itr * 1e-7);
    /// Evb speeding up
    // original : [0,1) < exp(-d / T)
    // optimized: [0,2^32) / 2^32 < pow(2, -d/T) <=> [0,2^32) < pow(2, -d/T + 32)
    //            round down -> [0,2^32) < 1<<(int)(-d/T + 32)
    // double coef = 0.0013;
    double a = -diff * coef / T + 32; // [-inf, 32]
    if(a < 15.0) return false; // tomerun cut
    return (*rng)() < 1ll<<(long long)(a);
  }
};


struct SA_counter{
  int num_itr = 0;
  int num_update = 0;
  int num_best_update = 0;
  int num_unforced_update = 0;
  int num_forced_update = 0;
  double best_score = 0.0;
  double score = 0.0;

  decltype(chrono::steady_clock::now()) start_time;

  inline void inc_itr(){
    ++num_itr;
  }
  inline void inc_best(double best_){
    ++num_best_update;
    best_score = best_;
  }
  inline void inc_forced(){
    ++num_forced_update;
    ++num_update;
  }
  inline void inc_unforced(){
    ++num_unforced_update;
    ++num_update;
  }

  void init(){
    start_time = chrono::steady_clock::now();
    num_itr = 0;
    num_update = 0;
    num_best_update = 0;
    num_unforced_update = 0;
    num_forced_update = 0;
    best_score = 0.0;
  }

  void print(){
    dump(num_itr);
    dump(num_update);
    dump(num_best_update);
    dump(num_unforced_update);
    dump(num_forced_update);
    dump(best_score);
  }

};

constexpr double TIME_LIMIT = 1.05;

vector<int> solver_SA(Problem& p){
  // State ini_state = init(p);
  // State_v2 state = construct_v2(p, ini_state.t);
  State state = init(p);

  SA_counter sa_cnt;
  sa_cnt.init();
  SimulatedAnnealing<xor_shift> sa;
  sa.rng = &rng;

  long long best = state.score;
  vector<int> best_ans = state.t;

  eprintln(state.score);

  vector<AliasMethod> alias(p.d);
  for(int i=0; i<p.d; i++){
    vector<double> d(begin(p.s[i]), end(p.s[i]));
    alias[i].init(d);
  }

  for(int i=0; ; i++){
    if((i&1023) == 1023 && timer::get() > TIME_LIMIT){
      break;
    }

    int trans_type = rng(100) > 40;

    int d = rng(p.d);
    int d2;
    if(trans_type == 1){
      constexpr int w = 60;
      d2 = rng(w + 1) - w/2 + d;
      while(d2 < 0 || d2 >= p.d){
        d2 = rng(w + 1) - w/2 + d;
      }
    }

    // int t = rng(types);
    int t = trans_type ? -1 : alias[d].get(rng.prob());
    long long diff;
    if(trans_type == 0){
      diff = get_diff(p, state, d, t);
    }else{
      diff = get_diff_swap(p, state, d, d2);
    }

    if(sa.accept(-diff, i)){
      if(trans_type == 0){
        update(p, state, d, t);
      }else{
        int t_a = state.t[d];
        int t_b = state.t[d2];
        update(p, state, d, t_b);
        update(p, state, d2, t_a);
      }
      state.score += diff;

      // long long s = calc_score(p, state.t, 0);
      // dump(state.score);
      // dump(s);
      // assert(state.score == s);

      if(state.score > best){
        best = state.score;
        best_ans = state.t;

        sa_cnt.inc_best(state.score);
      }
      if(diff >= 0){
        sa_cnt.inc_unforced();
      }else{
        sa_cnt.inc_forced();
      }
    }else{

    }
    sa_cnt.inc_itr();
  }

  sa_cnt.print();

  long long score = calc_score(p, best_ans, 0);
  dump(score);

  return best_ans;
}

template<class St>
long long dfs(
  Problem& p, St& s, 
  vector<int>& used,
  int depth, int day_hole, int t_floating, long long diff, long long start_diff
){
  constexpr int max_depth = 4;
  constexpr int search_width = 8;

  long long d_close = get_diff(p,s, day_hole, t_floating);
  if(d_close + diff + start_diff > 0){
    update(p, s, day_hole, t_floating);
    return d_close + diff + start_diff;
  }

  if(depth >= max_depth){
    return -1;
  }

  vector<pair<long long, int>> diffs;
  diffs.reserve(100);
  for(int day=0; day<p.d; day++){
    int t = s.t[day];
    if(used[day] || day == day_hole) continue;
    long long d_ = get_diff_swap(p,s, day_hole, day);
    long long diff_ = diff + d_;
    // if(diff_ < start_diff * 3 / 4) continue;
    if(diff_ < 0) continue;
    diffs.emplace_back(diff_, day);
  }

  if(diffs.size() == 0) return -1;
  // sort(rbegin(diffs), rend(diffs));
  rng.shuffle(begin(diffs), end(diffs));

  for(int i=0; i<search_width && i<diffs.size(); i++){
    int day = diffs[i].second;
    int t = s.t[day];
    update(p,s, day_hole, t);
    update(p,s, day, types);
    used[day] = 1;
    long long res = dfs(p,s,used, depth+1, day, t_floating, diffs[i].first, start_diff);
    if(res > 0) return res;
    used[day] = 0;
    update(p,s, day_hole, types);
    update(p,s, day, t);
  }

  return -1;
}

vector<int> solver_cycle(Problem& p, vector<int> t){
  auto state = construct(p, t);
  // auto state = construct_v2(p, t);

  constexpr double TIME_LIMIT_CYCLE = 1.95;

  dump(state.score);

  int itr;
  for(itr=0; ; itr++){
    if(timer::get() >= TIME_LIMIT_CYCLE) break;
    int start_day = rng(p.d);
    long long start_diff = get_diff(p, state, start_day, types);
    int t = state.t[start_day];
    vector<int> used(p.d, 0);
    used[start_day] = 1;
    update(p, state, start_day, types);
    long long res = dfs(p,state,used, 0, start_day, t, 0, start_diff);
    if(res <= 0){
      update(p, state, start_day, t);
    }else{
      state.score += res;
      dump(state.score);
      // dump(calc_score(p, state.t, 0));
      dump(itr);
    }
  }

  dump(itr);
  dump(state.score);

  return state.t;
}

// vector<int> solver_mcf(Problem& p, vector<int> t){
//   State state = construct(p, t);
//   constexpr double TIME_LIMIT_FLOW = 1.95;
//   dump(state.score);
  
// }

int main(int argc, char* argv[]){
  for(int i=1; i+1<argc; i++){
    if(argv[i] == string("-c")){
      coef = stod(string(argv[i+1]));
    }
  }

  timer::init();
  Problem p;
  cin >> p.d;
  p.c.resize(types);
  cin >> p.c;
  p.c.push_back(0);
  p.s.resize(p.d, vector<int>(types));
  cin >> p.s;
  for(int i=0; i<p.d; i++){
    p.s[i].push_back(0);
  }

  auto best_ans = solver_SA(p);
  auto best_ans_cycle = solver_cycle(p, best_ans);
  // auto s = init(p);
  // auto best_ans_cycle = solver_cycle(p, s.t);

  for(auto& x: best_ans_cycle)
    println(x + 1);

  return 0;
}


Measured memory_bytes: 4248