#include <iostream>
#include <cstdlib>

#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <iostream>
#include <fstream>
#include <unistd.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include "sys/time.h"
#ifdef LOCAL
#include <gd.h>
#include <gdfonts.h>
#endif
using namespace std;
#define HERE (cerr << "LINE: " << __LINE__ << " " << __FUNCTION__ << endl)

#define DBG(x) cerr << #x << ": " << x << endl

struct timeval timer_begin, timer_end;
uint64_t tsc_begin;
double sec_per_count = -1;
int timer_called;
inline uint64_t get_time_64() {
  uint32_t lo, hi;
  asm volatile ("rdtsc" : "=a" (lo), "=d" (hi));
  return (((uint64_t)hi << 32) | lo);
}

inline void timer_start() 
{
  timer_called++;
  gettimeofday(&timer_begin, NULL);
  tsc_begin = get_time_64();
}     
inline double timer_now() 
{
  if (sec_per_count < 0) {
    timer_called++;
    gettimeofday(&timer_end, NULL);         
    double duration = timer_end.tv_sec - timer_begin.tv_sec +
      (timer_end.tv_usec - timer_begin.tv_usec)/1000000.0;
    uint64_t tsc_duration = get_time_64() - tsc_begin;
    sec_per_count = duration / tsc_duration;
    DBG(1/sec_per_count);
  }
  return (get_time_64() - tsc_begin) * sec_per_count;
}

template<class T>
const T& clamp(const T& v,const T& lo,const T& hi) {
  return (v < lo) ? lo : (v > hi) ? hi : v;
}
template<typename T>
void assign_min_max(T& min,T& max,const T& x) {
  if (x < min)
    min = x;
  if (x > max)
    max = x;
}
unsigned int hash_function(unsigned long p) {
  // xor32()
  p ^= p<<7;
  p ^= p>>1;
  p ^= p<<25;
  unsigned int c = __builtin_popcount(p);
  return p<<c | p>>(32-c);
}
uint64_t hash_function64(uint64_t p) {
  // xor64()
  p ^= p<<16;
  p ^= p>>7;
  p ^= p<<39;
  uint64_t c = __builtin_popcount(p);
  return p<<c | p>>(64-c);
}  

struct xor128_t {
  uint64_t x, y, z, w;

  xor128_t(int seed=0) : x(123456789^seed) , y(362436069), z(521288629), w(88675123) {
    for (int i=0; i<48; i++)
      get();
  }

  void init(int seed) {
    x = 123456789^seed;
    y = 362436069;
    z = 521288629;
    w = 88675123;

    for (int i=0; i<48; i++)
      get();
  }

  inline uint64_t get() {
    uint64_t t=(x^(x<<11)); x=y; y=z; z=w;
    return (w=(w^(w>>19))^(t^(t>>8)));
  }

  inline uint64_t get(unsigned int sz) {
    if (sz <= 1)
      return 0;

    uint64_t x;
    const uint64_t mask = (1<<(ilogb(sz-1)+1)) - 1;
    //cout << sz << " " << mask << endl;
    assert(mask >= (sz-1) && mask < 2*sz-1);
    do {
      x = get() & mask;
    } while (x >= sz);

    return x;
  }

  inline int64_t get(int beg,int end) {
    return get(end-beg) + beg;
  }

  double get_double() {
    static const double double_factor = 1.0 / (1.0 + 0xffffffffffffffffuLL);
    return get() * double_factor;
  }

  double get_norm() {
    double a = get_double();
    double b = get_double();

    return sqrt(-2*log(a)) * cos(2*M_PI*b);
  }

  double get_gamma(double a) {
    if (a < 1.0) {
      return get_gamma(1+a) * pow(get_double(), 1/a);
    }
    
    double d = a - 1/3.0;
    double c = 1/sqrt(9.0 * d);

    while (true) {
      double x = get_norm();
      double uni = 1 - get_double();
      double v = (1.0+c*x)*(1.0+c*x)*(1.0+c*x);
      if (v > 0 && log(uni) < 0.5 * x*x + d - d*v + d*log(v))
	return d*v;
    }
  }

  template<typename T> void shuffle(vector<T>& v,int partial=-1) {
    int sz = v.size();
    if (partial < 0 || partial > sz)
      partial = sz;

    for (int i=0; i<partial; i++) {
      swap(v[i], v[i + get(sz-i)]);
    }
  }
  
  template<typename T> T sample(const vector<T>& v) {
    assert(!v.empty());
    return v[get(v.size())];
  }
};

// Van der Corput sequence
double vdc(int i,int base) {
  double result = 0;
  double f = 1;

  while (i > 0) {
    f /= base;
    result += f * (i%base);
    i = i/base;
  }

  return result;
}

struct uf_t {
  vector <int16_t> parent;

  void clear() {
    parent.clear();
  }

  void add(int elm) {
    if (elm >= parent.size()) 
      parent.resize(elm+1, -1);
  }

  void merge(int a,int b) {
    add(a);
    add(b);

    int ia = a;
    int ib = b;

    if ((ia^ib)&1) swap(ia, ib);  // ok?
      
    int ra = root(ia);
    int rb = root(ib);

    if (ra != rb) {
      parent[ra] += parent[rb];
      parent[rb] = ra;
    }
  }

  int size(int elm) {
    return -parent[root(elm)];
  }

  int id(int elm) {
    return root(elm);
  }

  int root(int ia) {
    add(ia);
    return (parent[ia] < 0) ? ia : (parent[ia] = root(parent[ia]));
  }
};

struct reusable_set_t {
  typedef uint8_t mark_t;
  mark_t mark;
  vector<mark_t> v;
  reusable_set_t() {}
  reusable_set_t(int n) : v(n), mark(1) {}

  void insert(int x) { v[x] = mark; }
  void erase(int x) { v[x] = mark-1; }
  int count(int x) const { return (v[x] == mark); }
  void clear() {
    mark++;
    if (mark == 0) {
      fill(v.begin(), v.end(), 0);
      mark ++;
    }
  }
};

struct sa_t {
  double ini, fin, inv_T, progress;
  int num_call, num_accept, num_better;
  xor128_t rng;
  sa_t() {}
  sa_t(double ini, double fin) : ini(ini), fin(fin), num_accept(0), num_call(0), num_better(0) {
    set_progress(0);
  }

  void set_progress(double x) {
    progress = clamp(x, 0.0, 1.0);
    inv_T = 1 / (ini * pow(fin/ini, progress));
  }

  bool acceptable(double x) {
    //bool result = (x > 0) || rng.get_double() < exp(x*inv_T);
    //bool result = (x > 0) || log(1-rng.get_double()) < x*inv_T;
    double z = x*inv_T;
    bool result = (x > 0) || (z > -12 && log(1-rng.get_double()) < z);

    //num_call ++;
    //num_accept += result;
    //num_better += (x > 0);

    return result;
  }

  void show_log() const {
    cerr << "better/accept/call: "
	 << num_better
	 << "/" << num_accept
	 << "/" << num_call 
	 << " " << (double)num_accept/num_call << endl;
  }
};


template <typename T>
struct pool_t {
  vector<T> v;
  int N;

  pool_t(int sz=0) : v(sz), N(0) {}

  void clear() { N = 0; }
  T& next() {
    N++;
    while (N >= v.size())
      v.resize(v.size()*11/10 + 1);
    return v[N-1];
  }

  typename vector<T>::iterator begin() { return v.begin(); }
  typename vector<T>::iterator end() { return v.begin()+N; }
  T& operator[](int i) { return v[i]; }
  size_t size() const { return N; }
  void resize(int sz) { assert(sz <= N); N = sz; }
  void swap(pool_t<T>& pl) {
    v.swap(pl.v);
    std::swap(N, pl.N);
  }
};

template <typename Score_t,typename Item_t,typename HashFunc_t>
struct best_k_t {
  vector<pair<Score_t,int>> v;
  vector<Item_t> items;
  HashFunc_t hashfunc;
  set<uint32_t> used;
  bool never_push;

  best_k_t() : never_push(false) {}

  void push_force(const Score_t sc,const Item_t& e) {
    int id = items.size();
    items.push_back(e);

    int n = v.size();
    v.push_back(pair<Score_t,int>(sc,id));

    int m = (n+1)/2 - 1;
    while (n > 0 && v[n] < v[m]) {
      swap(v[n], v[m]);
      n = m;
      m = (n+1)/2 - 1;
    }
  }

  bool push(const Score_t sc,const Item_t& e,int w) {
    assert(!never_push);
    if (v.size() < w) {
      auto h = hashfunc(e);
      if (!used.count(h)) {
	used.insert(h);
	push_force(sc, e);
	return true;
      } else {
	return false;
      }
    } else if (sc > v[0].first) {
      auto h = hashfunc(e);
      if (!used.count(h)) {
	int id = v[0].second;
	v[0].first = sc;
	items[id] = e;
	used.insert(h);
	rebuild();
	return true;
      } else {
	return false;
      }
    }
    return false;
  }

  bool match(const Score_t sc,int w) {
    return (v.size() < w || sc > v[0].first);
  }

  void rebuild() {
    int n = 0;
    while (true) {
      int L = (n+1)*2 - 1;
      int R = L+1;

      if (L >= v.size()) 
	break;

      int m = (R >= v.size() || v[L] < v[R]) ? L : R;

      if (v[m] < v[n]) {
	swap(v[m], v[n]);
	n = m;
      } else {
	break;
      }
    }
  }

  Item_t pop() {
    // fix me
    never_push = true;
    
    int id = v[0].second;
    Item_t ret = items[id];

    v[0] = v.back();
    v.pop_back();

    rebuild();

    return ret;
  }
  Item_t top() { return v[0].second; }

  Item_t best() const {
    int best_i = 0;
    for (int i=0; i<v.size(); i++) {
      if (v[i] < v[best_i])
	best_i = i;
    }
    return items[v[best_i].second];
  }

  void clear() { v.clear(); }
  bool empty() const { return v.empty(); }
  int size() const { return v.size(); }
};

template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[ ";
  for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " ]"; 
  return os; 
}
template<typename T> ostream& operator<<(ostream& os, const set<T>& v) {
  os << "{ ";
  for(typename set<T>::const_iterator it=v.begin(); it!=v.end(); ++it) {
    if (it != v.begin())
      os << ", ";
    os << *it; 
  }
  os << " }"; 
  return os; 
}
template<typename T1,typename T2> ostream& operator<<(ostream& os, const pair<T1,T2>& v) {
  os << "[ " << v.first << ", " << v.second << "]";
  return os; 
}

#ifdef LOCAL
double TIME_LIMIT_FACTOR = 0.55;
#else
double TIME_LIMIT_FACTOR = 1.0;
#endif
double TIME_LIMIT = TIME_LIMIT_FACTOR * 10.0;

/* insert here */
struct pos_t {
  double x, y;
  pos_t() : x(0), y(0) {}
  pos_t(double x,double y) : x(x), y(y) {}

  double distance_to(const pos_t& p) {
    double dx = x - p.x;
    double dy = y - p.y;
    return sqrt((dx*dx) + (dy*dy));
  }
};
ostream& operator<<(ostream& os,const pos_t& p) {
  char buf[256];
  sprintf(buf, "(%.3f,%.3f)", p.x, p.y);
  os << buf;
  return os;
}
bool is_opposite_side(const pos_t& a,const pos_t& b,
                      const pos_t& c,const pos_t& d) {
  double xab = b.x - a.x;
  double yab = b.y - a.y;
  double xac = c.x - a.x;
  double yac = c.y - a.y;
  double xad = d.x - a.x;
  double yad = d.y - a.y;

  return (xab*yac - yab*xac)*(xab*yad - yab*xad) < 0;
}

                           
bool is_intersect(const pos_t& a,const pos_t& b,
                  const pos_t& c,const pos_t& d) {
  return is_opposite_side(a, b, c, d) && is_opposite_side(c, d, a, b);
}

struct edge_t {
  int a, b, d;
};
ostream& operator<<(ostream& os,const edge_t& e) {
  os << "E" << e.a << "-" << e.b << "(" << e.d << ")";
  return os;
}

struct order_t {
  int t, id, dest;
};
ostream& operator<<(ostream& os,const order_t& o) {
  os << "o#" << o.id << "(" << o.dest << "@" << o.t << ")";
  return os;
}

struct testcase_t {
  int V, E;
  vector<edge_t> es;
  vector<int> freq;
  //vector<int> carrying;
  map<int,vector<int>> carrying;
  vector<order_t> os;
  int t_max;
  int ex_worst_delay;

  // read graph and t_max.
  // return: problem ID ('A' or 'B')
  char read_header(istream& is) {
    is >> V >> E;
    es.resize(E);
    for (int i=0; i<E; i++) {
      is >> es[i].a >> es[i].b >> es[i].d;
      es[i].a --;
      es[i].b --;
    }

    build_distance_table();
    calc_coordinates();
    make_groups();

    string s;
    getline(is, s);
    if (s.empty())
      getline(is, s);
    stringstream ss(s);
    if (find(s.begin(), s.end(), ' ') != s.end()) {
      freq.resize(V);
      for (int i=0; i<V; i++)
        ss >> freq[i];
      is >> t_max;
      return 'B';
    } else {
      ss >> t_max;
      return 'A';
    }
  }

  vector<int> ds;
  vector<int> via;
  void build_distance_table() {
    ds.resize(V*V, 1234567);
    via.resize(V*V);

    for (const auto& e : es) {
      ds[e.a*V+e.b] = e.d;
      ds[e.b*V+e.a] = e.d;
    }
    for (int i=0; i<V; i++)
      ds[i*V+i] = 0;

    for (int i=0; i<V; i++)
      for (int j=0; j<V; j++)
        via[i*V+j] = j;

    for (int k=0; k<V; k++)
      for (int i=0; i<V; i++)
        for (int j=0; j<V; j++) {
          if (ds[i*V+k]+ds[k*V+j] < ds[i*V+j]) {
            ds[i*V+j] = ds[i*V+k]+ds[k*V+j];
            via[i*V+j] = via[i*V+k];
          }
        }
  }

  vector<pos_t> ps;
  void calc_coordinates() {
#if 1
    vector<int> ds(V*V, 1234567);
    for (const auto& e : es) {
      ds[e.a*V+e.b] = 1;
      ds[e.b*V+e.a] = 1;
    }
    for (int i=0; i<V; i++)
      ds[i*V+i] = 0;

    for (int k=0; k<V; k++)
      for (int i=0; i<V; i++)
        for (int j=0; j<V; j++) {
          if (ds[i*V+k]+ds[k*V+j] < ds[i*V+j]) {
            ds[i*V+j] = ds[i*V+k]+ds[k*V+j];
          }
        }
#endif    
    int a = 0;
    for (int i=0; i<V; i++)
      if (ds[i] > ds[a])
        a = i;
    int b = a;
    for (int i=0; i<V; i++)
      if (ds[a*V+i] > ds[a*V+b])
        b = i;
    int u = b;
    for (int i=0; i<V; i++)
      if (ds[a*V+i]+ds[b*V+i] > ds[a*V+u]+ds[b*V+u])
        u = i;
    int c = u;
    for (int i=0; i<V; i++)
      if (ds[a*V+i]+ds[b*V+i]+ds[u*V+i] > ds[a*V+c]+ds[b*V+c]+ds[u*V+c])
        c = i;
    int d = c;
    for (int i=0; i<V; i++)
      if (ds[a*V+i]+ds[b*V+i]+ds[c*V+i] > ds[a*V+d]+ds[b*V+d]+ds[c*V+d])
        d = i;

    ps.resize(V);
    int mx = 0;
    double W = ds[a*V+c];
    xor128_t rng;
    for (int i=0; i<V; i++) {
      int x0 = ds[a*V+i]+ds[c*V+i]-ds[a*V+c];
      int x1 = ds[d*V+i]+ds[b*V+i]-ds[d*V+b];
      ps[i].x = 0.1 * rng.get_double() + W*(double)x0/(x0+x1);
      
      int y0 = ds[a*V+i]+ds[d*V+i]-ds[a*V+d];
      int y1 = ds[c*V+i]+ds[b*V+i]-ds[c*V+b];
      ps[i].y = 0.1 * rng.get_double() + W*(double)y0/(y0+y1);
    }

    {
      double sxy = 0;
      double sxx = 0;
      for (const auto& e : es) {
        double x = ps[e.a].distance_to(ps[e.b]);
        double y = 1;
        sxy += x*y;
        sxx += x*x;
      }
      double a = sxy / sxx;
      for (int i=0; i<V; i++) {
        ps[i].x *= a;
        ps[i].y *= a;
      }
    }
    //rng.shuffle(ps);
    
    vector<pos_t> vs(V);
    vector<map<int,double>> adjs(V);
    for (const auto& e : es) {
      adjs[e.a][e.b] = 1;
      adjs[e.b][e.a] = 1;
      //cerr << e.a << " " << e.b << " " << e.d << " : " << ps[e.a].distance_to(ps[e.b]) << endl;
    }
    
    for (int lp=0; lp<100; lp++) {
      double er2 = 0;
      double v2 = 0;
      vector<int> oo(V);
      for (int i=0; i<V; i++)
        oo[i] = i;
      rng.shuffle(oo);
      for (int i : oo) {
        for (int j=0; j<V; j++) {
          if (i == j)
            continue;
          if (adjs[i].count(j)) {
            double d = ps[i].distance_to(ps[j]);
            double e = adjs[i][j];

            //er2 += (e-floor(d))*(e-floor(d));
            
            //vs[i].x += 0.01 * (ps[i].x - ps[j].x)/d * (e-floor(d));
            //vs[i].y += 0.01 * (ps[i].y - ps[j].y)/d * (e-floor(d));
            
            er2 += (e-d)*(e-d);
            
            vs[i].x += 0.1 * (ps[i].x - ps[j].x)/d * (e-d);
            vs[i].y += 0.1 * (ps[i].y - ps[j].y)/d * (e-d);

          } else {
            double d = ps[i].distance_to(ps[j]);
            if (d < 1.2) {
              double e = 1.2;

              er2 += (e-d)*(e-d);
              
              vs[i].x += 0.1 * (ps[i].x - ps[j].x)/d * (e-d);
              vs[i].y += 0.1 * (ps[i].y - ps[j].y)/d * (e-d);
            }
          }
        }

        //cerr << lp << " " << i << " " << ps[i].x << " " << vs[i].x << endl;
        ps[i].x += vs[i].x;
        ps[i].y += vs[i].y;
        v2 += vs[i].x*vs[i].x + vs[i].y*vs[i].y;
        vs[i].x *= 0.3;
        vs[i].y *= 0.3;
      }
      if (__builtin_popcount(lp) == 1) {
        for (int a=0; a<V; a++) {
          for (const auto& pb : adjs[a]) {
            int b = pb.first;
            for (const auto& pc : adjs[b]) {
              int c = pc.first;
              if (c == a || c > b)
                continue;
              for (const auto& pd : adjs[c]) {
                int d = pd.first;
                if (d == a || d == b)
                  continue;

                if (is_intersect(ps[a], ps[b], ps[c], ps[d])) {
                  swap(ps[b], ps[c]);
                  swap(vs[b], vs[c]);
                  break;
                }
              }
            }
          }
        }
      }
    }

    double mnx = 1e234;
    double mxx = -1e234;
    double mny = 1e234;
    double mxy = -1e234;
    for (int i=0; i<ps.size(); i++) {
      assign_min_max(mnx, mxx, ps[i].x);
      assign_min_max(mny, mxy, ps[i].y);
    }
    for (int i=0; i<ps.size(); i++) {
      ps[i].x = (ps[i].x - mnx) / (mxx - mnx);
      ps[i].y = (ps[i].y - mny) / (mxy - mny);
    }
    cerr << "ps[0]: " << ps[0] << endl;

    
    if (false) {
      // graphviz DOT file
      auto tmp(ps);
      auto ps(tmp);
      rng.shuffle(ps);
      ofstream ofs("g.dot");
      ofs << "graph {" << endl;
      for (int i=0; i<V; i++) {
        ofs << "  v" << i+1 << " [pos=\""
            << ps[i].x << "," << ps[i].y << "\"];" << endl;
      }
      for (const auto& e : es) {
        ofs << "  v" << e.a+1 << " -- v" << e.b+1 << ";" << endl;
      }
      ofs << "}" << endl;
    }
    DBG(timer_now());

  }

  void read_turn_begin(istream& is,int t) {
    order_t o;
    o.t = t;     // FIXME
    int n;
    is >> n;
    for (int i=0; i<n; i++) {
      is >> o.id >> o.dest;
      o.dest --;
      os.push_back(o);
    }
    is >> n;
    for (int i=0; i<n; i++) {
      int oid;
      is >> oid;
      carrying[os[oid-1].dest].push_back(oid-1);
    }
  }

  vector<int> read_turn_end(istream& is) {
    string s;
    cin >> s;
    if (s.empty())
      cin >> s;      
    assert(s == "OK");
    int n;
    cin >> n;
    vector<int> delivered;
    for (int i=0; i<n; i++) {
      int oid;
      cin >> oid;
      delivered.push_back(oid-1);
    }

    return delivered;
  }
  
  void read_order(istream& is) {
    order_t o;
    int cnt = 0;
    for (int t=0; t<t_max; t++) {
      o.t = t;
      int n;
      is >> n;
      for (int i=0; i<n; i++) {
        cnt ++;
        is >> o.id >> o.dest;
        o.dest --;
        os.push_back(o);
      }
    }
    DBG(cnt);
  }

  vector<int> find_tsp(vector<int> perm) {
    // 2-opt TSP
    int N = perm.size() - 1;
    
    int best_d = 0;
    for (int i=0; i<N; i++)
      best_d += ds[perm[i]*V+perm[i+1]];
      
    sa_t sa(100.0, 0.1);
    for (int lp=0; lp<=100; lp++) {
      sa.set_progress(lp/100.0);      
      for (int a=0; a<N; a++) {
        int b = a+1;
        for (int c=b+1; c<N; c++) {
          int d = c+1;

          int cur = ds[perm[a]*V+perm[b]] + ds[perm[c]*V+perm[d]];
          int nxt = ds[perm[a]*V+perm[c]] + ds[perm[b]*V+perm[d]];

          if (sa.acceptable(cur - nxt)) {
            reverse(perm.begin()+b, perm.begin()+d);
            best_d = best_d - cur + nxt;
          }
        }
      }
      //DBG(best_d);
    }

    return perm;
  }
  
  vector<int> find_tsp2(vector<int> perm) {
    // 2-opt TSP
    int N = perm.size() - 1;
    
    int best_d = 0;
    for (int i=0; i<N; i++) {
      best_d += 10000*ds[perm[i]*V+perm[i+1]];
      best_d += (ds[perm[i]*V+perm[i+1]] < ds[perm[i]] + ds[perm[i+1]]);
    }
      
    sa_t sa(100.0*10000, 0.1);
    for (int lp=0; lp<=100; lp++) {
      sa.set_progress(lp/100.0);      
      for (int a=0; a<N; a++) {
        int b = a+1;
        for (int c=b+1; c<N; c++) {
          int d = c+1;

          int cur = ds[perm[a]*V+perm[b]] + ds[perm[c]*V+perm[d]];
          int nxt = ds[perm[a]*V+perm[c]] + ds[perm[b]*V+perm[d]];

          cur *= 10000;
          cur += (ds[perm[a]*V+perm[b]] < ds[perm[a]] + ds[perm[b]]);
          cur += (ds[perm[c]*V+perm[d]] < ds[perm[c]] + ds[perm[d]]);
          nxt *= 10000;
          nxt += (ds[perm[a]*V+perm[c]] < ds[perm[a]] + ds[perm[c]]);
          nxt += (ds[perm[b]*V+perm[d]] < ds[perm[b]] + ds[perm[d]]);

          if (sa.acceptable(cur - nxt)) {
            reverse(perm.begin()+b, perm.begin()+d);
            best_d = best_d - cur + nxt;
          }
        }
      }
    }

    if (false) {
      int best_d = 0;
      for (int i=0; i<N; i++) {
        best_d += 10000*ds[perm[i]*V+perm[i+1]];
        best_d += (ds[perm[i]*V+perm[i+1]] < ds[perm[i]] + ds[perm[i+1]]);
        cerr << perm[i]+1 << "->" << perm[i+1]+1 << " : "
             << ds[perm[i]*V+perm[i+1]] << " " << ds[perm[i]] + ds[perm[i+1]]
             << endl;
      }
      DBG(best_d);
    }      

    return perm;
  }
  
  vector<int> find_good_tour2(const map<int,vector<int>>& cs,
                              const map<int,vector<int>>& extra,
                              const int t0,bool final=false) {
    // 2-opt TSP
    cerr << "find_good_tour2: " << cs.size() << " @"  << t0 << endl;
    int N = cs.size() + 1;
    
    vector<int> perm;
    perm.push_back(0);
    for (const auto& pa : cs) {
      perm.push_back(pa.first);
    }
    perm.push_back(0);

    perm = find_tsp(perm);
    DBG(perm_to_path(perm).size());

    auto calc_cost = [&](const vector<int>& perm) {
      int64_t cost = 0;
      int t = t0;
      for (int i=0; i<N; i++) {
        t += ds[perm[i]*V+perm[i+1]];
        if (perm[i+1] > 0) {
          for (const auto& oid : cs.at(perm[i+1])) {
            if (t > t_max)
              cost += (int64_t)t_max * t_max;
            else
              cost += (int64_t)(t - os[oid].t)*(t - os[oid].t);
          }
        }
      }
      //return cost + (int64_t)perm.size()*(t - t0)*(t - t0);
      //return make_pair(t-t0, cost);
      //return cost;
      auto ex = (int64_t)(t - t0)*(t - t0)*(t - t0);
      if (t0 > 9500)
        ex = 0;
      ex += (int64_t)(extra.size() - cs.size())*(t - t0)*(t - t0);
      
      return cost + ex;
    };

    auto cur_cost = calc_cost(perm);
    auto best_cost = cur_cost;
    auto best_perm = perm;
    int cur_d = 0;
    for (int i=0; i+1<perm.size(); i++)
      cur_d += ds[perm[i]*V+perm[i+1]];
    int best_d = cur_d;
      
    //cerr << best_cost << " " << best_d << endl;    
    sa_t sa(1e8, 0.1);
    for (int lp=0; lp<=100; lp++) {
      sa.set_progress(lp/100.0);
      bool modified = false;
      for (int a=0; a<N; a++) {
        int b = a+1;
        for (int c=b+1; c<N; c++) {
          int d = c+1;

          int cur = ds[perm[a]*V+perm[b]] + ds[perm[c]*V+perm[d]];
          int nxt = ds[perm[a]*V+perm[c]] + ds[perm[b]*V+perm[d]];
          if (cur-nxt < -10)
            continue;

          reverse(perm.begin()+b, perm.begin()+d);
          auto nxt_cost = calc_cost(perm);

          //cerr << lp << " " << a << " " << c << " " << cur_cost - nxt_cost << endl;

          if (sa.acceptable(cur_cost - nxt_cost)) {
            modified = true;
            cur_cost = nxt_cost;
            cur_d = cur_d - cur + nxt;
            if (cur_cost < best_cost) {
              best_cost = cur_cost;
              best_perm = perm;
              best_d = cur_d;
            }
          } else {
            reverse(perm.begin()+b, perm.begin()+d);
          }
        }
      }
      cerr << best_cost << " " << best_d << endl;
      if (!modified)
        break;
    }
    //reverse(perm.begin(), perm.end());
    perm = best_perm;

    // yorimichi
    for (const auto& ex : extra) {
      int e = ex.first;
      if (cs.count(e))
        continue;

      int best_i;
      int best_ex = 12345;
      for (int i=0; i+1<perm.size(); i++) {
        int p = perm[i];
        int q = perm[i+1];
        //if (ds[p*V+e] + ds[e*V+q] <= ds[p*V+q]) {
        int ex = ds[p*V+e] + ds[e*V+q] - ds[p*V+q];
        if (ex < best_ex) {
          best_i = i;
          best_ex = ex;
        }
      }
      if (best_ex <= 1) {
        cerr << "ex: " << best_ex << " " << e << " " << endl;
        perm.insert(perm.begin()+best_i+1, e);
      }
    }
    
    vector<int> tour;
    {
      if (false) {
        for (int i=perm.size()/3+1; i+1<2*perm.size()/3; i++) {
          
          if (ds[perm[i]] <= ds[perm[i-1]] &&
              ds[perm[i]] <= ds[perm[i+1]] &&
              ds[perm[i]] <= 10) {
            perm.insert(perm.begin()+i, 0);
            i += 10;
          }
        }
      }

      
      for (int i=0; i+1+((final)?1:0)<perm.size(); i++) {
        int p = perm[i];
        int q = perm[i+1];
        while (p != q) {
          int v = via[p*V+q];
          for (int j=0; j<ds[p*V+v]; j++) {
            tour.push_back(v);
            //assert(tour.size() <= best_d);
          }

          p = v;
        }
      }
    }

    HERE;
    return tour;
  }

  map<int,vector<int>> choose_sub(const map<int,vector<int>>& carrying) {
    int worst_d = -1234567;
    int worst_dest = 0;
    for (const auto& pa : carrying) {
      for (int oid : pa.second) {
        int d = ds[pa.first] - os[oid-1].t;
        if (d > worst_d) {
          worst_d = d;
          worst_dest = pa.first;
        }
      }
    }
    auto carrying2(carrying);
    carrying2.clear();
    for (const auto& pa :carrying) {
#if 1
      int p = pa.first;
      int d1 = ds[worst_dest*V+p];
      int d2 = ds[p] + ds[worst_dest];
      if (2*d1 < d2) {
        carrying2.insert(pa);
      }
#else
      int p = pa.first;
      int q = worst_dest;
      if (ds[p] < ds[q])
        swap(p, q);
      int d1 = ds[p];
      int d2 = ds[q] + ds[q*V+p];
      if (d2 < d1+10)
        carrying2.insert(pa);
#endif
    }
    DBG(worst_dest+1);

    return carrying2;
  }

  vector<vector<int>> groups;
  vector<int> inv_group;
  void make_groups() {
    auto pa = make_groups_sub1();
    DBG(pa.first);
#if 0
    auto pa2 = make_groups_sub2();
    DBG(pa2.first);
    if (pa2.first-20*pa2.second.size() < pa.first-20*pa.second.size()) 
      pa = pa2;

    auto pa3 = make_groups_sub3();
    DBG(pa3.first);
    if (pa3.first-20*pa3.second.size() < pa.first-20*pa.second.size()) 
      pa = pa3;
#endif
    auto pa4 = make_groups_subK();
    DBG(pa4.first);
    if (pa4.first < pa.first) 
      pa = pa4;

    DBG(pa.first);
    groups = pa.second;

    inv_group.resize(V);
    for (int g=0; g<groups.size(); g++)
      for (const auto& x : groups[g])
        inv_group[x] = g;
  }

  pair<int, vector<vector<int>>> make_groups_sub1() {
    vector<vector<int>> subs;

    subs.resize(4);

    int a = 0;
    for (int i=0; i<V; i++)
      if (ds[i] > ds[a])
        a = i;
    int b = a;
    for (int i=0; i<V; i++)
      if (ds[a*V+i] > ds[a*V+b])
        b = i;
    int u = b;
    for (int i=0; i<V; i++)
      if (ds[a*V+i]+ds[b*V+i] > ds[a*V+u]+ds[b*V+u])
        u = i;
    int c = u;
    for (int i=0; i<V; i++)
      if (ds[a*V+i]+ds[b*V+i]+ds[u*V+i] > ds[a*V+c]+ds[b*V+c]+ds[u*V+c])
        c = i;
    int d = c;
    for (int i=0; i<V; i++)
      if (ds[a*V+i]+ds[b*V+i]+ds[c*V+i] > ds[a*V+d]+ds[b*V+d]+ds[c*V+d])
        d = i;

    vector<vector<int>> cc(4);
    for (int i=0; i<V; i++) {
      int la = ds[i] + ds[i*V+a] - ds[a];
      int lb = ds[i] + ds[i*V+b] - ds[b];
      int lc = ds[i] + ds[i*V+c] - ds[c];
      int ld = ds[i] + ds[i*V+d] - ds[d];
      vector<int> v = {la, lb, lc, ld};
      //for (int j=0; j<4; j++) { v[j] = v[j]*4 + (i+j)%4; }
      for (int j=0; j<4; j++) { v[j] = v[j]*(i+1) + subs[j].size(); }
        
      auto idx = min_element(v.begin(), v.end()) - v.begin();

      subs[idx].push_back(i);
    }

    {
      vector<int> perm;
      int sum = 0;
      int delay_max = 0;
      for (int i=0; i<4; i++) {
        perm.clear();
        perm.push_back(0);
        perm.insert(perm.end(), subs[i].begin(), subs[i].end());
        perm.push_back(0);
        perm = find_tsp(perm);
        auto path = perm_to_path(perm);
        //draw(path);
        cerr << "Group" << i << " c:" << subs[i].size() << " tsp:" << path.size() << endl;
        sum += path.size();
        delay_max = max(delay_max, (int)path.size());
      }
      ex_worst_delay = sum + delay_max;
      DBG(ex_worst_delay);
    }

    return make_pair(ex_worst_delay, subs);
  }
  
  pair<int, vector<vector<int>>> make_groups_subK() {
    // k-means
    const int K = 4;
    vector<vector<int>> subs(K);
    vector<pos_t> cs(K);
    for (int i=0; i<K; i++)
      cs[i] = ps[i+1];

    for (int lp=0; lp<10; lp++) {
      for (int g=0; g<K; g++)
        subs[g].clear();

      for (int i=1; i<V; i++) {
        double best_d = 1e234;
        int best_g = 0;
        for (int g=0; g<K; g++) {
          auto d = ps[i].distance_to(cs[g]);
          if (d < best_d) {
            best_g = g;
            best_d = d;
          }
        }
        subs[best_g].push_back(i);
      }

      for (int g=0; g<K; g++) {
        cs[g].x = cs[g].y = 0;
        for (const auto& x : subs[g]) {
          cs[g].x += ps[x].x;
          cs[g].y += ps[x].y;
        }
        cs[g].x /= subs[g].size();
        cs[g].y /= subs[g].size();
        //cerr << g << " " << cs[g] << " " << subs[g].size() << endl;
      }
    }

    {
      vector<int> perm;
      int sum = 0;
      int delay_max = 0;
      for (int i=0; i<K; i++) {
        perm.clear();
        perm.push_back(0);
        perm.insert(perm.end(), subs[i].begin(), subs[i].end());
        perm.push_back(0);
        perm = find_tsp(perm);
        auto path = perm_to_path(perm);
        //draw(path);
        cerr << "Group" << i << " c:" << subs[i].size() << " tsp:" << path.size() << endl;
        sum += path.size();
        delay_max = max(delay_max, (int)path.size());
      }
      ex_worst_delay = sum + delay_max;
      DBG(ex_worst_delay);
    }
    //exit(1);

    return make_pair(ex_worst_delay, subs);
  }
  
  pair<int, vector<vector<int>>> make_groups_sub2() {
    vector<vector<int>> subs;

    vector<vector<int>> perms;
    vector<int> lens;
    int total_len = 0;

    vector<int> perm1, perm2;
    for (int i=0; i<V; i++)
      perm1.push_back(i);
    perm1.push_back(0);
    perm1 = find_tsp(perm1);
    perms.push_back(perm1);
    lens.push_back(route_length(perm1));
    total_len = lens.back();

    while (true) {
      bool modified = false;
      assert(perms.size() < V);
      for (int idx=0; idx<lens.size(); idx++) {
        cerr << idx << "/" << perms.size() << " " << lens[idx] << endl;
        
        perm1.clear();
        perm2.clear();
        perm2.push_back(0);
        int i;
        int l = 0;
        for (i=0; i+1<perms[idx].size(); i++) {
          if (l + ds[perms[idx][i]*V+perms[idx][i+1]] > lens[idx]/2)
            break;
          l += ds[perms[idx][i]*V+perms[idx][i+1]];
          perm1.push_back(perms[idx][i]);
        }
        for (/**/; i+1<perms[idx].size(); i++) {
          perm2.push_back(perms[idx][i]);
        }
        perm1.push_back(0);
        perm2.push_back(0);

        if (perm1.size() <= 2 || perm2.size() <= 2)
          continue;

        perm1 = find_tsp(perm1);
        perm2 = find_tsp(perm2);
        int l1 = route_length(perm1);
        int l2 = route_length(perm2);

        int l0 = lens[idx];
        lens[idx] = 0;
        int ex_worst_cur = l0 + l0;
        int ex_worst_nxt = l1+l2 + max(max(l1, l2), *max_element(lens.begin(), lens.end()));
        cerr << "l1l2: " << l1 << " " << l2 << endl;
        DBG(ex_worst_cur);
        DBG(ex_worst_nxt);
        double val_cur = 0;
        double val_nxt = 0;
        for (int i=0; i<subs.size(); i++) {
          if (i == idx)
            continue;
          val_cur += (double)(total_len+lens[i])*(total_len+lens[i]) * perms[i].size();
          val_nxt += (double)(total_len+l1+l2-l0+lens[i])*(total_len+l1+l2-l0+lens[i]) * perms[i].size();
        }
        val_cur += (double)(total_len+l0)*(total_len+l0) * perms[idx].size();
        val_nxt += (double)(total_len+l1+l2)*(total_len+l1+l2) * perms[idx].size();
          
        if (ex_worst_nxt <= ex_worst_cur) {
          //if (val_nxt <= val_cur) {
          total_len = total_len - l0 + l1+l2;
          modified = true;
          perms[idx] = perm1;
          lens[idx] = l1;
          perms.push_back(perm2);
          lens.push_back(l2);
        } else {
          lens[idx] = l0;
        }
      }
      if (!modified)
        break;
    }
    subs.resize(perms.size());

    set<int> used;
    int ex_worst_delay = 0;
    for (int i=0; i<perms.size(); i++) {
      subs[i].insert(subs[i].end(), perms[i].begin()+1, perms[i].end()-1);
      cerr << "Group" << i << " c:" << subs[i].size() << " tsp:" << lens[i] << endl;      
      for (int x : subs[i]) {
        used.insert(x);
      }
      ex_worst_delay += lens[i];
    }
    ex_worst_delay += *max_element(lens.begin(), lens.end());
    
    return make_pair(ex_worst_delay, subs);
  }

  pair<vector<int>, vector<int>> find_tsp_division(vector<int> perm) {
    int N = perm.size() - 1;
    int mid = perm.size()/2;
    perm.insert(perm.begin()+mid, 0);

    vector<int> acc(N+2);

    for (int i=0; i<=N; i++)
      acc[i+1] = acc[i] + ds[perm[i]*V+perm[i+1]];

    int left = acc[mid];
    int right = acc[N+1] - acc[mid];

    sa_t sa(10000.0, 0.1);
    for (int lp=0; lp<=100; lp++) {
      sa.set_progress(lp/100.0);
      for (int a=0; a<N; a++) {
        int b = a+1;
        for (int c=b+1; c<N; c++) {
          int d = c+1;

          assert(perm[mid] == 0);

          int left2 = left;
          int right2 = right;

          if (mid <= a) {
            right2 -= ds[perm[a]*V+perm[b]] + ds[perm[c]*V+perm[d]];
            right2 += ds[perm[a]*V+perm[c]] + ds[perm[b]*V+perm[d]];
          } else if (mid >= d) {
            left2 -= ds[perm[a]*V+perm[b]] + ds[perm[c]*V+perm[d]];
            left2 += ds[perm[a]*V+perm[c]] + ds[perm[b]*V+perm[d]];
          } else {
            left2 = acc[a] + ds[perm[a]*V+perm[c]] + acc[c] - acc[mid];
            right2 = (acc[N+1] - acc[d]) + ds[perm[b]*V+perm[d]] + acc[mid] - acc[b];
          }

          //if (left2*left2 + right2*right2 < left*left + right*right) {
          if (sa.acceptable((left*left + right*right) - (left2*left2 + right2*right2))) {
            left = left2;
            right = right2;
                       
            reverse(perm.begin()+b, perm.begin()+d);
            //cerr << left*left + right*right << " " << left << " " << right << endl;
            if (mid >= b && mid <= c) {
              mid = b+c - mid;
            }
            for (int i=0; i<=N; i++)
              acc[i+1] = acc[i] + ds[perm[i]*V+perm[i+1]];

            {
#if 0              
              DBG(a);
              DBG(c);
              DBG(mid);
              DBG(perm[mid]);
#endif              
              int left3 = 0;
              int right3 = 0;
              for (int i=0; i<mid; i++)
                left3 += ds[perm[i]*V+perm[i+1]];
              for (int i=mid; i+1<perm.size(); i++)
                right3 += ds[perm[i]*V+perm[i+1]];
#if 0
              DBG(left);
              DBG(right);
              DBG(left3);
              DBG(right3);
#endif
              assert(left3 == left);
              assert(right3 == right);
            }
            
          }
        }
      }
    }

    auto it = find(perm.begin()+1, perm.end(), 0);
    assert(it != perm.end());
    vector<int> perm1(perm.begin(), it+1);
    vector<int> perm2(it, perm.end());

    return make_pair(perm1, perm2);
  }

  pair<int, vector<vector<int>>> make_groups_sub3() {
    vector<vector<int>> subs;

    vector<vector<int>> perms;
    vector<int> lens;
    int total_len = 0;

    vector<int> perm1, perm2;
    for (int i=0; i<V; i++)
      perm1.push_back(i);
    perm1.push_back(0);
    perm1 = find_tsp(perm1);
    perms.push_back(perm1);
    lens.push_back(route_length(perm1));
    total_len = lens.back();

    while (true) {
      bool modified = false;
      assert(perms.size() < V);
      int sz = lens.size();
      for (int idx=0; idx<sz; idx++) {
        cerr << idx << "/" << perms.size() << " " << lens[idx] << endl;

        tie(perm1, perm2) = find_tsp_division(perms[idx]);
        if (perm1.size() <= 2 || perm2.size() <= 2)
          continue;
        
        int l1 = route_length(perm1);
        int l2 = route_length(perm2);

        int l0 = lens[idx];
        lens[idx] = 0;
        int ex_worst_cur = l0 + l0;
        int ex_worst_nxt = l1+l2 + max(max(l1, l2), *max_element(lens.begin(), lens.end()));
        cerr << "l1l2: " << l1 << " " << l2 << endl;
        DBG(ex_worst_cur);
        DBG(ex_worst_nxt);
        double val_cur = 0;
        double val_nxt = 0;
        for (int i=0; i<subs.size(); i++) {
          if (i == idx)
            continue;
          val_cur += (double)(total_len+lens[i])*(total_len+lens[i]) * perms[i].size();
          val_nxt += (double)(total_len+l1+l2-l0+lens[i])*(total_len+l1+l2-l0+lens[i]) * perms[i].size();
        }
        val_cur += (double)(total_len+l0)*(total_len+l0) * perms[idx].size();
        val_nxt += (double)(total_len+l1+l2)*(total_len+l1+l2) * perms[idx].size();
          
        if (ex_worst_nxt <= ex_worst_cur || sz<8) {
          //if (val_nxt <= val_cur) {
          total_len = total_len - l0 + l1+l2;
          modified = true;
          perms[idx] = perm1;
          lens[idx] = l1;
          perms.push_back(perm2);
          lens.push_back(l2);
        } else {
          lens[idx] = l0;
        }
      }
      if (!modified)
        break;
    }
    subs.resize(perms.size());

    set<int> used;
    int ex_worst_delay = 0;
    for (int i=0; i<perms.size(); i++) {
      subs[i].insert(subs[i].end(), perms[i].begin()+1, perms[i].end()-1);
      cerr << "Group" << i << " c:" << subs[i].size() << " tsp:" << lens[i] << endl;      
      for (int x : subs[i]) {
        used.insert(x);
      }
      ex_worst_delay += lens[i];

      auto path = perm_to_path(perms[i]);
    }
    ex_worst_delay += *max_element(lens.begin(), lens.end());
    
    return make_pair(ex_worst_delay, subs);
  }

  map<int,vector<int>> choose_sub2(const map<int,vector<int>>& carrying,int t0) {
    assert(!groups.empty());
    
#if 1
    int worst_d = -1234567;
    int worst_dest = 0;
    for (const auto& pa : carrying) {
      for (int oid : pa.second) {
        int d = (t0 + ds[pa.first]) - os[oid-1].t;
        if (d > worst_d) {
          worst_d = d;
          worst_dest = pa.first;
        }
      }
    }
    auto carrying2(carrying);
    carrying2.clear();
    for (int x : groups[inv_group[worst_dest]]) {
      if (carrying.count(x))
        carrying2[x] = carrying.at(x);
    }
    cerr << "worst_dest: " << worst_dest+1 << " delay: " << worst_d
         << " G" << inv_group[worst_dest]
         << "(sz:" << groups[inv_group[worst_dest]].size() << ")"
         << endl;
    //return carrying2;
#endif
#if 1
    int64_t worst_sum = 0;
    int64_t worst_g = 0;
    for (int g=0; g<groups.size(); g++) {
      int64_t sum = 0;
      int num = 0;
      for (int x : groups[g]) {
        if (carrying.count(x)) {
          for (int oid : carrying.at(x)) {
            int d = (t0 + ds[x]) - os[oid-1].t;
            d += 500;
            sum += (int64_t)d*d;
            num ++;
          }
        }
      }
      cerr << g << " " << sum << "/" << num << endl;
      if (sum > worst_sum) {
        worst_g = g;
        worst_sum = sum;
      }
    }
    {
      auto carrying2(carrying);
      carrying2.clear();
      for (int x : groups[worst_g]) {
        if (carrying.count(x))
          carrying2[x] = carrying.at(x);
      }
      cerr << " G" << worst_g
           << "(sz:" << groups[worst_g].size() << ")"
           << endl;
      return carrying2;
    }
#endif
#if 0
    static int gid = 0;
    for (int i=0; i<groups.size(); i++, gid=(gid+1)%groups.size())
      if (any_of(groups[gid].begin(), groups[gid].end(), [&](int x){
            return carrying.count(x);
          })) {
          auto carrying2(carrying);
          carrying2.clear();
          for (int x : groups[gid]) {
            if (carrying.count(x))
              carrying2[x] = carrying.at(x);
          }
          gid = (gid+1)%groups.size();
          return carrying2;
        }

    return carrying;
#endif    
  }

  int route_length(const vector<int>& perm) {
    int d = 0;
    for (int i=0; i+1<perm.size(); i++)
      d += ds[perm[i]*V+perm[i+1]];

    return d;
  }

  vector<int> perm_to_path(const vector<int>& perm) {
    vector<int> path;
    for (int i=0; i+1<perm.size(); i++) {
      int p = perm[i];
      int q = perm[i+1];
      while (p != q) {
        int x = via[p*V+q];
        for (int j=0; j<ds[p*V+x]; j++)
          path.push_back(x);
        p = x;
      }
    }

    return path;
  }
  
  void run_B(istream& is) {

    int64_t sum = 0;
    int delivered_num = 0;
    int cur = 0;
    vector<int> tour;
    for (int t=0; t<t_max; t++) {
      read_turn_begin(is, t);

      if (!tour.empty()) {
        int x = tour.back();
        tour.pop_back();
        cout << x+1 << endl;
        //cerr << "@" << t << " " << x+1 << " " << ps[x] << endl;
      } else if (!carrying.empty()) {
        vector<int> v;

        if (t < 0.95*t_max) {
          auto carrying2 = choose_sub2(carrying, t);
          tour = find_good_tour2(carrying2, carrying, t);
        } else {
          tour = find_good_tour2(carrying, carrying, t);
        }
        
        reverse(tour.begin(), tour.end());
        int x = tour.back();
        tour.pop_back();
        cout << x+1 << endl;
        //cerr << "@" << t << " " << x+1 << " " << ps[x] << endl;
      } else {
        cout << -1 << endl;
      }

      auto delivered = read_turn_end(is);
      if (!delivered.empty()) {
        int dest;
        for (int i=0; i<delivered.size(); i++) {
          int delay = t - os[delivered[i]].t + 1;
          sum += t_max*t_max - delay*delay;
          delivered_num ++;

          dest = os[delivered[i]].dest;
        }
        carrying.erase(dest);
      }
    }
    DBG(sum);
    int undelivered = os.size() - delivered_num;
    DBG(undelivered);
  }

  void run_A(istream& is) {
    read_order(is);

    if (false) {
      vector<int> perm;
      for (int i=0; i<V; i++)
        perm.push_back(i);
      perm.push_back(0);
      HERE;
      perm = find_tsp2(perm);
      auto path = perm_to_path(perm);
      DBG(path.size());

      {
        vector<vector<int>> subs;
        vector<int> inv(V);
        subs.resize(4);

        int a = 0;
        for (int i=0; i<V; i++)
          if (ds[i] > ds[a])
            a = i;
        int b = a;
        for (int i=0; i<V; i++)
          if (ds[a*V+i] > ds[a*V+b])
            b = i;
        int u = b;
        for (int i=0; i<V; i++)
          if (ds[a*V+i]+ds[b*V+i] > ds[a*V+u]+ds[b*V+u])
            u = i;
        int c = u;
        for (int i=0; i<V; i++)
          if (ds[a*V+i]+ds[b*V+i]+ds[u*V+i] > ds[a*V+c]+ds[b*V+c]+ds[u*V+c])
            c = i;
        int d = c;
        for (int i=0; i<V; i++)
          if (ds[a*V+i]+ds[b*V+i]+ds[c*V+i] > ds[a*V+d]+ds[b*V+d]+ds[c*V+d])
            d = i;

        for (int i=0; i<V; i++) {
          int la = ds[i] + ds[i*V+a] - ds[a];
          int lb = ds[i] + ds[i*V+b] - ds[b];
          int lc = ds[i] + ds[i*V+c] - ds[c];
          int ld = ds[i] + ds[i*V+d] - ds[d];
          vector<int> v = {la, lb, lc, ld};
          //for (int j=0; j<4; j++) { v[j] = v[j]*4 + (i+j)%4; }
          for (int j=0; j<4; j++) { v[j] = v[j]*(i+1) + subs[j].size(); }
        
          auto idx = min_element(v.begin(), v.end()) - v.begin();
          subs[idx].push_back(i);
          inv[i] = idx;
        }

        {
          int sum = 0;
          for (int i=0; i<4; i++) {
            auto perm(subs[i]);
            perm.insert(perm.begin(), 0);
            perm.push_back(0);
            perm = find_tsp2(perm);
            auto path = perm_to_path(perm);

            cerr << "G" << i << " " << path.size() << endl;
            sum += path.size();
          }
          DBG(sum);
        }
      }
      
      
      //draw(path);
      exit(1);
    }

    vector<int> path;
    int idx = 0;
    int t = 0;
    int64_t sc = 0;
    int delivered = 0;
    //map<int,vector<int>> carrying;    
    while (idx < os.size()) {
      if (t < os[idx].t) {
        path.push_back(-2);
        t++;
      } else {
        cerr << "=====" << endl;
        while (idx < os.size() && os[idx].t <= t) {
          carrying[os[idx].dest].push_back(os[idx].id);
          idx ++;
        }
        double tm = timer_now();
        vector<int> tour;

        if (t < 0.95*t_max) {
          DBG(carrying.size());
          //auto carrying2 = choose_sub2(carrying, t);
          auto carrying2 = choose_sub2(carrying, t);
          tour = find_good_tour2(carrying2, carrying, t);
          DBG(carrying2.size());
          DBG(tour.size());
          vector<int> tour2;
          for (int i=0; tour2.size()<10 && i<tour.size(); i++)
            if (tour2.empty() || tour2.back() != tour[i]+1)
              tour2.push_back(tour[i]+1);
          DBG(tour2);
          //draw(tour);
        } else {
          tour = find_good_tour2(carrying, carrying, t);
        }
          
        
        DBG(timer_now() - tm);
        DBG(tour.size());
        //draw(tour);

        for (int i=0; i<tour.size(); i++) {
          if (i-1 >= 0 && tour[i-1] != tour[i]) {
            int cur_node = tour[i-1];
            for (const auto& oid : carrying[cur_node]) {
              if (t < t_max) {
                int delay = t - os[oid-1].t;
                sc += t_max*t_max - delay*delay;
                delivered ++;
                if (delay > ex_worst_delay) {
                  cerr << "!!! " << t << " " << os[oid-1] << " " << delay << endl;
                }
              }
            }
            carrying.erase(cur_node);
          }
          
          path.push_back(tour[i]);
          t ++;
          if (i+1 < tour.size() && tour[i] == 0 && tour[i+1] != 0) {
            cerr << i+1 << "/" << tour.size() << endl;
            break;
          }
        }
      }
    }
    if (!carrying.empty()) {
      auto tour = find_good_tour2(carrying, carrying, t);

      for (int i=0; i<tour.size(); i++) {
        if (i-1 >= 0 && tour[i-1] != tour[i]) {
          int cur_node = tour[i-1];
          for (const auto& oid : carrying[cur_node]) {
            if (t < t_max) {
              sc += t_max*t_max - (t - os[oid-1].t)*(t - os[oid-1].t);
              delivered ++;
              //cerr << "delivered: " << t << " " << os[oid-1] << endl;
            }
          }
          carrying.erase(cur_node);
        }
          
        path.push_back(tour[i]);
        t ++;
      }
    }

    path.resize(t_max, -2);
    DBG(sc);
    DBG(os.size());
    DBG(sqrt(t_max*t_max - sc/os.size()));
    int undelivered = os.size() - delivered;
    DBG(undelivered);

    //draw(path);
    for (const auto& x : path)
      cout << x+1 << endl;
  }
  
  void run_A_or_B(istream& is) {
    auto ret = read_header(is);
    cerr << "problem: " << ret << endl;
    if (ret == 'A') {
      run_A(is);
    } else {
      run_B(is);
    }
  }

#ifdef LOCAL
  void draw(vector<int> path,const vector<int>& dests={}) const {
    path.insert(path.begin(), 0);
    static int file_id = 0;

    double mnx = 1e234;
    double mxx = -1e234;
    double mny = 1e234;
    double mxy = -1e234;
    for (int i=0; i<ps.size(); i++) {
      assign_min_max(mnx, mxx, ps[i].x);
      assign_min_max(mny, mxy, ps[i].y);
    }
    
    double W = 1600;
    
    int beg = 0;
    gdImagePtr img = gdImageCreateTrueColor(W+20, W+20);

    bool redraw = true;
    char buf[256];
    for (int i=0; i<=path.size(); i++) {
      if (i==path.size() ||
          i > 0 && path[i-1] != 0 && path[i] == 0) {
        for (int i=0; i<V; i++) {
          int x = 10 + W * (ps[i].x - mnx)/(mxx - mnx);
          int y = 10 + W * (ps[i].y - mny)/(mxy - mny);
          int u = i;
          if (u > 0 && !dests.empty() && find(dests.begin(), dests.end(), i) == dests.end())
            u = -1;
          sprintf(buf, "%d", i+1);
          int dx = (i+1 < 10) ? 4 : (i+1 < 100) ? 6 : 9;
          int col =
            (u+1 == 0) ? 0xccffff :
            (u+1 == 1) ? 0xffcccc : 0xccffcc;

          gdImageFilledRectangle(img, x-dx-2, y-5, x+dx, y+6, col);
          gdImageRectangle(img, x-dx-2, y-5, x+dx, y+6, 0x000000);
          gdImageString(img, gdFontSmall, x-dx, y-5, (unsigned char*)buf, 0x000000);
        }

        char fname[256];
        sprintf(fname, "images/out%04d.png", file_id);
        file_id ++;
        FILE *fp = fopen(fname, "wb");
        assert(fp);
        gdImagePng(img, fp);
        fclose(fp);

        redraw = true;
      }

      if (redraw) {
        redraw = false;
        gdImageFilledRectangle(img, 0, 0, W+20, W+20, 0xffffff);
        for (const auto& e : es) {
          int x1 = 10 + W * (ps[e.a].x - mnx)/(mxx - mnx);
          int y1 = 10 + W * (ps[e.a].y - mny)/(mxy - mny);
          int x2 = 10 + W * (ps[e.b].x - mnx)/(mxx - mnx);
          int y2 = 10 + W * (ps[e.b].y - mny)/(mxy - mny);

          gdImageLine(img, x1, y1, x2, y2, 0x888888);

          sprintf(buf, "%d", ds[e.a*V+e.b]);
          gdImageString(img, gdFontSmall, (x1+x2)/2 - 4, (y1+y2)/2, (unsigned char*)buf, 0x000000);
        }
      }

      if (i+1 < path.size()) {
        auto p = max(path[i], 0);
        auto q = max(path[i+1], 0);
        if (p != q) {
          auto it = find_if(es.begin(), es.end(), [&](const edge_t& e) {
                return (e.a == p && e.b == q) || (e.b == p && e.a == q);
            });
          if (it == es.end()) {
            cerr << "no edge: " << p+1 << " " << q+1 << endl;
            DBG(path);
            assert(false);
          } else {
            //cerr << *it << endl;
          }
          
          int x1 = 10 + W * (ps[p].x - mnx)/(mxx - mnx);
          int y1 = 10 + W * (ps[p].y - mny)/(mxy - mny);
          int x2 = 10 + W * (ps[q].x - mnx)/(mxx - mnx);
          int y2 = 10 + W * (ps[q].y - mny)/(mxy - mny);

          gdImageLine(img, x1, y1, x2, y2, 0xff0000);
          {
            int sx = (x1+2*x2)/3;
            int sy = (y1+2*y2)/3;
            int ex = (x1+4*x2)/5;
            int ey = (y1+4*y2)/5;

            int dx = ((ey - sy)*4+3)/7;
            int dy = ((sx - ex)*4+3)/7;

            gdPoint pp[3];
            pp[0].x = ex;
            pp[0].y = ey;
            pp[1].x = sx + dx;
            pp[1].y = sy + dy;
            pp[2].x = sx - dx;
            pp[2].y = sy - dy;
            gdImageFilledPolygon(img, pp, 3, 0xff0000);
          }
        }
      }
    }
    gdImageDestroy(img);
  }
#endif
};


int main()
{
  timer_start();
  testcase_t tc;

  tc.run_A_or_B(cin);

  return 0;
}


Measured memory_bytes: 2304