#ifndef TIMER_H
#define TIMER_H

#include <cstdint>

#ifdef ONLY_MY_ENVIR

#include <chrono>
class Timer {
	const std::chrono::time_point<std::chrono::system_clock> start;
	int64_t limit_microsec = 0;

public:
	Timer();
	void set(int64_t time_microsec);
	bool elapsed() const;
	int64_t getMicrosec() const;
};

#else

class Timer {
	static const uint64_t ClocksPerMicrosec;
	const uint64_t start_clocks;
	uint64_t limit_clocks;

	uint64_t getClocks() const;
public:
	Timer();
	void set(int64_t time_microsec);
	bool elapsed() const;
	int64_t getMicrosec() const;
};

#endif

#endif

#ifdef ONLY_MY_ENVIR
#include "Timer.h"
#endif

#ifdef ONLY_MY_ENVIR

using namespace std::chrono;

Timer::Timer()
	: start(system_clock::now()) {
}

void Timer::set(int64_t time_microsec) {
	limit_microsec += time_microsec;
}

bool Timer::elapsed() const {
	return getMicrosec() >= limit_microsec;
}

int64_t Timer::getMicrosec() const {
	return duration_cast<microseconds>(system_clock::now() - start).count();
}

#else

const uint64_t Timer::ClocksPerMicrosec = 2790;

uint64_t Timer::getClocks() const {
	unsigned int lo, hi;
	__asm__ volatile ("rdtsc" : "=a" (lo), "=d" (hi));
	return ((uint64_t)hi << 32) | lo;
}

Timer::Timer() 
	: start_clocks(getClocks()), limit_clocks(start_clocks) {
}

void Timer::set(int64_t time_microsec) {
	limit_clocks += time_microsec * ClocksPerMicrosec;
}

bool Timer::elapsed() const {
	return getClocks() >= limit_clocks;
}

int64_t Timer::getMicrosec() const {
	return (getClocks() - start_clocks) / ClocksPerMicrosec;
}

#endif

#ifndef RANDOM_H
#define RANDOM_H

#include <cstdint>
#include <utility>

uint32_t rnd();
uint32_t rnd(uint32_t max);

template <class T>
void shuffle(T& arr) {
	for (int i = arr.size(); i > 1; --i) {
		std::swap(arr[i - 1], arr[rnd(i)]);
	}
}

#endif
#ifdef ONLY_MY_ENVIR
#include "Random.h"
#endif

#include <vector>

uint32_t rnd() {
	static uint32_t val = 3141592653ul;
	val ^= val << 13;
	val ^= val >> 17;
	val ^= val << 15;
	return val;
}

uint32_t rnd(uint32_t max) {
	return rnd() % max;
}

#ifndef __GLOBAL_H__
#define __GLOBAL_H__

#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <chrono>

#define REP(i, a, n) for(int i = (a), i##_max_ = (n); i < i##_max_; ++i)
#define REM(i, a, n) for(int i = (int)(n) - 1, i##min_ = (a); i >= i##min_; --i)

template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) {
	fill(dest, dest + N, val);
}

template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) {
	for (int i = 0; i < M; ++i) {
		Fill(dest[i], val);
	}
}

template <class T>
T read(std::istream& ist) {
	T buffer;
	ist >> buffer;
	return buffer;
}

using Edge = std::pair<int, int>;
using Graph = std::vector<std::vector<Edge>>;
using Command = int;
using Path = std::vector<int>;
using Score = int64_t;

using Freq = int;
using Freqs = std::vector<Freq>;

template <class T>
using Matrix = std::vector<std::vector<T>>;

struct MultiGraphEdge {
	int to;
	int multiplicity;
	int rev;
};
using MultiGraph = std::vector<std::vector<MultiGraphEdge>>;

struct Order {
	int t;
	int id;
	int v;

	Order() = default;
	Order(int t, int id, int v)
		: t(t), id(id), v(v) {
	}
};

extern std::ofstream ofsdebug;

Graph readGraph(std::istream& ist);
std::vector<Order> readOrders(std::istream& ist, int t_max);
std::vector<Order> readOrdersOneTurn(std::istream& ist, int t);
void writeCommand(std::ostream& ost, Command command);
std::pair<Matrix<int>, Matrix<Path>> findShortestPaths(const Graph& graph);

Matrix<int> restrictMatrix(const Matrix<int>& original, const std::vector<int>& domain);
int lengthOfRoute(int start, const Path& route, const Matrix<int>& dist_mat);
int countTasksAchieved(int start, const Path& route, const std::vector<int>& task_nums, int t_limit, const Matrix<int>& dist_mat);

template <class Func>
double findMinimum(Func f, double lo, double hi, int iterations = 50) {
	REP(z, 0, iterations) {
		double mid_lo = (lo + lo + hi) / 3;
		double mid_hi = (lo + hi + hi) / 3;
		double val_lo = f(mid_lo);
		double val_hi = f(mid_hi);
		if (val_lo < val_hi) {
			hi = mid_hi;
		} else {
			lo = mid_lo;
		}
	}
	return (lo + hi) / 2;
}


#endif



#ifdef ONLY_MY_ENVIR
#include "Global.h"
#endif

std::ofstream ofsdebug("abcdefg.txt", std::ios::app);

Graph readGraph(std::istream& ist) {
	int N, M;
	ist >> N >> M;

	Graph ret(N);
	REP(j, 0, M) {
		int a, b, c;
		ist >> a >> b >> c;
		--a; --b;
		ret[a].push_back(Edge(b, c));
		ret[b].push_back(Edge(a, c));
	}

	return ret;
}

std::vector<Order> readOrders(std::istream& ist, int t_max) {
	std::vector<Order> ret;
	REP(t, 0, t_max) {
		auto orders = readOrdersOneTurn(ist, t);
		for (const Order& order : orders) {
			ret.push_back(order);
		}
	}
	return ret;
}

std::vector<Order> readOrdersOneTurn(std::istream& ist, int t) {
	std::vector<Order> ret;
	int k;
	ist >> k;
	REP(i, 0, k) {
		int id, v;
		ist >> id >> v;
		--v;
		ret.push_back(Order(t, id, v));
	}
	return ret;
}

void writeCommand(std::ostream& ost, Command command) {
	if (command == -1) {
		ost << -1 << std::endl;
	} else {
		ost << command + 1 << std::endl;
	}
}


std::pair<Matrix<int>, Matrix<Path>> findShortestPaths(const Graph& graph) {
	auto subFunc = [](const Graph& graph, int start) -> std::pair<std::vector<int>, std::vector<Path>> {
		const int N = graph.size();
		const int inf = 1e9;
		using State = std::tuple<int, int, int>;
		std::priority_queue<State, std::vector<State>, std::greater<State>> que;

		std::vector<int> dists(N, inf);
		std::vector<int> prevs(N, -1);
		que.push(State(0, start, -1));
		while (!que.empty()) {
			auto p = que.top(); que.pop();
			int dist = std::get<0>(p);
			int from = std::get<1>(p);
			int prev = std::get<2>(p);
			if (dists[from] != inf) continue;
			dists[from] = dist;
			prevs[from] = prev;
			for (auto e : graph[from]) {
				int to = e.first;
				int cost = e.second;
				que.push(State(dist + cost, to, from));
			}
		}

		std::vector<Path> paths;
		REP(i, 0, N) {
			Path path;
			int curr = i;
			while (curr != start) {
				path.push_back(curr);
				curr = prevs[curr];
			}
			std::reverse(path.begin(), path.end());
			paths.emplace_back(std::move(path));
		}
		return std::make_pair(dists, paths);
	};

	const int N = graph.size();
	Matrix<int> dist_mat;
	Matrix<Path> path_mat;

	REP(start, 0, N) {
		auto pair = subFunc(graph, start);
		dist_mat.emplace_back(std::move(pair.first));
		path_mat.emplace_back(std::move(pair.second));
	}

	return std::make_pair(dist_mat, path_mat);
}

Matrix<int> restrictMatrix(const Matrix<int>& original, const std::vector<int>& domain) {
	Matrix<int> ret;
	for (int i : domain) {
		std::vector<int> row;
		for (int j : domain) {
			row.push_back(original[i][j]);
		}
		ret.push_back(row);
	}
	return ret;
}

int lengthOfRoute(int start, const Path& route, const Matrix<int>& dist_mat) {
	int sum = 0;
	int v_curr = start;
	for (int v : route) {
		sum += dist_mat[v_curr][v];
		v_curr = v;
	}
	return sum;
}

int countTasksAchieved(int start, const Path& route, const std::vector<int>& task_nums, int t_limit, const Matrix<int>& dist_mat) {
	const int N = dist_mat.size();
	int t = 0;
	int v_curr = start;
	int count = 0;

	std::vector<bool> visited(N);
	for (int v : route) {
		t += dist_mat[v_curr][v];
		if (t > t_limit) break;
		if (!visited[v]) {
			visited[v] = true;
			count += task_nums[v];
		}
		v_curr = v;
	}
	return count;
}

#ifndef __OPTIMIZER_H__
#define __OPTIMIZER_H__

#ifdef ONLY_MY_ENVIR
#include "Random.h"
#include "Global.h"
#endif

// ax^2 + bx + c (c は last 以外では必要ないので高速化可)
struct QuadraticCost {
	Score a = 0;
	Score b = 0;
};

class OptimizerOracle {
	std::vector<int> state;

	Score score;
	Score score_prev;

	const int size;
	const Matrix<int> dist_mat;
	const std::vector<QuadraticCost> costs;
	struct Memo {
		int l;
		int r;
	} memo;

	constexpr static Score delay_penalty = 4.5e7;
public:
	OptimizerOracle(const Matrix<int>& dist_mat, const std::vector<QuadraticCost>& costs);
	Score transition(double tmp);
	void undo();
	Score getScore() const;
	std::vector<int> get() const;

private:
	Score calc() const;
};

std::vector<int> optimizeRoute(const Matrix<int>& dist_mat, const std::vector<std::vector<Order>>& tasks, int turn, int64_t iterations);


class OptimizerOracleLast {
	std::vector<int> state;

	Score score;
	Score score_prev;

	const int size;		// size == 頂点数
	const int thres;
	const Matrix<int> dist_mat;
	const std::vector<int> task_nums;

	struct Memo {
		int type;
		int l;
		int r;
		int from;
		int to;
	} memo;

public:
	OptimizerOracleLast(int thres, const Matrix<int>& dist_mat, const std::vector<int>& task_nums);
	int transition();
	void slide(int from, int to);
	void undo();
	int getScore() const;
	std::vector<int> get() const;

private:
	int calc() const;
};

std::vector<int> optimizeRouteLast(const Matrix<int>& dist_mat, const std::vector<std::vector<Order>>& tasks, int turn, int t_max, int ans_estim, int64_t iterations);
std::pair<bool, Path> optimizeRouteLastSub(const Matrix<int>& dist_mat, const std::vector<int>& task_nums, int t_limit, int thres, int iterations);

#endif

#ifdef ONLY_MY_ENVIR
#include "Optimizer.h"
#endif

OptimizerOracle::OptimizerOracle(const Matrix<int>& dist_mat, const std::vector<QuadraticCost>& costs)
	: size(dist_mat.size()), dist_mat(dist_mat), costs(costs) {

	REP(i, 0, size) {
		state.push_back(i);
	}
	state.push_back(0);
	score = calc();
}

Score OptimizerOracle::transition(double tmp) {
	score_prev = score;

	// こういうところもやや高速化できる？
	int l;
	int r;
	do {
		l = rnd(size) + 1;
		r = rnd(size) + 1;
	} while (l == r);
	if (l > r) std::swap(l, r);

	/* 経路長が長くなりすぎるときは棄却する(高速化のため) */
	int u0 = state[l - 1];
	int u1 = state[l];
	int v0 = state[r - 1];
	int v1 = state[r];

	int len_delta = 0;
	len_delta -= dist_mat[u0][u1] + dist_mat[v0][v1];
	len_delta += dist_mat[u0][v0] + dist_mat[u1][v1];
	if (len_delta * delay_penalty >= 10 * tmp) return 0;

	/* 遷移 */
	std::reverse(state.begin() + l, state.begin() + r);
	memo.l = l;
	memo.r = r;

	score = calc();
	Score delta = score - score_prev;
	return -delta;		// 最小化なので反転
}

void OptimizerOracle::undo() {
	std::reverse(state.begin() + memo.l, state.begin() + memo.r);
	score = score_prev;
}

Score OptimizerOracle::getScore() const {
	return score;
}

std::vector<int> OptimizerOracle::get() const {
	std::vector<int> ret(state);
	ret.erase(ret.begin());
	return ret;
}

Score OptimizerOracle::calc() const {
	int v_curr = state.front();
	int64_t t = 0;
	Score sum = 0;
	REP(i, 0, size) {
		int v_next = state[i + 1];
		t += dist_mat[v_curr][v_next];
		const QuadraticCost& cost = costs[v_next];
		sum += (cost.a * t + cost.b) * t;
		v_curr = v_next;
	}

	sum += t * delay_penalty;
	return sum;
}

// route を返す
std::vector<int> optimizeRoute(const Matrix<int>& dist_mat, const std::vector<std::vector<Order>>& tasks, int turn,  int64_t iterations) {
	// Timer timer;
	const int N = dist_mat.size();
	std::vector<QuadraticCost> costs(N);
	REP(i, 0, N) {
		for (const Order& order : tasks[i]) {
			int64_t diff = turn - order.t;
			costs[i].a += 1;
			costs[i].b += 2 * diff;
		}
	}

	OptimizerOracle oracle(dist_mat, costs);
	//constexpr int time_limit = 1500000;
	constexpr double tmp_start = 1e12;
	constexpr double tmp_finish = 1e5;
	double tmp = tmp_start;

	int64_t z = 0;
	//timer.set(time_limit);
	//while (z % 512 != 0 || !timer.elapsed()) {
	while (z < iterations) {
		++z;
		if (z % 4096 == 0) {
			//double ratio = double(timer.getMicrosec()) / time_limit;
			double ratio = double(z) / iterations;
			tmp = tmp_start * std::pow(tmp_finish / tmp_start, ratio);
#if ONLY_MY_ENVIR
			//std::cerr << tmp << ' ' << oracle.getScore() << std::endl;
#endif
		}

		Score delta = oracle.transition(tmp);
		bool accepted = delta >= 0
			|| -delta <= 8 * tmp && rnd() < std::exp(delta / tmp) * (1ll << 32);

		if (!accepted) {
			oracle.undo();
		}
	}

	//std::cerr << oracle.getScore() << std::endl;
	auto state = oracle.get();

	return state;
}


/*----------------------------------------*/
/*----------------------------------------*/
/*----------------------------------------*/

OptimizerOracleLast::OptimizerOracleLast(int thres, const Matrix<int>& dist_mat, const std::vector<int>& task_nums)
	:size(dist_mat.size()), thres(thres), dist_mat(dist_mat), task_nums(task_nums) {

	REP(i, 0, size) {
		state.push_back(i);
	}
	state.push_back(0);
	score = calc();
}

int OptimizerOracleLast::transition() {
	score_prev = score;

	int type = rnd(2);
	memo.type = type;

	if (type == 0) {
		int l;
		int r;
		do {
			l = rnd(size) + 1;
			r = rnd(size) + 1;
		} while (l == r);
		if (l >= thres + 5 && r >= thres + 5) return 0;
		if (l > r) std::swap(l, r);
		std::reverse(state.begin() + l, state.begin() + r);

		memo.l = l;
		memo.r = r;
	} else {
		int from = rnd(size - 1) + 1;
		int to;
		do {
			to = rnd(size - 1) + 1;
		} while (from == to);
		if (from >= thres + 5 && to >= thres + 5) return 0;

		slide(from, to);

		memo.from = from;
		memo.to = to;
	}

	score = calc();
	Score delta = score - score_prev;
	return -delta;		// 最小化なので反転
}

void OptimizerOracleLast::slide(int from, int to) {
	// 要高速化
	int v = state[from];
	state.erase(state.begin() + from);
	state.insert(state.begin() + to, v);

	if (from < to) {
		int v = state[from];
		REP(i, from, to) {
			state[i] = state[i + 1];
		}
		state[to] = v;
	} else {
		int v = state[from];
		REM(i, to, from) {
			state[i + 1] = state[i];
		}
		state[to] = v;
	}
}

void OptimizerOracleLast::undo() {
	if (memo.type == 0) {
		std::reverse(state.begin() + memo.l, state.begin() + memo.r);
	} else {
		slide(memo.to, memo.from);
	}
	score = score_prev;
}

int OptimizerOracleLast::getScore() const {
	return score;
}

std::vector<int> OptimizerOracleLast::get() const {
	std::vector<int> ret(state);
	ret.erase(ret.begin());
	return ret;
}

int OptimizerOracleLast::calc() const {
	int v_curr = state.front();
	int t = 0;
	int count = 0;

	REP(i, 0, size) {
		int v_next = state[i + 1];
		t += dist_mat[v_curr][v_next];
		count += task_nums[v_next];
		if (count >= thres) return t;
		v_curr = v_next;
	}
	return 1e9;
}

/* ans_estim を達成できない場合、空パスを返すので注意 */
std::vector<int> optimizeRouteLast(const Matrix<int>& dist_mat, const std::vector<std::vector<Order>>& tasks, int turn, int t_max, int ans_estim, int64_t iterations) {	
	const int N = dist_mat.size();
	const int t_remain = t_max - turn;
	int tasks_count = 0;
	for (auto&& row : tasks) {
		tasks_count += row.size();
	}

	std::vector<int> task_nums;
	for (auto&& row : tasks) {
		task_nums.push_back(row.size());
	}

	auto can_travel = [&dist_mat, &task_nums, tasks_count, t_remain](int k, int iterations, Path& route) -> bool {
		if (k > tasks_count) return false;
		auto res = optimizeRouteLastSub(dist_mat, task_nums, t_remain, k, iterations);
		bool ok = res.first;
		route = res.second;
		std::cerr << k << (ok ? " ok" : " ng") << std::endl;
		return ok;
	};

	Path route_best;
	int achieved_best = ans_estim;

	std::map<int, Path> routes;
	int exceeding = 1;
	for(; ; exceeding *= 2) {
		int k = achieved_best + exceeding;
		Path route;
		if (can_travel(k, iterations, route)) {
			routes[k] = route;
		} else {
			break;
		}
	}

	int lo = achieved_best + exceeding / 2;
	int hi = achieved_best + exceeding;
	while (hi - lo > 1) {
		int mid = (lo + hi) / 2;
		Path route;
		if (can_travel(mid, iterations, route)) {
			routes[mid] = route;
			lo = mid;
		} else {
			hi = mid;
		}
	}
	
	// 最終的にもう一度探索したい
	return routes[lo];
}

std::pair<bool, Path> optimizeRouteLastSub(const Matrix<int>& dist_mat, const std::vector<int>& task_nums, int t_limit, int thres, int iterations) {
	// Timer timer;
	const int N = dist_mat.size();
	OptimizerOracleLast oracle(thres, dist_mat, task_nums);
	//constexpr int time_limit = 1500000;
	constexpr double tmp_start = 2e3;
	constexpr double tmp_finish = 0.02;
	double tmp = tmp_start;

	int64_t z = 0;
	//timer.set(time_limit);
	//while (z % 512 != 0 || !timer.elapsed()) {
	while (z < iterations) {
		++z;
		if (z % 4096 == 0) {
			//double ratio = double(timer.getMicrosec()) / time_limit;
			double ratio = double(z) / iterations;
			tmp = tmp_start * std::pow(tmp_finish / tmp_start, ratio);
#if ONLY_MY_ENVIR
			//std::cerr << tmp << ' ' << oracle.getScore() << std::endl;
#endif
		}

		Score delta = oracle.transition();
		bool accepted = delta >= 0
			|| -delta <= 8 * tmp && rnd() < std::exp(delta / tmp) * (1ll << 32);

		if (!accepted) {
			oracle.undo();
		}

		if (oracle.getScore() <= t_limit) {
			return std::make_pair(true, oracle.get());
		}
	}

	//std::cerr << oracle.getScore() << std::endl;
	
	return std::make_pair(false, Path());
}

#ifndef __REGION_H__
#define __REGION_H__

#ifdef ONLY_MY_ENVIR
#include "Global.h"
#endif

/* 遷移はあとで調整する(部分列を入れ替える遷移を入れたい) */
class RegionOracleB {
	const Matrix<int> dist_mat;
	const int N;
	const int region_count;

	std::vector<std::vector<int>> state;
	std::vector<int> lengths;
	std::vector<int> delta_lengths;

	int score;
	int estim_score;

	struct Memo {
		bool changed;

		int type;
		int k;
		int l;
		int r;

		int kfrom;
		int kto;
		int ifrom;
		int ito;

		int ka;
		int kb;
		int width;
	} memo;
	
public:
	RegionOracleB(const Matrix<int>& dist_mat, int region_count);
	int estimate();
	void transition();
	int getScore() const;
	std::vector<int> get() const;

private:
	int calc();
	int penalty(int size) const;
};

std::vector<int> optimizeRegionB(const Matrix<int>& dist_mat, int region_count, int64_t iterations);


#endif

#ifdef ONLY_MY_ENVIR
#include "Region.h"
#include "Random.h"
#endif

RegionOracleB::RegionOracleB(const Matrix<int>& dist_mat, int region_count)
	: dist_mat(dist_mat), N(dist_mat.size()), region_count(region_count),
	state(region_count), lengths(region_count), delta_lengths(region_count) {

	REP(k, 0, region_count) {
		state[k].push_back(0);
	}

	REP(i, 1, N) {
		state[i % region_count].push_back(i);
	}

	REP(k, 0, region_count) {
		state[k].push_back(0);
	}

	score = calc();
}

int RegionOracleB::estimate() {
	int delta = 0;
	int type = rnd(3);
	memo.type = type;
	if (type == 0) {
		// swap
		int k = rnd(region_count);
		int size = state[k].size();
		if (size <= 3) {
			memo.changed = false;		// 注意
			return 0;
		}

		int l;
		int r;
		do {
			l = rnd(size - 1) + 1;
			r = rnd(size - 1) + 1;
		} while (l == r);
		if (l > r) std::swap(l, r);

		memo.k = k;
		memo.l = l;
		memo.r = r;

		int u0 = state[k][l - 1];
		int u1 = state[k][l];
		int v0 = state[k][r - 1];
		int v1 = state[k][r];

		delta_lengths[k] = (dist_mat[u0][v0] + dist_mat[u1][v1]) - (dist_mat[u0][u1] + dist_mat[v0][v1]);
		delta = penalty(lengths[k] + delta_lengths[k]) - penalty(lengths[k]);
	} else if (type == 1) {
		// move
		int kfrom = rnd(region_count);
		int kto;
		do {
			kto = rnd(region_count);
		} while (kfrom == kto);

		if (state[kfrom].size() <= 2) {
			memo.changed = false;
			return 0;
		}

		int ifrom = rnd(state[kfrom].size() - 2) + 1;
		int ito = rnd(state[kto].size() - 1) + 1;

		memo.kfrom = kfrom;
		memo.kto = kto;
		memo.ifrom = ifrom;
		memo.ito = ito;

		int ua = state[kfrom][ifrom - 1];
		int ub = state[kfrom][ifrom];
		int uc = state[kfrom][ifrom + 1];

		int va = state[kto][ito - 1];
		int vb = state[kto][ito];

		delta_lengths[kfrom] = dist_mat[ua][uc] - (dist_mat[ua][ub] + dist_mat[ub][uc]);
		delta_lengths[kto] = (dist_mat[va][ub] + dist_mat[ub][vb]) - dist_mat[va][vb];

		delta = penalty(lengths[kfrom] + delta_lengths[kfrom]) - penalty(lengths[kfrom]);
		delta += penalty(lengths[kto] + delta_lengths[kto]) - penalty(lengths[kto]);
	} else {
		int ka = rnd(region_count);
		int kb;
		do {
			kb = rnd(region_count);
		} while (ka == kb);

		if (state[ka].size() <= 2 || state[kb].size() <= 2) {
			memo.changed = false;
			return 0;
		}
		
		int cap = std::min(state[ka].size() - 2, state[kb].size() - 2);
		int width = rnd(cap) + 1;
		
		auto calcLength = [this](int k, int width) -> int {
			int sum = 0;
			REP(i, 0, width) {
				int from = state[k][i];
				int to = state[k][i + 1];
				sum += dist_mat[from][to];
			}
			return sum;
		};

		int lengtha = calcLength(ka, width);
		int lengthb = calcLength(kb, width);

		int u0 = state[ka][width];
		int u1 = state[ka][width + 1];
		int v0 = state[kb][width];
		int v1 = state[kb][width + 1];

		delta_lengths[ka] = lengthb - lengtha + (dist_mat[v0][u1] - dist_mat[u0][u1]);
		delta_lengths[kb] = lengtha - lengthb + (dist_mat[u0][v1] - dist_mat[v0][v1]);

		delta = penalty(lengths[ka] + delta_lengths[ka]) - penalty(lengths[ka]);
		delta += penalty(lengths[kb] + delta_lengths[kb]) - penalty(lengths[kb]);

		memo.ka = ka;
		memo.kb = kb;
		memo.width = width;
	}

	memo.changed = true;
	estim_score = score + delta;
	return -delta;		// 最小化なので反転
}

void RegionOracleB::transition() {
	if (!memo.changed) return;

	score = estim_score;
	if (memo.type == 0) {
		std::reverse(state[memo.k].begin() + memo.l, state[memo.k].begin() + memo.r);
		lengths[memo.k] += delta_lengths[memo.k];
	} else if(memo.type == 1) {
		int v = state[memo.kfrom][memo.ifrom];
		state[memo.kto].insert(state[memo.kto].begin() + memo.ito, v);
		state[memo.kfrom].erase(state[memo.kfrom].begin() + memo.ifrom);
		lengths[memo.kfrom] += delta_lengths[memo.kfrom];
		lengths[memo.kto] += delta_lengths[memo.kto];
	} else {
		std::swap_ranges(
			state[memo.ka].begin() + 1, state[memo.ka].begin() + (memo.width + 1),
			state[memo.kb].begin() + 1
			);
		lengths[memo.ka] += delta_lengths[memo.ka];
		lengths[memo.kb] += delta_lengths[memo.kb];
	}
}

int RegionOracleB::getScore() const {
	return score;
}

std::vector<int> RegionOracleB::get() const {
	int sum = 0;
	REP(k, 0, region_count) {
		int length = 0;
		REP(i, 1, state[k].size()) {
			int from = state[k][i - 1];
			int to = state[k][i];
			length += dist_mat[from][to];
		}
		ofsdebug << k << ": " << length << std::endl;
		sum += length;
	}
	ofsdebug << "length: " << sum << std::endl;

	std::vector<int> ret(N);
	REP(k, 0, region_count) {
		for (int v : state[k]) {
			ret[v] = k;
		}
	}
	ret[0] = -1;
	return ret;
}

int RegionOracleB::calc() {
	int sum = 0;
	REP(k, 0, region_count) {
		int length = 0;
		REP(i, 1, state[k].size()) {
			int from = state[k][i - 1];
			int to = state[k][i];
			length += dist_mat[from][to];
		}
		lengths[k] = length;
		sum += penalty(length);
	}
	return sum;
}

int RegionOracleB::penalty(int size) const {
	const int coeff = dist_mat.size();
	return (size + coeff) * size;
}

std::vector<int> optimizeRegionB(const Matrix<int>& dist_mat, int region_count, int64_t iterations) {
	// Timer timer;

	RegionOracleB oracle(dist_mat, region_count);
	//constexpr int time_limit = 1500000;
	constexpr double tmp_start = 7e4;
	constexpr double tmp_finish = 1e0;
	double tmp = tmp_start;

	int64_t z = 0;
	//timer.set(time_limit);
	//while (z % 512 != 0 || !timer.elapsed()) {
	while (z < iterations) {
		++z;
		if (z % 4096 == 0) {
			//double ratio = double(timer.getMicrosec()) / time_limit;
			double ratio = double(z) / iterations;
			tmp = tmp_start * std::pow(tmp_finish / tmp_start, ratio);
#if ONLY_MY_ENVIR
			//std::cerr << tmp << ' ' << oracle.getScore() << std::endl;
#endif
		}

		Score delta = oracle.estimate();
		bool accepted = delta >= 0
			|| -delta <= 8 * tmp && rnd() < std::exp(delta / tmp) * (1ll << 32);

		if (accepted) {
			oracle.transition();
		}
	}

	//std::cerr << oracle.getScore() << std::endl;
	auto state = oracle.get();
	return state;
}

#ifndef __PROBLEM_B_H__
#define __PROBLEM_B_H__

#ifdef ONLY_MY_ENVIR
#include "Global.h"
#endif

void problemA(std::ostream& log_stream);
void problemB(std::ostream& log_stream);
void readLoading(std::istream& ist);
bool readVerdict(std::istream& ist);

class Simulator {
	std::vector<Order> orders;
	std::vector<std::vector<Order>> tasks;	// 頂点ごとに割り振った注文(車に積んだものだけ)
	int tpos_loaded = 0;					// 次に車に積む注文番号

	int turn = 0;
	int v_curr = 0;		// 前の頂点
	int v_next = 0;		// 次の頂点
	int position = 0;	// 距離をいくら進んだか
	int distance = 0;
	
	const int t_max;
	Matrix<int> dist_mat;

	Score score = 0;
	int completed_count = 0;

public:
	Simulator(int t_max, int N);
	void init(const Matrix<int>& dist_mat_arg);

	bool step(Command command);
	void addOrderInfo(const Order& order);
	Score estimate(const Path& path) const;
	int hasTasks(int v) const;
	std::vector<Order> getTasks(int v) const;

	int completedCount() const;
	Score getScore() const;

private:
	bool isAtStore() const;
	void updateTasks();
};

class ManagerB {
	const Graph graph;
	const Freqs freqs;
	const int t_max;
	const int t_last_order;

	const std::pair<Matrix<int>, Matrix<Path>> mat_pair;
	const Matrix<int>& dist_mat;
	const Matrix<Path>& path_mat;

	std::vector<Command> commands;

	int turn = 0;
	std::vector<Order> orders;
	Simulator simulator;
	std::chrono::system_clock::time_point start_time;

	enum class State {
		Normal,
		Last,
		PostLast
	} state = State::Normal;

	constexpr static int region_count = 4;
	std::vector<int> region_id;
	
public:
	ManagerB(const Graph& graph, const Freqs& freqs, int t_max);
	void debug(std::ostream& log_stream);
	void precalc();
	Command step(const std::vector<Order>& orders_turn);
	void updateCommands();
	Path improveLastTravel(int ans_estim);
};

Path routeToPath(int start, const Path& route, const Matrix<Path>& path_mat);
std::vector<Command> pathToCommands(int start, const Path& path, const Matrix<int>& dist_mat);
std::vector<Command> pathToCommandsLast(int start, const Path& path, int turn_max, const Matrix<int>& dist_mat, const Matrix<Path>& path_mat);
MultiGraph pathToGraph(int N, int start, const Path& path);

#endif

#ifdef ONLY_MY_ENVIR
#include "problemB.h"
#include "Timer.h"
#include "Optimizer.h"
#include "Region.h"
#endif

using std::cin;
using std::cout;

void problemA(std::ostream& log_stream) {
	Graph graph = readGraph(cin);
	std::vector<int> freqs(graph.size(), 1);
	freqs[0] = 0;
	int t_max = read<int>(cin);

	ManagerB manager(graph, freqs, t_max);
	REP(t, 0, t_max) {
		auto orders_turn = readOrdersOneTurn(cin, t);
		Command command = manager.step(orders_turn);
		writeCommand(cout, command);
	}
	manager.debug(log_stream);
	return;
}

void problemB(std::ostream& log_stream) {
	Graph graph = readGraph(cin);
	std::vector<int> freqs;
	REP(i, 0, graph.size()) {
		freqs.push_back(read<int>(cin));
	}

	int t_max = read<int>(cin);

	ManagerB manager(graph, freqs, t_max);
	REP(t, 0, t_max) {
		auto orders_turn = readOrdersOneTurn(cin, t);
		readLoading(cin);		// ignore
		Command command = manager.step(orders_turn);
		writeCommand(cout, command);
		bool is_correct = readVerdict(cin);
		if (!is_correct) return;
	}
	manager.debug(log_stream);
	return;
}

void readLoading(std::istream& ist) {
	int n;
	ist >> n;
	REP(z, 0, n) {
		int buf;
		ist >> buf;
	}
}

bool readVerdict(std::istream& ist) {
	std::string verdict = read<std::string>(ist);
	if (verdict != "OK") return false;
	int k;
	ist >> k;
	REP(z, 0, k) {
		int id;
		ist >> id;
	}
	return true;
}

/*---------------------------------*/
/*---------   Simulator   ---------*/
/*---------------------------------*/

Simulator::Simulator(int t_max, int N)
	: t_max(t_max), tasks(N) {
	assert(isAtStore());
}

void Simulator::init(const Matrix<int>& dist_mat_arg) {
	dist_mat = dist_mat_arg;
}

bool Simulator::step(Command command) {
	++turn;
	if (command == -1) {
		// nothing
	} else {
		if (position == 0) {
			// 本当は隣接判定をしたい
			v_next = command;
			distance = dist_mat[v_curr][v_next];
			++position;
		} else {
			if (command == v_next) {
				++position;
			} else if (command == v_curr) {
				--position;
			} else {
				return false;	// invalid
			}
		}

		if (position == distance) {
			v_curr = v_next;
			position = 0;

			// タスクを消化
			completed_count += tasks[v_curr].size();
			
			for (auto task : tasks[v_curr]) {
				int64_t t_opt = task.t;
				int64_t t_diff = turn - t_opt;
				Score delta = int64_t(t_max) * t_max - t_diff * t_diff;
				score += delta;
			}

			tasks[v_curr].clear();		// タスクを消化
		}
	}

	if (isAtStore()) {
		updateTasks();
	}
	return true;
}

void Simulator::addOrderInfo(const Order& order) {
	orders.push_back(order);

	if (isAtStore()) {
		updateTasks();
	}
}

// 現在時刻から path を巡回したら何点得られるか
Score Simulator::estimate(const Path& path) const {
	assert(isAtStore());

	Score score = 0;
	int t = turn;
	int v = 0;
	std::vector<bool> visited(dist_mat.size());
	for (auto v_to : path) {
		t += dist_mat[v][v_to];
		if (t > t_max) break;

		// 頂点を訪れる
		if (!visited[v_to]) {
			visited[v_to] = true;
			for (Order order : tasks[v_to]) {
				int64_t t_opt = order.t;
				int64_t t_diff = t - t_opt;
				Score delta = int64_t(t_max) * t_max - t_diff * t_diff;
				score += delta;
			}
		}
		v = v_to;
	}
	t += dist_mat[v_curr][0];
	return score;
}

int Simulator::hasTasks(int v) const {
	return tasks[v].size();
}

std::vector<Order> Simulator::getTasks(int v) const {
	return tasks[v];
}

int Simulator::completedCount() const {
	return completed_count;
}

Score Simulator::getScore() const {
	return score;
}

bool Simulator::isAtStore() const {
	return v_curr == 0 && position == 0;
}

void Simulator::updateTasks() {
	// 店にいるなら新たな商品を車に積む
	if (isAtStore()) {
		while (tpos_loaded < orders.size() && orders[tpos_loaded].t <= turn) {
			const Order& order = orders[tpos_loaded];
			tasks[order.v].push_back(order);
			++tpos_loaded;
		}
	}
}

/*--------------------------------*/
/*---------   ManagerB   ---------*/
/*--------------------------------*/

ManagerB::ManagerB(const Graph& graph, const Freqs& freqs, int t_max) 
	: graph(graph), freqs(freqs), t_max(t_max), t_last_order((0.95 + 1e-8) * t_max), simulator(t_max, graph.size()),
	mat_pair(findShortestPaths(graph)), dist_mat(mat_pair.first), path_mat(mat_pair.second) {

	start_time = std::chrono::system_clock::now();
	precalc();
	simulator.init(dist_mat);
}

void ManagerB::debug(std::ostream& log_stream) {
	//time_t timepoint = time(nullptr);
	//char str[256];
	//strftime(str, sizeof(str), "%Y-%m-%d %H:%M:%S", localtime(&timepoint));
	//log_stream << str << std::endl;

	constexpr Score unit = 100000000;
	int tasks_remaining = orders.size() - simulator.completedCount();
	Score score = simulator.getScore();
	Score loss = orders.size() * unit - score;
	Score loss_by_lost = tasks_remaining * unit;
	Score loss_by_late = loss - loss_by_lost;
	log_stream << std::setprecision(14) << std::fixed
		<< double(loss) / unit << ' '
		<< double(loss_by_lost) / unit << ' '
		<< double(loss_by_late) / unit << ' ';

	using namespace std::chrono;
	auto end_time = system_clock::now();
	log_stream << "time: " << duration_cast<microseconds>(end_time - start_time).count() << std::endl;
}

void ManagerB::precalc() {
	const int iterations = 3e7;
	region_id = optimizeRegionB(dist_mat, region_count, iterations);

	REP(i, 0, 500) {
		commands.push_back(-1);
	}
}

Command ManagerB::step(const std::vector<Order>& orders_turn) {
	for (const Order& order : orders_turn) {
		orders.push_back(order);
		simulator.addOrderInfo(order);
	}

	updateCommands();
	Command command = commands[turn];
	simulator.step(command);

	++turn;
	return command;
}

void ManagerB::updateCommands() {
	if (commands.size() > turn) return;
	if (state == State::Normal && turn >= t_last_order) {
		state = State::Last;
	}

	const int N = graph.size();
	
	/* 回りたい頂点を列挙 */
	std::vector<int> vs = { 0 };
	static int region_curr = 0;
	REP(i, 1, N) {
		if (region_id[i] != region_curr) continue;
		if (simulator.hasTasks(i)) {
			vs.push_back(i);
		}
	}

	++region_curr;
	if (region_curr == region_count) {
		region_curr = 0;
	}
	
	// タスクがないときは無視して休む
	if (vs.size() == 1) {
		REP(z, 0, 200) {
			commands.push_back(-1);
		}
		return;
	}

	Matrix<int> dist_mat_reduced = restrictMatrix(dist_mat, vs);
	std::vector<std::vector<Order>> tasks_reduced;
	for (int i : vs) {
		tasks_reduced.push_back(simulator.getTasks(i));
	}

	std::vector<int> task_nums_reduced;
	for (const auto& task : tasks_reduced) {
		task_nums_reduced.push_back(task.size());
	}

	int task_count = std::accumulate(task_nums_reduced.begin(), task_nums_reduced.end(), 0);

	constexpr int64_t iterations_per_task = 1.5e4;
	const int64_t iterations = iterations_per_task * task_count; //1e7;
	Path route_reduced = optimizeRoute(dist_mat_reduced, tasks_reduced, turn, iterations);

	Path route;
	for (int p : route_reduced) {
		route.push_back(vs[p]);
	}

	if (state == State::Last) {
		// 暫定解
		int achieved = countTasksAchieved(0, route_reduced, task_nums_reduced, t_max - turn, dist_mat_reduced);
		Path res = improveLastTravel(achieved);
		if (!res.empty()) {
			route = res;
		}
		state = State::PostLast;
	}

	Path path = routeToPath(0, route, path_mat);
	auto commands_to_add = pathToCommands(0, path, dist_mat);

	/* 操作列を補充 */
	for (Command command : commands_to_add) {
		commands.push_back(command);
	}
}

// 空パスを返しうる
Path ManagerB::improveLastTravel(int ans_estim) {
	const int N = dist_mat.size();
	std::vector<int> vs_last = { 0 };
	REP(i, 1, N) {
		if (simulator.hasTasks(i)) {
			vs_last.push_back(i);
		}
	}

	Matrix<int> dist_mat_reduced_last = restrictMatrix(dist_mat, vs_last);
	std::vector<std::vector<Order>> tasks_reduced_last;
	for (int i : vs_last) {
		tasks_reduced_last.push_back(simulator.getTasks(i));
	}

	std::vector<int> task_nums_last;
	for (auto&& row : tasks_reduced_last) {
		task_nums_last.push_back(row.size());
	}

	int task_count_last = std::accumulate(task_nums_last.begin(), task_nums_last.end(), 0);
	constexpr int64_t iterations_per_task = 1.0e4;
	const int64_t iterations_last = iterations_per_task * task_count_last;

	Path res_reduced = optimizeRouteLast(dist_mat_reduced_last, tasks_reduced_last, turn, t_max, ans_estim, iterations_last);
	Path ret_route;
	for (int p : res_reduced) {
		ret_route.push_back(vs_last[p]);
	}
	return ret_route;
}

// 0始点の route を path に変換(必ず隣接点同士を結ぶような形式に変換)
Path routeToPath(int start, const Path& route, const Matrix<Path>& path_mat) {
	Path ret;
	int v_curr = start;
	for (int v : route) {
		for (int i : path_mat[v_curr][v]) {
			ret.push_back(i);
		}
		v_curr = v;
	}
	return ret;
}

// 0始点の pathを達成するコマンド列を作成
std::vector<Command> pathToCommands(int start, const Path& path, const Matrix<int>& dist_mat) {
	std::vector<Command> ret;
	int v_curr = start;
	for (int v : path) {
		int dist = dist_mat[v_curr][v];
		REP(x, 0, dist) {
			ret.push_back(v);
		}
		v_curr = v;
	}
	return ret;
}

MultiGraph pathToGraph(int N, int start, const Path& path) {
	Matrix<int> mat(N, std::vector<int>(N, 0));

	int v_curr = start;
	for (int v : path) {
		if (v == v_curr) continue;
		++mat[v_curr][v];
		++mat[v][v_curr];
		v_curr = v;
	}

	MultiGraph ret(N);
	REP(i, 0, N) {
		REP(j, i + 1, N) {
			if (mat[i][j] == 0) continue;
			int idx = ret[i].size();
			int idx_rev = ret[j].size();
			ret[i].push_back(MultiGraphEdge{ j, mat[i][j], idx_rev });
			ret[j].push_back(MultiGraphEdge{ i, mat[i][j], idx });
		}
	}
	return ret;
}
#ifndef __MAIN_H__
#define __MAIN_H__

#ifdef ONLY_MY_ENVIR
#include "Global.h"
#include "Random.h"
#endif

#endif




#ifdef ONLY_MY_ENVIR
#include "Main.h"
#include "ProblemB.h"
#include "Test.h"
#include "Optimizer.h"
#endif

/* V <= 400, E <= 800, D <= 114 */
int main(int argc, char *argv[]) {
	problemB(std::cerr);
	return 0;
}



Measured memory_bytes: 34384