#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cerr << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace Input
{
	int V, E;
	vector<pair<int, PII>> edges;
	int Tmax;
	vector<vector<PII>> info;
	
	void read()
	{
		cin >> V >> E;
		edges.resize(E);
		for(auto& i: edges) cin >> i.Y.X >> i.Y.Y >> i.X;
		cin >> Tmax;
		info.resize(Tmax);
		for(auto& i: info)
		{
			int x;
			cin >> x;
			i.resize(x);
			for(auto& j: i)
				cin >> j.X >> j.Y;
		}
	};
};

namespace Grader
{	
	namespace Random
	{			
		const size_t MIN_N = 200;
		const size_t MAX_N = 400;

		const size_t MIN_C = 1;
		const size_t MAX_C = 100;

		const size_t TIME_LIMIT = 10000;
		const size_t TIME_LAST = static_cast<size_t>(TIME_LIMIT * 0.95);

		const size_t INDEXED = 1;

		const size_t MAX_DEGREE = 5;

		const size_t MIN_N_ORDER = 0;
		const size_t MAX_N_ORDER = 1;

		const size_t MIN_ID = 1;
		const size_t MAX_ID = TIME_LAST + 1;

		const size_t MIN_FREQ = 1;
		const size_t MAX_FREQ = 2;

		const size_t SCALE_HIGHWAY = 2;
		const size_t SCALE_ROAD = 4;

		const size_t NUM_OF_CASE = 2;
		class random_number : private std::mt19937_64 {
		public:
		  using uint64 = uint64_t;
		  using uint32 = uint32_t;
		  using int64 = int64_t;
		  using int32 = int32_t;
		  using std::mt19937_64::mt19937_64;
		  using std::mt19937_64::operator();

		  uint64 next_ulong();                   // [0, 2^{64})
		  uint64 next_ulong(uint64 m);           // [0, m)
		  uint64 next_ulong(uint64 a, uint64 b); // [a, b]

		  uint32 next_uint();                    // [0, 2^{32})
		  uint32 next_uint(uint32 m);            // [0, m)
		  uint32 next_uint(uint32 a, uint32 b);  // [a, b]

		  int64 next_long();                     // [0, 2^{63})
		  int64 next_long(int64 m);              // [0, m)
		  int64 next_long(int64 a, int64 b);     // [a, b]

		  int32 next_int();                      // [0, 2^{31})
		  int32 next_int(int32 m);               // [0, m)
		  int32 next_int(int32 a, int32 b);      // [a, b]

		  double next_double();                  // [0, 1)

		  template <typename random_access_iterator>
		  void shuffle(random_access_iterator l, random_access_iterator r); // [l, r)
		};

		using uint64 = random_number::uint64;
		using uint32 = random_number::uint32;
		using int64 = random_number::int64;
		using int32 = random_number::int32;

		uint64 random_number::next_ulong() {
		  return (*this)();
		}
		uint64 random_number::next_ulong(uint64 m) {
		  assert(m > 0);
		  return next_ulong() % m;
		}
		uint64 random_number::next_ulong(uint64 a, uint64 b) {
		  return next_ulong(b - a + 1) + a;
		}

		uint32 random_number::next_uint() {
		  return static_cast<uint32>(next_ulong() & 0xFFFFFFFFUL);
		}
		uint32 random_number::next_uint(uint32 m) {
		  assert(m > 0);
		  return next_uint() % m;
		}
		uint32 random_number::next_uint(uint32 a, uint32 b) {
		  return next_uint(b - a + 1) + a;
		}

		int64 random_number::next_long() {
		  return static_cast<int64>(next_ulong() & 0x7FFFFFFFFFFFFFFFUL);
		}
		int64 random_number::next_long(int64 m) {
		  assert(m > 0);
		  return next_long() % m;
		}
		int64 random_number::next_long(int64 a, int64 b) {
		  return next_long(b - a + 1) + a;
		}

		int32 random_number::next_int() {
		  return static_cast<int32>(next_ulong() & 0x7FFFFFFFUL);
		}
		int32 random_number::next_int(int32 m) {
		  assert(m > 0);
		  return next_int() % m;
		}
		int32 random_number::next_int(int32 a, int32 b) {
		  return next_int(b - a + 1) + a;
		}

		double random_number::next_double() {
		  int32 p = next_int();
		  return 1.0 * p / std::numeric_limits<int32>::max();
		}

		template <typename random_access_iterator>
		void random_number::shuffle(random_access_iterator l, random_access_iterator r) {
		  for(random_access_iterator itr=l; itr!=r; itr++) {
			std::iter_swap(l + next_uint(itr - l + 1), itr);
		  }
		}
	};

	using namespace Random;

	namespace Graph
	{		
		class edge {
		public:
		  using cost_type = int_fast64_t;
		  static const cost_type INF = 1LL << 28;
		  
		  size_t src, dst;
		  cost_type cost;
		  
		  edge() : cost(INF) {}
		  edge(size_t u, size_t v, cost_type c) : src(u), dst(v), cost(c) {}
		};

		const edge::cost_type INF = 1 << 28;

		template <typename edge_type>
		class graph {
		public:
		  using cost_type = typename edge_type::cost_type;
		  std::vector< std::vector<edge_type> > g;
		  std::vector<cost_type> f; // frequency

		  graph() = default;
		  graph(size_t N) : g(N), f(N) {}
		  graph(size_t N, const std::vector<cost_type> freq) : g(N), f(freq) { sort_edges(); }
		  graph(const graph &g_) : g(g_.g), f(g_.f) { sort_edges(); }
		  size_t size() const { return g.size(); }
		  const std::vector<edge_type>& operator[](int k) const { return g[k]; }
		  std::vector<edge_type>& operator[](int k) { return g[k]; }

		  void add_edge(size_t u, size_t v, size_t c) {
			g[u].emplace_back(u, v, c);
		  }

		  void sort_edges() {
			for(size_t i=0; i<g.size(); i++) {
			  std::sort(g[i].begin(), g[i].end(), [](edge_type a, edge_type b) {
			  return a.dst < b.dst;
			});
			}
		  }

		  // 頂点 u と直接結ばれている辺であって、端点が v であるもの (のインデックス) を返す
		  size_t find(size_t u, size_t v) const {
			size_t lb = 0, ub = g[u].size();
			while(ub - lb > 1) {
			  size_t mid = (ub + lb) >> 1;
			  if(g[u][mid].dst <= v) lb = mid;
			  else ub = mid;
			}

			if(g[u][lb].dst == v) return lb;
			else return -1;
		  }
		};

	};

	namespace State
	{			
		using namespace Graph;
		class order {
		public:
		  using order_num_type = int_fast64_t;
		private:
		  static const order_num_type na;
		  order_num_type id, dst, start_time, end_time;
		  
		public:
		  order();
		  order(order_num_type id_, order_num_type dst_,
			order_num_type start_time_, order_num_type end_time_);
		  order(order_num_type id_, order_num_type dst_,
			order_num_type start_time_);

		  bool complete_order();

		  order_num_type duration();

		  void register_end_time(order_num_type t);

		  std::tuple<order_num_type, order_num_type, order_num_type, order_num_type> get_order_info() const;
		};

		using o_nt = order::order_num_type;
		const o_nt order::na = -1;

		order::order() = default;
		order::order(o_nt id_, o_nt dst_,
				 o_nt start_time_, o_nt end_time_) :
		  id(id_), dst(dst_), start_time(start_time_), end_time(end_time_) {}
		order::order(o_nt id_, o_nt dst_,
				 o_nt start_time_) :
		  id(id_), dst(dst_), start_time(start_time_), end_time(na) {}

		bool order::complete_order() {
		  return end_time != na;
		}

		o_nt order::duration() {
		  if(!complete_order()) return -1;
		  return end_time - start_time;
		}

		void order::register_end_time(o_nt t) {
		  assert(end_time == na);
		  end_time = t;
		}

		std::tuple<o_nt, o_nt, o_nt, o_nt> order::get_order_info() const {
		  return std::make_tuple(id, dst, start_time, end_time);
		}


				
		class agent {
		public:
		  enum AGENT_STATE {
			ON_EDGE = 1,
			ON_VERTEX = 2,
		  };

		protected:
		  // ON_EDGE: u と v を結ぶ辺上にいて、u から d 離れた地点にいる
		  // ON_VERTEX: u 上にいる
		  AGENT_STATE agent_state;
		  size_t ep_1, ep_2;
		  edge::cost_type agent_pos, edge_length;

		public:
		  // 店 は 0 番目の頂点
		  agent() = default;
		  agent(size_t v) : agent_state(ON_VERTEX),
					ep_1(v), ep_2(-1),
					agent_pos(0), edge_length(-1) {}

		  void change_agent_state(size_t x) {
			agent_state = ON_VERTEX;
			ep_1 = x, ep_2 = -1;
			agent_pos = 0, edge_length = -1;
		  }
		  void change_agent_state(size_t x, size_t y,
					  edge::cost_type c, edge::cost_type d) {
			assert(abs(c - agent_pos) == 1);

			agent_state = ON_EDGE;
			ep_1 = x, ep_2 = y;
			agent_pos = c, edge_length = d;

			// agent_pos が 0 の場合は x に到達している
			if(agent_pos == 0) {
			  change_agent_state(x);
			  return;
			}

			// agent_pos が d の場合は y に到達している
			if(agent_pos == d) {
			  change_agent_state(y);
			  return;
			}
		  }

		  // 現在地から v に向けて進むことが valid であるか
		  template <typename graph_type>
		  bool is_valid_move(const graph_type &g, size_t v) {
			if(agent_state == ON_EDGE) {
			  if(ep_1 == v and
			 0 <= agent_pos - 1 and agent_pos - 1 <= edge_length)
			return true;
			  if(ep_2 == v and
			 0 <= agent_pos + 1 and agent_pos + 1 <= edge_length)
			return true;
			
			  return false;
			}
			else if(agent_state == ON_VERTEX) {
			  return g.find(ep_1, v) != size_t(-1);
			}
			else assert(false);
		  }

		  // 現在地から v に向けて 1 進める (agent の情報を更新)
		  // あくまで移動させるだけであり、その他の情報更新は別
		  // (辺の長さが 1 の時がやばいと思うので注意)
		  template <typename graph_type>
		  void proceed(const graph_type &g, size_t v) {
			assert(is_valid_move(g, v));
			
			// 辺上にあるときの移動
			if(agent_state == ON_EDGE) {
			  if(ep_1 == v) {
			change_agent_state(ep_1, ep_2, agent_pos - 1, edge_length);
			  }
			  if(ep_2 == v) {
			change_agent_state(ep_1, ep_2, agent_pos + 1, edge_length);
			  }
			}
			// 頂点上にあるときの移動
			else if(agent_state == ON_VERTEX) {
			  size_t edge_idx = g.find(ep_1, v);
			  edge::cost_type len = g[ep_1][edge_idx].cost;
			  change_agent_state(ep_1, v, 1, len);
			}
		  }
		};

		class state : public agent {
		public:
		  using time_type = int_fast64_t;
		  using query_type = int;
		  using order_num_type = order::order_num_type;
		  using score_type = int_fast64_t;
		  
		  static const std::string OK_STR;
		  static const std::string NG_STR;
		  const size_t depot_index;

		  graph<edge> G;

		  // 発生した注文をすべて記録 (id を 1-indexed にするために、先頭にダミー注文を入れる)
		  std::vector<order> order_list;
		  // グラフの、depot 以外の頂点それぞれについて未処理の注文を記録
		  std::vector< std::set<order_num_type> > pending_order_list;
		  // depot の頂点について、商品が agent に受け渡されていない注文を記録
		  // agent について、その時点で保有している商品に対応する注文を記録
		  std::set<order_num_type> depot_order_list, agent_order_list;
		  time_type current_time, max_time;

		  // コンテスタントのコマンド
		  std::vector<int> commands;
		  // 事前に与えられる注文の情報
		  std::vector< std::vector<order> > given_order_info;
		  
		  state(const graph<edge> &G_, const time_type &max_time_,
			std::vector<int> commands_,
			std::vector< std::vector<order> > given_order_info_,
			size_t v);

		  double prob_by_time();
		  order_num_type next_dst();
		  
		  // コンテスタントから命令を受け取る・コマンドの判定結果を出す
		  query_type input_by_agent();
		  void output_verdict(std::string verdict);

		  // 注文をランダムに追加する
		  // (追加されたものは注文リストに追加し、コンテスタントに向けて出力)
		  void get_order();

		  // 現在地に応じて情報を更新
		  // - agent が持つ商品が増える (depot にある商品が減る)
		  // - agent が注文を処理し終える (各頂点にある未処理の注文が減り、終了時刻が記録される)
		  void get_removed_order_list();
		  void get_completed_order_list();
		  
		  // ステップ数を 1 進める
		  // (コンテスタントから命令を受け取る・進める・状態更新・時間情報更新)
		  // 不正な入力を受け取った時など、正常に終了しない時に false を返す
		  bool increment_step();

		  // スコア計算
		  score_type calculate_score();

		  // 注文の数の合計
		  size_t get_num_of_orders() const;
		  // 0-indexed で k 番目の注文情報を得る
		  order get_kth_order(size_t k) const;
		};

		const std::string state::OK_STR = "OK";
		const std::string state::NG_STR = "NG";

		state::state(const graph<edge> &G_, const time_type &max_time_,
				 std::vector<int> commands_,
				 std::vector< std::vector<order> > given_order_info_,
				 size_t v=0)
		  : agent(v), depot_index(v), G(G_),
			order_list(), pending_order_list(G_.size()),
			depot_order_list(), agent_order_list(),
			current_time(0), max_time(max_time_),
			commands(commands_), given_order_info(given_order_info_) {
		  order_list.emplace_back(0, -1, -1); // ダミー注文
		  G.sort_edges();
		}

		state::query_type state::input_by_agent() {
		  return commands[current_time];
		}

		void state::output_verdict(std::string verdict) {
		#ifdef DEBUG
		  fprintf(stderr, "# verdict: %s\n", verdict.c_str());
		#endif
		}

		void state::get_order() {

		  std::vector<order> new_orders_list;
		  for(size_t i=0; i<given_order_info[current_time].size(); i++) {
			const order &od = given_order_info[current_time][i];
			o_nt id, dst, start_time;
			std::tie(id, dst, start_time, std::ignore) = od.get_order_info();
			
			// 全体のリストに追加
			order_list.emplace_back(id, dst, start_time);

			// dst 番目の頂点に「待ち状態の注文」として情報を追加
			pending_order_list[dst].emplace(id);

			// depot に「持ち出し待ちの注文」として情報を追加
			depot_order_list.emplace(id);

			new_orders_list.emplace_back(id, dst, start_time);
		  }
		}

		void state::get_removed_order_list() {
		  size_t agent_v = ep_1;

		  // depot から回収された商品に対応する注文一覧
		  std::vector<o_nt> removed_order_list;
		  if(agent_state == ON_VERTEX and agent_v == depot_index) {
			removed_order_list.reserve(depot_order_list.size());
			for(const auto &e : depot_order_list) {
			  removed_order_list.emplace_back(e);
			  agent_order_list.emplace(e);
			}
			depot_order_list.clear();
		  }
		}

		void state::get_completed_order_list() {
		  size_t agent_v = ep_1;

		  // 処理された注文一覧
		  std::vector<o_nt> completed_order_list;
		  if(agent_state == ON_VERTEX and agent_v != depot_index) {
			set_intersection(pending_order_list[agent_v].begin(),
					 pending_order_list[agent_v].end(),
					 agent_order_list.begin(),
					 agent_order_list.end(),
					 std::back_inserter(completed_order_list));
			for(const auto &e : completed_order_list) {
			  pending_order_list[agent_v].erase(e);
			  agent_order_list.erase(e);
			  // 終了時間を記録
			  order_list[e].register_end_time(current_time);
			}
		  }
		}

		bool state::increment_step() {
		  const int V = static_cast<int>(G.size());

		  // 新しく注文が来る
		  // (注文リストを更新してコンテスタントに情報を送らないといけない)
		  get_order();
		  get_removed_order_list();
		  
		  // コンテスタントからの命令を受け取る
		  query_type query = input_by_agent();

		  // 命令を処理 (agent を動かすだけ！)
		  if(query == -1) {
			// stay
			output_verdict(OK_STR);
		  }
		  else {
			int vertex = query - static_cast<int>(INDEXED);
			if(0 <= vertex and vertex < V) {
			  // move
			  if(is_valid_move(G, vertex)) {
			output_verdict(OK_STR);
			proceed(G, vertex);
			  }
			  else {
			output_verdict(NG_STR);
			return false;
			  }
			}
			else {
			  output_verdict(NG_STR);
			  return false;
			}
		  }

		  // 命令を処理し終わったので 1 分経過させる
		  current_time++;

		  // その時点で捌いた注文のリスト・新しく持った商品のリストなどを得る
		  get_completed_order_list();

		  assert(pending_order_list[depot_index].empty());

		  return true;
		}

		state::score_type state::calculate_score() {
		  size_t num_of_orders = get_num_of_orders();

		  auto func = [&](score_type s) {
			return s * s;
		  };
		  
		  score_type score = 0;
		  for(size_t i=0; i<num_of_orders; i++) {
			time_type start_time, end_time;
			std::tie(std::ignore, std::ignore, start_time, end_time) = get_kth_order(i).get_order_info();
			if(end_time != -1) {
			  score += func(max_time) - func(end_time - start_time);
			}
		  }
		  return score;
		}

		size_t state::get_num_of_orders() const {
		  return order_list.size() - 1;
		}

		order state::get_kth_order(size_t k) const {
		  return order_list[k + 1];
		}
	};
	
	using namespace Graph;
	using namespace State;
	
	size_t V, E;
	graph<edge> G;
	int T_max;
	vector< std::vector<order> > given_order_info;
	
	void init()
	{
		V = Input::V;
		E = Input::E;
		 
        G = graph<edge>(V);
		for(size_t i=0; i<E; i++)
		{
			int u, v, dist;
			dist = Input::edges[i].X;
			u = Input::edges[i].Y.X;
			v = Input::edges[i].Y.Y;
			u -= INDEXED, v -= INDEXED;
			G.add_edge(u, v, dist);
			G.add_edge(v, u, dist);
		}

		T_max = Input::Tmax; 
		given_order_info.resize(T_max);
		for(int i=0; i<T_max; i++)
		{
			int N = (int)Input::info[i].size();
			for(int j=0; j<N; j++) 
			{
				int new_id, dst;
				new_id = Input::info[i][j].X;
				dst = Input::info[i][j].Y;
				dst -= INDEXED;
				given_order_info[i].emplace_back(new_id, dst, i);
			}
		}
	}
	
	LL grade(vector<int>& ans)
	{
		int sz = SZ(ans);
		ans.resize(T_max);
		FOR(i, sz, T_max) ans[i] = -1;
		
		state st(G, T_max, ans, given_order_info);
		for(int i=0; i<T_max; i++)
			assert(st.increment_step());		
		return st.calculate_score(); 
	}
};

namespace Solution
{
	const int T = 10000 + 7;
	int Tmax;
	const int N = 400 + 7;
	const int M = 800 + 7;
	int n, m;
	vector<PII> g[N];
	pair<int, PII> edges[M];
	PII order[T];
	VI needed[N];
	int dist[N][N];
	int rebra[N][N];
	int parent[N][N];
	int G[N][N];
	int number_of_orders_on_suf[T];
	int TPeak;
	int TLast = 9500;
	int freq[N];

	double probability(int chas)
	{
		if (chas < TPeak) return chas / (double) TPeak;
		return (TLast - chas) / (TLast - TPeak);
	}

	inline int waiting_orders(int l, int r)
	{
		r = min(r, T - 1);
		if (l > r) return 0;
		return number_of_orders_on_suf[r] - (l ? number_of_orders_on_suf[l - 1] : 0);
	}

	void graph_input()
	{
		n = Input::V;
		m = Input::E;
		FOR(i, 1, n + 1) FOR(j, 1, n + 1) G[i][j] = INF;
		FOR(i, 1, n + 1) G[i][i] = 0;
		
		FOR(i, 0, m)
		{
			int u, v, w;
			w = Input::edges[i].X;
			u = Input::edges[i].Y.X;
			v = Input::edges[i].Y.Y;
			G[u][v] = G[v][u] = w;
			g[u].PB({v, w});
			g[v].PB({u, w});
			edges[i] = {w, {u, v}};
		}
	}

	void find_peak()
	{
		double maxCoef = 0;
		int suma = 0;
		FOR(i, 0, Tmax)
		{
			int t = (int)Input::info[i].size();
			suma += t;
			if (suma / (i + 1.0) > maxCoef)
			{
				maxCoef = suma / (i + 1.0);
				TPeak = i;
			}		
		}
	}
	
	void order_input()
	{
		Tmax = Input::Tmax;
		FILL(order, -1);
		FILL(number_of_orders_on_suf, 0);
		vector<pair<int , int> > v(n + 1);
		for(int i = 0; i <= n; i++)
			v[i].Y = i;
		FOR(i, 0, Tmax)
		{
			int t = (int)Input::info[i].size();	
			if (i)
				number_of_orders_on_suf[i] = number_of_orders_on_suf[i - 1];
				
			if (t == 0) continue;
			number_of_orders_on_suf[i]++;
			int id, dst;
			id = Input::info[i][0].X;
			dst = Input::info[i][0].Y;
			v[dst].X++;
			order[i] = {id, dst};
			needed[dst].PB(i);		
		}
		
		 sort(v.begin() , v.end());
  

		for(int i = 3 * SZ(v) / 4; i < SZ(v); i++)
			freq[v[i].Y] = 1;
	}

	void preprocess()
	{
		FOR(i, 1, n + 1)
		{
			FOR(j, 1, n + 1) dist[i][j] = INF;
			dist[i][i] = 0;
			set<PII> S;
			FOR(j, 1, n + 1)
				S.insert({dist[i][j], j});
			
			while(SZ(S))
			{
				int v = S.begin()->Y;
				S.erase(S.begin());
				
				for(auto e: g[v])
				{
					int to = e.X, len = e.Y;
					if (dist[i][to] <= dist[i][v] + len) continue;
					parent[i][to] = v;
					S.erase({dist[i][to], to});
					dist[i][to] = dist[i][v] + len;
					rebra[i][to] = rebra[i][v] + 1;
					S.insert({dist[i][to], to});
				}
			}
		}
	}

	vector<int> path(int from, int to)
	{
		vector<int> res;
		while(from != to)
		{
			res.PB(to);
			to = parent[from][to];
		}
		
		res.PB(from);
		reverse(ALL(res));
		return res;
	}
	
	void init()
	{
		graph_input();
		order_input();
		find_peak();
		preprocess();		
	}
	
	void clear_orders(vector<int>& orders, int vertex)
	{
		FOR(i, 0, SZ(orders))
		{
			if (order[orders[i]].Y != vertex) continue;
			swap(orders[i], orders.back());
			orders.pop_back();
			--i;
		}
	}
};

namespace Solution0
{
	using namespace Solution;
	
	int choose_next(int curr_vertex, int start_time, int curr_time, vector<int>& orders)
	{
		int to = -1;
		for(auto i: orders)
			if (to == -1 || dist[curr_vertex][to] > dist[curr_vertex][order[i].Y])
				to = order[i].Y;
		return to;
	}

	inline bool go_to_baza(int curr_vertex, int start_time, int curr_time, vector<int>& orders, int to)
	{
		if (curr_vertex == 1) return false;
		if (curr_time - start_time < 47) return false;
		if (dist[curr_vertex][1] * 2 < dist[curr_vertex][to]) return true;
		return false;
	}
	
	int last_get_order = -1;
	
	vector<int> go(int& curr_vertex, int start_time, int curr_time, 
		vector<int>& orders, int end_time)
	{	
		vector<int> res; 
		if (curr_vertex == 1)
		{
			FOR(i, last_get_order + 1, curr_time + 1)
			{
				if (order[i].X != -1)
					orders.PB(i);
			}
			
			last_get_order = curr_time;
		}
		
		while (curr_vertex == 1 && SZ(orders) == 0 && curr_time < end_time)
		{
			if (order[curr_time].X != -1)
				orders.PB(curr_time);
			curr_time++;
			res.PB(-1);
		}		
		
		if (curr_time == end_time) return res;
		if (SZ(orders) == 0)
		{
			vector<int> way = path(curr_vertex, 1);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
			
			curr_vertex = 1;					
			return res;
		}
		
		while(SZ(orders))
		{
			clear_orders(orders, curr_vertex);
			int to = choose_next(curr_vertex, start_time, curr_time, orders);			
			
			if (go_to_baza(curr_vertex, start_time, curr_time, orders, to))
				to = 1;
			
			vector<int> way = path(curr_vertex, to);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
					
			curr_time = start_time + SZ(res);
			curr_vertex = to;
			sort(ALL(way));
			vector<int> nxt;
			for(auto i: orders)
			{
				auto it = lower_bound(ALL(way), order[i].Y);
				if (it != way.end() && *it == order[i].Y) continue;
				nxt.PB(i);
			}

			orders = nxt;
			if (curr_vertex == 1) break;
		}  
		  
		return res;
	}

	vector<int> solve(vector<int> rozdil = {Tmax})
	{
		vector<int> res;
		vector<int> orders;
		
		int chas = 0;
		int curr_vertex = 1;
		
		FOR(r, 0, SZ(rozdil))
		{
			vector<int> here;
			while(chas < rozdil[r])
			{
				auto tut = go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			assert(chas == rozdil[r]);
			for(auto i: here) res.PB(i);
		}
		
		return res;		
	}
};

namespace Solution1
{
	using namespace Solution;
	
	int choose_next(int curr_vertex, int start_time, int curr_time, vector<int>& orders)
	{
		map<int, int> pokupci;
		for(auto i: orders)
			pokupci[order[i].Y]++;
		
		int po_dist = -1, po_reb = -1, po_waga = -1;
		int bst_cnt = -1;
		for(auto it: pokupci)
		{
			int i = it.X;
			int j = it.Y;
			if (po_dist == -1 || dist[curr_vertex][po_dist] > dist[curr_vertex][i]) po_dist = i;
			if (po_reb == -1 || rebra[curr_vertex][po_reb] > rebra[curr_vertex][i]) po_reb = i;
			if (po_waga == -1 || dist[curr_vertex][i] * bst_cnt < dist[curr_vertex][po_waga] * j)
				po_waga = i, bst_cnt = j;
		}
			
		int mx1 = -1;
		int MX = 0;
		for(auto it: pokupci)
		{
			int i = it.X;
			if (rebra[curr_vertex][i] != 1) continue;
			if (mx1 == -1 || it.Y > MX) mx1 = i, MX = it.Y;
		}
		
		if (po_waga == po_dist) return po_dist;
		if (mx1 != -1) return mx1;
		
		return po_waga;
	}

	inline bool go_to_baza(int curr_vertex, int start_time, int curr_time, vector<int>& orders, int to)
	{
		if (2 * dist[curr_vertex][to] > dist[curr_vertex][1] && 
			curr_time - start_time >= 47) return true;
		
		//if (5 * dist[curr_vertex][to] < dist[curr_vertex][1]) return false;
		
		if (abs(curr_time - TPeak) <= min(75, 4 * dist[curr_vertex][1]) && curr_time < TPeak) return true;
		
		return false;
	}

	int last_get_order = -1;
	
	vector<int> go(int& curr_vertex, int start_time, int curr_time, 
		vector<int>& orders, int end_time)
	{	
		vector<int> res; 
		if (curr_vertex == 1)
		{
			FOR(i, last_get_order + 1, curr_time + 1)
			{
				if (order[i].X != -1)
					orders.PB(i);
			}
			
			last_get_order = curr_time;
		}
		
		while (curr_vertex == 1 && SZ(orders) == 0 && curr_time < end_time)
		{
			if (order[curr_time].X != -1)
				orders.PB(curr_time);
			curr_time++;
			res.PB(-1);
		}		
		
		if (curr_time == end_time) return res;
		if (SZ(orders) == 0)
		{
			vector<int> way = path(curr_vertex, 1);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
			
			curr_vertex = 1;					
			return res;
		}
		
		while(SZ(orders))
		{
			clear_orders(orders, curr_vertex);
			int to = choose_next(curr_vertex, start_time, curr_time, orders);			
			
			if (go_to_baza(curr_vertex, start_time, curr_time, orders, to))
				to = 1;
			
			vector<int> way = path(curr_vertex, to);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
					
			curr_time = start_time + SZ(res);
			curr_vertex = to;
			sort(ALL(way));
			vector<int> nxt;
			for(auto i: orders)
			{
				auto it = lower_bound(ALL(way), order[i].Y);
				if (it != way.end() && *it == order[i].Y) continue;
				nxt.PB(i);
			}

			orders = nxt;
			if (curr_vertex == 1) break;
		}  
		  
		return res;
	}
	
	vector<int> solve(vector<int> rozdil = {Tmax})
	{
		vector<int> res;
		vector<int> orders;
		
		int chas = 0;
		int curr_vertex = 1;
		
		FOR(r, 0, SZ(rozdil))
		{
			vector<int> here;
			while(chas < rozdil[r])
			{
				auto tut = go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			assert(chas == rozdil[r]);
			for(auto i: here) res.PB(i);
		}
		
		return res;		
	}
	
};

namespace Solution2
{
	using namespace Solution;
			
	int choose_next(int curr_vertex, int start_time, int curr_time, vector<int>& orders)
	{
		map<int, int> pokupci;
		for(auto i: orders)
			pokupci[order[i].Y]++;
		
		int po_dist = -1, po_reb = -1, po_waga = -1;
		int bst_cnt = -1;
		for(auto it: pokupci)
		{
			int i = it.X;
			int j = it.Y;
			if (po_dist == -1 || dist[curr_vertex][po_dist] > dist[curr_vertex][i]) po_dist = i;
			if (po_reb == -1 || rebra[curr_vertex][po_reb] > rebra[curr_vertex][i]) po_reb = i;
			if (po_waga == -1 || dist[curr_vertex][i] * bst_cnt < dist[curr_vertex][po_waga] * j)
				po_waga = i, bst_cnt = j;
		}
			
		int mx1 = -1;
		int MX = 0;
		for(auto it: pokupci)
		{
			int i = it.X;
			if (rebra[curr_vertex][i] != 1) continue;
			if (mx1 == -1 || it.Y > MX) mx1 = i, MX = it.Y;
		}
		
		if (po_dist == po_waga) return po_waga;
		if (mx1 != -1) return mx1;	
		return po_waga;
	}

	inline bool go_to_baza(int curr_vertex, int start_time, int curr_time, vector<int>& orders, int to)
	{
		if (2 * dist[curr_vertex][to] > dist[curr_vertex][1] && 
			curr_time - start_time >= 47 && curr_time < TLast) return true;
		
		//if (5 * dist[curr_vertex][to] < dist[curr_vertex][1]) return false;
		
		//if (abs(curr_time - TPeak) <= min(75, 4 * dist[curr_vertex][1]) && curr_time < TPeak) return true;

		if(waiting_orders(start_time , curr_time) > SZ(orders) && SZ(orders) > 200)
			return true;
		return false;
	}

	int last_get_order = -1;

	vector<int> go(int& curr_vertex, int start_time, int curr_time, 
		vector<int>& orders, int end_time)
	{	
		vector<int> res; 
		if (curr_vertex == 1)
		{
			FOR(i, last_get_order + 1, curr_time + 1)
			{
				if (order[i].X != -1)
					orders.PB(i);
			}
			
			last_get_order = curr_time;
		}
		
		while (curr_vertex == 1 && SZ(orders) == 0 && curr_time < end_time)
		{
			if (order[curr_time].X != -1)
				orders.PB(curr_time);
			curr_time++;
			res.PB(-1);
		}		
		
		if (curr_time == end_time) return res;
		if (SZ(orders) == 0)
		{
			vector<int> way = path(curr_vertex, 1);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
			
			curr_vertex = 1;					
			return res;
		}
		
		while(SZ(orders))
		{
			clear_orders(orders, curr_vertex);
			int to = choose_next(curr_vertex, start_time, curr_time, orders);			
			
			if (go_to_baza(curr_vertex, start_time, curr_time, orders, to))
				to = 1;
			
			vector<int> way = path(curr_vertex, to);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
					
			curr_time = start_time + SZ(res);
			curr_vertex = to;
			sort(ALL(way));
			vector<int> nxt;
			for(auto i: orders)
			{
				auto it = lower_bound(ALL(way), order[i].Y);
				if (it != way.end() && *it == order[i].Y) continue;
				nxt.PB(i);
			}

			orders = nxt;
			if (curr_vertex == 1) break;
		}  
		  
		return res;
	}
	
	vector<int> solve(vector<int> rozdil = {Tmax})
	{
		vector<int> res;
		vector<int> orders;
		
		int chas = 0;
		int curr_vertex = 1;
		
		FOR(r, 0, SZ(rozdil))
		{
			vector<int> here;
			while(chas < rozdil[r])
			{
				auto tut = go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			assert(chas == rozdil[r]);
			for(auto i: here) res.PB(i);
		}
		
		return res;		
	}
	
};

namespace Solution3
{
	using namespace Solution;
	
	int choose_next(int curr_vertex, int start_time, int curr_time, vector<int>& orders)
	{
		map<int, int> pokupci;
		for(auto i: orders)
			pokupci[order[i].Y]++;
		
		int po_dist = -1, po_reb = -1, po_waga = -1;
		int bst_cnt = -1;
		for(auto it: pokupci)
		{
			int i = it.X;
			int j = it.Y;
			if (po_dist == -1 || dist[curr_vertex][po_dist] > dist[curr_vertex][i]) po_dist = i;
			if (po_reb == -1 || rebra[curr_vertex][po_reb] > rebra[curr_vertex][i]) po_reb = i;
			if (po_waga == -1 || dist[curr_vertex][i] * bst_cnt < dist[curr_vertex][po_waga] * j)
				po_waga = i, bst_cnt = j;
		}
			
		int mx1 = -1;
		int MX = 0;
		for(auto it: pokupci)
		{
			int i = it.X;
			if (rebra[curr_vertex][i] != 1) continue;
			if (mx1 == -1 || it.Y > MX) mx1 = i, MX = it.Y;
		}
		
		if (mx1 != -1) return mx1;		
		return po_waga;
	}

	inline bool go_to_baza(int curr_vertex, int start_time, int curr_time, vector<int>& orders, int to)
	{
		if (2 * dist[curr_vertex][to] > dist[curr_vertex][1] && 
			curr_time - start_time >= 47) return true;
		
		if (5 * dist[curr_vertex][to] < dist[curr_vertex][1]) return false;
		
		if (abs(curr_time - TPeak) <= min(75, 4 * dist[curr_vertex][1]) && curr_time < TPeak) return true;
		
		return false;
	}
	
	int last_get_order = -1;
	
	vector<int> go(int& curr_vertex, int start_time, int curr_time, 
		vector<int>& orders, int end_time)
	{	
		vector<int> res; 
		if (curr_vertex == 1)
		{
			FOR(i, last_get_order + 1, curr_time + 1)
			{
				if (order[i].X != -1)
					orders.PB(i);
			}
			
			last_get_order = curr_time;
		}
		
		while (curr_vertex == 1 && SZ(orders) == 0 && curr_time < end_time)
		{
			if (order[curr_time].X != -1)
				orders.PB(curr_time);
			curr_time++;
			res.PB(-1);
		}		
		
		if (curr_time == end_time) return res;
		if (SZ(orders) == 0)
		{
			vector<int> way = path(curr_vertex, 1);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
			
			curr_vertex = 1;					
			return res;
		}
		
		while(SZ(orders))
		{
			clear_orders(orders, curr_vertex);
			int to = choose_next(curr_vertex, start_time, curr_time, orders);			
			
			if (go_to_baza(curr_vertex, start_time, curr_time, orders, to))
				to = 1;
			
			vector<int> way = path(curr_vertex, to);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
					
			curr_time = start_time + SZ(res);
			curr_vertex = to;
			sort(ALL(way));
			vector<int> nxt;
			for(auto i: orders)
			{
				auto it = lower_bound(ALL(way), order[i].Y);
				if (it != way.end() && *it == order[i].Y) continue;
				nxt.PB(i);
			}

			orders = nxt;
			if (curr_vertex == 1) break;
		}  
		  
		return res;
	}
	
	vector<int> solve(vector<int> rozdil = {Tmax})
	{
		vector<int> res;
		vector<int> orders;
		
		int chas = 0;
		int curr_vertex = 1;
		
		FOR(r, 0, SZ(rozdil))
		{
			vector<int> here;
			while(chas < rozdil[r])
			{
				auto tut = go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			assert(chas == rozdil[r]);
			for(auto i: here) res.PB(i);
		}
		
		return res;		
	}
};

namespace Solution4
{
	using namespace Solution;
	
	int choose_next(int curr_vertex, int start_time, int curr_time, vector<int>& orders)
	{
		map<int, int> pokupci;
		for(auto i: orders)
			pokupci[order[i].Y]++;
		
		int po_dist = -1, po_reb = -1, po_waga = -1;
		int bst_cnt = -1;
		for(auto it: pokupci)
		{
			int i = it.X;
			int j = it.Y;
			if (po_dist == -1 || dist[curr_vertex][po_dist] > dist[curr_vertex][i]) po_dist = i;
			if (po_reb == -1 || rebra[curr_vertex][po_reb] > rebra[curr_vertex][i]) po_reb = i;
			if (po_waga == -1 || dist[curr_vertex][i] * bst_cnt < dist[curr_vertex][po_waga] * j)
				po_waga = i, bst_cnt = j;
		}
			
		int mx1 = -1;
		int MX = 0;
		for(auto it: pokupci)
		{
			int i = it.X;
			if (rebra[curr_vertex][i] != 1) continue;
			if (mx1 == -1 || it.Y > MX) mx1 = i, MX = it.Y;
		}
		
		return po_dist;
		if (mx1 != -1) return mx1;		
		return po_waga;
	}

	inline bool go_to_baza(int curr_vertex, int start_time, int curr_time, vector<int>& orders, int to)
	{
		if (2 * dist[curr_vertex][to] > dist[curr_vertex][1] && 
			curr_time - start_time >= 47) return true;
		
		if (5 * dist[curr_vertex][to] < dist[curr_vertex][1]) return false;
		
		if (abs(curr_time - TPeak) <= min(75, 4 * dist[curr_vertex][1]) && curr_time < TPeak) return true;
		
		return false;
	}
	
	int last_get_order = -1;
	
	vector<int> go(int& curr_vertex, int start_time, int curr_time, 
		vector<int>& orders, int end_time)
	{	
		vector<int> res; 
		if (curr_vertex == 1)
		{
			FOR(i, last_get_order + 1, curr_time + 1)
			{
				if (order[i].X != -1)
					orders.PB(i);
			}
			
			last_get_order = curr_time;
		}
		
		while (curr_vertex == 1 && SZ(orders) == 0 && curr_time < end_time)
		{
			if (order[curr_time].X != -1)
				orders.PB(curr_time);
			curr_time++;
			res.PB(-1);
		}		
		
		if (curr_time == end_time) return res;
		if (SZ(orders) == 0)
		{
			vector<int> way = path(curr_vertex, 1);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
			
			curr_vertex = 1;					
			return res;
		}
		
		while(SZ(orders))
		{
			clear_orders(orders, curr_vertex);
			int to = choose_next(curr_vertex, start_time, curr_time, orders);			
			
			if (go_to_baza(curr_vertex, start_time, curr_time, orders, to))
				to = 1;
			
			vector<int> way = path(curr_vertex, to);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
					
			curr_time = start_time + SZ(res);
			curr_vertex = to;
			sort(ALL(way));
			vector<int> nxt;
			for(auto i: orders)
			{
				auto it = lower_bound(ALL(way), order[i].Y);
				if (it != way.end() && *it == order[i].Y) continue;
				nxt.PB(i);
			}

			orders = nxt;
			if (curr_vertex == 1) break;
		}  
		  
		return res;
	}
	
	vector<int> solve(vector<int> rozdil = {Tmax})
	{
		vector<int> res;
		vector<int> orders;
		
		int chas = 0;
		int curr_vertex = 1;
		
		FOR(r, 0, SZ(rozdil))
		{
			vector<int> here;
			while(chas < rozdil[r])
			{
				auto tut = go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			assert(chas == rozdil[r]);
			for(auto i: here) res.PB(i);
		}
		
		return res;		
	}
};

namespace Solution5
{
	using namespace Solution;
	
	int choose_next(int curr_vertex, int start_time, int curr_time, vector<int>& orders)
	{
		map<int, int> pokupci;
		for(auto i: orders)
			pokupci[order[i].Y]++;
		
		int po_dist = -1, po_reb = -1, po_waga = -1;
		int bst_cnt = -1;
		for(auto it: pokupci)
		{
			int i = it.X;
			int j = it.Y;
			if (po_dist == -1 || dist[curr_vertex][po_dist] > dist[curr_vertex][i]) po_dist = i;
			if (po_reb == -1 || rebra[curr_vertex][po_reb] > rebra[curr_vertex][i]) po_reb = i;
			if (po_waga == -1 || dist[curr_vertex][i] * bst_cnt < dist[curr_vertex][po_waga] * j)
				po_waga = i, bst_cnt = j;
		}
			
		int mx1 = -1;
		int MX = 0;
		for(auto it: pokupci)
		{
			int i = it.X;
			if (rebra[curr_vertex][i] != 1) continue;
			if (mx1 == -1 || it.Y > MX) mx1 = i, MX = it.Y;
		}
		
		//if (mx1 != -1) return mx1;		
		return po_waga;
	}

	inline bool go_to_baza(int curr_vertex, int start_time, int curr_time, vector<int>& orders, int to)
	{
		if (2 * dist[curr_vertex][to] > dist[curr_vertex][1] && 
			curr_time - start_time >= 47) return true;
		
		//if (5 * dist[curr_vertex][to] < dist[curr_vertex][1]) return false;
		
		if (abs(curr_time - TPeak) <= min(75, 4 * dist[curr_vertex][1]) && curr_time < TPeak) return true;
		
		return false;
	}

	int last_get_order = -1;
	
	vector<int> go(int& curr_vertex, int start_time, int curr_time, 
		vector<int>& orders, int end_time)
	{	
		vector<int> res; 
		if (curr_vertex == 1)
		{
			FOR(i, last_get_order + 1, curr_time + 1)
			{
				if (order[i].X != -1)
					orders.PB(i);
			}
			
			last_get_order = curr_time;
		}
		
		while (curr_vertex == 1 && SZ(orders) == 0 && curr_time < end_time)
		{
			if (order[curr_time].X != -1)
				orders.PB(curr_time);
			curr_time++;
			res.PB(-1);
		}		
		
		if (curr_time == end_time) return res;
		if (SZ(orders) == 0)
		{
			vector<int> way = path(curr_vertex, 1);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
			
			curr_vertex = 1;					
			return res;
		}
		
		while(SZ(orders))
		{
			clear_orders(orders, curr_vertex);
			int to = choose_next(curr_vertex, start_time, curr_time, orders);			
			
			if (go_to_baza(curr_vertex, start_time, curr_time, orders, to))
				to = 1;
			
			vector<int> way = path(curr_vertex, to);
			int tuta_chas = 0;
			FOR(i, 0, SZ(way) - 1)
				tuta_chas += G[way[i]][way[i + 1]];
			
			if (tuta_chas + curr_time > end_time)
			{
				FOR(i, 0, end_time - curr_time) res.PB(-1);
				return res;
			}
			
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
					
			curr_time = start_time + SZ(res);
			curr_vertex = to;
			sort(ALL(way));
			vector<int> nxt;
			for(auto i: orders)
			{
				auto it = lower_bound(ALL(way), order[i].Y);
				if (it != way.end() && *it == order[i].Y) continue;
				nxt.PB(i);
			}

			orders = nxt;
			if (curr_vertex == 1) break;
		}  
		  
		return res;
	}
	
	vector<int> solve(vector<int> rozdil = {Tmax})
	{
		vector<int> res;
		vector<int> orders;
		
		int chas = 0;
		int curr_vertex = 1;
		
		FOR(r, 0, SZ(rozdil))
		{
			vector<int> here;
			while(chas < rozdil[r])
			{
				auto tut = go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			assert(chas == rozdil[r]);
			for(auto i: here) res.PB(i);
		}
		
		return res;		
	}
};

namespace Solution6
{
	using namespace Solution;
	int de;

	double cof[N];
	
	vector<int> go(vector<int>& orders, int start_time)
	{
	  int curr_vertex = 1;
	  vector<int> res;
	  vector<int> ostov;
	  ostov.PB(1);
	  while(SZ(orders))
	  {
		memset(cof , 0 , sizeof cof);
		for(auto ord : orders)
		  cof[order[ord].Y]++;
		int to = -1;
		int curr_time = start_time + SZ(res);
		if(de > 8800)
		{
		  for(auto i: orders)
			if (to == -1 || dist[curr_vertex][to] * (1.5 + freq[to]) / cof[to] >
			 dist[curr_vertex][order[i].Y] * (1.5 + freq[order[i].Y]) / cof[order[i].Y] ||
			 (cof[order[i].Y] > 6 && cof[to] < cof[order[i].Y] && dist[curr_vertex][order[i].Y] < 7) )
			  to = order[i].Y;
		}
		else
		{
		  for(auto i: orders)
		  if (to == -1 || dist[curr_vertex][to] / cof[to] > dist[curr_vertex][order[i].Y] / cof[order[i].Y] ||
		   (cof[order[i].Y] > 6 && cof[to] < cof[order[i].Y] && dist[curr_vertex][order[i].Y] < 7) )
			to = order[i].Y;
		}
		
		ostov.PB(to);
		
			
		if (curr_vertex != 1 && dist[curr_vertex][to] / cof[to] > dist[curr_vertex][1] * 7 / (waiting_orders(start_time , curr_time) + 1)  
		 )
		  to = 1;
		
		vector<int> way = path(curr_vertex, to);
		FOR(i, 0, SZ(way) - 1)
		  FOR(j, 0, G[way[i]][way[i + 1]])
			res.PB(way[i + 1]);
		
		curr_vertex = way.back();
		sort(ALL(way));
		vector<int> nxt;
		for(auto i: orders)
		{
		  auto it = lower_bound(ALL(way), order[i].Y);
		  if (it != way.end() && *it == order[i].Y) continue;
		  nxt.PB(i);
		}
		
		orders = nxt;
		
		if (to == 1) break;
	  }  
	  
	  vector<int> way = path(curr_vertex, 1);
	  FOR(i, 0, SZ(way) - 1)
		FOR(j, 0, G[way[i]][way[i + 1]])
		  res.PB(way[i + 1]);
	  //int hujna = 0;
	  
	  //cerr << SZ(res) << " " << hujna << endl;
	  return res;
	}

	vector<int> solve()
	{
		de = TPeak;
		vector<int> res;
		vector<int> orders;
		
		int chas = 0;
		while(chas < Tmax)
		{
			if (order[chas].X != -1)
				orders.PB(chas);
				
			if (SZ(orders))
			{
				auto tut = go(orders, chas);
				for(auto i: tut) res.PB(i);
				if (SZ(res) >= Tmax)
				{
					res.resize(Tmax);
					break;
				}
				
				FOR(i, 0, SZ(tut))
				{
					chas++;
					if (order[chas].X != -1) orders.PB(chas);
				}
				
				continue;
			}
			
			chas++;		
			res.PB(-1);
		}
		
		
		return res;
		
	}
};

namespace Solution7
{
	using namespace Solution;
	
	double cof[N];
	vector<int> go(vector<int>& orders, int start_time)
	{
	  int curr_vertex = 1;
	  vector<int> res;
	  vector<int> ostov;
	  ostov.PB(1);
	  while(SZ(orders))
	  {
		memset(cof , 0 , sizeof cof);
		for(auto ord : orders)
		  cof[order[ord].Y]++;
		int to = -1;
		for(auto i: orders)
		  if (to == -1 || dist[curr_vertex][to] / cof[to] > dist[curr_vertex][order[i].Y] / cof[order[i].Y] ||
		   (cof[order[i].Y] > 6 && cof[to] < cof[order[i].Y] && dist[curr_vertex][order[i].Y] < 7) )
			to = order[i].Y;
		
		ostov.PB(to);
		
		int curr_time = start_time + SZ(res);
		//int nxt_time = start_time + SZ(res) + dist[curr_vertex][to];
		//cerr << curr_time << " " << nxt_time << '\n';
		
		if (curr_vertex != 1 && dist[curr_vertex][to] / cof[to] > dist[curr_vertex][1] * 7 / (waiting_orders(start_time , curr_time) + 1)  
		 )
		  to = 1;
		
		vector<int> way = path(curr_vertex, to);
		FOR(i, 0, SZ(way) - 1)
		  FOR(j, 0, G[way[i]][way[i + 1]])
			res.PB(way[i + 1]);
		
		curr_vertex = to;
		sort(ALL(way));
		vector<int> nxt;
		for(auto i: orders)
		{
		  auto it = lower_bound(ALL(way), order[i].Y);
		  if (it != way.end() && *it == order[i].Y) continue;
		  nxt.PB(i);
		}
		
		orders = nxt;
		
		if (to == 1) break;
	  }  
	  
	  vector<int> way = path(curr_vertex, 1);
	  FOR(i, 0, SZ(way) - 1)
		FOR(j, 0, G[way[i]][way[i + 1]])
		  res.PB(way[i + 1]);
	  //int hujna = 0;
	  
	  //cerr << SZ(res) << " " << hujna << endl;
	  return res;
	}
	
	vector<int> solve()
	{
		vector<int> res;
		vector<int> orders;
		
		int chas = 0;
		while(chas < Tmax)
		{
			if (order[chas].X != -1)
				orders.PB(chas);
				
			if (SZ(orders))
			{
				auto tut = go(orders, chas);
				for(auto i: tut) res.PB(i);
				if (SZ(res) >= Tmax)
				{
					res.resize(Tmax);
					break;
				}
				
				FOR(i, 0, SZ(tut))
				{
					chas++;
					if (order[chas].X != -1) orders.PB(chas);
				}
				
				continue;
			}
			
			chas++;		
			res.PB(-1);
		}
		
		
		return res;
		
	}

};

namespace Solution8
{
	using namespace Solution;
	
	double cof[N];
	
	vector<int> go(vector<int>& orders, int start_time)
	{
	  int curr_vertex = 1;
	  vector<int> res;
	  const int Magic = 47;
	  vector<int> ostov;
	  ostov.PB(1);
	  while(SZ(orders))
	  {
		memset(cof , 0 , sizeof cof);
		for(auto ord : orders)
		  cof[order[ord].Y]++;
		int to = -1;
		for(auto i: orders)
		  if (to == -1 || dist[curr_vertex][to] / cof[to] > dist[curr_vertex][order[i].Y] / cof[order[i].Y] ||
		   (cof[order[i].Y] > 6 && cof[to] < cof[order[i].Y] && dist[curr_vertex][order[i].Y] < 7) )
			to = order[i].Y;
		
		ostov.PB(to);
		
		int curr_time = start_time + SZ(res);
		int nxt_time = start_time + SZ(res) + dist[curr_vertex][to];
		//cerr << curr_time << " " << nxt_time << '\n';
		if(curr_time < 9500 && nxt_time >= 9500 && curr_vertex != 1)
		  to = 1;
		if (curr_vertex != 1 && 2 * dist[curr_vertex][to] > dist[curr_vertex][1] && SZ(res) >= Magic && curr_time < 9500)
		  to = 1;
		
		vector<int> way = path(curr_vertex, to);
		FOR(i, 0, SZ(way) - 1)
		  FOR(j, 0, G[way[i]][way[i + 1]])
			res.PB(way[i + 1]);
		
		curr_vertex = to;
		sort(ALL(way));
		vector<int> nxt;
		for(auto i: orders)
		{
		  auto it = lower_bound(ALL(way), order[i].Y);
		  if (it != way.end() && *it == order[i].Y) continue;
		  nxt.PB(i);
		}
		
		orders = nxt;
		
		if (to == 1) break;
	  }  
	  
	  vector<int> way = path(curr_vertex, 1);
	  FOR(i, 0, SZ(way) - 1)
		FOR(j, 0, G[way[i]][way[i + 1]])
		  res.PB(way[i + 1]);
	  //int hujna = 0;
	  
	  //cerr << SZ(res) << " " << hujna << endl;
	  return res;
	}

	vector<int> solve()
	{
		vector<int> res;
		vector<int> orders;
		
		int chas = 0;
		while(chas < Tmax)
		{
			if (order[chas].X != -1)
				orders.PB(chas);
				
			if (SZ(orders))
			{
				auto tut = go(orders, chas);
				for(auto i: tut) res.PB(i);
				if (SZ(res) >= Tmax)
				{
					res.resize(Tmax);
					break;
				}
				
				FOR(i, 0, SZ(tut))
				{
					chas++;
					if (order[chas].X != -1) orders.PB(chas);
				}
				
				continue;
			}
			
			chas++;		
			res.PB(-1);
		}
		
		
		return res;
		
	}
	
};

namespace Solution9
{
	using namespace Solution;
	int DIFF_PEAK;//200
	int WAITING_ORDERS;//5
	int MIN_TIME;//47
	double DIFF_DIST;//2
	double DIFF_DIST2;//5
	double DIFF_DIST3;//4
	int CONST_PEAK;//75
	
	inline bool go_to_baza(int curr_vertex, int to, int start_time, int curr_time, 
		vector<int>& orders)
	{
		if (dist[curr_vertex][to] > dist[curr_vertex][1] &&
			waiting_orders(start_time, curr_time) > WAITING_ORDERS) return true;
		if (DIFF_DIST * dist[curr_vertex][to] > dist[curr_vertex][1] && 
			curr_time - start_time >= MIN_TIME) return true;
		
		if (DIFF_DIST2 * dist[curr_vertex][to] < dist[curr_vertex][1]) return false;
		
		if (abs(curr_time - TPeak) <= min(CONST_PEAK,
			(int)(DIFF_DIST3 * dist[curr_vertex][1])) && curr_time < TPeak) return true;
		
		return false;
	}
	 
	int cnt[N];
	 
	vector<int> go(vector<int>& orders, int start_time)
	{
		int curr_vertex = 1;
		vector<int> res;
		
		while(SZ(orders))
		{
			int to = -1;
			for(auto i: orders)
				cnt[order[i].Y] = 0;
			for(auto i: orders)
				cnt[order[i].Y]++;
			for(auto i: orders)
				if (to == -1 || dist[curr_vertex][to] * cnt[order[i].Y] > dist[curr_vertex][order[i].Y] * cnt[to])
					to = order[i].Y;
			
			if (curr_vertex != 1 && go_to_baza(curr_vertex, to, start_time, start_time + SZ(res), orders)) 
				to = 1;
						
			vector<int> way = path(curr_vertex, to);
			FOR(i, 0, SZ(way) - 1)
				FOR(j, 0, G[way[i]][way[i + 1]])
					res.PB(way[i + 1]);
			
			curr_vertex = to;
			sort(ALL(way));
			vector<int> nxt;
			for(auto i: orders)
			{
				auto it = lower_bound(ALL(way), order[i].Y);
				if (it != way.end() && *it == order[i].Y) continue;
				nxt.PB(i);
			}
			
			orders = nxt;
			if (to == 1) break;
		}	
		
		vector<int> way = path(curr_vertex, 1);
		FOR(i, 0, SZ(way) - 1)
			FOR(j, 0, G[way[i]][way[i + 1]])
				res.PB(way[i + 1]);
		
		return res;
	}
	 
	int min_orders(int chas)
	{
		if (abs(chas - TPeak) <= DIFF_PEAK) return TPeak - chas;
		return 0;
	}
	
	vector<int> solve(int _d, int _w, int _m, double _d1, double _d2, double _d3, int _c)
	{	
		DIFF_PEAK = _d;
		WAITING_ORDERS = _w;
		MIN_TIME = _m;
		DIFF_DIST = _d1;
		DIFF_DIST2 = _d2;
		DIFF_DIST3 = _d3;
		CONST_PEAK = _c;
		
		vector<int> res;
		vector<int> orders;
		
		int chas = 0;
		while(chas < Tmax)
		{
			if (order[chas].X != -1)
				orders.PB(chas);
				
			if (SZ(orders) > min_orders(chas))
			{
				auto tut = go(orders, chas);
				for(auto i: tut) res.PB(i);
				if (SZ(res) >= Tmax)
				{
					res.resize(Tmax);
					break;
				}
				
				FOR(i, 0, SZ(tut))
				{
					chas++;
					if (order[chas].X != -1) orders.PB(chas);
				}
				
				continue;
			}
			
			chas++;		
			res.PB(-1);
		}
		
		return res;
	}
};

namespace CombiSolution
{
	using namespace Solution;
		
	LL get_score(vector<int>& res, vector<int> here)
	{
		vector<int> R = res;
		for(auto i: here) R.PB(i);
		return Grader::grade(R);
	}	
	
	LL best_score;
	vector<int> best;
	vector<int> res;
	int best_curr_vertex;
	vector<int> best_orders;
	
	void update(vector<int>& here, int curr_vertex, vector<int>& orders)
	{
		LL S = get_score(res, here);
		if (best_score >= S) return;
		best_score = S;
		best = here;
		best_curr_vertex = curr_vertex;
		best_orders = orders;
	}
		
	vector<int> solve(vector<int> rozdil = {Tmax})
	{
		vector<int> main_orders, orders;
		
		int main_curr_vertex = 1;
		int chas;
		vector<int> here;
		int curr_vertex;
		
		FOR(r, 0, SZ(rozdil))
		{
			best_score = -1;
				
			//try new
				
			here.clear();
			chas = r ? rozdil[r - 1] : 0;
			curr_vertex = main_curr_vertex;
			orders = main_orders;
						
			while(chas < rozdil[r])
			{
				auto tut = Solution0::go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			update(here, curr_vertex, orders);
			
			//end try
			
			//try new
				
			here.clear();
			chas = r ? rozdil[r - 1] : 0;
			curr_vertex = main_curr_vertex;
			orders = main_orders;
						
			while(chas < rozdil[r])
			{
				auto tut = Solution1::go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			update(here, curr_vertex, orders);
			
			//end try
			
			//try new
				
			here.clear();
			chas = r ? rozdil[r - 1] : 0;
			curr_vertex = main_curr_vertex;
			orders = main_orders;
						
			while(chas < rozdil[r])
			{
				auto tut = Solution2::go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			update(here, curr_vertex, orders);
			
			//end try
			
			//try new
				
			here.clear();
			chas = r ? rozdil[r - 1] : 0;
			curr_vertex = main_curr_vertex;
			orders = main_orders;
						
			while(chas < rozdil[r])
			{
				auto tut = Solution3::go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			update(here, curr_vertex, orders);
			
			//end try
			
			//try new
				
			here.clear();
			chas = r ? rozdil[r - 1] : 0;
			curr_vertex = main_curr_vertex;
			orders = main_orders;
						
			while(chas < rozdil[r])
			{
				auto tut = Solution4::go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			update(here, curr_vertex, orders);
			
			//end try
			
			//try new
				
			here.clear();
			chas = r ? rozdil[r - 1] : 0;
			curr_vertex = main_curr_vertex;
			orders = main_orders;
						
			while(chas < rozdil[r])
			{
				auto tut = Solution5::go(curr_vertex, chas, chas, orders, rozdil[r]);
				chas += SZ(tut);
				for(auto i: tut) here.PB(i);
			}
			
			update(here, curr_vertex, orders);
			
			//end try
					
			for(auto i: best) res.PB(i);
			main_curr_vertex = best_curr_vertex;
			main_orders = best_orders;
		}
		
		return res;		
	}
};
	
vector<int> res;
LL score;

void update(vector<int> ans)
{
	LL s = Grader::grade(ans);
	if (s < score) return;
	score = s;
	res = ans;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	Input::read();
	Grader::init();
	Solution::init();
	
	update(Solution0::solve());
	update(Solution1::solve());
	update(Solution2::solve());
	update(Solution3::solve());
	update(Solution4::solve());
	update(Solution5::solve());
	update(Solution6::solve());
	update(Solution7::solve());
	update(Solution8::solve());
	update(Solution9::solve(200, 5, 47, 2, 5, 4, 75));
	update(Solution9::solve(300, 7, 47, 2.3, 7, 5, 90));
	update(Solution9::solve(100, 5, 57, 2.3, 7, 5, 60));
	update(Solution9::solve(600, 5, 97, 2.5, 7, 5, 70));
	update(Solution9::solve(500, 6, 178, 2, 7, 4.5, 60));
	update(Solution9::solve(400, 8, 47, 3, 7, 4.5, 180));
	update(Solution9::solve(300, 7, 47, 2.5, 7, 4.5, 90));
	vector<int> vec;
	int C;
	
	C = 8;
	vec.clear();
	FOR(i, 1, C + 1) vec.PB(i * 10000 / C);
	update(CombiSolution::solve(vec));
	
	C = 10;
	vec.clear();
	FOR(i, 1, C + 1) vec.PB(i * 10000 / C);
	update(CombiSolution::solve(vec));
	
	C = 4;
	vec.clear();
	FOR(i, 1, C + 1) vec.PB(i * 10000 / C);
	update(CombiSolution::solve(vec));
	
	C = 5;
	vec.clear();
	FOR(i, 1, C + 1) vec.PB(i * 10000 / C);
	update(CombiSolution::solve(vec));
	
	C = 2;
	vec.clear();
	FOR(i, 1, C + 1) vec.PB(i * 10000 / C);
	update(CombiSolution::solve(vec));
	
	update(CombiSolution::solve({5000, 8000, 9500, 10000}));
	
	cerr << score << endl;
	for(auto i: res) cout << i << '\n';
	cerr << clock() / (double) CLOCKS_PER_SEC << endl;
	return 0;
}


Measured memory_bytes: 5892