#![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 check_div(ps: &Vec<usize>, idx: &Vec<usize>, mv: &[(usize, usize)], div: usize, id_div: &Vec<usize>, n: usize) -> bool {
	profile!(check_div);
	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)
}

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
}

fn tsp_with_div(input: &Input, qs: &[usize], div: usize, until: f64, dbg: bool) -> Vec<usize> {
	profile!(tsp_with_div);
	if dbg {
		eprintln!("===== tsp_with_div =====");
	}
	let until = until.min(TIME_LIMIT);
	let mut id = vec![!0; input.n + div - 1];
	let mut id_div = vec![];
	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;
		}
		loop {
			rep += 1;
			let mut ok = 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;
				}
			}
			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 {
								if check_div(&ps, &idx, &[(i, di), (j, dj)], div, &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(&ps, &idx, &[(i, di), (j, dj), (k, dk)], div, &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 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 path0 = paths[0].clone();
	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);
	}
	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.4;
	// 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];
	let mut near = vec![0; n];
	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());
	let mut rep = 0;
	let mut kick = 0;
	while rep == 0 || get_time() < until {
		kick += 1;
		loop {
			if get_time() >= until {
				break;
			}
			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;
						}
					}
					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 {
				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();
						let mut qs = vec![ps[0]];
						let mut tmp = t;
						for j in 0..ps.len()-1 {
							tmp += input.dij[ps[j]].dist[ps[j + 1]] as usize;
							if tmp > input.T {
								break;
							}
							qs.push(ps[j + 1]);
						}
						if let Some(ref vis) = vis {
							vis.vis(&format!("finish{}.svg", finish), &qs, &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.1, 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' {
			let tmp = read!(String);
			// assert_eq!("OK", tmp);
			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: 19388