#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>
#include <time.h>
#include <stdlib.h>

#define Inf 2000000000
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(X) (X).begin(),(X).end()
#define graph_from1 true
#define graph_tree false
#define graph_weight true
#define graph_digraph false
using namespace std;
typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int debug = 0; // 0 : 提出, 1 : コードテスト, 2 : fin - fout
double time_ratio;
clock_t time_ini;
double time_limit = 30000.0; // 30000.0
double time_2_3 = time_limit * 2 / 3; // 20000.0

int V, E;
vector<vector<Pii>> G(V);

typedef struct {
	int new_id;
	int time;
	int dst;
}Order;

typedef struct {
	int Nnew;
	vector<Order> orders;
}Info;

class Info_all{
public:
	int Tmax;
	vector<Info> infos;
	vector<Order> idlist;
};

class Command_all {
public:
	int Tmax;
	vi commands;
};

class Graph_func
{
public:
	int Vnum;
	int Enum;
	vector<pair<int, int> > edgelist;
	vector<int> edgeweight;
	vector<vector<int> > adjlist;
	vector<vector<int> > adjlistweight;
	vector<int> adjnum;

	vector<int> xdist;
	vector<vi> xydist;
	vector<vi> xylen;
	vi xydist_max;
	vi x_from;
	vector<vi> xy_from;

	int v_cent;
	vi v_circle;

	vector<bool> x_visited;
	vector<int> x_prqarr;
	vector<bool> x_filled;

	void graphini();
	void adjini();
	void visited_ini();
	void adjsort();
	void graph_BFS(int BFS_ini);
	void graph_DFS(int DFS_ini);
	void xyDist(int x);   // ex. xyDist(3, 0)
	int dim_num(int dim);

	vi v_circle_ini_dp();
	void v_circle_ini();

	bool xydist_def = false;
};

void Graph_func::graphini()
{
	edgelist.resize(Enum);
	edgeweight.resize(Enum);
	adjnum.resize(Vnum);
	xdist.resize(Vnum);
	adjlist.resize(Vnum);
	adjlistweight.resize(Vnum);
	xydist.resize(Vnum);
	xylen.resize(Vnum);
	xydist_max.resize(Vnum);
	x_from.resize(Vnum);
	xy_from.resize(Vnum);
	rep(i, Vnum) {
		xydist[i].resize(Vnum);
		xylen[i].resize(Vnum);
		xydist_max[i] = 0;
		xy_from[i].resize(Vnum);
		rep(j, Vnum) {
			xylen[i][j] = -1;
		}
	}
	return;
}

void Graph_func::adjini()
{
	for (int i = 0; i < Vnum; i++)
		adjnum[i] = 0;
	for (int i = 0; i < Enum; i++)
	{
		int x = edgelist[i].first;
		int y = edgelist[i].second;
		adjlist[x].push_back(y);
		adjlist[y].push_back(x);
		int xyweight = edgeweight[i];
		adjlistweight[x].push_back(xyweight);
		adjlistweight[y].push_back(xyweight);
		xylen[x][y] = xyweight;
		xylen[y][x] = xyweight;
		adjnum[x]++;
		adjnum[y]++;
	}
	x_visited.resize(Vnum);
	visited_ini();

	return;
}

void Graph_func::visited_ini()
{
	for (int i = 0; i < Vnum; i++)
		x_visited[i] = false;
	x_prqarr.resize(0);
}

void Graph_func::adjsort()
{
	for (int i = 0; i < Vnum; i++)
		sort(adjlist[i].begin(), adjlist[i].end(), less<int>());
	return;
}



void Graph_func::graph_BFS(int BFS_ini)
{
	visited_ini();
	x_prqarr.push_back(BFS_ini);
	x_visited[BFS_ini] = true;

	while (!x_prqarr.empty())
	{
		int Ntmp = x_prqarr.size();
		for (int a = 0; a < Ntmp; a++)
		{
			int x = x_prqarr[0];
			x_prqarr.erase(x_prqarr.begin());
			for (int i = 0; i < adjnum[x]; i++)
			{
				int x_new = adjlist[x][i];
				if (!x_visited[x_new])
				{
					x_prqarr.push_back(x_new);
					x_visited[x_new] = true;
				}
			}
		}
	}
	return;
}

void Graph_func::graph_DFS(int DFS_ini)
{
	visited_ini();
	x_prqarr.push_back(DFS_ini);
	x_visited[DFS_ini] = true;

	while (!x_prqarr.empty())
	{
		int Ntmp = x_prqarr.size();
		for (int a = 0; a < Ntmp; a++)
		{
			int x = x_prqarr[x_prqarr.size() - 1];
			x_prqarr.pop_back();
			for (int i = 0; i < adjnum[x]; i++)
			{
				int x_new = adjlist[x][i];
				if (!x_visited[x_new])
				{
					x_prqarr.push_back(x_new);
					x_visited[x_new] = true;
				}
			}
		}
	}
	return;
}

void Graph_func::xyDist(int x)  // ex. xyDist(3), Dijkstra's algorithm
{
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > xdist_que; //Alive_vertices
	for (int i = 0; i < Vnum; i++)
		xdist[i] = Inf;
	xdist[x] = 0;
	x_from[x] = x;
	pair<int, int> xdist_que_tmp;
	xdist_que_tmp.first = 0;
	xdist_que_tmp.second = x;
	xdist_que.push(xdist_que_tmp);
	while (!xdist_que.empty())
	{
		xdist_que_tmp = xdist_que.top();
		xdist_que.pop();
		int xdist_tmp = xdist_que_tmp.first;
		int x_tmp = xdist_que_tmp.second;
		if (xdist[x_tmp] == xdist_tmp)
		{
			for (int i = 0; i < adjnum[x_tmp]; i++)
			{
				int x_new = adjlist[x_tmp][i];
				int dist_diff;
				if (graph_weight)
					dist_diff = adjlistweight[x_tmp][i];
				else dist_diff = 1;
				if (xdist[x_new] > xdist[x_tmp] + dist_diff)
				{
					x_from[x_new] = x_tmp;
					xdist[x_new] = xdist[x_tmp] + dist_diff;
					xdist_que_tmp.first = xdist[x_new];
					xdist_que_tmp.second = x_new;
					xdist_que.push(xdist_que_tmp);
				}
			}
		}
	}
	/*rep(i, V) {
		int x_tmp = i;
		while (1) {
			xway[i].push_back(x_tmp);
			if (x_tmp == x)
				break;
			x_tmp = x_from[x_tmp];
		}
		if (i == x)
			xway[i].push_back(x);
		reverse(xway[i].begin(), xway[i].end());
	}*/
}

int Graph_func::dim_num(int dim)
{
	int anstmp = 0;
	for (int i = 0; i < Vnum; i++)
	{
		if (adjnum[i] == dim)
			anstmp++;
	}
	return anstmp;
}

typedef struct {
	int dist;
	vi vlist;
}DP;

vi Graph_func::v_circle_ini_dp() {
	int bit_sum = 1;
	rep(i, 12)
		bit_sum *= 2;
	vector<vector<DP>> dp;
	dp.resize(bit_sum);
	rep(b, bit_sum) {
		dp[b].resize(12);
		rep(i, 12) {
			dp[b][i].dist = Inf;
			dp[b][i].vlist.push_back(0);
		}
	}
	dp[1][0].dist = 0;
	rep(i, 12) { // 更新前の要素数
		if (i == 0)
			continue;
		rep(b, bit_sum) { // 更新前のbit
			int bit_num = 0;
			rep(j, 12) {
				if ((b >> j) % 2 == 1)
					bit_num++;
			}
			if (bit_num != i)
				continue;
			rep(v_next, 12) {
				rep(v_prev, 12) {
					if ((b >> v_next) % 2 == 1) // 配置予定が既に存在している
						continue;
					if ((b >> v_prev) % 2 == 0) // 配置済みがまだ存在しない
						continue;
					int bit_add = 1 << v_next;
					int x_prev = v_circle[v_prev];
					int x_next = v_circle[v_next];
					int dist_eval = dp[b][v_prev].dist + xydist[v_prev][v_next];
					if (dp[b + bit_add][v_next].dist > dist_eval) {
						dp[b + bit_add][v_next].dist = dist_eval;
						dp[b + bit_add][v_next].vlist = dp[b][v_prev].vlist;
						dp[b + bit_add][v_next].vlist.push_back(v_next);
					}
				}
			}
		}
	}
	int dist_min = Inf;
	vi vlist_min;
	rep(v_prev, 12) { // 環状化
		int b = bit_sum - 1;
		int v_next = 0;
		int x_prev = v_circle[v_prev];
		int x_next = v_circle[v_next];
		int dist_eval = dp[b][v_prev].dist + xydist[v_prev][v_next];
		if (dist_min > dist_eval) {
			dist_min = dist_eval;
			vlist_min = dp[b][v_prev].vlist;
		}
	}
	vi v_circle_new = v_circle;
	rep(i, 12) {
		v_circle_new[i] = v_circle[vlist_min[i]];
		cout << (v_circle_new[i] + 1) << " ";
	}
	cout << endl;
	v_circle = v_circle_new;
}

void Graph_func::v_circle_ini() {
	double R = sqrt((double)V);
	double r = R * (sqrt(2.0) / 4.0); // xy座標上の円の半径
	r *= 4.0; // グラフ上の円の半径
	int xydist_max_min = Inf;
	v_cent = 0;
	rep(v, V) {
		if (xydist_max_min > xydist_max[v]) {
			xydist_max_min = xydist_max[v];
			v_cent = v;
		}
	}
	cout << (v_cent + 1) << endl;
	//cout << r << endl;
	vector<Pii> v_diff(V);
	rep(v, V) {
		int diff_tmp = abs(xydist[v_cent][v] - (int)r);
		v_diff[v].first = diff_tmp;
		v_diff[v].second = v;
	}
	sort(v_diff.begin(), v_diff.end(), less<Pii>());
	rep(i, 12) {
		v_circle.push_back(v_diff[i].second);
		cout << (v_diff[i].second + 1) << " ";
	}
	cout << endl;
	v_circle_ini_dp();
}

Graph_func graph;
Info_all info_all;
Command_all command_all;
vector<vi> dst_to_id;
vector<double> order_num;
vector<double> time_return_ratio;

void readProblem() {
	time_ini = clock();
	string sample;
	ifstream fin;
	if (debug == 2) {
		string num;
		cout << " input : ";
		cin >> num;
		string filename;
		filename = "input_2_" + num + ".txt";
		fin.open(filename);
		string new_command;
		new_command = "copy /B " + filename + " input.txt";
		const char* new_command_c = new_command.c_str();
		system(new_command_c);
	}
	if (debug == 2)
		fin >> V >> E;
	else
		cin >> V >> E;
	graph.Vnum = V;
	graph.Enum = E;

	graph.graphini();

	rep(i, E) {
		// recieve edges
		int u, v, d;
		if (debug == 2)
			fin >> u >> v >> d;
		else
			cin >> u >> v >> d;
		u--; v--;
		graph.edgelist[i].first = u;
		graph.edgelist[i].second = v;
		graph.edgeweight[i] = d;
		//G[u].push_back({ v, d });
		//G[v].push_back({ u, d });
	}

	int Tmax;
	if (debug == 2)
		fin >> Tmax;
	else
		cin >> Tmax;
	info_all.Tmax = Tmax;
	info_all.infos.resize(Tmax);
	dst_to_id.resize(V);


	// recieve info
	double order_num_prev = 0.0;
	rep(t, Tmax) {
		int Nnew;
		if (debug == 2)
			fin >> Nnew;
		else
			cin >> Nnew;
		info_all.infos[t].Nnew = Nnew;
		vector<Order> order;
		for (int n = 0; n < Nnew; n++) {
			Order order_tmp;
			if (debug == 2)
				fin >> order_tmp.new_id >> order_tmp.dst;
			else
				cin >> order_tmp.new_id >> order_tmp.dst;
			order_tmp.new_id--;
			order_tmp.dst--;
			order_tmp.time = t;
			order.push_back(order_tmp);
			info_all.idlist.push_back(order_tmp);
			dst_to_id[order_tmp.dst].push_back(order_tmp.new_id);
		}
		double num_count = 100.0;
		double Nnew_add = (double)Nnew;
		if ((t - (int)num_count) >= 0)
			Nnew_add -= info_all.infos[t - (int)num_count].Nnew;
		order_num_prev += Nnew_add / num_count;
		order_num.push_back(order_num_prev);
		double time_return_ratio_tmp;
		if (order_num[t] == 0) {
			time_return_ratio_tmp = Inf;
		}
		else {
			time_return_ratio_tmp = 5.0 / order_num[t]; // 往復距離*2
		}
		time_return_ratio_tmp = min(time_return_ratio_tmp, 10.0);
		time_return_ratio.push_back(time_return_ratio_tmp);
		info_all.infos[t].orders = order;
	}

	if (debug == 2)
		fin.close();

	if (debug == 2)
		time_ratio = 0.115;
	else
		time_ratio = 1;

	graph.adjini();

	command_all.Tmax = Tmax;
	command_all.commands.resize(Tmax);

	return;
}

void writeSolution() {
	ofstream fout;
	if (debug == 2)
		fout.open("output.txt");

	rep(i, command_all.Tmax) {
		int command = command_all.commands[i];
		if (command != -1)
			command++;
		if (debug == 2)
		{
			fout << command << endl;
		}
		else {
			cout << command << endl;
		}
	}

	if (debug == 2)
		fout.close();

	return;
}

void write_val(ll val_tmp, string S)
{
	if (debug != 0)
		cout << val_tmp << S << endl;
	return;
}

double time_diff()
{
	int time_tmp = clock();
	const double time = time_ratio * static_cast<double>(time_tmp - time_ini) / CLOCKS_PER_SEC * 1000.0;
	return time;
}

int xor128() {
	static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	int t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

double xor128_0to1(){
	int t = xor128();
	while (1) {
	if (t < 1000000000)
		break;
	t = xor128();
	}
	double d = (double)t / 1000000000.0;
	return d;
}

typedef struct {
	int begin_t;
	int end_t;
}Ptt;

map<int, Ptt> id_t_list;

ll evaluation() {
	ll pe_sum = 0;
	int over_count = 0;
	for (pair<int, Ptt> id_tmp : id_t_list) {
		Ptt tttmp = id_t_list[id_tmp.first];
		ll pe_tmp = tttmp.end_t - tttmp.begin_t;
		if (tttmp.end_t > 10000) {
			pe_tmp = 10000;
			over_count++;
		}
		pe_tmp *= pe_tmp;
		/*if (tttmp.end_t > 9990) {
			pe_tmp *= 2;
		}*/
		pe_tmp = min(pe_tmp, (ll)100000000);
		pe_sum += pe_tmp;
	}
	ll eval = pe_sum * (-1);
	//write_val(over_count, " O");
	return eval;
}

void solve() {
	rep(i, V) {
		graph.xyDist(i);
		graph.xydist[i] = graph.xdist;
		graph.xy_from[i] = graph.x_from;
		rep(j, V) {
			graph.xydist_max[i] = max(graph.xydist_max[i], graph.xydist[i][j]);
		}
	}
	int diff_0_max = 0;
	rep(i, V) {
		diff_0_max = max(diff_0_max, graph.xydist[0][i]);
	}
	//double time_return = (double)diff_0_max; // *8.0;
	//time_return = 500.0;

	//graph.v_circle_ini();

	double T_double = (double)info_all.Tmax; // 10000.0
	double T_99 = T_double * 0.99; // 9900.0
	double T_back_to_0 = T_double * 0.948; // 9480.0

	int x_begin = 0;
	int x_end = 0;
	int x_prev = 0;
	int x_next = 0;
	int x_len_from_prev = 0;
	vi x_list(2);
	vi x_list_sum(2);
	vi x_list_sum_excluded;
	int x_list_i = 0;
	int x_list_sum_i = 0;
	set<int> waitinglist;
	set<int> loadedlist;
	int dist_max = 0;

	bool x_0 = true; // 店舗にいる
	bool new_dst = false; // 目的地を更新
	bool new_new_dst = false; // 経路全体を更新
	bool x_last = false; // t=9500付近で店舗に戻る
	rep(t, info_all.Tmax) {
		Info info_tmp = info_all.infos[t];
		rep(n, info_tmp.Nnew) {
			waitinglist.insert(info_tmp.orders[n].new_id);
		}
		int waitingnum = waitinglist.size();
		int loadednum = loadedlist.size();

		// ---------- 店舗にいる場合の処理	 ----------

		if (x_0) {
			if (t > 9500)
				x_last = true;
			if (waitingnum == 0 && loadednum == 0) { // 店舗にいて注文なし
				command_all.commands[t] = -1;
			}
			else { // 店舗にいて注文あり
				//write_val(loadedlist.size(), "A");
				//write_val(waitinglist.size(), "A");
				auto it = waitinglist.begin();
				for (int id_tmp : waitinglist) {
					//write_val(id_tmp, " A");
					loadedlist.insert(id_tmp);
				}
				waitinglist.clear();
				new_new_dst = true;
				new_dst = true;
			}
		}

		// ---------- 経路全体を更新する場合の処理	 ----------

		if (new_new_dst) {
			new_new_dst = false;
			x_list_sum.clear();
			x_list_sum.push_back(0);
			x_list_sum_excluded.clear();

			set<int> waitinglist_tmp = waitinglist;
			set<int> loadedlist_tmp = loadedlist;
			int waitingnum_tmp = waitinglist.size();
			int loadednum_tmp = loadedlist.size();
			id_t_list.clear();

			double time_return = (double)diff_0_max * time_return_ratio[t];
			int dist_sum_tmp = 0;
			while (1) {
				int x_list_sum_size = x_list_sum.size();
				int x_end_end = x_list_sum[x_list_sum_size - 1];
				if (x_end_end == 0 && x_list_sum_size > 1) // 店に帰還
					break;
				//if (dist_sum_tmp + t > 10000)
					//break;
				float eval_min = Inf;
				float dist_min = Inf;
				int x_end_end_nxt = -1;
				int id_nxt = -1;
				int time_rem = T_back_to_0 - t;
				bool goto_0 = false;
				//if (!x_0 && (loadednum == 0 || waitingnum != 0)) {
				if (x_list_sum_size != 1 && (loadednum_tmp == 0 || dist_sum_tmp >= 20)) {
					eval_min = (float)graph.xydist[x_end_end][0]; // 行先店舗も候補に入れる
					dist_min = (float)graph.xydist[x_end_end][0]; // 行先店舗も候補に入れる
					x_end_end_nxt = 0;
				}
				if (!x_last && x_end_end != 0 && dist_sum_tmp + graph.xydist[x_end_end][0] > time_return) { // 強制的に店に帰還
					goto_0 = true;
					eval_min = (float)graph.xydist[x_end_end][0]; // 行先店舗も候補に入れる
					dist_min = (float)graph.xydist[x_end_end][0]; // 行先店舗も候補に入れる
					x_end_end_nxt = 0;
				}
				if (x_last && loadednum_tmp != 0 && waitingnum_tmp == 0) {
					eval_min = Inf; // 行先店舗を極力除外
				}
				if (!x_last && x_end_end != 0 && t + dist_sum_tmp + graph.xydist[x_end_end][0] > T_back_to_0) { // 強制的に店に帰還
					x_last = true;
					goto_0 = true;
					eval_min = (float)graph.xydist[x_end_end][0]; // 行先店舗も候補に入れる
					dist_min = (float)graph.xydist[x_end_end][0]; // 行先店舗も候補に入れる
					x_end_end_nxt = 0;
				}
				if (!goto_0) {
					for (int id_tmp : loadedlist_tmp) {
						int x = x_end_end;
						int y = info_all.idlist[id_tmp].dst;
						//write_val(y, " y");
						float t_over = t - info_all.idlist[id_tmp].time;
						float dist_tmp = (float)graph.xydist[x][y];
						float dist_ysum = 0.0;
						int ycount = 0;
						for (int id_tmp_other : loadedlist_tmp) {
							int y_other = info_all.idlist[id_tmp_other].dst;
							dist_ysum += (float)graph.xydist[y][y_other];
							ycount++;
						}
						dist_ysum /= ycount;
						float eval_tmp = (float)graph.xydist[x][y];
						//eval_tmp += dist_ysum;
						float dist_over = ((float)dist_tmp +  (float)graph.xydist[0][y] - (float)time_rem) * 2.0; // 9500帰還
						dist_over = min((float)0.0, dist_over);
						float dist_over2 = ((float)dist_tmp + (float)graph.xydist[0][y] - (time_return - (float)dist_sum_tmp)) * 2.0; // 500帰還
						dist_over2 = min((float)0.0, dist_over2);
						dist_over = max(dist_over2, dist_over);
						//write_val(eval, " eval");
						if (!x_last && dist_over > 0) {
							eval_tmp += dist_over;
						}
						if (eval_min > eval_tmp) {
							eval_min = eval_tmp;
							dist_min = dist_tmp;
							x_end_end_nxt = y;
							id_nxt = id_tmp;
						}
					}
				}
				dist_sum_tmp += dist_min;
				x_list_sum.push_back(x_end_end_nxt);
				int dstnum = dst_to_id[x_end_end_nxt].size();
				rep(i, dstnum) { // 配達*1 + たまたま配達*(dstnum-1)
					int id_tmp = dst_to_id[x_end_end_nxt][i];
					auto it = loadedlist_tmp.find(id_tmp);
					if (it != loadedlist_tmp.end()) {
						int begin_t_tmp = info_all.idlist[id_tmp].time;
						int end_t_tmp = t + dist_sum_tmp;
						id_t_list[id_tmp].begin_t = begin_t_tmp;
						id_t_list[id_tmp].end_t = end_t_tmp;
						loadedlist_tmp.erase(it);
						loadednum_tmp--;
					}
				}
			}
			for (int id_tmp : loadedlist_tmp) { // 店舗に戻ったとき残ったもの
				int begin_t_tmp = info_all.idlist[id_tmp].time;
				int end_t_tmp = t + dist_sum_tmp;
				id_t_list[id_tmp].begin_t = begin_t_tmp;
				id_t_list[id_tmp].end_t = end_t_tmp;
				int x_list_sum_excluded_num = x_list_sum_excluded.size();
				bool can = true;
				rep(x_, x_list_sum_excluded_num) {
					if (x_list_sum_excluded[x_] == info_all.idlist[id_tmp].dst) {
						can = false; // 既に存在
					}
				}
				if (can) {
					x_list_sum_excluded.push_back(info_all.idlist[id_tmp].dst);
				}
			}


			// ---------- 以上暫定解,以下山登り ----------
			
			double t_end = t + dist_sum_tmp;
			t_end = min(t_end, T_99);
			double time_end = t_end / T_double * time_2_3;
			if (t >= T_back_to_0)
				time_end = T_99 / T_double * time_limit;
			ll eval_max = evaluation();
			write_val(t, "t");
			write_val(id_t_list.size(), " S");
			write_val(eval_max, " eval_max");

			double time_99 = T_99 / T_double * time_limit;
			double time_95 = T_back_to_0 / T_double * time_limit;

			int loop_count = 0;
			while (1) {
				//break;
				const double time = time_diff();
				if (time >= time_end)
					break;
				double time_rem = 0.0;
				if (t >= T_back_to_0)
					time_rem = (time_99 - time) / (time_99 - time_95); // 1->0
				double Temp = time_rem * 0.0001;
				Temp = max(Temp, 0.00001);
				rep(P, 100) {
					loop_count++;
					int x_from = xor128();
					int x_to = xor128();
					int xnum = x_list_sum.size();
					int x_ec_num = x_list_sum_excluded.size();

					int xnum_old = xnum;
					int x_ec_num_old = x_ec_num;
					map<int, Ptt> id_t_list_old = id_t_list;
					vi x_list_sum_old = x_list_sum;
					vi x_list_sum_excluded_old = x_list_sum_excluded;
					int dist_sum_prev = dist_sum_tmp;
					set<int> loadedlist_tmp_tmp = loadedlist;
					id_t_list.clear();

					bool eval_diff = true; // 更新するかどうか
					// 以上共通
					int Ptype = P % 6;
					if (Ptype == 0) {// swap
						if (xnum < 4)
							continue;
						x_from %= (xnum - 2);
						x_to %= (xnum - 2);
						if (x_from == x_to)
							continue;
						x_from++;
						x_to++; // 両端は除外
						int dist_old = 0;
						int dist_new = 0;
						if (t < T_back_to_0) {
							dist_old = graph.xydist[x_list_sum[x_from - 1]][x_list_sum[x_from]] + graph.xydist[x_list_sum[x_from]][x_list_sum[x_from + 1]] + graph.xydist[x_list_sum[x_to - 1]][x_list_sum[x_to]] + graph.xydist[x_list_sum[x_to]][x_list_sum[x_to + 1]];
						}
						swap(x_list_sum[x_from], x_list_sum[x_to]);
						if (t < T_back_to_0) {
							dist_new = graph.xydist[x_list_sum[x_from - 1]][x_list_sum[x_from]] + graph.xydist[x_list_sum[x_from]][x_list_sum[x_from + 1]] + graph.xydist[x_list_sum[x_to - 1]][x_list_sum[x_to]] + graph.xydist[x_list_sum[x_to]][x_list_sum[x_to + 1]];
						}
						if (dist_old < dist_new)
							eval_diff = false;
					}
					else if (Ptype == 1) { // move
						if (xnum < 4)
							continue;
						x_from %= (xnum - 2);
						x_to %= (xnum - 2);
						if (x_from == x_to)
							continue;
						if (x_from + 1 == x_to)
							continue;
						x_from++;
						x_to++; // 両端は除外
						int dist_old = 0;
						int dist_new = 0;
						if (t < T_back_to_0) {
							dist_old = graph.xydist[x_list_sum[x_from - 1]][x_list_sum[x_from]] + graph.xydist[x_list_sum[x_from]][x_list_sum[x_from + 1]] + graph.xydist[x_list_sum[x_to - 1]][x_list_sum[x_to]];
						}
						int xtmp = x_list_sum[x_from];
						x_list_sum.erase(x_list_sum.begin() + x_from);
						if (x_to > x_from)
							x_to--;
						else
							x_from++;
						x_list_sum.insert(x_list_sum.begin() + x_to, xtmp);
						if (t < T_back_to_0) {
							dist_new = graph.xydist[x_list_sum[x_from - 1]][x_list_sum[x_from]] + graph.xydist[x_list_sum[x_to - 1]][x_list_sum[x_to]] + graph.xydist[x_list_sum[x_to]][x_list_sum[x_to + 1]];
						}
						if (dist_old < dist_new)
							eval_diff = false;
					}
					else if (Ptype == 2) { // change
						if (xnum < 3)
							continue;
						if (x_ec_num == 0)
							continue;
						x_to %= (xnum - 2);
						x_from %= x_ec_num;
						x_to++; // 両端は除外
						int dist_old = 0;
						int dist_new = 0;
						if (t < T_back_to_0) {
							dist_old = graph.xydist[x_list_sum[x_to - 1]][x_list_sum[x_to]] + graph.xydist[x_list_sum[x_to]][x_list_sum[x_to + 1]];
						}
						swap(x_list_sum[x_to], x_list_sum_excluded[x_from]);
						if (t < T_back_to_0) {
							dist_old = graph.xydist[x_list_sum[x_to - 1]][x_list_sum[x_to]] + graph.xydist[x_list_sum[x_to]][x_list_sum[x_to + 1]];
						}
						if (dist_old < dist_new)
							eval_diff = false;
					}
					else if (Ptype == 3) { // insert
						continue; // 廃止
						if (x_ec_num == 0)
							continue;
						x_to %= (xnum - 1);
						x_from %= x_ec_num;
						x_to++; // 左端は除外
						x_list_sum.insert(x_list_sum.begin() + x_to, x_list_sum_excluded[x_from]);
						x_list_sum_excluded.erase(x_list_sum_excluded.begin() + x_from);
						xnum++;
						x_ec_num--;
					}
					else if (Ptype == 4) { // swap_group
						x_from %= (xnum - 2);
						x_to %= (xnum - 2);
						x_from++; // 左端は除外
						x_to++; // 左端は除外
						int Len = xor128() % (xnum / 2);
						Len++;
						if (x_from + Len > x_to)
							continue;
						if (x_to + Len > xnum - 1)
							continue;
						int dist_old = 0;
						int dist_new = 0;
						if (t < T_back_to_0) {
							dist_old = graph.xydist[x_list_sum[x_from - 1]][x_list_sum[x_from]] + graph.xydist[x_list_sum[x_from + Len - 1]][x_list_sum[x_from + Len]] + graph.xydist[x_list_sum[x_to - 1]][x_list_sum[x_to]] + graph.xydist[x_list_sum[x_to + Len - 1]][x_list_sum[x_to + Len]];
						}
						rep(l, Len) {
							swap(x_list_sum[x_from + l], x_list_sum[x_to + l]);
						}
						if (t < T_back_to_0) {
							dist_old = graph.xydist[x_list_sum[x_from - 1]][x_list_sum[x_from]] + graph.xydist[x_list_sum[x_from + Len - 1]][x_list_sum[x_from + Len]] + graph.xydist[x_list_sum[x_to - 1]][x_list_sum[x_to]] + graph.xydist[x_list_sum[x_to + Len - 1]][x_list_sum[x_to + Len]];
						}
						if (dist_old < dist_new)
							eval_diff = false;
					}
					else { // move_group
						x_from %= (xnum - 2);
						x_to %= (xnum - 2);
						x_from++;
						x_to++; // 両端は除外
						int Len = xor128() % (xnum - 2);
						Len++;
						if (x_from >= x_to) {
							if (x_from + Len <= x_to)
								continue;
						}
						else {
							if (x_from + Len > x_to)
								continue;
						}

						if (x_from + Len > xnum - 1)
							continue;
						vi xtmp(0);
						int dist_old = 0;
						int dist_new = 0;
						if (t < T_back_to_0) {
							dist_old = graph.xydist[x_list_sum[x_from - 1]][x_list_sum[x_from]] + graph.xydist[x_list_sum[x_from + Len - 1]][x_list_sum[x_from + Len]] + graph.xydist[x_list_sum[x_to - 1]][x_list_sum[x_to]];
						}
						rep(l, Len) {
							xtmp.push_back(x_list_sum[x_from + l]);
						}
						x_list_sum.erase(x_list_sum.begin() + x_from, x_list_sum.begin() + x_from + Len);
						if (x_to > x_from)
							x_to -= Len;
						else
							x_from += Len;
						x_list_sum.insert(x_list_sum.begin() + x_to, xtmp.begin(), xtmp.end());
						if (t < T_back_to_0) {
							dist_old = graph.xydist[x_list_sum[x_from - 1]][x_list_sum[x_from]] + graph.xydist[x_list_sum[x_to - 1]][x_list_sum[x_to]] + graph.xydist[x_list_sum[x_to + Len - 1]][x_list_sum[x_to + Len]];
						}
						if (dist_old < dist_new)
							eval_diff = false;
					}
					// erase??

					ll eval_new = 0;
					if (eval_diff) {
						dist_sum_tmp = 0;
						for (int xi = 1; xi < xnum; xi++) {
							int xprev = x_list_sum[xi - 1];
							int xtmp = x_list_sum[xi];
							int dist_tmp = graph.xydist[xprev][xtmp];
							dist_sum_tmp += dist_tmp;
							//if (dist_sum_tmp + t > 10000)
								//break;

							int dstnum = dst_to_id[xtmp].size();
							rep(i, dstnum) { // 配達*1 + たまたま配達*(dstnum-1)
								int id_tmp = dst_to_id[xtmp][i];
								auto it = loadedlist_tmp_tmp.find(id_tmp);
								if (it != loadedlist_tmp_tmp.end()) {
									int begin_t_tmp = info_all.idlist[id_tmp].time;
									int end_t_tmp = t + dist_sum_tmp;
									id_t_list[id_tmp].begin_t = begin_t_tmp;
									id_t_list[id_tmp].end_t = end_t_tmp;
									loadedlist_tmp_tmp.erase(it);
								}
							}
						}
						for (int id_tmp : loadedlist_tmp_tmp) { // 店舗に戻ったとき残ったもの
							int begin_t_tmp = info_all.idlist[id_tmp].time;
							int end_t_tmp = t + dist_sum_tmp;
							id_t_list[id_tmp].begin_t = begin_t_tmp;
							id_t_list[id_tmp].end_t = end_t_tmp;
							if (x_last)
								id_t_list[id_tmp].end_t = Inf;
						}
						if ((t < T_back_to_0) && (dist_sum_prev - dist_sum_tmp) < 0) // 店舗に戻る時刻が遅い
							eval_diff = false;
						else {
							eval_new = evaluation();
							if ((eval_new - eval_max) <= 0) // evalが悪化
								eval_diff = false;
						}
					}
					/*if (!eval_diff && eval_new != eval_max && t >= T_back_to_0) { // 焼きなまし
						if (xor128_0to1() < exp(((double)(eval_new - eval_max) / abs((double)eval_max)) / Temp)) {
							cout << "A " << xor128_0to1() << endl;
							cout << "B " << exp(((double)(eval_new - eval_max) / abs((double)eval_max)) / Temp) << endl;
							eval_diff = true;
						}
					}*/
					if(!eval_diff) {
						xnum = xnum_old;
						x_ec_num = x_ec_num_old;
						dist_sum_tmp = dist_sum_prev;
						id_t_list = id_t_list_old;
						x_list_sum = x_list_sum_old;
						x_list_sum_excluded = x_list_sum_excluded_old;
					}
					else {
						if (debug == 2) {
							cout << eval_max << " " << eval_new << " " << (Ptype) << endl;
							cout << dist_sum_prev << " " << dist_sum_tmp << endl;
						}
						eval_max = eval_new;
					}
				}
			}
			write_val(loop_count, "loop_count");
			x_list_sum_i = 0;
		}

		// ---------- 目的地を更新する場合の処理	 ----------

		if (new_dst) {
			new_dst = false;
			x_begin = x_list_sum[x_list_sum_i];
			x_end = x_list_sum[x_list_sum_i + 1];
			x_list_sum_i++;
			int x_tmp = x_end;
			x_list.clear();
			x_list.push_back(-1);
			while (1) {
				x_list.push_back(x_tmp);
				if (x_tmp == x_begin)
					break;
				x_tmp = graph.xy_from[x_begin][x_tmp];
			}
			reverse(x_list.begin(), x_list.end());
			x_prev = x_list[0];
			x_next = x_list[1];
			x_len_from_prev = 0;
			x_list_i = 0;
			x_0 = false;
		}

		// ---------- 配達途中の場合の処理	 ----------

		if (x_end != x_prev) {
			x_len_from_prev++;
			command_all.commands[t] = x_next;
			if (graph.xylen[x_prev][x_next] == x_len_from_prev) { // 次の頂点に移動
				int dstnum = dst_to_id[x_next].size();
				rep(i, dstnum) { // たまたま配達した
					int id_tmp = dst_to_id[x_next][i];
					auto it = loadedlist.find(id_tmp);
					if (it != loadedlist.end()) {
						loadedlist.erase(it);
					}
				}
				x_len_from_prev = 0;
				x_list_i++;
				x_prev = x_list[x_list_i];
				x_next = x_list[x_list_i + 1];
			}
			if (x_end == x_prev) { // 移動完了
				if (x_end == 0) { // 店舗到着
					new_dst = false;
					x_0 = true;
				}
				else { // 配達完了
					new_dst = true;
					x_0 = false;
				}
			}
		}
	}
	write_val(info_all.idlist.size(), "N");
	write_val(loadedlist.size(), "L");
	write_val(waitinglist.size(), "W");
	return;
}

int main() {
	readProblem();
	solve();
	writeSolution();
	return 0;
}


Measured memory_bytes: 5248