#![allow(non_snake_case, unused)]

#[cfg(feature = "local")]
extern crate hokudai19;

#[cfg(feature = "local")]
use hokudai19::*;

#[cfg(not(feature = "local"))]
macro_rules! profile {
	($id:ident) => {
	};
}

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

////////// missing functions in 1.15.1 //////////
macro_rules! eprint {
	($($t:tt)*) => {{
		use ::std::io::Write;
		let _ = write!(::std::io::stderr(), $($t)*);
	}};
}
macro_rules! eprintln {
	() => { eprintln!(""); };
	($($t:tt)*) => {{
		use ::std::io::Write;
		let _ = writeln!(::std::io::stderr(), $($t)*);
	}};
}
macro_rules! dbg {
	($v:expr) => {{
		let val = $v;
		eprintln!("[{}:{}] {} = {:?}", file!(), line!(), stringify!($v), val);
		val
	}}
}
/////////////////////////////////////////////////
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;
			}
		}
		// for i in 1..f.len() {
		// 	f[i] = 1;
		// }
	}
	let lastT = if problem == 'a' {
		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>) {
		profile!(compute_best_path);
		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 {
		profile!(dijkstra);
		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
}

// mv: (i, dir)
fn apply_move(tour: &mut Vec<usize>, idx: &mut Vec<usize>, mv: &[(usize, usize)]) {
	profile!(apply_move);
	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;
	}
}

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];

fn tsp(input: &Input, qs: &[usize], until: f64, dbg: bool) -> Vec<usize> {
	profile!(tsp);
	if dbg {
		eprintln!("===== tsp =====");
	}
	let until = until.min(TIME_LIMIT);
	let mut id = vec![!0; input.n];
	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();
	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;
		}
		loop {
			rep += 1;
			let mut ok = false;
			for i in 0..n {
				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 {
								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] {
											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 {
				// 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 {
				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()
}

fn compute_cost2(g: &Vec<Vec<i32>>, w: &Vec<i32>, paths: &Vec<Vec<usize>>) -> i32 {
	let mut ls: Vec<_> = paths.iter().map(|ps| compute_cost(g, ps)).collect();
	let mut ws: Vec<_> = paths.iter().map(|ps| ps.iter().map(|&i| w[i]).sum::<i32>()).collect();
	ws.iter().sum::<i32>() * ls.iter().sum::<i32>() + (0..paths.len()).map(|i| ws[i] * ls[i]).sum::<i32>()
}

fn compute_paths(input: &Input, k: usize) -> Vec<Vec<usize>> {
	profile!(compute_paths);
	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 mut f = vec![vec![]; input.n];
	for i in 0..input.n {
		for j in 0..input.n {
			if i != j {
				f[i].push((g[i][j], j));
			}
		}
		f[i].sort();
	}
	let path0 = tsp(input, &greedy(input), get_time() + 1.0, true);
	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();
	for i in 0..k {
		paths[i] = tsp(input, &paths[i], get_time() + 0.1, true);
	}
	let (mut min, mut min_paths) = (compute_cost2(&g, &input.f, &paths), paths.clone());
	eprintln!("init: {}", min);
	let mut rep = 0;
	let mut rng = XorShift::new(47894);
	let until = get_time() + 10.0;
	while get_time() < until {
		rep += 1;
		paths = min_paths.clone();
		let mut cost = min;
		// loop {
		// 	profile!(crossover);
		// 	let mut ps = vec![(!0, !0); input.n];
		// 	let mut ls: Vec<_> = paths.iter().map(|ps| compute_cost(&g, ps)).collect();
		// 	let mut ws: Vec<_> = paths.iter().map(|ps| ps.iter().map(|&i| input.f[i]).sum::<i32>()).collect();
		// 	let mut lss = vec![vec![]; k];
		// 	let mut wss = vec![vec![]; k];
		// 	for i in 0..k {
		// 		lss[i] = vec![0; paths[i].len()];
		// 		wss[i] = vec![0; paths[i].len()];
		// 		for a in 0..paths[i].len()-1 {
		// 			lss[i][a + 1] = lss[i][a] + g[paths[i][a]][paths[i][a + 1]];
		// 			wss[i][a + 1] = wss[i][a] + input.f[paths[i][a + 1]];
		// 		}
		// 		for a in 1..paths[i].len()-1 {
		// 			ps[paths[i][a]] = (i, a);
		// 		}
		// 	}
		// 	let mut best = min;
		// 	let mut best_iajbr = (!0, !0, !0, !0, false);
		// 	for i in 0..k {
		// 		for a in 0..paths[i].len()-1 {
		// 			for j in i+1..k {
		// 				for b in 0..paths[j].len()-1 {
		// 					let mut ls2 = ls.clone();
		// 					let mut ws2 = ws.clone();
		// 					ls2[i] = lss[i][a] + g[paths[i][a]][paths[j][b + 1]] + ls[j] - lss[j][b + 1];
		// 					ls2[j] = lss[j][b] + g[paths[j][b]][paths[i][a + 1]] + ls[i] - lss[i][a + 1];
		// 					ws2[i] = wss[i][a] + ws[j] - wss[j][b];
		// 					ws2[j] = wss[j][b] + ws[i] - wss[i][a];
		// 					if best.setmin(ws2.iter().sum::<i32>() * ls2.iter().sum::<i32>() + (0..k).map(|x| ws2[x] * ls2[x]).sum::<i32>()) {
		// 						best_iajbr = (i, a, j, b, false);
		// 					}
		// 					let mut ls2 = ls.clone();
		// 					let mut ws2 = ws.clone();
		// 					ls2[i] = lss[i][a] + g[paths[i][a]][paths[j][b]] + lss[j][b];
		// 					ls2[j] = ls[i] - lss[i][a + 1] + g[paths[i][a + 1]][paths[j][b + 1]] + ls[j] - lss[j][b + 1];
		// 					ws2[i] = wss[i][a] + wss[j][b];
		// 					ws2[j] = ws[i] - wss[i][a] + ws[j] - wss[j][b];
		// 					if best.setmin(ws2.iter().sum::<i32>() * ls2.iter().sum::<i32>() + (0..k).map(|x| ws2[x] * ls2[x]).sum::<i32>()) {
		// 						best_iajbr = (i, a, j, b, true);
		// 					}
		// 				}
		// 			}
		// 		}
		// 	}
		// 	if cost.setmin(best) {
		// 		let (i, a, j, b, r) = best_iajbr;
		// 		let mut old = paths.clone();
		// 		if r {
		// 			paths[i] = old[i][0..a + 1].iter().chain(old[j][0..b + 1].iter().rev()).cloned().collect();
		// 			paths[j] = old[i][a + 1..].iter().rev().chain(old[j][b + 1..].iter()).cloned().collect();
		// 		} else {
		// 			paths[i] = old[i][0..a + 1].iter().chain(old[j][b + 1..].iter()).cloned().collect();
		// 			paths[j] = old[j][0..b + 1].iter().chain(old[i][a + 1..].iter()).cloned().collect();
		// 		}
		// 		assert_eq!(cost, compute_cost2(&g, &input.f, &paths));
		// 	} else {
		// 		break;
		// 	}
		// }
		if rep > 1 {
			let i = rng.next(k);
			let mut j = rng.next(k - 1);
			if i <= j {
				j += 1;
			}
			let a = rng.next(paths[i].len() - 1);
			let b = rng.next(paths[j].len() - 1);
			let r = rng.next(2) == 0;
			let mut old = paths.clone();
			if r {
				paths[i] = old[i][0..a + 1].iter().chain(old[j][0..b + 1].iter().rev()).cloned().collect();
				paths[j] = old[i][a + 1..].iter().rev().chain(old[j][b + 1..].iter()).cloned().collect();
			} else {
				paths[i] = old[i][0..a + 1].iter().chain(old[j][b + 1..].iter()).cloned().collect();
				paths[j] = old[j][0..b + 1].iter().chain(old[i][a + 1..].iter()).cloned().collect();
			}
			cost = compute_cost2(&g, &input.f, &paths);
		}
		{
			profile!(variable_depth_insert);
			let mut ls: Vec<_> = paths.iter().map(|ps| compute_cost(&g, ps)).collect();
			let mut ws: Vec<_> = paths.iter().map(|ps| ps.iter().map(|&i| input.f[i]).sum::<i32>()).collect();
			let mut moved = vec![false; input.n];
			let mut best = cost;
			let mut best_paths = paths.clone();
			let mut count = 0;
			for t in 0..input.n-1 {
				let mut best2 = i32::max_value();
				let mut best_iajb = (!0, !0, !0, !0);
				for i in 0..k {
					for a in 1..paths[i].len()-1 {
						if moved[paths[i][a]] {
							continue;
						}
						let tmp_i = g[paths[i][a - 1]][paths[i][a + 1]] - g[paths[i][a - 1]][paths[i][a]] - g[paths[i][a]][paths[i][a + 1]];
						ls[i] += tmp_i;
						ws[i] -= input.f[paths[i][a]];
						for j in 0..k {
							if i == j {
								continue;
							}
							for b in 1..paths[j].len() {
								let tmp_j = g[paths[i][a]][paths[j][b - 1]] + g[paths[i][a]][paths[j][b]] - g[paths[j][b - 1]][paths[j][b]];
								ls[j] += tmp_j;
								ws[j] += input.f[paths[i][a]];
								if best2.setmin(ws.iter().sum::<i32>() * ls.iter().sum::<i32>() + (0..k).map(|x| ws[x] * ls[x]).sum::<i32>()) {
									best_iajb = (i, a, j, b);
								}
								ls[j] -= tmp_j;
								ws[j] -= input.f[paths[i][a]];
							}
						}
						ls[i] -= tmp_i;
						ws[i] += input.f[paths[i][a]];
					}
				}
				let (i, a, j, b) = best_iajb;
				let u = paths[i][a];
				ls[i] += g[paths[i][a - 1]][paths[i][a + 1]] - g[paths[i][a - 1]][paths[i][a]] - g[paths[i][a]][paths[i][a + 1]];
				ws[i] -= input.f[u];
				ls[j] += g[paths[i][a]][paths[j][b - 1]] + g[paths[i][a]][paths[j][b]] - g[paths[j][b - 1]][paths[j][b]];
				ws[j] += input.f[u];
				moved[u] = true;
				paths[i].remove(a);
				paths[j].insert(b, u);
				if best.setmin(best2) {
					best_paths = paths.clone();
					count = 0;
				} else {
					count += 1;
					if count >= 10 {
						break;
					}
				}
				assert_eq!(best2, compute_cost2(&g, &input.f, &paths));
			}
			paths = best_paths.clone();
		}
		for i in 0..k {
			paths[i] = tsp(input, &paths[i], 0.0, false);
		}
		if min.setmin(compute_cost2(&g, &input.f, &paths)) {
			eprintln!("{:.3}: {}", get_time(), min);
			min_paths = paths.clone();
		}
	}
	eprintln!("rep = {}", rep);
	paths = min_paths;
	for i in 0..k {
		paths[i] = tsp(input, &paths[i], get_time() + 1.0, true);
	}
	eprintln!("cost = {}", compute_cost2(&g, &input.f, &paths));
	paths
}

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)
}

fn compute_final_path(input: &Input, qs: &Vec<usize>, ws: &Vec<i32>, T: i32) -> Vec<usize> {
	profile!(final_path);
	eprintln!("===== final =====");
	let until = TIME_LIMIT + 0.5;
	// let mut ws = qs.iter().map(|u| )
	let mut id = vec![!0; input.n];
	for i in 0..qs.len() - 1 {
		id[qs[i]] = i;
	}
	let n = qs.len();
	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 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());
	let mut rep = 0;
	let mut kick = 0;
	while rep == 0 || get_time() < until {
		kick += 1;
		loop {
			rep += 1;
			let mut ok = false;
			for i in 0..n-2 {
				for j in i+1..n-1 {
					let gain = g[ps[i]][ps[i + 1]] - g[ps[i]][ps[j]];
					if gain >= -3 {
						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;
						}
					}
				}
				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 {
				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;
		}
	}
	eprintln!("rep = {}", rep);
	eprintln!("kick = {}", kick);
	assert_eq!(min, compute_cost_with_T(&g, &min_ps, ws, T));
	min_ps.into_iter().map(|i| qs[i]).collect()
}

fn run() {
	let input = read_input();
	eprintln!("Problem = {}", input.problem);
	eprintln!("n = {}", input.n);
	#[cfg(feature = "local")]
	let vis = if let Some(p) = std::env::args().nth(1) {
		Some(Vis::new(&input.g, &p))
	} else {
		None
	};
	let paths = compute_paths(&input, 4);
	eprintln!("paths = {:?}", paths.iter().map(|ps| ps.len() - 2).collect::<Vec<_>>());
	#[cfg(feature = "local")]
	{
		let vs = if input.problem == 'b' {
			(0..input.n).filter(|&i| input.f[i] == 2).collect()
		} else {
			(0..input.n).filter(|&i| input.f[i] > 9500 / 2 / input.n as i32 * 3 / 2).collect()
		};
		if let Some(ref vis) = vis {
			for i in 0..paths.len() {
				vis.vis(&format!("path{}.svg", i + 1), &paths[i], &vs);
			}
		}
	}
	let mut length = 0;
	for path in &paths {
		for i in 0..path.len() - 1 {
			length += input.dij[path[i]].dist[path[i + 1]];
		}
	}
	eprintln!("length = {}", length);
	let mut i = 0;
	let mut commands = vec![];
	let mut state = State::new(&input);
	let mut tmp = 0;
	let mut finish = 0;
	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 {
			assert!(state.u == state.v);
			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 {
					finish += 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);
					#[cfg(feature = "local")]
					{
						let vs = (0..input.n).filter(|&i| state.orders[i].len() > 0).collect();
						if let Some(ref vis) = vis {
							vis.vis(&format!("finish{}.svg", finish), &ps, &vs);
						}
					}
				}
			} 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.2, true);
						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;
							tmp += p1.0;
							eprintln!("gain: {}", p1.0);
						} else {
							commands = p2.1;
							tmp += p2.0;
							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' {
			assert_eq!("OK", 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>());
	#[cfg(feature = "local")]
	{
		let vs = (0..input.n).filter(|&i| state.orders[i].len() > 0).collect();
		if let Some(ref vis) = vis {
			vis.vis(&format!("fail.svg"), &vec![], &vs);
		}
	}
	#[cfg(feature = "local")]
	write_profile(&mut std::io::stderr());
}


Measured memory_bytes: 20824