use std::io; pub mod random { pub struct PcgXshRr { state: u64, } impl PcgXshRr { pub fn new(state: u64) -> Self { PcgXshRr { state } } pub fn next_int(&mut self) -> u32 { let oldstate = self.state; self.state = oldstate * 6364136223846793005u64 + 521u64; let xorshift: u32 = (((oldstate >> 18) ^ oldstate) >> 27) as u32; let rotation: u32 = (oldstate >> 59) as u32; return (xorshift >> rotation) | (xorshift << ((-1 * rotation as i32) & 31)); } pub fn next_double(&mut self) -> f64 { return (self.next_int() as f64) * 0.00000000023283064365386963; } pub fn gen(&mut self) -> usize { return self.next_int() as usize; } } } fn get_time() -> f64 { static mut START: f64 = -1.0; let time = std::time::SystemTime::now() .duration_since(std::time::UNIX_EPOCH) .unwrap() .as_secs_f64(); unsafe { if START < 0.0 { START = time; } time - START } } fn main() { get_time(); let mut input_line = String::new(); io::stdin().read_line(&mut input_line).unwrap(); let mut iter = input_line.split_whitespace(); let n: usize = iter.next().unwrap().parse().unwrap(); let k: usize = iter.next().unwrap().parse().unwrap(); let mut a = vec![0; n]; let mut b = vec![0; n]; let mut c = vec![0; 2 * n]; let mut d = vec![0; 2 * n]; let mut e = vec![0; n]; let mut f = vec![0; n]; input_line.clear(); io::stdin().read_line(&mut input_line).unwrap(); let mut iter = input_line.split_whitespace(); for i in 0..n { a[i] = iter.next().unwrap().parse().unwrap(); } input_line.clear(); io::stdin().read_line(&mut input_line).unwrap(); let mut iter = input_line.split_whitespace(); for i in 0..n { b[i] = iter.next().unwrap().parse().unwrap(); } input_line.clear(); io::stdin().read_line(&mut input_line).unwrap(); let mut iter = input_line.split_whitespace(); for i in 0..(2 * n) { c[i] = iter.next().unwrap().parse().unwrap(); } input_line.clear(); io::stdin().read_line(&mut input_line).unwrap(); let mut iter = input_line.split_whitespace(); for i in 0..(2 * n) { d[i] = iter.next().unwrap().parse().unwrap(); } input_line.clear(); io::stdin().read_line(&mut input_line).unwrap(); let mut iter = input_line.split_whitespace(); for i in 0..n { e[i] = iter.next().unwrap().parse().unwrap(); } input_line.clear(); io::stdin().read_line(&mut input_line).unwrap(); let mut iter = input_line.split_whitespace(); for i in 0..n { f[i] = iter.next().unwrap().parse().unwrap(); } let mut rng = random::PcgXshRr::new(5342); let mut u = (0..n).collect::>(); let mut x = (0..n).collect::>(); u.sort_by_key(|&i| a[i]); x.sort_by_key(|&i| e[i]); let mut vw = (0..2 * n).collect::>(); vw.sort_by_key(|&i| c[i]); let mut v = (0..2 * n) .step_by(2) .map(|i| vw[i]) .skip(n - k) .chain((0..2 * n).step_by(2).map(|i| vw[i]).take(n - k)) .collect::>(); let mut w = (1..2 * n) .step_by(2) .map(|i| vw[i]) .skip(n - k) .chain((1..2 * n).step_by(2).map(|i| vw[i]).take(n - k)) .collect::>(); let mut heights = (0..n) .map(|i| a[u[i]] + c[v[i]] + c[w[i]] + e[x[i]]) .collect::>(); for i in 0..k { for j in i + 1..k { if heights[j - 1] > heights[j] { u.swap(j - 1, j); v.swap(j - 1, j); w.swap(j - 1, j); x.swap(j - 1, j); heights.swap(j - 1, j); } } } { let start_temperature = 2e1; let end_temperature = 1e-9; let mut temperature = start_temperature; let max_iterations = 1e5 as usize; for iterations in 0..max_iterations { if (iterations & ((1 << 7) - 1)) == ((1 << 7) - 1) { temperature = end_temperature + (start_temperature - end_temperature) * (max_iterations - iterations) as f64 / (max_iterations) as f64; } let uvx = rng.gen() % 3; if uvx == 0 { let i = rng.gen() % k; let mut j = rng.gen() % (n - 1); if j >= i { j += 1; } if e[x[i]] < a[u[j]] && a[u[j]] < c[v[i]] { } else { continue; } if j < k { if e[x[j]] < a[u[i]] && a[u[i]] < c[v[j]] { } else { continue; } } let height_i = b[u[j]] + d[v[i]] + d[w[i]] + f[x[i]]; let height_j = b[u[i]] + d[v[j]] + d[w[j]] + f[x[j]]; let mut max = heights[k - 1].max(height_i); if j < k { max = max.max(height_j); } let mut min = heights[0].min(height_i); if j < k { min = min.min(height_j); } let delta_score = (40000 - (max - min)) - (40000 - (heights[k - 1] - heights[0])); if delta_score >= 0 || (delta_score as f64 / temperature >= -10.0 && rng.next_double() < (delta_score as f64 / temperature).exp()) { u.swap(i, j); heights[i] = height_i; heights[j] = height_j; sort(k, &mut u, &mut v, &mut w, &mut x, &mut heights); } } else if uvx == 1 { let i = rng.gen() % k; let mut j = rng.gen() % (n - 1); if j >= i { j += 1; } let vw1 = rng.gen() % 2; let vw2 = rng.gen() % 2; if vw1 == 0 { if vw2 == 0 { v.swap(i, j); } else { let swap = v[i]; v[i] = w[j]; w[j] = swap; } } else { if vw2 == 0 { let swap = w[i]; w[i] = v[j]; v[j] = swap; } else { w.swap(i, j); } } if a[u[i]] < c[v[i]].min(c[w[i]]) { } else { if vw1 == 0 { if vw2 == 0 { v.swap(i, j); } else { let swap = v[i]; v[i] = w[j]; w[j] = swap; } } else { if vw2 == 0 { let swap = w[i]; w[i] = v[j]; v[j] = swap; } else { w.swap(i, j); } } continue; } if j < k { if a[u[j]] < c[v[j]].min(c[w[j]]) { } else { if vw1 == 0 { if vw2 == 0 { v.swap(i, j); } else { let swap = v[i]; v[i] = w[j]; w[j] = swap; } } else { if vw2 == 0 { let swap = w[i]; w[i] = v[j]; v[j] = swap; } else { w.swap(i, j); } } continue; } } let height_i = b[u[i]] + d[v[i]] + d[w[i]] + f[x[i]]; let height_j = b[u[j]] + d[v[j]] + d[w[j]] + f[x[j]]; let mut max = heights[k - 1].max(height_i); if j < k { max = max.max(height_j); } let mut min = heights[0].min(height_i); if j < k { min = min.min(height_j); } let delta_score = (40000 - (max - min)) - (40000 - (heights[k - 1] - heights[0])); if delta_score >= 0 || (delta_score as f64 / temperature >= -10.0 && rng.next_double() < (delta_score as f64 / temperature).exp()) { if c[v[i]] > c[w[i]] { let swap = v[i]; v[i] = w[i]; w[i] = swap; } if c[v[j]] > c[w[j]] { let swap = v[j]; v[j] = w[j]; w[j] = swap; } heights[i] = height_i; heights[j] = height_j; sort(k, &mut u, &mut v, &mut w, &mut x, &mut heights); } else { if vw1 == 0 { if vw2 == 0 { v.swap(i, j); } else { let swap = v[i]; v[i] = w[j]; w[j] = swap; } } else { if vw2 == 0 { let swap = w[i]; w[i] = v[j]; v[j] = swap; } else { w.swap(i, j); } } } } else if uvx == 2 { let i = rng.gen() % k; let mut j = rng.gen() % (n - 1); if j >= i { j += 1; } if e[x[j]] < a[u[i]] { } else { continue; } if j < k { if e[x[i]] < a[u[j]] { } else { continue; } } let height_i = b[u[i]] + d[v[i]] + d[w[i]] + f[x[j]]; let height_j = b[u[j]] + d[v[j]] + d[w[j]] + f[x[i]]; let mut max = heights[k - 1].max(height_i); if j < k { max = max.max(height_j); } let mut min = heights[0].min(height_i); if j < k { min = min.min(height_j); } let delta_score = (40000 - (max - min)) - (40000 - (heights[k - 1] - heights[0])); if delta_score >= 0 || (delta_score as f64 / temperature >= -10.0 && rng.next_double() < (delta_score as f64 / temperature).exp()) { x.swap(i, j); heights[i] = height_i; heights[j] = height_j; sort(k, &mut u, &mut v, &mut w, &mut x, &mut heights); } } } } { let start_temperature = 2e1; let end_temperature = 1e-9; let mut temperature = start_temperature; let max_iterations = 2e7 as usize; for iterations in 0..max_iterations { if (iterations & ((1 << 7) - 1)) == ((1 << 7) - 1) { temperature = end_temperature + (start_temperature - end_temperature) * (max_iterations - iterations) as f64 / (max_iterations) as f64; } let uvx = rng.gen() % 3; if uvx == 0 { let i = (rng.gen() % 2 + (k - 1)) % k; let mut j = rng.gen() % (n - 1); if j >= i { j += 1; } if e[x[i]] < a[u[j]] && a[u[j]] < c[v[i]] { } else { continue; } if j < k { if e[x[j]] < a[u[i]] && a[u[i]] < c[v[j]] { } else { continue; } } let height_i = b[u[j]] + d[v[i]] + d[w[i]] + f[x[i]]; let height_j = b[u[i]] + d[v[j]] + d[w[j]] + f[x[j]]; let mut max = heights[k - 1].max(height_i); if j < k { max = max.max(height_j); } let mut min = heights[0].min(height_i); if j < k { min = min.min(height_j); } let delta_score = (40000 - (max - min)) - (40000 - (heights[k - 1] - heights[0])); if delta_score >= 0 || (delta_score as f64 / temperature >= -10.0 && rng.next_double() < (delta_score as f64 / temperature).exp()) { u.swap(i, j); heights[i] = height_i; heights[j] = height_j; sort(k, &mut u, &mut v, &mut w, &mut x, &mut heights); } } else if uvx == 1 { let i = (rng.gen() % 2 + (k - 1)) % k; let mut j = rng.gen() % (n - 1); if j >= i { j += 1; } let vw1 = rng.gen() % 2; let vw2 = rng.gen() % 2; if vw1 == 0 { if vw2 == 0 { v.swap(i, j); } else { let swap = v[i]; v[i] = w[j]; w[j] = swap; } } else { if vw2 == 0 { let swap = w[i]; w[i] = v[j]; v[j] = swap; } else { w.swap(i, j); } } if a[u[i]] < c[v[i]].min(c[w[i]]) { } else { if vw1 == 0 { if vw2 == 0 { v.swap(i, j); } else { let swap = v[i]; v[i] = w[j]; w[j] = swap; } } else { if vw2 == 0 { let swap = w[i]; w[i] = v[j]; v[j] = swap; } else { w.swap(i, j); } } continue; } if j < k { if a[u[j]] < c[v[j]].min(c[w[j]]) { } else { if vw1 == 0 { if vw2 == 0 { v.swap(i, j); } else { let swap = v[i]; v[i] = w[j]; w[j] = swap; } } else { if vw2 == 0 { let swap = w[i]; w[i] = v[j]; v[j] = swap; } else { w.swap(i, j); } } continue; } } let height_i = b[u[i]] + d[v[i]] + d[w[i]] + f[x[i]]; let height_j = b[u[j]] + d[v[j]] + d[w[j]] + f[x[j]]; let mut max = heights[k - 1].max(height_i); if j < k { max = max.max(height_j); } let mut min = heights[0].min(height_i); if j < k { min = min.min(height_j); } let delta_score = (40000 - (max - min)) - (40000 - (heights[k - 1] - heights[0])); if delta_score >= 0 || (delta_score as f64 / temperature >= -10.0 && rng.next_double() < (delta_score as f64 / temperature).exp()) { if c[v[i]] > c[w[i]] { let swap = v[i]; v[i] = w[i]; w[i] = swap; } if c[v[j]] > c[w[j]] { let swap = v[j]; v[j] = w[j]; w[j] = swap; } heights[i] = height_i; heights[j] = height_j; sort(k, &mut u, &mut v, &mut w, &mut x, &mut heights); } else { if vw1 == 0 { if vw2 == 0 { v.swap(i, j); } else { let swap = v[i]; v[i] = w[j]; w[j] = swap; } } else { if vw2 == 0 { let swap = w[i]; w[i] = v[j]; v[j] = swap; } else { w.swap(i, j); } } } } else if uvx == 2 { let i = (rng.gen() % 2 + (k - 1)) % k; let mut j = rng.gen() % (n - 1); if j >= i { j += 1; } if e[x[j]] < a[u[i]] { } else { continue; } if j < k { if e[x[i]] < a[u[j]] { } else { continue; } } let height_i = b[u[i]] + d[v[i]] + d[w[i]] + f[x[j]]; let height_j = b[u[j]] + d[v[j]] + d[w[j]] + f[x[i]]; let mut max = heights[k - 1].max(height_i); if j < k { max = max.max(height_j); } let mut min = heights[0].min(height_i); if j < k { min = min.min(height_j); } let delta_score = (40000 - (max - min)) - (40000 - (heights[k - 1] - heights[0])); if delta_score >= 0 || (delta_score as f64 / temperature >= -10.0 && rng.next_double() < (delta_score as f64 / temperature).exp()) { x.swap(i, j); heights[i] = height_i; heights[j] = height_j; sort(k, &mut u, &mut v, &mut w, &mut x, &mut heights); } } } } eprint!( "score : {}, time : {}", 40000 - (heights[k - 1] - heights[0]), get_time() ); for i in 0..k { println!("{} {} {} {}", u[i] + 1, v[i] + 1, w[i] + 1, x[i] + 1); } } fn sort( k: usize, u: &mut [usize], v: &mut [usize], w: &mut [usize], x: &mut [usize], heights: &mut [i32], ) { for _ in 0..2 { for b in 1..k { let a = b - 1; if heights[a] > heights[b] { u.swap(a, b); v.swap(a, b); w.swap(a, b); x.swap(a, b); heights.swap(a, b); } } } for _ in 0..2 { for b in (1..k).rev() { let a = b - 1; if heights[a] > heights[b] { u.swap(a, b); v.swap(a, b); w.swap(a, b); x.swap(a, b); heights.swap(a, b); } } } }