#![allow(non_snake_case)]

use std::collections::*;
use std::io::prelude::*;

////////// missing functions in 1.15.1 //////////
macro_rules! eprintln {
	() => { eprintln!(""); };
	($($t:tt)*) => {{
		use ::std::io::Write;
		let _ = writeln!(::std::io::stderr(), $($t)*);
	}};
}
/////////////////////////////////////////////////
pub trait SetMinMax {
	fn setmin(&mut self, v: Self) -> bool;
	fn setmax(&mut self, v: Self) -> bool;
}
impl<T> SetMinMax for T where T: PartialOrd {
	fn setmin(&mut self, v: T) -> bool {
		*self > v && { *self = v; true }
	}
	fn setmax(&mut self, v: T) -> bool {
		*self < v && { *self = v; true }
	}
}

macro_rules! mat {
	($($e:expr),*) => { Vec::from(vec![$($e),*]) };
	($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
	($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
	($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}

pub fn readln() -> String {
	let mut line = String::new();
	::std::io::stdin().read_line(&mut line).unwrap_or_else(|e| panic!("{}", e));
	line
}

macro_rules! read {
	($($t:tt),*; $n:expr) => {{
		let stdin = ::std::io::stdin();
		let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
			let line = line.unwrap();
			let mut it = line.split_whitespace();
			_read!(it; $($t),*)
		}).collect::<Vec<_>>();
		ret
	}};
	($($t:tt),*) => {{
		let line = readln();
		let mut it = line.split_whitespace();
		_read!(it; $($t),*)
	}};
}

macro_rules! _read {
	($it:ident; [char]) => {
		_read!($it; String).chars().collect::<Vec<_>>()
	};
	($it:ident; [u8]) => {
		Vec::from(_read!($it; String).into_bytes())
	};
	($it:ident; usize1) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
	};
	($it:ident; [usize1]) => {
		$it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
	};
	($it:ident; [$t:ty]) => {
		$it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
	};
	($it:ident; $t:ty) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
	};
	($it:ident; $($t:tt),+) => {
		($(_read!($it; $t)),*)
	};
}

pub fn main() {
	let _ = ::std::thread::Builder::new().name("run".to_string()).stack_size(32 * 1024 * 1024).spawn(run).unwrap().join();
}

////////// for marathon competitions //////////

pub struct XorShift {
	pub x: [u32; 4]
}

impl XorShift {
	pub fn new(mut seed: u32) -> XorShift {
		let mut x = [0; 4];
		for i in 0..4 {
			seed = 1812433253u32.wrapping_mul(seed ^ (seed >> 30)).wrapping_add(i as u32);
			x[i] = seed;
		}
		XorShift { x: x }
	}
	pub fn next32(&mut self) -> usize {
		let t = self.x[0] ^ (self.x[0] << 11);
		for i in 0..3 { self.x[i] = self.x[i + 1] }
		self.x[3] = self.x[3] ^ (self.x[3] >> 19) ^ t ^ (t >> 8);
		self.x[3] as usize
	}
	/// [0, n)
	pub fn next(&mut self, n: usize) -> usize {
		loop {
			let t = self.next32();
			let r = t % n;
			if (t - r).checked_add(n).is_some() {
				return r;
			}
		}
	}
}

fn get_time() -> f64 {
	static mut STIME: f64 = -1.0;
	let t = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
	let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
	unsafe {
		if STIME < 0.0 {
			STIME = ms;
		}
		ms - STIME
	}
}

/////////////////////////////////////////////////

const TIME_LIMIT: f64 = 29.0;

type Graph = Vec<Vec<(usize, i32)>>;

#[derive(Clone, Debug)]
struct Input {
	n: usize,
	g: Graph,
	f: Vec<i32>,
	T: usize,
	lastT: usize,
	problem: char,
	dij: Vec<Dijkstra>,
	orders: Vec<usize>,
}

fn read_input() -> Input {
	let (n, m) = read!(usize, usize);
	get_time();
	let mut g = vec![vec![]; n];
	for (u, v, d) in read!(usize1, usize1, i32; m) {
		g[u].push((v, d));
		g[v].push((u, d));
	}
	let (mut f, T, problem) = {
		let f = read!([i32]);
		if f[0] > 2 {
			(vec![0; g.len()], f[0] as usize, 'a')
		} else {
			(f, read!(usize), 'b')
		}
	};
	let mut dij = vec![];
	for i in 0..n {
		dij.push(Dijkstra::compute(&g, i)); // 予め全点間最短路を計算しておく
	}
	let orders = if problem == 'a' {
		(0..T).map(|_| read_new_order()).collect()
	} else {
		vec![]
	};
	if problem == 'a' {
		for &u in &orders {
			if u != !0 {
				f[u] += 1;
			}
		}
	}
	let lastT = if problem == 'a' { // 最終注文時刻。A問題の場合は実際の値、他の問題の場合は0.95Tを使用。
		let mut lastT = 0;
		for t in 0..T {
			if orders[t] != !0 {
				lastT = t;
			}
		}
		lastT
	} else {
		T * 95 / 100
	};
	Input { n: n, g: g, f: f, T: T, lastT: lastT, problem: problem, dij: dij, orders: orders }
}

fn read_new_order() -> usize {
	let n = read!(usize);
	if n == 0 {
		!0
	} else {
		let (_, id) = read!(usize1, usize1);
		id
	}
}

/// 注文や車の状態を管理。
struct State {
	g: Graph,
	T: usize,
	orders: Vec<Vec<usize>>,
	score: usize,
	t: usize,
	received: usize,
	u: usize,
	v: usize,
	dist_u: i32,
	dist_v: i32,
}

impl State {
	fn new(input: &Input) -> Self {
		State { g: input.g.clone(), T: input.T, orders: vec![vec![]; input.n], score: 0, t: 0, received: 0, u: 0, v: 0, dist_u: 0, dist_v: 0 }
	}
	fn add_order(&mut self, v: usize) {
		if v != !0 {
			self.orders[v].push(self.t);
		}
	}
	fn command(&mut self, v: usize) {
		if v != !0 {
			if self.u == self.v {
				for &(w, l) in &self.g[self.u] {
					if w == v {
						self.v = w;
						self.dist_u = 0;
						self.dist_v = l;
					}
				}
				// assert!(self.u != self.v);
			}
			if self.u == v {
				std::mem::swap(&mut self.u, &mut self.v);
				std::mem::swap(&mut self.dist_u, &mut self.dist_v);
			}
			// assert!(self.v == v);
			self.dist_u += 1;
			self.dist_v -= 1;
			if self.dist_v == 0 {
				self.u = self.v;
				self.dist_u = 0;
			}
		}
		self.t += 1;
		if self.u == self.v {
			if self.u == 0 {
				self.received = self.t;
				if v == 0 {
					eprintln!("home: {}", self.t);
				}
			} else {
				let mut rem = vec![];
				for &t in &self.orders[self.u] {
					if t <= self.received {
						let w = self.t - t;
						self.score += self.T * self.T - w * w;
					} else {
						rem.push(t);
					}
				}
				self.orders[self.u] = rem;
			}
		}
	}
	/// 指定された点を順に通過する最適なパスを計算し、(スコア,コマンド列)を返す。
	/// 連続する２点間に直接の辺がない場合があるのでダイクストラを復元し、スコアが高いパスを選択。
	fn compute_best_path(&self, input: &Input, ps: &Vec<usize>) -> (usize, Vec<usize>) {
		let mut score = 0;
		let mut t = self.t;
		let mut visited = vec![false; input.n];
		let mut max_score = vec![0; input.n];
		let mut prev = vec![!0; input.n];
		let mut vs = vec![];
		let mut command = vec![];
		for i in 0..ps.len() - 1 {
			vs.clear();
			let mut que = BinaryHeap::new();
			let len = input.dij[ps[i + 1]].dist[ps[i]];
			que.push((len, ps[i]));
			while let Some((d, u)) = que.pop() {
				vs.push(u);
				let t2 = t + (len - d) as usize;
				if !visited[u] && t2 <= input.T {
					for &s in &self.orders[u] {
						let w = t2 - s;
						max_score[u] += self.T * self.T - w * w;
					}
				}
				if u == 0 {
					max_score[u] += 1000 * self.T * self.T;
				}
				for &(v, l) in &self.g[u] {
					if input.dij[ps[i + 1]].dist[u] == input.dij[ps[i + 1]].dist[v] + l {
						if prev[v] == !0 {
							que.push((input.dij[ps[i + 1]].dist[v], v));
							max_score[v] = max_score[u];
							prev[v] = u;
						} else {
							let tmp = max_score[u];
							if max_score[v].setmax(tmp) {
								prev[v] = u;
							}
						}
					}
				}
			}
			let mut u = ps[i + 1];
			let mut us = vec![u];
			while u != ps[i] {
				u = prev[u];
				us.push(u);
			}
			us.reverse();
			for &v in &vs {
				max_score[v] = 0;
				prev[v] = !0;
			}
			vs.clear();
			for i in 0..us.len() - 1 {
				let (u, v) = (us[i], us[i + 1]);
				let d = input.dij[u].dist[v] as usize;
				for _ in 0..d {
					command.push(v);
				}
				t += d;
				if !visited[v] && t <= input.T {
					for &s in &self.orders[v] {
						let w = t - s;
						score += self.T * self.T - w * w;
					}
				}
				visited[v] = true;
			}
		}
		(score, command)
	}
}

#[derive(Clone, Debug)]
struct Dijkstra {
	dist: Vec<i32>,
	prev: Vec<usize>,
}

impl Dijkstra {
	fn compute(g: &Graph, s: usize) -> Self {
		let n = g.len();
		let mut dist = vec![i32::max_value(); n];
		let mut prev = vec![!0; n];
		let mut que = BinaryHeap::new();
		que.push((0, s));
		dist[s] = 0;
		while let Some((d, u)) = que.pop() {
			let d = -d;
			if dist[u] != d {
				continue;
			}
			for &(v, l) in &g[u] {
				if dist[v].setmin(d + l) {
					prev[v] = u;
					que.push((-dist[v], v));
				}
			}
		}
		Dijkstra { dist: dist, prev: prev }
	}
}

/// 一番近い点を順に選択する貪欲法。
fn greedy(input: &Input) -> Vec<usize> {
	let mut ps = vec![0];
	let mut used = vec![false; input.n];
	used[0] = true;
	for i in 0..input.n-1 {
		let mut to = !0;
		let mut cost = i32::max_value();
		for j in 0..input.n {
			if !used[j] && cost.setmin(input.dij[ps[i]].dist[j]) {
				to = j;
			}
		}
		used[to] = true;
		ps.push(to);
	}
	ps.push(0);
	ps
}

fn compute_cost(g: &Vec<Vec<i32>>, ps: &Vec<usize>) -> i32 {
	let mut tmp = 0;
	for i in 0..ps.len() - 1 {
		tmp += g[ps[i]][ps[i + 1]];
	}
	tmp
}

/// tour: ハミルトン閉路の頂点順
/// idx: tourの逆関数
/// mv: k-optの表現。 (i, dir)の配列。
/// tourとidxにmvを適用して更新する。
fn apply_move(tour: &mut Vec<usize>, idx: &mut Vec<usize>, mv: &[(usize, usize)]) {
	let k = mv.len();
	let mut ids: Vec<_> = (0..k).collect();
	ids.sort_by_key(|&i| mv[i].0);
	let mut order = vec![0; k];
	for i in 0..k {
		order[ids[i]] = i;
	}
	let mut tour2 = Vec::with_capacity(mv[ids[k - 1]].0 - mv[ids[0]].0);
	let mut i = ids[0];
	let mut dir = 0;
	loop {
		let (j, rev) = if dir == mv[i].1 {
			((i + 1) % k, 0)
		} else {
			((i + k - 1) % k, 1)
		};
		if mv[j].1 == rev {
			if order[j] == k - 1 {
				break;
			} else {
				i = ids[order[j] + 1];
				dir = 0;
				tour2.extend_from_slice(&tour[mv[j].0 + 1..mv[i].0 + 1]);
			}
		} else {
			i = ids[order[j] - 1];
			dir = 1;
			tour2.extend(tour[mv[i].0 + 1..mv[j].0 + 1].iter().rev().cloned());
		}
	}
	// assert_eq!(tour2.len(), mv[ids[k - 1]].0 - mv[ids[0]].0);
	tour[mv[ids[0]].0 + 1..mv[ids[k - 1]].0 + 1].copy_from_slice(&tour2);
	for i in mv[ids[0]].0 + 1..mv[ids[k - 1]].0 + 1 {
		idx[tour[i]] = i;
	}
}

/// 3-optのfeasible判定用事前計算テーブル。
const FEASIBLE3: [bool; 64] = [false, false, false, true, false, true, true, true, true, true, true, false, true, false, false, false,
								false, false, false, false, false, false, false, false, false, false, false, true, false, true, true, true,
								true, true, true, false, true, false, false, false, false, false, false, false, false, false, false, false,
								false, false, false, true, false, true, true, true, true, true, true, false, true, false, false, false];

/// qs: 初期解
/// until: 時間制限
/// dbg: デバッグ出力を表示するか
/// TSPを3-opt+kickで計算
fn tsp(input: &Input, qs: &[usize], until: f64, dbg: bool) -> Vec<usize> {
	if dbg {
		eprintln!("===== tsp =====");
	}
	let until = until.min(TIME_LIMIT);
	let mut id = vec![!0; input.n]; // qsが全点を含まれないケースがあるので、必要な点のみについて頂点番号を圧縮。
	for i in 0..qs.len() - 1 {
		id[qs[i]] = i;
	}
	let n = qs.len() - 1;
	let mut g = mat![1 << 29; n; n]; // 距離行列を生成。
	for i in 0..n {
		for j in 0..n {
			g[i][j] = input.dij[qs[i]].dist[qs[j]];
		}
	}
	let mut f = vec![vec![]; n]; // 後で枝刈りに使うために、各点について、距離の近い順に点をソートしておく。
	for i in 0..n {
		for j in 0..n {
			if i != j {
				f[i].push((g[i][j], j));
			}
		}
		f[i].sort();
	}
	let mut rng = XorShift::new(47894);
	let mut ps: Vec<_> = (0..n).chain(0..1).collect(); // 現在のtour
	let mut idx = vec![!0; n]; // psの逆関数
	let mut cost = compute_cost(&g, &ps); // 現在のコスト
	if dbg {
		eprintln!("init: {}", cost);
	}
	let (mut min, mut min_ps) = (cost, ps.clone());
	let mut rep = 0;
	let mut kick = 0;
	while rep == 0 || get_time() < until {
		kick += 1;
		for p in 0..n {
			idx[ps[p]] = p;
		}
		loop {
			rep += 1;
			let mut ok = false;
			for i in 0..n { // 削除する一辺目の選択
				for di in 0..2 { // 一辺目の向き（よく考えると0固定で良かったかも？）
					'loop_ij: for &(ij, vj) in &f[ps[i + di]] { // 追加する一辺目の選択。距離の短い順にループを回す
						if g[ps[i]][ps[i + 1]] - ij <= 0 { // 閉路の和が正ならば、部分和が常に正となる開始地点があることを利用した有名な枝刈り
							break;
						}
						for dj in 0..2 { // 削除する二辺目の向き
							let j = if idx[vj] == 0 && dj == 0 {
								n - 1
							} else {
								idx[vj] - 1 + dj
							};
							let gain = g[ps[i]][ps[i + 1]] - ij + g[ps[j]][ps[j + 1]];
							// 2-opt
							if di != dj && gain - g[ps[j + dj]][ps[i + 1 - di]] > 0 { // 2-optがfeasible ⇔ 消す二辺の向きが異なる
								cost -= gain - g[ps[j + dj]][ps[i + 1 - di]];
								apply_move(&mut ps, &mut idx, &[(i, di), (j, dj)]);
								ok = true;
								break 'loop_ij;
							}
							// 3-opt
							for &(jk, vk) in &f[ps[j + dj]] { // 追加する二辺目の選択
								if gain - jk <= 0 { // 部分和が正でないなら枝刈り
									break;
								}
								for dk in 0..2 { // 削除する三辺目の向き
									let k = if idx[vk] == 0 && dk == 0 {
										n - 1
									} else {
										idx[vk] - 1 + dk
									};
									if i == k || j == k {
										continue;
									}
									let gain = gain - jk + g[ps[k]][ps[k + 1]];
									if gain - g[ps[k + dk]][ps[i + 1 - di]] > 0 {
										let mask = if i < j { 1 << 5 } else { 0 }
												| if i < k { 1 << 4 } else { 0 }
												| if j < k { 1 << 3 } else { 0 }
												| di << 2 | dj << 1 | dk;
										if FEASIBLE3[mask] { // 事前計算しておいたテーブルを使って3-optがfeasibleかを判定
											cost -= gain - g[ps[k + dk]][ps[i + 1 - di]];
											apply_move(&mut ps, &mut idx, &[(i, di), (j, dj), (k, dk)]);
											ok = true;
											break 'loop_ij;
										}
									}
								}
							}
						}
					}
				}
			}
			if !ok {
				break;
			}
		}
		if min.setmin(cost) {
			if dbg {
				eprintln!("{:.3}: {}", get_time(), cost);
			}
			min_ps = ps;
		}
		ps = min_ps.clone();
		if n <= 4 {
			break;
		}
		// 現在のベスト解をランダムに少し変化させたものを次の局所最適化の初期解とする
		loop {
			if rng.next(2) == 0 {
				// ランダムなnon-sequential 4-opt (double bridge)を適用
				let mut is: Vec<_> = (0..4).map(|_| rng.next(n)).collect();
				is.sort();
				if is[0] == is[1] || is[1] == is[2] || is[2] == is[3] {
					continue;
				}
				ps = ps[0..is[0]+1].iter()
						.chain(ps[is[2]+1..is[3]+1].iter())
						.chain(ps[is[1]+1..is[2]+1].iter())
						.chain(ps[is[0]+1..is[1]+1].iter())
						.chain(ps[is[3]+1..].iter())
						.cloned().collect();
				cost = compute_cost(&g, &ps);
			} else {
				// ランダムに2-optを6回適用
				for _ in 0..6 {
					loop {
						let i = 1 + rng.next(n - 1) as usize;
						let j = 1 + rng.next(n - 1) as usize;
						if i < j && j - i < n - 2 {
							ps = ps[0..i].iter().chain(ps[i..j+1].iter().rev()).chain(ps[j+1..].iter()).cloned().collect();
							break;
						}
					}
				}
				cost = compute_cost(&g, &ps);
			}
			break;
		}
	}
	if dbg {
		eprintln!("rep = {}", rep);
		eprintln!("kick = {}", kick);
	}
	// assert_eq!(min, compute_cost(&g, &min_ps));
	min_ps.into_iter().map(|i| qs[i]).collect()
}

/// mv適用後の分割がバランス良いか判定。
/// 実際にtourを更新しなくても、適用後の分割点の位置がO(1)で計算出来る。
fn check_div(idx: &Vec<usize>, mv: &[(usize, usize)], id_div: &Vec<usize>, n: usize) -> bool {
	let mut pos: Vec<_> = id_div.iter().map(|&x| (idx[x], idx[x])).collect();
	let k = mv.len();
	let mut ids: Vec<_> = (0..k).collect();
	ids.sort_by_key(|&i| mv[i].0);
	let mut order = vec![0; k];
	for i in 0..k {
		order[ids[i]] = i;
	}
	let mut len = mv[ids[0]].0 + 1;
	let mut i = ids[0];
	let mut dir = 0;
	loop {
		let (j, rev) = if dir == mv[i].1 {
			((i + 1) % k, 0)
		} else {
			((i + k - 1) % k, 1)
		};
		if mv[j].1 == rev {
			if order[j] == k - 1 {
				break;
			} else {
				i = ids[order[j] + 1];
				dir = 0;
				let (s, t) = (mv[j].0 + 1, mv[i].0 + 1);
				for p in &mut pos {
					if s <= p.0 && p.0 < t {
						p.1 = len + p.0 - s;
					}
				}
				len += t - s;
				// tour2.extend_from_slice(&tour[mv[j].0 + 1..mv[i].0 + 1]);
			}
		} else {
			i = ids[order[j] - 1];
			dir = 1;
			let (s, t) = (mv[i].0 + 1, mv[j].0 + 1);
			for p in &mut pos {
				if s <= p.0 && p.0 < t {
					p.1 = len + t - p.0 - 1;
				}
			}
			// tour2.extend(tour[mv[i].0 + 1..mv[j].0 + 1].iter().rev().cloned());
			len += t - s;
		}
	}
	let mut pos: Vec<_> = pos.into_iter().map(|p| p.1).collect();
	pos.push(0);
	pos.push(n);
	pos.sort();
	check_div_pos(&pos)
}

/// pos: 分割位置
/// 最大の長さ <= 1.5 × 最小の長さ ならバランス良いと判定
fn check_div_pos(pos: &Vec<usize>) -> bool {
	let mut min_sub = usize::max_value();
	let mut max_sub = 0;
	for x in 0..pos.len()-1 {
		min_sub.setmin(pos[x + 1] - pos[x]);
		max_sub.setmax(pos[x + 1] - pos[x]);
	}
	min_sub * 3 / 2 >= max_sub
}

/// qs: 初期解
/// div個の閉路で全点覆う最適な閉路分割を求める
/// n番以降の点は分割点を表すダミー
fn tsp_with_div(input: &Input, qs: &[usize], div: usize, until: f64, dbg: bool) -> Vec<usize> {
	if dbg {
		eprintln!("===== tsp_with_div =====");
	}
	let until = until.min(TIME_LIMIT);
	let mut id = vec![!0; input.n + div - 1]; // 各点の位置 (id[qs[i]] == i が成立)
	let mut id_div = vec![]; // id_div[i] := i番目の分割点の位置
	for i in 0..qs.len() - 1 {
		id[qs[i]] = i;
		if qs[i] >= input.n {
			id_div.push(i);
		}
	}
	
	let n = qs.len() - 1;
	let mut g = mat![1 << 29; n; n]; // 距離行列を計算
	for i in 0..n {
		for j in 0..n {
			g[i][j] = input.dij[if qs[i] >= input.n { 0 } else { qs[i] }].dist[if qs[j] >= input.n { 0 } else { qs[j] }];
		}
	}
	let mut f = vec![vec![]; n]; // 枝刈り用に点を近い順にソートしておく
	for i in 0..n {
		for j in 0..n {
			if i != j {
				f[i].push((g[i][j], j));
			}
		}
		f[i].sort();
	}
	let mut rng = XorShift::new(47894);
	let mut ps: Vec<_> = (0..n).chain(0..1).collect();
	let mut idx = vec![!0; n];
	let mut cost = compute_cost(&g, &ps);
	if dbg {
		eprintln!("init: {}", cost);
	}
	let (mut min, mut min_ps) = (cost, ps.clone());
	let mut rep = 0;
	let mut kick = 0;
	while rep == 0 || get_time() < until {
		kick += 1;
		for p in 0..n {
			idx[ps[p]] = p;
		}
		let mut hoge;
		loop {
			rep += 1;
			let mut ok = false;
			{ // kickでバランス崩れたまま最適解を更新してしまうバグがあったので応急処置でバランス良いかチェックした
				hoge = false;
				let mut tmp: Vec<_> = (0..div-1).map(|x| idx[id_div[x]]).collect();
				tmp.push(0);
				tmp.push(n);
				tmp.sort();
				if !check_div_pos(&tmp) {
					break;
				}
				hoge = true;
			}
			for i in 0..n { // 通常のTSPの場合と同様に2-opt, 3-optを列挙
				for di in 0..2 {
					'loop_ij: for &(ij, vj) in &f[ps[i + di]] {
						if g[ps[i]][ps[i + 1]] - ij <= 0 {
							break;
						}
						for dj in 0..2 {
							let j = if idx[vj] == 0 && dj == 0 {
								n - 1
							} else {
								idx[vj] - 1 + dj
							};
							let gain = g[ps[i]][ps[i + 1]] - ij + g[ps[j]][ps[j + 1]];
							// 2-opt
							if di != dj && gain - g[ps[j + dj]][ps[i + 1 - di]] > 0 {
								if check_div(&idx, &[(i, di), (j, dj)], &id_div, n) { // バランスが崩れていないか判定
									cost -= gain - g[ps[j + dj]][ps[i + 1 - di]];
									apply_move(&mut ps, &mut idx, &[(i, di), (j, dj)]);
									ok = true;
									break 'loop_ij;
								}
							}
							// 3-opt
							for &(jk, vk) in &f[ps[j + dj]] {
								if gain - jk <= 0 {
									break;
								}
								for dk in 0..2 {
									let k = if idx[vk] == 0 && dk == 0 {
										n - 1
									} else {
										idx[vk] - 1 + dk
									};
									if i == k || j == k {
										continue;
									}
									let gain = gain - jk + g[ps[k]][ps[k + 1]];
									if gain - g[ps[k + dk]][ps[i + 1 - di]] > 0 {
										let mask = if i < j { 1 << 5 } else { 0 }
												| if i < k { 1 << 4 } else { 0 }
												| if j < k { 1 << 3 } else { 0 }
												| di << 2 | dj << 1 | dk;
										if FEASIBLE3[mask] {
											if check_div(&idx, &[(i, di), (j, dj), (k, dk)], &id_div, n) { // バランスが崩れていないか判定
												cost -= gain - g[ps[k + dk]][ps[i + 1 - di]];
												apply_move(&mut ps, &mut idx, &[(i, di), (j, dj), (k, dk)]);
												ok = true;
												break 'loop_ij;
											}
										}
									}
								}
							}
						}
					}
				}
			}
			if !ok {
				break;
			}
		}
		if hoge {
			if min.setmin(cost) {
				if dbg {
					eprintln!("{:.3}: {}", get_time(), cost);
				}
				min_ps = ps;
			}
		}
		ps = min_ps.clone();
		if n <= 4 {
			break;
		}
		loop { // kick
			if rng.next(2) == 0 {
				// double bridge
				let mut is: Vec<_> = (0..4).map(|_| rng.next(n)).collect();
				is.sort();
				if is[0] == is[1] || is[1] == is[2] || is[2] == is[3] {
					continue;
				}
				ps = ps[0..is[0]+1].iter()
						.chain(ps[is[2]+1..is[3]+1].iter())
						.chain(ps[is[1]+1..is[2]+1].iter())
						.chain(ps[is[0]+1..is[1]+1].iter())
						.chain(ps[is[3]+1..].iter())
						.cloned().collect();
				cost = compute_cost(&g, &ps);
			} else {
				// random 2-opt × 6
				for _ in 0..6 {
					loop {
						let i = 1 + rng.next(n - 1) as usize;
						let j = 1 + rng.next(n - 1) as usize;
						if i < j && j - i < n - 2 {
							ps = ps[0..i].iter().chain(ps[i..j+1].iter().rev()).chain(ps[j+1..].iter()).cloned().collect();
							break;
						}
					}
				}
				cost = compute_cost(&g, &ps);
			}
			break;
		}
	}
	if dbg {
		eprintln!("rep = {}", rep);
		eprintln!("kick = {}", kick);
	}
	min_ps.into_iter().map(|i| qs[i]).collect()
}

// 全体をk個の閉路で覆う総長最小の分割を求める
// 閉路長のバランスを取るため、一番長い閉路の長さ <= 1.5 * 一番短い閉路の長さ という制約を入れた　(1.5は実験的に良さそうな値として選んだ)
fn compute_paths(input: &Input, k: usize) -> Vec<Vec<usize>> {
	let mut g = mat![1 << 29; input.n; input.n];
	for i in 0..input.n {
		for j in 0..input.n {
			g[i][j] = input.dij[i].dist[j];
		}
	}
	let path0 = tsp(input, &greedy(input), get_time() + 1.0, true); // とりあえず通常のTSPを求めてからk分割
	let mut paths: Vec<Vec<usize>> = (0..k).map(|i| [0].iter().chain(path0[1 + (input.n - 1) * i / k .. 1 + (input.n - 1) * (i + 1) / k].iter()).chain(&[0]).cloned().collect()).collect(); // それを均等にk分割することで初期解を生成
	for i in 0..k {
		paths[i] = tsp(input, &paths[i], get_time() + 0.1, true); // 初期解の各閉路をそれぞれTSPで最適化
	}
	
	let mut path0 = paths[0].clone(); // 実装を楽にするために、ダミーの点 n, n+1, ..., n+k-2 を間に挟むことで、閉路の分割を一つの閉路として扱う
	path0.pop();
	for i in 0..k-1 {
		path0.push(input.n + i);
		path0.extend(paths[i + 1][1..paths[i + 1].len()-1].iter().cloned());
	}
	path0.push(0);
	
	let path0 = tsp_with_div(input, &path0, k, get_time() + 10.0, true); // ここまでで計算した初期解をベースに最適化
	
	let mut paths: Vec<Vec<usize>> = vec![vec![]]; // ダミー頂点を元に戻して分割を得る
	for p in path0 {
		let a = paths.len();
		if p >= input.n {
			paths[a - 1].push(0);
			paths.push(vec![0]);
		} else {
			paths[a - 1].push(p);
		}
	}
	for i in 0..k {
		paths[i] = tsp(input, &paths[i], get_time() + 0.5, true); // 最後に各閉路をもう一度TSPで最適化
	}
	paths
}

/// g: 距離行列
/// ps: パス
/// ws[i]: 点iの重み
/// (時刻Tまでに回収できない点の重みの和, 時刻Tまでの長さ, 総長)を返す。
/// 時刻Tまでの長さを評価に入れてる理由は、出来るだけ前に詰めたほうが隙間に他のを入れやすそうだから。
/// 総長を評価に入れている理由は、2-optでのつなぎ変え時にはT以降の部分も使うため、そこも最適化が必要だから。
/// mv適用後のスコアを高速に計算とかも出来るかもしれないが、この実装ではO(n)時間かけており、改善の余地あり。
fn compute_cost_with_T(g: &Vec<Vec<i32>>, ps: &Vec<usize>, ws: &Vec<i32>, T: i32) -> (i32, i32, i32) {
	let mut tmp = 0;
	let mut fail = 0;
	let mut head = -1;
	for i in 0..ps.len() - 1 {
		tmp += g[ps[i]][ps[i + 1]];
		if tmp > T {
			if head < 0 {
				head = tmp - g[ps[i]][ps[i + 1]];
			}
			fail += ws[ps[i + 1]];
		}
	}
	(fail, head, tmp)
}

/// 残り時間Tで出来るだけ多くの注文を届けるパス最適化
/// qs: 注文のある頂点
/// ws[i]: 点qs[i]にある注文の個数
fn compute_final_path(input: &Input, qs: &Vec<usize>, ws: &Vec<i32>, T: i32) -> Vec<usize> {
	eprintln!("===== final =====");
	let until = TIME_LIMIT + 0.6;
	let n = qs.len();
	
	let mut g = mat![1 << 29; n; n]; // qs内の点のみに圧縮したグラフを作成
	let mut near = vec![0; n]; // 枝刈り用に5番目に近い点までの距離を計算
	for i in 0..n {
		for j in 0..n {
			g[i][j] = input.dij[qs[i]].dist[qs[j]];
		}
		let mut tmp = g[i].clone();
		tmp.sort();
		near[i] = tmp[std::cmp::min(5, n - 1)];
	}
	
	let mut rng = XorShift::new(47894);
	let mut ps: Vec<_> = (0..n).collect(); // 現在のパス
	let mut cost = compute_cost_with_T(&g, &ps, ws, T);
	eprintln!("init: {:?}", cost);
	let (mut min, mut min_ps) = (cost, ps.clone()); // これまでに見つけたベスト解
	while get_time() < until {
		loop {
			if get_time() >= until {
				break;
			}
			let mut ok = false;
			for i in 0..n-2 { // 一つ目に消す辺(i,i+1)
				for j in i+1..n-1 { // １つ目に追加する辺(i,j)
					// 2-opt + αの近傍を調べる
					// 詳しくはps2の構築部分を参照
					let gain = g[ps[i]][ps[i + 1]] - g[ps[i]][ps[j]];
					if gain >= -3 { // スコアの評価がO(n)で重いので、つなぎ変えによる部分的なコストの変化を見て枝刈りしている
						let ps2 = ps[0..i+1].iter().chain(ps[i+1..j+1].iter().rev()).chain(ps[j+1..].iter()).cloned().collect();
						if cost.setmin(compute_cost_with_T(&g, &ps2, ws, T)) {
							ps = ps2;
							ok = true;
						}
					}
					let gain = g[ps[i]][ps[i + 1]] - g[ps[i]][ps[j + 1]];
					if gain >= -3 {
						let ps2 = ps[0..i+1].iter().chain(ps[j+1..].iter()).chain(ps[i+1..j+1].iter()).cloned().collect();
						if cost.setmin(compute_cost_with_T(&g, &ps2, ws, T)) {
							ps = ps2;
							ok = true;
						}
					}
					if g[ps[i]][ps[j + 1]] <= near[ps[i]] {
						for k in j+1..n-1 {
							if g[ps[i + 1]][ps[k]] <= near[ps[i + 1]] {
								let ps2 = ps[0..i+1].iter().chain(ps[j+1..k+1].iter()).chain(ps[i+1..j+1].iter()).chain(ps[k+1..].iter()).cloned().collect();
								if cost.setmin(compute_cost_with_T(&g, &ps2, ws, T)) {
									ps = ps2;
									ok = true;
								}
							}
						}
					}
				}
				let ps2 = ps[0..i+1].iter().chain(ps[i+1..].iter().rev()).cloned().collect();
				if cost.setmin(compute_cost_with_T(&g, &ps2, ws, T)) {
					ps = ps2;
					ok = true;
				}
			}
			if !ok {
				break;
			}
		}
		if min.setmin(cost) {
			eprintln!("{:.3}: {:?}", get_time(), cost);
			min_ps = ps;
		}
		ps = min_ps.clone();
		if n <= 4 {
			break;
		}
		loop {
			if rng.next(2) == 0 {
				// double bridge
				let mut is: Vec<_> = (0..4).map(|_| rng.next(n - 1)).collect();
				is.sort();
				if is[0] == is[1] || is[1] == is[2] || is[2] == is[3] {
					continue;
				}
				ps = ps[0..is[0]+1].iter()
						.chain(ps[is[2]+1..is[3]+1].iter())
						.chain(ps[is[1]+1..is[2]+1].iter())
						.chain(ps[is[0]+1..is[1]+1].iter())
						.chain(ps[is[3]+1..].iter())
						.cloned().collect();
				cost = compute_cost_with_T(&g, &ps, ws, T);
			} else {
				// random 2-opt × 6
				for _ in 0..6 {
					loop {
						let i = rng.next(n - 2) as usize;
						let j = 1 + rng.next(n - 2) as usize;
						if i < j {
							ps = ps[0..i+1].iter().chain(ps[i+1..j+1].iter().rev()).chain(ps[j+1..].iter()).cloned().collect();
							break;
						}
					}
				}
				cost = compute_cost_with_T(&g, &ps, ws, T);
			}
			break;
		}
	}
	min_ps.into_iter().map(|i| qs[i]).collect()
}

fn run() {
	let input = read_input();
	eprintln!("Problem = {}", input.problem);
	eprintln!("n = {}", input.n);
	let paths = compute_paths(&input, 4); // 閉路４つの分割で全点を覆う。４は実験的に一番良さそうな値として決めた。
	let mut i = 0; // 今何番目の閉路を辿っているか
	let mut commands = vec![]; // これから先、発行するコマンド列
	let mut state = State::new(&input);
	for t in 0..input.T {
		if input.problem == 'a' {
			state.add_order(input.orders[t]);
		} else {
			state.add_order(read_new_order());
			let k = read!(usize);
			read!(usize; k);
		}
		if commands.len() == 0 { // この時点で店に居る
			if t >= input.lastT { // これ以上注文は発生しないので残りの注文を出来るだけ届けることの出来るパスを計算
				let mut ps = vec![0]; // 注文の残っている頂点のリスト
				for _ in 0..paths.len() {
					i = (i + 1) % paths.len();
					ps.extend(paths[i].iter().filter(|&&u| state.orders[u].len() > 0).cloned());
				}
				if ps.len() > 1 {
					ps = compute_final_path(&input, &ps, &ps.iter().map(|&i| state.orders[i].len() as i32).collect(), (input.T - t) as i32);
					ps.push(0);
					let p = state.compute_best_path(&input, &ps);
					commands = p.1.into_iter().rev().collect();
					eprintln!("gain: {}", p.0);
				}
			} else {
				for _ in 0..paths.len() { // 閉路を順番に見ていき、注文が一つでもある閉路を巡る
					i = (i + 1) % paths.len();
					if paths[i].iter().any(|&u| state.orders[u].len() > 0) {
						let qs: Vec<_> = paths[i].iter().filter(|&&u| u == 0 || state.orders[u].len() > 0).cloned().collect(); // 注文のある頂点のリスト
						let qs = tsp(&input, &qs, get_time() + 0.1, true); // TSPで最適化
						let p1 = state.compute_best_path(&input, &qs); // 順向きで辿る場合と
						let p2 = state.compute_best_path(&input, &qs.iter().cloned().rev().collect()); // 逆向きで辿る場合のスコアを計算し
						if p1.0 > p2.0 { // 良い方を採用
							commands = p1.1;
							eprintln!("gain: {}", p1.0);
						} else {
							commands = p2.1;
							eprintln!("gain: {}", p2.0);
						}
						commands = commands.into_iter().rev().collect();
						break;
					}
				}
			}
		}
		if let Some(c) = commands.pop() { // 既に計算したコマンド列を一つずつ発行
			state.command(c);
			println!("{}", c + 1);
		} else {
			state.command(!0);
			println!("-1");
		}
		std::io::stdout().flush().unwrap();
		if input.problem == 'b' {
			let _ = read!(String);
			let k = read!(usize);
			read!(usize; k);
		}
	}
	eprintln!("Score = {}", state.score);
	eprintln!("Time = {:.3}", get_time());
	eprintln!("fail = {}", state.orders.iter().map(|a| a.len()).sum::<usize>());
}


Measured memory_bytes: 16756