//#include <bits/stdc++.h>

#include <iostream>
#include <algorithm>

#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <cstring>
#include <string>
#include <utility>
#include <array>
#include <complex>
#include <valarray>

#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>

#include<memory>


using namespace std;
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
//typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double,int> pdi;
typedef pair<long double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<29;
const ll INFLL = 1LL<<62;
const long double EPS = 1e-12;
const ll mod = 1000000000 + 7;
//const ll mod = 998244353;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const long double pi = 3.141592653589793;

#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod
#define inside(y, x, h, w) (0 <= (y) && (y) < (h) && 0 <= (x) && (x) < (w)) ? true : false

//debug
#define DEBUG

#define DUMPOUT cerr

#ifdef DEBUG
#define dump(...) DUMPOUT<<#__VA_ARGS__<<" :["<<__FUNCTION__<<":"<<__LINE__<<"]"<<endl; DUMPOUT<<"    "; dump_func(__VA_ARGS__)
#else
#define dump(...)
#endif

void dump_func() {DUMPOUT << endl;};

template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) == 0) DUMPOUT << " ";
    else DUMPOUT << ", ";
    dump_func(std::move(tail)...);
}

//ostream
template<typename T> ostream& operator << (ostream& os, vector<T>& vec) {
    os << "["; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "]";
    return os;
}

template<typename T, typename U> ostream& operator << (ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}

template<typename T, typename U> ostream& operator << (ostream& os, map<T, U>& map_var) {
    os << "[";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")"; itr++;  if(itr != map_var.end()) os << ", "; itr--;
    }
    os << "]";
    return os;
}

template<typename T> ostream& operator << (ostream& os, set<T>& set_var) {
    os << "[";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr; ++itr; if(itr != set_var.end()) os << ", "; itr--;
    }
    os << "]";
    return os;
}

auto start = chrono::system_clock::now();
double timelimit = 29800;

inline bool check_time() {
    auto end = chrono::system_clock::now();
    auto dur = end - start;
    auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
    if (msec >= timelimit) return false;
    return true;
}

inline double get_time() {
  auto end = chrono::system_clock::now();
  auto dur = end - start;
  auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
  return msec;
}

inline void now_time() {
  auto end = chrono::system_clock::now();
  auto dur = end - start;
  auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
  cout << "time : " << msec << " msec"<< endl;
}

unsigned long long seed128[4]; //x,y,z,wとして利用
inline void seed(unsigned long long s){
    for(int i=1; i<=4; i++){
        seed128[i-1] = s = 1812433253U * (s^(s>>30)) + i;
    }
}

inline unsigned long long Xor128(){
  unsigned long long t;
  t=(seed128[0]^(seed128[0]<<11));
  seed128[0]=seed128[1];
  seed128[1]=seed128[2];
  seed128[2]=seed128[3];
  seed128[3]=(seed128[3]^(seed128[3]>>19))^(t^(t>>8));
  return seed128[3];
}

int n, m; //頂点数, 辺数
vector<vector<pair<int, int>>> g;
const int T = 10000;
vector<pii> order; //(id, v) ただし(-1, -1)は注文がないことを表す
int order_cnt = 0; //注文数
vector<int> start_o; //start_o[id]:= 注文idを開始した時刻
vector<vector<int>> order_info; //order_info[v]:= 頂点vの注文リスト

vector<vector<int>> d; //d[i][j]:= iからjへの最短経路距離
vector<vector<vector<int>>> path; //d[i][j]:= iからjへの最短経路path
int delivery_cnt = 0; //達成した注文数

int peak = 0;
vector<int> pri_v;
ll max_score = 0;
vector<vector<bool>> store_on_path;

void read() {
  //input graph
  cin >> n >> m;
  g.resize(n);
  rep(i, m) {
    int u, v, c;
    cin >> u >> v >> c;
    u--; v--;
    g[u].emplace_back(v, c);
    g[v].emplace_back(u, c);
  }
  /*
  rep(i, (int)g[0].size()) {
    cerr << g[0][i] << " ";
  }
  cerr << endl;
  exit(0);
  */
  //input order
  order_info.resize(n);
  int tmp_T;
  cin >> tmp_T;
  //assert(tmp_T == T);
  order.resize(T+1);
  rep(i, T+1) order[i] = {-1, -1};
  //rep(i, T) cerr << order[i].fi << " " << order[i].se << endl;
  rep(i, tmp_T) {
    int info;
    cin >> info;
    if (info == 0) {
      order[i] = {-1, -1};
      //order.emplace_back(-1, -1);
      continue;
    }
    assert(info == 1);
    order_cnt++;
    int id, v;
    cin >> id >> v;
    id--; v--;
    order[i] = {id, v};
    start_o.push_back(i);
  }
  order[T] = {-1, -1};
  //order.emplace_back(-1, -1);
}

void analysis() {
  //cerr << order_cnt << endl;
  //各頂点の注文数
  int region[n] = {};
  rep(i, T) {
    if (order[i].fi == -1) continue;
    region[order[i].se]++;
  }
  vector<pii> freq;
  rep(i, n) freq.emplace_back(region[i], i);
  sort(rall(freq));
  pri_v.resize(n, INF);
  rep(i, n) {
    int num = freq[i].fi;
    int v = freq[i].se;
    pri_v[v] = num;
  }
  /*
  rep(i, n) {
    cerr << freq[i].se+1 << " " << freq[i].fi << endl;
  }
  exit(0);
  */
  //注文率([-range/2, range/2]の平均)
  int range = 1000;
  vector<double> rates;
  rep2(i, range/2, T-range/2) {
    double rate = 0;
    rep2(j, i-range/2, i+range/2+1) {
      if (order[j].fi == -1) continue;
      rate++;
    }
    rate /= (double)range;
    //cout << i << " " << rate << endl;
    rates.push_back(rate);
  }
  double mx_rate = 0;
  rep(i, (int)rates.size()) {
    if (mx_rate < rates[i]) {
      mx_rate = rates[i];
      peak = i + range/2;
    }
  }
}

vector<int> dijkstra(const int s, const int n, vector<int>& pv, const vector<vector<pii>>& g) {
  priority_queue<pii, vector<pii>, greater<pii>> que;
  vector<int> d(n, INF); d[s] = 0;
  que.emplace(0, s);
  while (!que.empty()) {
    pii p = que.top();que.pop();
    int fr = p.second;
    if (d[fr] < p.first) continue;
    for (pair<int, int> e: g[fr]) {
      int to = e.fi;
      int cost = e.se;
      if (d[to] > d[fr] + cost) {
        d[to] = d[fr] + cost;
        pv[to] = fr;
        que.emplace(d[to], to);
      }
    }
  }
  return d;

}

vector<int> get_path(int t, const vector<int>& pv) {
    vector<int> path;
    while (t != -1) {
      path.push_back(t);
      t = pv[t];
    }
    reverse(path.begin(),path.end());
    return path;
}

void calc_graph() {
  d.resize(n);
  path.resize(n);
  store_on_path.resize(n);
  rep(i, n) {
    path[i].resize(n);
    store_on_path[i].resize(n, false);
  }

  rep(i, n) {
    vector<int> pv(n, -1);
    d[i] = dijkstra(i, n, pv, g);
    rep(j, n) {
      if (i == j) continue;
      path[i][j] = get_path(j, pv);
    }
  }
  store_on_path[0][0] = true;
  rep(i, n) {
    rep(j, n) {
      if (i == j) continue;
      rep2(k, 1, (int)path[i][j].size()) {
        if (path[i][j][k] == 0) store_on_path[i][j] = true;
      }
    }
  }
}

//nowtでidの注文を完了した時に、それによって得られるスコア
inline double calc_value(const int nowt, const int id) {
  double wait = (nowt - start_o[id]);
  return max(0.0, (double)T*T - wait*wait);
}

void output(const vector<int>& ans) {
  rep(i, T) {
    if (ans[i] == -1) cout << ans[i] << endl;
    else cout << ans[i]+1 << endl;
  }
}

bool last_return = false;

int update_ans(double& score, int& nowt, const vector<int>& TSP_path, vector<int>& ans, vector<int>& next_TSP_path) {
  assert(TSP_path[0] == 0);
  if (nowt < 9500) assert(TSP_path[(int)TSP_path.size()-1] == 0);
  //rep2(i, 1, (int)TSP_path.size()-1) assert(TSP_path[i] != 0);
  vector<pii> new_order; //まだ商品を持っていないが注文は来ているid

  rep(i, (int)TSP_path.size()-1) {
    int now = TSP_path[i];
    int nx = TSP_path[i+1];
    if (nowt + d[now][nx] > T) return 0;
    double rate = 1;
    if (nowt < peak) rate = (double)nowt/peak;
    else rate = (double)(10001-nowt) /(10001-peak);
    //int limd = 1+Xor128() % (int)(1+30*rate);
    //double limd =1+10*rate+Xor128() % 20;
    //int limd = 10+Xor128()%(1 + (int)(6000/(int)new_order.size()));
    int limd = 5 + Xor128() % 30;
    //limd = 1+20*rate;
    //cerr << limd << " " << rate << endl;
    int limo = 50 + Xor128() % 200;
    /*
    double mx_order = 0;
    double ave_order = 0;
    double order_cnt = 0;
    rep(i, n) {
      if (order_info[i].size() == 0) continue;
      order_cnt++;
      ave_order += order_info[i].size();
      mx_order = max(mx_order, (double)order_info[i].size());
    }
    if (peak-5000 > nowt || nowt > peak+5000) {
      mx_order = INF;
      ave_order = INF;
    }
    ave_order /= n;
    */
    //cerr << "ave_order : " << ave_order << endl;
    //cerr << mx_order << endl;
    //cerr << order_cnt << endl;
    if (now != 0 && (nowt < T && (int)new_order.size() >= limo && d[now][0] <= limd && d[now][0]+nowt <= T)) {
    //if (nowt <= 10000 && (int)new_order.size() >= limo && d[now][0] <= limd) {
      //if (nowt >= 9500) last_return = true;
      assert(now != 0);
      //cerr << "return !" << endl;
      rep(j, (int)path[now][0].size()-1) {
        int pnow = path[now][0][j];
        int pnx = path[now][0][j+1];
        rep(k, d[pnow][pnx]) {
          ans[nowt++] = pnx;
          /*
          if ((ll)score + 100000000LL * (order_cnt-delivery_cnt) < max_score) {
            nowt = T;
            return;
          }
          */
          int id = order[nowt].fi;
          int v = order[nowt].se;
          if (id != -1) {
            new_order.push_back(order[nowt]);
          }
        }
        if ((int)order_info[pnx].size() != 0) {
          assert(pnx != 0);
          next_TSP_path.push_back(pnx);
          for (int id : order_info[pnx]) {
            //next_idS.insert({id, pnx});
            delivery_cnt++;
            score += calc_value(nowt, id);
          }
          order_info[pnx].clear();
        }
      }
      for (auto p : new_order) {
        int id = p.fi;
        int v = p.se;
        order_info[v].push_back(id);
      }
      next_TSP_path.push_back(0);
      new_order.clear();
      return -1;
    }

    rep(j, (int)path[now][nx].size()-1) {
      int pnow = path[now][nx][j];
      int pnx = path[now][nx][j+1];
      rep(k, d[pnow][pnx]) {
        ans[nowt++] = pnx;
        /*
        if ((ll)score + 100000000LL * (order_cnt-delivery_cnt) < max_score) {
          cerr << (ll)score + 100000000LL * (order_cnt-delivery_cnt) << " " << max_score << endl;
          nowt = T;
          return;
        }
        */
        int id = order[nowt].fi;
        int v = order[nowt].se;
        if (id != -1) {
          new_order.push_back(order[nowt]);
        }
      }
      if ((int)order_info[pnx].size() != 0) {
        assert(pnx != 0);
        for (int id : order_info[pnx]) {
          delivery_cnt++;
          score += calc_value(nowt, id);
          //next_idS.insert({id, pnx});
        }
        next_TSP_path.push_back(pnx);
        order_info[pnx].clear();
      }
      if (pnx == 0) {
        for (auto p : new_order) {
          int id = p.fi;
          int v = p.se;
          order_info[v].push_back(id);
        }
        next_TSP_path.push_back(0);
        new_order.clear();
        return -1;
      }
    }
  }
  return -1;
}

inline vector<int> heulistic_TSP(const int nowt, const vector<int>& DS) {
  priority_queue<pii> pq;
  for (int v : DS) {
    pq.push({order_info[v].size(), v});
  }
  vector<int> VS;
  int lm = 200;
  while ((int)VS.size() < lm && !pq.empty()) {
    pii x = pq.top(); pq.pop();
    //cerr << x.fi << endl;
    VS.push_back(x.se);
  }
  //cerr << pq.size() << " " << VS.size() << endl;
  //cerr << "--------" << endl;

  vector<int> TSP_path;
  int now = 0;
  int tmp_nowt = nowt;
  TSP_path.push_back(0);
  vector<bool> visited(n, false);
  int cnt = 0;
  vector<pii> tmp_new_order(n);
  while (true) {
    double mn_score = INF;
    int nx = -1;
    for (auto v : VS) {
      if (visited[v]) continue;
      int tmpt = tmp_nowt + d[now][v];
      //if (tmpt - nowt > 10000) continue;
      double ocnt = order_info[v].size();
      /*
      double sco = 0;
      for (auto id : order_info[v]) {
        sco += calc_value(tmpt, id);
      }
      */
      double tmp_score = d[now][v];
      double low = 20000;
      double up = 20000;
      if (peak-low <= nowt && nowt <= peak+up) {
        tmp_score = d[now][v]*d[now][v]*d[now][v] / (ocnt);
        //tmp_score = d[now][v] * d[now][v] * sqrt(d[now][v]) / sqrt(sco);
      }
      /*
      vector<bool> tmp_visited = visited;
      int cnt_f = 0;
      int lim_f = 1;
      int now_v = v;
      while (cnt_f < lim_f) {
        int nx_f = -1;
        int mn_tmp_score1 = INF;
        for (auto u : VS) {
          if (tmp_visited[u]) continue;
          ocnt = order_info[u].size();
          double tmp_score1 = d[now_v][u] * sqrt(d[now_v][u]) / (ocnt);
          if (tmp_score1 < mn_tmp_score1) {
            mn_tmp_score1 = tmp_score1;
            nx_f = u;
          }
        }
        if (nx_f == -1) break;
        now_v = nx_f;
        tmp_visited[nx_f] = true;
        tmp_score += mn_tmp_score1;
        cnt_f++;
      }
      */
      //double tmp_score = d[now][v];
      if (tmp_score < mn_score) {
        mn_score = tmp_score;
        nx = v;
      }
    }
    if (nx == -1) break; //TSP完了
    /*
    int limd = 1+Xor128()%30;
    int limo = 100 + Xor128() % 500;
    if (nowt <= 9800 && (int)tmp_new_order.size() >= limo && d[now][0] <= limd) {
      TSP_path.push_back(0);
      return TSP_path;
    }
    */
    visited[nx] = true;
    bool via_store = false;
    rep2(i, 1, (int)path[now][nx].size()) {
      if (path[now][nx][i] == 0) {
        via_store = true;
        break;
      }
    }
    if (via_store) {
      TSP_path.push_back(0);
      return TSP_path;
    }
    for (auto v : VS) {
      if (visited[v]) continue;
      if (d[now][nx] >= d[now][v] + d[v][nx]) {
        visited[v] = true;
        TSP_path.push_back(v);
        break;
      }
    }
    TSP_path.push_back(nx);
    /*
    rep2(t, tmp_nowt+1, tmp_nowt+d[now][nx]+1) {
      if (t > 9500) break;
      int id = order[t].fi;
      //int v = order[t].se;
      if (id != -1) {
        tmp_new_order.push_back(order[t]);
      }
    }
    */
    tmp_nowt += d[now][nx];
    now = nx;
    cnt++;
    //if (cnt == 1000) break;
  }
  /*
  vector<int> v;
  for (int x : VS) {
    v.push_back(x);
  }
  vector<pair<double, int>> score_v;
  for (int x : v) {
    double score = 0;
    for (int id : order_info[x]) {
      score += calc_value(nowt, id);
    }
    score_v.emplace_back(score, x);
  }
  sort(rall(score_v));
  rep(i, (int)score_v.size()) cerr << score_v[i].fi << endl;
  int limit = 3000;
  rep(i, min(limit, (int)score_v.size())) {
    int v = score_v[i].se;
    TSP_path.push_back(v);
  }
  */
  //if (nowt >= 9500) return TSP_path;
  TSP_path.push_back(0);
  return TSP_path;
}

//最小単位で表現 (u->vをu->w->v)
vector<int> trans_minimum(const vector<int> TSP) {
  vector<int> ret;
  rep(i, (int)TSP.size()-1) {
    int now = TSP[i];
    int nx = TSP[i+1];
    rep(j, (int)path[now][nx].size()-1) {
      ret.push_back(path[now][nx][j]);
    }
    if (i == (int)TSP.size() - 2) {
      ret.push_back(0);
    }
  }
  return ret;
}

double sim(int nowt, const vector<int>& TSP_path) {
  double t = 0;
  double score = 0;
  rep(i, (int)TSP_path.size()-1) {
    int now = TSP_path[i];
    int nx = TSP_path[i+1];
    double ocnt = order_info[nx].size();
    if (nx == 0) {
      //score += d[now][nx];
    }
    else {
      assert(ocnt != 0);
      score += d[now][nx]*d[now][nx]*d[now][nx]/ocnt;
    }
  }
  return score;
  //vector<int> min_path = TSP_path;
  //vector<int> min_path = trans_minimum(TSP_path);

  /*
  rep(i, (int)min_path.size()-1) {
    int now = min_path[i];
    int nx = min_path[i+1];
    t += d[now][nx];
  }
  return t;
  if (nowt < 9500) return t;
  */
  //if (nowt < peak-500 || peak+500 < nowt) return t;
  /*
  int pret = nowt+1;
  vector<vector<int>> tmp_order_info = order_info;
  rep(i, (int)min_path.size()-1) {
    int now = min_path[i];
    int nx = min_path[i+1];
    if (nowt + d[now][nx] > T) return -score;
    nowt += d[now][nx];
    t += d[now][nx];
    if ((int)tmp_order_info[nx].size() != 0) {
      rep(j, (int)tmp_order_info[nx].size()) {
        int id = tmp_order_info[nx][j];
        score += calc_value(nowt, id);
      }
      tmp_order_info[nx].clear();
    }
    //修正
    if (nx == 0) {
      //return -score;
      while (pret <= nowt) {
        int id = order[pret].fi;
        int v = order[pret].se;
        if (id != -1) {
          tmp_order_info[v].push_back(id);
        }
        pret++;
      }
      //return -score/t;
    }
  }
  //return t;
  //cerr << score << " " << t << endl;
  return -score;
  */
}

double opt2_SA(int nowt, vector<int>& TSP_path) {
  if (TSP_path.size() == 2) return INF;
  int u = -1;
  int v = -1;
  int sz = TSP_path.size();
  int s = 0;
  int t = sz-1;
  int loop = 0;
  int limit_loop = 1000;
  while (loop < limit_loop && (u == v || u == s || v == t)) {
    loop++;
    u = Xor128() % sz;
    v = Xor128() % sz;
    if (u > v) swap(u, v);
  }
  if (loop == limit_loop) return INF;
  /*
  double diff_score = d[TSP_path[u-1]][TSP_path[u]] + d[TSP_path[v]][TSP_path[v+1]];
  Score -= diff_score;
  diff_score = d[TSP_path[u-1]][TSP_path[v]] + d[TSP_path[u]][TSP_path[v+1]];
  Score += diff_score;
  */
  reverse(TSP_path.begin()+u, TSP_path.begin()+v+1);
  //TODO: 高速化
  return sim(nowt, TSP_path);
}

double swap_2(int nowt, vector<int>& TSP_path) {
  if (TSP_path.size() == 2) return INF;
  int u = -1;
  int v = -1;
  int sz = TSP_path.size();
  int s = 0;
  int t = sz-1;
  int loop = 0;
  int limit_loop = 1000;
  while (loop < limit_loop && (u == v || u == s || v == t)) {
    loop++;
    u = Xor128() % sz;
    v = Xor128() % sz;
    if (u > v) swap(u, v);
  }
  if (loop == limit_loop) return INF;
  swap(TSP_path[u], TSP_path[v]);
  return sim(nowt, TSP_path);
}

double insert(int nowt, vector<int>& TSP_path) {
  if (TSP_path.size() == 2) return INF;
  int u = -1;
  int v = -1;
  int sz = TSP_path.size();
  int s = 0;
  int t = sz-1;
  int loop = 0;
  int limit_loop = 1000;
  while (loop < limit_loop && (u == v || u == s || v == t)) {
    loop++;
    u = Xor128() % sz;
    v = Xor128() % sz;
    if (u > v) swap(u, v);
  }
  if (loop == limit_loop) return INF;
  int iv = TSP_path[v];
  TSP_path.erase(TSP_path.begin()+v);
  TSP_path.insert(TSP_path.begin()+u, iv);
  return sim(nowt, TSP_path);
}

double or_opt(int nowt, vector<int>& TSP_path) {
  if (TSP_path.size() == 2) return INF;
  int len = 1+Xor128() % min((int)TSP_path.size()-2, 3);
  int l = Xor128() % TSP_path.size();
  int loop = 0;
  int limit = 1000;
  while (loop < limit && (l == 0 || l+len-1 >= (int)TSP_path.size()-1)) {
    loop++;
    l = Xor128() % TSP_path.size();
  }
  if (loop == limit) return INF;
  vector<int> tmp;
  vector<int> insP;
  rep(i, (int)TSP_path.size()) {
    if (l <= i && i < l + len)  {
      insP.push_back(TSP_path[i]);
    }
    else {
      tmp.push_back(TSP_path[i]);
    }
  }
  int ins = Xor128() % (int)tmp.size();
  loop = 0;
  while (loop < limit && (ins == 0 || ins == (int)tmp.size()-1)) {
    loop++;
    ins = Xor128() % (int) tmp.size();
  }
  if (loop == limit) return INF;
  for (auto x : insP) {
    tmp.insert(tmp.begin()+ins, x);
    ins++;
  }
  double ret = sim(nowt, tmp);
  //cerr << ret << endl;
  return ret;
}

double remove(int nowt, vector<int>& TSP_path, vector<int>& removed) {
  if ((int)TSP_path.size() == 2) return INF;
  int r = Xor128() % (int)TSP_path.size();
  int loop = 0;
  int limit = 1000;
  while (loop < limit && (r == 0 || r == (int)TSP_path.size()-1)) {
    loop++;
    r = Xor128() % (int)TSP_path.size();
  }
  if (loop == limit) return INF;
  int rv = TSP_path[r];
  TSP_path.erase(TSP_path.begin()+r);
  removed.push_back(rv);
  return sim(nowt, TSP_path);
}

double add(int nowt, vector<int>& TSP_path, vector<int>& removed) {
  if ((int)removed.size() == 0) return INF;
  int a = Xor128() % (int)removed.size();
  int av = removed[a];
  removed.erase(removed.begin()+a);
  int ins = Xor128() % (int)TSP_path.size();
  int loop = 0;
  int limit = 1000;
  while (loop < limit && (ins == 0 || ins == ((int)TSP_path.size()-1))) {
    loop++;
    ins = Xor128() % TSP_path.size();
  }
  if (loop == limit) return INF;
  TSP_path.insert(TSP_path.begin()+ins, av);
  return sim(nowt, TSP_path);
}

double NeighborSearch(int nowt, vector<int>& TSP_path, vector<int>& removed) {
  int id = Xor128() %3;
  if (id == 0) return opt2_SA(nowt, TSP_path);
  else if (id == 1) return or_opt(nowt, TSP_path);
  else if (id == 2) return swap_2(nowt, TSP_path);
  //else if (id == 3) return remove(nowt, TSP_path, removed);
  //else if (id == 4) return add(nowt, TSP_path, removed);
  //else if (id == 1) return insert(nowt, TSP_path);
  //else if (id == 1) return oropt_SA(TSP_path);
}



vector<int> SA(const int nowt, const vector<int>& TSP_path) {
  //construct TSP_path
  assert(TSP_path[0] == 0);
  if (nowt < 9500) assert(TSP_path[(int)TSP_path.size()-1] == 0);
  rep2(i, 1, (int)TSP_path.size()-1) {
    assert(TSP_path[i] != 0);
  }
  /*
  rep(i, (int)TSP_ans.size()-1) {
    int now = TSP_ans[i].se;
    int nx = TSP_ans[i+1].se;
    rep(j, (int)path[now][nx].size()-1) {
      int pnow = path[now][nx][j];
      TSP_path.push_back(pnow);
    }
    tmp_nowt += d[now][nx];
    if (i+1 == (int)TSP_ans.size()-1) {
      assert(TSP_ans[i+1].se == 0);
      TSP_path.push_back(0);
    }
  }
  */
  //cerr << TSP_path.size() << endl;
  if (TSP_path.size() <= 10) return TSP_path;
  vector<int> tmp_TSP_path = TSP_path;
  //tmp_TSP_path = trans_minimum(tmp_TSP_path);
  /*
  cerr << tmp_TSP_path.size() << endl;
  bool used[n] = {};
  vector<int> uni_path = {0};
  used[0] = true;
  rep(i, (int)tmp_TSP_path.size()) {
    int v = tmp_TSP_path[i];
    if (used[v]) continue;
    uni_path.push_back(v);
    used[v] = true;
  }
  uni_path.push_back(0);
  cerr << uni_path.size() << endl;
  */
  //start SA;
  //double limit_time = 3000 * (double)tmp_TSP_path.size()/300;
  double limit_time = 3;

  double bestScore = sim(nowt, tmp_TSP_path);
  vector<int> bestPath = tmp_TSP_path;
  vector<int> best_removed;

  double curScore = bestScore;
  vector<int> curPath = tmp_TSP_path;
  vector<int> cur_removed;


  int R = INF;
  int loop = 0;
  double preScore = curScore;
  //cerr << "before Score : " << (ll)curScore << " path size : " << tmp_TSP_path.size() << endl;
  rep(_, 1) {
    double startTemp = 1;
    //if (peak - 500 <= nowt && nowt <= peak+500) startTemp = 10000;
    //if (nowt >= 9500) startTemp = 1000;
    double endTemp = 0;
    double st_time = get_time();
    //cerr << "SA loop : " <<  _ << endl;
    while (true) {
      if (!check_time()) return bestPath;
      loop++;
      //cerr << loop << endl;
      double t = get_time() - st_time;
      double temp = startTemp + (endTemp - startTemp) * t / limit_time;
      if (temp <= 0) break;
      vector<int> nextPath = curPath;
      vector<int> next_removed = cur_removed;
      /*
      pair<int, int> p = opt2_SA(nextScore, curPath);
      if (p.fi == -1 && p.se == -1) break;
      */
      double nextScore = NeighborSearch(nowt, nextPath, next_removed);
      double prob = exp((curScore - nextScore) / temp);
      bool FORCE = prob > (double)(Xor128() % R) / R;
      //bool FORCE = (curScore > nextScore);
      if (FORCE) {
        curScore = nextScore;
        curPath = nextPath;
        cur_removed = next_removed;
        if (curScore < bestScore) {
          bestScore = curScore;
          bestPath = curPath;
          best_removed = cur_removed;
        }
      }
      if (loop % 1000 == 0) {
        //cerr << "loop : " << loop << " curScore : " << (ll)curScore << " bestScore : " <<  (ll)bestScore << " temp :"<< temp << endl;
      }
    }
  }
  //cerr << "after Score :  " << (ll)bestScore << endl;
  cerr << "diff score : " << (ll)preScore-(ll)bestScore << endl;
  //cerr << "-----------" << endl;
  return bestPath;
}
/*
void optimize_tsp(vector<int>& TSP_path) {
  if ((int)TSP_path.size() == 3) return;
  //dump(TSP_path);
  int best_t = 0;
  int sz = TSP_path.size();
  rep(i, sz-1) best_t += d[TSP_path[i]][TSP_path[i+1]];
  //cerr << "pre : " << best_t << endl;
  double limt = get_time() + 200;
  while (get_time() < limt) {
    int u = Xor128() % sz;
    int v = Xor128() % sz;
    if (u > v) swap(u, v);
    int loop = 0;
    int loop_limit = 100;
    while (loop < loop_limit && (u == v || u == 0 || v == sz-1)) {
      loop++;
      u = Xor128() % sz;
      v = Xor128() % sz;
      if (u > v) swap(u, v);
    }
    if (loop == loop_limit) break;
    reverse(TSP_path.begin()+u, TSP_path.begin()+v+1);
    int tmp_t = 0;
    rep(i, sz-1) tmp_t += d[TSP_path[i]][TSP_path[i+1]];
    //cerr << tmp_t << " " << u << " " << v << endl;
    //dump(TSP_path);
    if (tmp_t < best_t) best_t = tmp_t;
    else reverse(TSP_path.begin()+u, TSP_path.begin()+v+1);
  }
  //dump(TSP_path);
  //cerr << "aft : " << best_t << endl;
  //cerr << "---------------" << endl;
}
*/


int delivery(double& score, int& nowt, vector<int>& ans, vector<vector<int>>& TSPS) {
  vector<int> DS;
  rep(i, n) {
    if ((int)order_info[i].size() == 0) continue;
    DS.push_back(i);
  }
  vector<pii> TSP_ans;
  vector<int> TSP_path;
  vector<int> best_TSP_path;
  //cerr << "heulistic_TSP" << endl;
  TSP_path = heulistic_TSP(nowt, DS);
  if ((int)TSP_path.size() == 2) return -2;
  best_TSP_path = TSP_path;
  //best_TSP_path = SA(nowt, TSP_path);
  //optimize_tsp(best_TSP_path);
  //best_TSP_path = trans_minimum(best_TSP_path);
  if ((int)best_TSP_path.size() <= 2) return -2;
  vector<int> next_TSP_path = {0};
  //set<pii> next_idS;
  //cerr << nowt << " " << best_TSP_path.size() << endl;
  int val = update_ans(score, nowt, best_TSP_path, ans, next_TSP_path);
  //cerr << nowt << endl;
  TSPS.push_back(next_TSP_path);
  //idS.push_back(next_idS);
  return val;
}

double simulate(int& next_t, vector<vector<int>>& next_TSPS, vector<int>& next_ans) {
  double tmp_score = 0;
  vector<vector<int>> tmp_order_info(n);
  vector<pii> tmp_new_order;
  vector<vector<int>> tmp_TSPS;
  //1段目
  while (next_t < T) {
    int id = order[next_t].fi;
    int v = order[next_t].se;
    if (id != -1) {
      order_info[v].push_back(id);
      break;
    }
    next_t++;
  }
  //2段目
  rep(i, (int)next_TSPS.size()) {
    rep(j, (int)next_TSPS[i].size()-1) {
      int now = next_TSPS[i][j];
      int nx = next_TSPS[i][j+1];
      rep(k, (int)path[now][nx].size()-1) {
        int pnow = path[now][nx][k];
        int pnx = path[now][nx][k+1];
        rep(l, d[pnow][pnx]) {
          next_ans[next_t++] = pnx;
          if (next_t > T) return -INF;
          int id = order[next_t].fi;
          int v = order[next_t].se;
          if (id != -1) {
            tmp_new_order.emplace_back(id, v);
          }
        }
        if (tmp_order_info[pnx].size() != 0) {
          assert(pnx != 0);
          for (int id : tmp_order_info[pnx]) {
            tmp_score += calc_value(next_t, id);
          }
          tmp_order_info[pnx].clear();
        }
      }
      //次の注文を受ける
      if (nx == 0) {
        for (pii p : tmp_new_order) {
          int id = p.fi;
          int v = p.se;
          tmp_order_info[v].push_back(id);
        }
        tmp_new_order.clear();
      }
    }

    bool update = false;
    rep(j, n) {
      if (tmp_order_info[j].size() != 0) update = true;
    }
    if (!update) {
      next_t++;
      while (next_t < T) {
        int id = order[next_t].fi;
        int v = order[next_t].se;
        if (id != -1) {
          tmp_order_info[v].push_back(id);
          break;
        }
        next_t++;
      }
    }
  }
  cerr << (ll)tmp_score << " " << next_t << endl;
  //3段目:0にもう帰らない戦略か, 0に変えることも含めた戦略か
  int sz = next_TSPS[(int)next_TSPS.size()-1].size();
  int now = next_TSPS[(int)next_TSPS.size()-1][sz-1];
  while (next_t < T) {
    bool update = false;
    rep(j, n) {
      if (tmp_order_info[j].size() != 0) update = true;
    }
    if (now == 0) {
      if (!update) {
        next_t++;
        while (next_t < T) {
          int id = order[next_t].fi;
          int v = order[next_t].se;
          if (id != -1) {
            tmp_order_info[v].push_back(id);
            break;
          }
          next_t++;
        }
      }
    }
    else {
      if (!update) {
        int nx = 0;
        rep(k, (int)path[now][nx].size()-1) {
          int pnow = path[now][nx][k];
          int pnx = path[now][nx][k+1];
          rep(l, d[pnow][pnx]) {
            next_ans[next_t++] = pnx;
            if (next_t > T) return tmp_score;
            int id = order[next_t].fi;
            int v = order[next_t].se;
            if (id != -1) {
              tmp_new_order.emplace_back(id, v);
            }
          }
          if (tmp_order_info[pnx].size() != 0) {
            assert(pnx != 0);
            for (int id : tmp_order_info[pnx]) {
              tmp_score += calc_value(next_t, id);
            }
            tmp_order_info[pnx].clear();
          }
          if (pnx == 0) {
            for (pii p : tmp_new_order) {
              int id = p.fi;
              int v = p.se;
              tmp_order_info[v].push_back(id);
            }
            tmp_new_order.clear();
          }
        }
      }
    }
    int nx = -1;
    int mn = INF;
    rep(i, n) {
      if ((int)tmp_order_info[i].size() == 0) continue;
      double ocnt = tmp_order_info[i].size();
      double cost = d[now][i] / ocnt;
      if (d[now][i]+next_t > T) continue;
      if (cost < mn) {
        mn = cost;
        nx = i;
      }
    }
    if (nx == -1) break;
    rep(k, (int)path[now][nx].size()-1) {
      int pnow = path[now][nx][k];
      int pnx = path[now][nx][k+1];
      rep(l, d[pnow][pnx]) {
        next_ans[next_t++] = pnx;
        int id = order[next_t].fi;
        int v = order[next_t].se;
        if (id != -1) {
          tmp_new_order.emplace_back(id, v);
        }
      }
      if (tmp_order_info[pnx].size() != 0) {
        assert(pnx != 0);
        for (int id : tmp_order_info[pnx]) {
          tmp_score += calc_value(next_t, id);
        }
        tmp_order_info[pnx].clear();
      }
      if (pnx == 0) {
        for (pii p : tmp_new_order) {
          int id = p.fi;
          int v = p.se;
          tmp_order_info[v].push_back(id);
        }
        tmp_new_order.clear();
        //breakすべき?
      }
    }
    now = nx;
  }
  cerr << (ll)tmp_score << " " << next_t << endl;
  cerr << "----------------" << endl;
  return tmp_score;
}

/*
double simulate(int& next_t, vector<vector<int>>& next_TSPS, vector<set<pii>>& cur_idS, vector<set<pii>>& next_idS, vector<int>& next_ans) {
  double tmp_score = 0;
  vector<vector<int>> tmp_order_info(n);
  vector<pii> tmp_new_order;
  vector<vector<int>> tmp_TSPS;
  set<pii> not_accept;
  //1段目
  while (next_t < T) {
    int id = order[nowt].fi;
    int v = order[nowt].se;
    if (id != -1) {
      order_info[v].push_back(id);
      break;
    }
    next_t++;
  }
  //2段目
  rep(i, (int)next_TSPS.size()) {
    rep(j, (int)next_TSPS[i].size()-1) {
      int now = next_TSPS[i][j];
      int nx = next_TSPS[i][j+1];
      //0を経由する可能性がある
      rep(k, (int)path[now][nx].size()-1) {
        int pnow = path[now][nx][k];
        int pnx = path[now][nx][k+1];
        rep(l, d[pnow][pnx]) {
          next_ans[next_t++] = pnx;
          if (next_t > T) return INF;
          int id = order[next_t].fi;
          int v = order[next_t].se;
          if (id != -1) {
            tmp_new_order.emplace_back(id, v);
          }
        }
        if (tmp_order_info[pnx].size() != 0) {
          assert(pnx != 0);
          for (int id : tmp_order_info[pnx]) {
            tmp_score += calc_value(next_t, id);
          }
          tmp_order_info[pnx].clear();
        }
      }
    }
    //次の注文を受ける
    if (nx == 0) {
      if (i == (int)next_TSPS.size()-1) {
        for (pii p : tmp_new_order) {
          int id = p.fi;
          int v = p.se;
          tmp_order_info[v].push_back(id);
        }
        tmp_new_order.clear();
        break;
      }
      vector<bool> next_erase(next_TSPS[i+1].size(), true);
      set<pii> priority_insert;
      next_erase[0] = false;
      next_erase[(int)next_TSPS[i+1].size()-1] = false;
      for (pii p : tmp_new_order) {
        int id = p.fi;
        int v = p.se;
        tmp_order_info[v].push_back(id);
        rep(k, (int)next_TSPS[i+1].size()) {
          if (next_TSPS[i+1][k] == v) {
            next_erase[k] = false;
          }
        }
        if (not_accept.find(p) != not_accept.end()) {
          not_accept.erase(p);
          priority_insert.insert(p);
        }
      }
      for (pii p : cur_idS[i+1]) {
        bool vainished = true;
        for (pii np : tmp_new_order) {
          if (p == np) {
            vainished = false;
            break;
          }
        }
        if (vainished) {
          not_accept.insert(p);
        }
      }
      tmp_new_order.clear();
      vector<pii> erase_pri;
      for (pii p : priority_insert) {
        int id = p.fi;
        int v = p.se;
        rep(k, (int)next_TSPS[i+1].size()) {
          if (next_TSPS[i+1][k] == v) {
            next_erase[k] = false;
            erase_pri.push_back(p);
          }
        }
      }
      for (pii p : erase_pri) {
        priority_insert.erase(p);
      }
      erase_pri.clear();
      //次のTSP
      vector<int> new_TSP;
      rep(k, (int)next_TSPS[i+1].size()) {
        if (next_erase[k]) continue;
        new_TSP.push_back(next_TSPS[i+1][k]);
      }
      int lim_d = 10000;
      for (pii p : priority_insert) {
        int mn = INF;
        int id = p.fi;
        int v = p.se;
        int ins = -1;
        rep2(k, 1, (int)new_TSP.size()-1) {
          int l = new_TSP[k];
          int r = new_TSP[k+1];
          int dist1 = d[l][r];
          int dist2 = d[l][v] + d[v][r];
          if (dist2 - dist1 <= lim_d) {
            if (dist2 - dist1 < mn) {
              mn = dist2 - dist1;
              ins = k;
            }
          }
        }
        if (ins == -1) continue;
        new_TSP.insert(new_TSP.begin()+ins, v);
        erase_pri.push_back(p);
      }
      for (pii p : erase_pri) {
        priority_insert.erase(p);
      }
      erase_pri.clear();
      next_TSPS[i+1] = new_TSP;
    }

    bool update = false;
    rep(j, n) {
      if (tmp_order_info[j].size() != 0) update = true;
    }
    if (!update) {
      assert((int)next_TSPS[i+1].size() == 2);
      next_t++;
      while (next_t < T) {
        int id = order[next_t].fi;
        int v = order[next_t].se;
        if (id != -1) {
          tmp_order_info[v].push_back(id);
          if (not_accept.find({id, v}) != not_accept.end()) {
            not_accept.erase({id, v});
          }
          break;
        }
        next_t++;
      }
    }
  }
  //3段目
  if ()
  while (next_t < T) {
    int id = order[next_t].fi;
    int v = order[next_t].se;
    if (id != -1) {
      order_info[v].push_back(id);
      break;
    }
    nowt++;
  }
  while (nowt < T) {
    bool update = delivery(score, nowt, ans, TSPS, idS);
    if (!update) {
      nowt++;
      while (nowt < T) {
        int id = order[nowt].fi;
        int v = order[nowt].se;
        if (id != -1) {
          order_info[v].push_back(id);
          break;
        }
        nowt++;
      }
    }
  }
  return tmp_score;
}
*/

double opt2(int& next_t, const int& p, vector<vector<int>>& next_TSPS, vector<int>& next_ans) {
  vector<int>& TSP_path = next_TSPS[p];
  if (TSP_path.size() == 2) return INF;
  int u = -1;
  int v = -1;
  int sz = TSP_path.size();
  int s = 0;
  int t = sz-1;
  int loop = 0;
  int limit_loop = 1000;
  while (loop < limit_loop && (u == v || u == s || v == t)) {
    loop++;
    u = Xor128() % sz;
    v = Xor128() % sz;
    if (u > v) swap(u, v);
  }
  if (loop == limit_loop) return INF;
  /*
  double diff_score = d[TSP_path[u-1]][TSP_path[u]] + d[TSP_path[v]][TSP_path[v+1]];
  Score -= diff_score;
  diff_score = d[TSP_path[u-1]][TSP_path[v]] + d[TSP_path[u]][TSP_path[v+1]];
  Score += diff_score;
  */
  int pret = 0;
  rep(i, (int)TSP_path.size()-1) {
    int now = TSP_path[i];
    int nx = TSP_path[i+1];
    pret += d[now][nx];
  }
  reverse(TSP_path.begin()+u, TSP_path.begin()+v+1);
  int aftt = 0;
  rep(i, (int)TSP_path.size()-1) {
    int now = TSP_path[i];
    int nx = TSP_path[i+1];
    aftt += d[now][nx];
  }
  if (pret < aftt) return INF;
  //TODO: 高速化

  return -simulate(next_t, next_TSPS,  next_ans);
}

double swap_2(int& next_t, const int& p, vector<vector<int>>& next_TSPS, vector<int>& next_ans) {
  vector<int>& TSP_path = next_TSPS[p];
  if (TSP_path.size() == 2) return INF;
  int u = -1;
  int v = -1;
  int sz = TSP_path.size();
  int s = 0;
  int t = sz-1;
  int loop = 0;
  int limit_loop = 1000;
  while (loop < limit_loop && (u == v || u == s || v == t)) {
    loop++;
    u = Xor128() % sz;
    v = Xor128() % sz;
    if (u > v) swap(u, v);
  }
  if (loop == limit_loop) return INF;
  int pret = 0;
  rep(i, (int)TSP_path.size()-1) {
    int now = TSP_path[i];
    int nx = TSP_path[i+1];
    pret += d[now][nx];
  }
  swap(TSP_path[u], TSP_path[v]);
  int aftt = 0;
  rep(i, (int)TSP_path.size()-1) {
    int now = TSP_path[i];
    int nx = TSP_path[i+1];
    aftt += d[now][nx];
  }
  if (pret < aftt) return INF;
  return -simulate(next_t, next_TSPS,  next_ans);
}

double or_opt(int& next_t, const int& p, vector<vector<int>>& next_TSPS, vector<int>& next_ans) {
  vector<int>& TSP_path = next_TSPS[p];
  if (TSP_path.size() == 2) return INF;
  int pret = 0;
  rep(i, (int)TSP_path.size()-1) {
    int now = TSP_path[i];
    int nx = TSP_path[i+1];
    pret += d[now][nx];
  }
  int len = 1+Xor128() % min((int)TSP_path.size()-2, 3);
  int l = Xor128() % TSP_path.size();
  int loop = 0;
  int limit = 1000;
  while (loop < limit && (l == 0 || l+len-1 >= (int)TSP_path.size()-1)) {
    loop++;
    l = Xor128() % TSP_path.size();
  }
  if (loop == limit) return INF;
  vector<int> tmp;
  vector<int> insP;
  rep(i, (int)TSP_path.size()) {
    if (l <= i && i < l + len)  {
      insP.push_back(TSP_path[i]);
    }
    else {
      tmp.push_back(TSP_path[i]);
    }
  }
  int ins = Xor128() % (int)tmp.size();
  loop = 0;
  while (loop < limit && (ins == 0 || ins == (int)tmp.size()-1)) {
    loop++;
    ins = Xor128() % (int) tmp.size();
  }
  if (loop == limit) return INF;
  for (auto x : insP) {
    tmp.insert(tmp.begin()+ins, x);
    ins++;
  }
  int aftt = 0;
  rep(i, (int)TSP_path.size()-1) {
    int now = TSP_path[i];
    int nx = TSP_path[i+1];
    aftt += d[now][nx];
  }
  if (pret < aftt) return INF;
  double ret = -simulate(next_t, next_TSPS, next_ans);
  //cerr << ret << endl;
  return ret;
}


double NeighborSearch(int& next_t, vector<vector<int>>& next_TSPS, vector<int>& next_ans) {
  int id = Xor128() % 3;
  int p = Xor128() % next_TSPS.size();
  double tmp_score = 0;
  /*
  if (id == 0) tmp_score = opt2(next_t, p, next_TSPS, cur_idS, next_idS, next_ans);
  else if (id == 1) tmp_score = swap_2(next_t, p, next_TSPS, cur_idS, next_idS, next_ans);
  else if (id == 2) tmp_score = or_opt(next_t, p, next_TSPS, cur_idS, next_idS, next_ans);
  */
  if (id == 0) tmp_score = opt2(next_t, p, next_TSPS, next_ans);
  else if (id == 1) tmp_score = swap_2(next_t, p, next_TSPS, next_ans);
  else if (id == 2) tmp_score = or_opt(next_t, p, next_TSPS, next_ans);
  return tmp_score;
}

void simulate1(double& next_score, int& next_t, vector<int>& next_TSP, vector<vector<int>>& next_order_info, vector<int>& next_ans) {
  vector<pii> tmp_new_order;
  rep(i, (int)next_TSP.size()-1) {
    int now = next_TSP[i];
    int nx = next_TSP[i+1];
    //cerr << next_t << " " << d[now][nx] << " " << now << " " << nx << endl;
    if (d[now][nx] + next_t > T) {

      next_score = -INF;
      return;
    }
    rep(j, (int)path[now][nx].size()-1) {
      int pnow = path[now][nx][j];
      int pnx = path[now][nx][j+1];
      rep(k, d[pnow][pnx]) {
        next_ans[next_t++] = pnx;
        int id = order[next_t].fi;
        int v = order[next_t].se;
        if (id != -1) {
          tmp_new_order.push_back(order[next_t]);
        }
      }
      if ((int)next_order_info[pnx].size() != 0) {
        for (int id : next_order_info[pnx]) {
          next_score += calc_value(next_t, id);
        }
        next_order_info[pnx].clear();
      }
      if (pnx == 0) {
        for (pii p : tmp_new_order) {
          next_order_info[p.se].push_back(p.fi);
        }
        tmp_new_order.clear();
      }
    }
  }
  return;
}

void opt2_1(double& next_score, int& now_t, vector<int>& TSP_path, vector<vector<int>>& next_order_info, vector<int>& next_ans) {
  if (TSP_path.size() == 2) {
    next_score = -INF;
    return;
  }
  int u = -1;
  int v = -1;
  int sz = TSP_path.size();
  int s = 0;
  int t = sz-1;
  int loop = 0;
  int limit_loop = 1000;
  while (loop < limit_loop && (u == v || u == s)) {
    loop++;
    u = Xor128() % sz;
    v = Xor128() % sz;
    if (u > v) swap(u, v);
  }
  if (loop == limit_loop) {
    next_score = -INF;
    return;
  }
  /*
  double diff_score = d[TSP_path[u-1]][TSP_path[u]] + d[TSP_path[v]][TSP_path[v+1]];
  Score -= diff_score;
  diff_score = d[TSP_path[u-1]][TSP_path[v]] + d[TSP_path[u]][TSP_path[v+1]];
  Score += diff_score;
  */
  reverse(TSP_path.begin()+u, TSP_path.begin()+v+1);
  //TODO: 高速化
  simulate1(next_score, now_t, TSP_path, next_order_info, next_ans);
}

void swap_2_1(double& next_score, int& now_t, vector<int>& TSP_path, vector<vector<int>>& next_order_info, vector<int>& next_ans) {
  if (TSP_path.size() == 2) {
    next_score = -INF;
    return;
  }
  int u = -1;
  int v = -1;
  int sz = TSP_path.size();
  int s = 0;
  int t = sz-1;
  int loop = 0;
  int limit_loop = 1000;
  while (loop < limit_loop && (u == v || u == s)) {
    loop++;
    u = Xor128() % sz;
    v = Xor128() % sz;
    if (u > v) swap(u, v);
  }
  if (loop == limit_loop) {
    next_score = -INF;
    return;
  }
  swap(TSP_path[u], TSP_path[v]);
  simulate1(next_score, now_t, TSP_path, next_order_info, next_ans);
}

void or_opt_1(double& next_score, int& now_t, vector<int>& TSP_path, vector<vector<int>>& next_order_info, vector<int>& next_ans) {
  if (TSP_path.size() == 2) {
    next_score = -INF;
    return;
  }
  int len = 1+Xor128() % min((int)TSP_path.size()-2, 3);
  int l = Xor128() % TSP_path.size();
  int loop = 0;
  int limit = 1000;
  while (loop < limit && (l == 0 || l+len-1 >= (int)TSP_path.size()-1)) {
    loop++;
    l = Xor128() % TSP_path.size();
  }
  if (loop == limit) {
    next_score = -INF;
    return;
  }
  vector<int> tmp;
  vector<int> insP;
  rep(i, (int)TSP_path.size()) {
    if (l <= i && i < l + len)  {
      insP.push_back(TSP_path[i]);
    }
    else {
      tmp.push_back(TSP_path[i]);
    }
  }
  int ins = Xor128() % (int)tmp.size();
  loop = 0;
  while (loop < limit && (ins == 0)) {
    loop++;
    ins = Xor128() % (int) tmp.size();
  }
  if (loop == limit) {
    next_score = -INF;
    return;
  }
  for (auto x : insP) {
    tmp.insert(tmp.begin()+ins, x);
    ins++;
  }
  simulate1(next_score, now_t, TSP_path, next_order_info, next_ans);
}

void swap_in_out(double& next_score, int& next_t, vector<int>& next_TSP, vector<vector<int>>& next_order_info, vector<int>& next_not_visited, vector<int>& next_ans) {
  int i_sz = next_TSP.size();
  int u = Xor128() % i_sz;
  int loop = 0;
  int limit = 100;
  while (loop < limit && u == 0) {
    loop++;
    u = Xor128() % i_sz;
  }
  if (loop == limit) {
    next_score = -INF;
    return;
  }
  int o_sz = next_not_visited.size();
  int v = Xor128() % o_sz;
  loop = 0;
  limit = 100;
  /*
  while (loop < limit) {
    //loop++;
    v = Xor128() % o_sz;
  }
  */
  if (loop == limit) {
    next_score = -INF;
    return;
  }
  swap(next_TSP[u], next_not_visited[v]);
  simulate1(next_score, next_t, next_TSP, next_order_info, next_ans);
}

void NeighborSearch1(double& next_score, int& next_t, vector<int>& next_TSP, vector<vector<int>>& next_order_info, vector<int>& next_not_visited, vector<int>& next_ans) {
  int id = Xor128() % 4;
  if (next_not_visited.size() == 0) id = Xor128() % 3;
  if (id == 0) opt2_1(next_score, next_t, next_TSP, next_order_info, next_ans);
  else if (id == 1) or_opt_1(next_score, next_t, next_TSP, next_order_info, next_ans);
  else if (id == 2) swap_2_1(next_score, next_t, next_TSP, next_order_info, next_ans);
  else if (id == 3) swap_in_out(next_score, next_t, next_TSP, next_order_info, next_not_visited, next_ans);
}


vector<int> solve() {
  double best_score = 0;
  vector<int> best_ans;
  vector<vector<int>> best_TSPS;
  //vector<set<pii>> best_idS;
  vector<int> best_TSP_start;
  vector<vector<vector<int>>> best_rec_order_info;
  vector<double> best_rec_score;
  int best_nowt =  0;
  timelimit = 20000;
  int loop = 0;
  while (check_time()) {
    loop++;
    double score = 0;
    int nowt = 0;
    vector<int> ans(T+1, -1);
    vector<vector<int>> TSPS;
    vector<int> TSP_start;
    //vector<set<pii>> idS;
    vector<vector<vector<int>>> rec_order_info;
    vector<double> rec_score;

    delivery_cnt = 0;
    rep(i, n) order_info[i].clear();
    while (nowt < T) {
      int id = order[nowt].fi;
      int v = order[nowt].se;
      if (id != -1) {
        order_info[v].push_back(id);
        break;
      }
      nowt++;
    }
    while (nowt < T) {
      //cerr << "will deliver " << nowt << endl;
      TSP_start.push_back(nowt);
      rec_order_info.push_back(order_info);
      rec_score.push_back(score);
      int update = delivery(score, nowt, ans, TSPS);
      if (update == 0) break;
      if (update == -2) {
        TSP_start.pop_back();
        rec_order_info.pop_back();
        rec_score.pop_back();
        nowt++;
        while (nowt < T) {
          int id = order[nowt].fi;
          int v = order[nowt].se;
          if (id != -1) {
            order_info[v].push_back(id);
            break;
          }
          nowt++;
        }
      }
      //cerr << "[now time] : " << nowt << " [delivery] : " << can_delivery.size() << endl;
      //peak付近でちょっと待つ
      /*
      double wait = 50;
      int plus_cnt = 0;
      rep2(t, 1, wait+1)  {
        if (t+nowt >= T) break;
        int id = order[nowt+t].fi;
        int v = order[nowt+t].se;
        if (id != -1) {
          plus_cnt++;
        }
      }
      //cerr << plus_cnt << endl;
      if (40 <= plus_cnt) {
        while (nowt < T && plus_cnt > 0) {
          nowt++;
          int id = order[nowt].fi;
          int v = order[nowt].se;
          if (id != -1) {
            plus_cnt--;
            order_info[v].push_back(id);
          }
        }
        while (nowt < T && peak-wait <= nowt && nowt <= peak+wait) {
          nowt++;
          if (nowt >= T) break;
          int id = order[nowt].fi;
          int v = order[nowt].se;
          if (id != -1) {
            order_info[v].push_back(id);
          }
        }
        if (!update) {
          nowt++;
          while (nowt < T) {
            int id = order[nowt].fi;
            int v = order[nowt].se;
            if (id != -1) {
              order_info[v].push_back(id);
              break;
            }
            nowt++;
          }
        }
      }
      */
    }
    if (best_score < score) {
      //cerr << "loop : " << loop << " score : " << (ll)score <<  " best_score : " << (ll)best_score << " order_cnt : " << order_cnt << " delivery_cnt : " << delivery_cnt << " delivery_rate : " << (double)delivery_cnt / order_cnt << endl;
      best_score = score;
      best_ans = ans;
      max_score = score;
      best_TSPS = TSPS;
      //best_idS = idS;
      best_TSP_start = TSP_start;
      best_rec_order_info = rec_order_info;
      best_nowt = nowt;
      best_rec_score = rec_score;
    }
  }
  //1
  timelimit = 24800;
  loop = 0;
  vector<int> cur_ans = best_ans;
  vector<vector<int>> cur_TSPS = best_TSPS;
  vector<int> cur_TSP_start = best_TSP_start;
  //vector<set<pii>> cur_idS = best_idS;
  vector<vector<vector<int>>> cur_rec_order_info = best_rec_order_info;
  vector<double> cur_rec_score = best_rec_score;
  double cur_score = best_score;

  //double startTemp = 50000000;
  //double endTemp = 0;
  //double st_time = get_time();
  //double SA_limit_time = timelimit-st_time;
  //int R = INF;
  bool BREAK_FORCE = false;
  double pre_score = best_score;
  while (check_time()) {
    //cerr << best_TSPS.size() << " " << best_TSP_start.size() << " " << best_rec_order_info.size() << " " << best_rec_score.size() << endl;
    //int rs = (int)best_TSPS.size()/2 + Xor128() % ((int)best_TSPS.size()/3); //rs番目のTSPから再スタート
    //double t = get_time() - st_time;
    //double temp = startTemp + (endTemp - startTemp) * t / SA_limit_time;
    //if (temp <= 0) break;
    int delta = 0;
    int rs = delta + Xor128() % ((int)cur_TSPS.size()-delta);
    loop++;
    double score = 0;
    int nowt = cur_TSP_start[rs];
    vector<int> ans(T+1, -1);
    rep(i, nowt) ans[i] = cur_ans[i];
    vector<vector<int>> TSPS;
    rep(i, rs) TSPS.push_back(cur_TSPS[i]);
    vector<int> TSP_start;
    rep(i, rs) TSP_start.push_back(cur_TSP_start[i]);
    //vector<set<pii>> idS;
    //rep(i, rs) idS.push_back(cur_idS[i]);
    //delivery_cnt = 0;
    bool wait = true;
    vector<vector<vector<int>>> rec_order_info;
    rep(i, rs) rec_order_info.push_back(cur_rec_order_info[i]);
    rep(i, n) {
      order_info[i] = cur_rec_order_info[rs][i];
      if ((int)order_info[i].size() > 0) wait = false;
    }
    vector<double> rec_score;
    rep(i, rs) rec_score.push_back(cur_rec_score[i]);
    score = cur_rec_score[rs];
    //cerr << "start score : " << score << endl;
    while (wait && nowt < T) {
      int id = order[nowt].fi;
      int v = order[nowt].se;
      if (id != -1) {
        order_info[v].push_back(id);
        break;
      }
      nowt++;
    }
    while (nowt < T) {
      //cerr << "will deliver " << nowt << endl;
      TSP_start.push_back(nowt);
      rec_order_info.push_back(order_info);
      rec_score.push_back(score);
      int update = delivery(score, nowt, ans, TSPS);
      if (update == 0) break;
      if (update == -2) {
        TSP_start.pop_back();
        rec_order_info.pop_back();
        rec_score.pop_back();
        nowt++;
        while (nowt < T) {
          int id = order[nowt].fi;
          int v = order[nowt].se;
          if (id != -1) {
            order_info[v].push_back(id);
            break;
          }
          nowt++;
        }
      }
    }
    //double prob = exp((-cur_score + score) / temp);
    //bool FORCE = prob > (double)(Xor128() % R) / R;
    bool FORCE = cur_score < score;
    //cerr << prob << " " << (ll)score << endl;
    if (FORCE || BREAK_FORCE) {
      BREAK_FORCE = false;
      cur_score = score;
      cur_TSPS = TSPS;
      cur_ans = ans;
      //cur_idS = idS;
      cur_TSP_start = TSP_start;
      cur_rec_order_info = rec_order_info;
      cur_rec_score = rec_score;
      //cur_idS = next_idS;
      if (best_score < score) {
        best_score = score;
        best_ans = ans;
        best_TSPS = TSPS;
        //best_idS = idS;
        best_TSP_start = TSP_start;
        best_rec_order_info = rec_order_info;
        best_nowt = nowt;
        best_rec_score = rec_score;
      }
    }
    if (loop % 100 == 0) {
      //if (cur_score == pre_score) BREAK_FORCE = true;
      //pre_score = cur_score;
      //cerr << "loop : " << loop << " score : " << (ll)score <<  " cur_score : " << (ll)cur_score << " best_score : " << (ll)best_score << endl;
    }
  }
  //cerr << "peak : " << peak << endl;
  //2
  int last = best_TSPS.size()-1;
  //dump(best_TSPS[last]);
  if (best_TSPS[last].back() != 0 || best_TSPS[last].back() == 0) {
    vector<int> cur_TSP = best_TSPS[last];
    vector<bool> visited(n, false);
    rep(i, (int)cur_TSP.size()) {
      visited[cur_TSP[i]] = true;
    }
    vector<int> cur_not_visited;
    rep(v, n) {
      if (best_rec_order_info[last][v].size() == 0) continue;
      if (visited[v]) continue;
      cur_not_visited.push_back(v);
    }
    //dump(cur_not_visited);
    double cur_score = best_score;
    vector<int> cur_ans = best_ans;
    //SA
    //cerr << "before : " << (ll)best_score << endl;
    timelimit = 29800;
    //vector<int> TSP_start;
    //vector<set<pii>> cur_idS = best_idS;

    double startTemp = 1000000;
    double endTemp = 0;
    double st_time = get_time();
    double SA_limit_time = timelimit - st_time;
    int R = INF;
    loop = 0;
    while (check_time()) {
      loop++;
      double t = get_time() - st_time;
      double temp = startTemp + (endTemp - startTemp) * t / SA_limit_time;
      if (temp <= 0) break;
      int start_t = best_TSP_start[last];
      vector<int> next_TSP = cur_TSP;
      vector<int> next_not_visited = cur_not_visited;
      vector<int> next_ans = cur_ans;
      rep2(t, start_t, T) next_ans[t] = -1;
      vector<vector<int>> next_order_info = best_rec_order_info[last];
      double next_score = best_rec_score[last];
      //cerr << (ll)next_score << " " << start_t << endl;
      NeighborSearch1(next_score, start_t, next_TSP, next_order_info,  next_not_visited, next_ans);
      double prob = exp((next_score - cur_score) / temp);
      bool FORCE = prob > (double)(Xor128() % R) / R;
      if (FORCE && start_t <= T) {
        cur_score = next_score;
        cur_TSP = next_TSP;
        cur_not_visited = next_not_visited;
        //cur_idS = next_idS;
        if (best_score < cur_score) {
          best_score = cur_score;
          best_ans = next_ans;
          //best_TSPS = cur_TSPS;
          //best_idS = cur_idS
        }
      }
      if (loop % 10000 == 0) {
        //cerr << loop << " " << (ll)next_score << " " << (ll)cur_score << endl;
      }
    }
    cerr << "after : " << (ll)best_score << endl;
  }
  return best_ans;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  seed(37);
  read();
  analysis();
  //cerr << "peak : " << peak << endl;
  //cerr << "read passed" << endl;
  calc_graph();
  //cerr << "calc_graph passed" << endl;
  //analysis();
  vector<int> ans = solve();
  //cerr << "solve passed" << endl;
  output(ans);
}


Measured memory_bytes: 24732