#![allow(non_snake_case, unused_must_use, unused_imports)] use std::io::{self, prelude::*}; fn main() { let (stdin, stdout) = (io::read_to_string(io::stdin()).unwrap(), io::stdout()); let (mut stdin, mut buffer) = (stdin.split_whitespace(), io::BufWriter::new(stdout.lock())); macro_rules! input { ($t: tt, $n: expr) => { (0..$n).map(|_| input!($t)).collect::>() }; (Chars) => { input!(String).chars().collect::>() }; (Usize1) => { stdin.next().unwrap().parse::().unwrap() - 1 }; ($t: ty) => { stdin.next().unwrap().parse::<$t>().unwrap() }; } let N = input!(usize); let D = input!(usize, N); let Q = input!(usize); let CS = CumulativeSum::from(&D); for _ in 0..Q { let mut y = input!(usize); let mut m = input!(usize); let mut d = input!(usize); let mut k = input!(usize); // 1月1日に戻す k += d - 1; d = 1; if m > 1 { k += CS.sum(0..m - 1); m = 1; } let dy = k / CS.sum(..); y += dy; k -= dy * CS.sum(..); if D[0] > k { writeln!(buffer, "{} {} {}", y, m, k + 1); continue; } let mut ok = 0; let mut ng = N + 1; while ng - ok > 1 { let mid = (ok + ng) / 2; if CS.sum(..=mid) < k { ok = mid; } else { ng = mid; } } m = ok + 2; d = k + 1 - CS.sum(..=ok); writeln!(buffer, "{} {} {}", y, m, d); } } pub struct CumulativeSum { size: usize, prefix_sum: Vec, } impl + Default + Clone + Copy> CumulativeSum { pub fn from(array: &[T]) -> Self { let size = array.len(); let mut prefix_sum = vec![T::default(); size + 1]; for i in 0..size { prefix_sum[i + 1] = prefix_sum[i] + array[i]; } Self { size, prefix_sum } } pub fn prefix_sum(&self, i: usize) -> T { self.prefix_sum[i + 1] } } impl + std::ops::Sub + Default + Clone + Copy> CumulativeSum { pub fn sum>(&self, range: R) -> T { let left = match range.start_bound() { std::ops::Bound::Included(&l) => l, std::ops::Bound::Excluded(&l) => l + 1, std::ops::Bound::Unbounded => 0, }; let right = match range.end_bound() { std::ops::Bound::Included(&r) => r, std::ops::Bound::Excluded(&r) => r - 1, std::ops::Bound::Unbounded => self.size - 1, }; if left == 0 { return self.prefix_sum(right); } else { return self.prefix_sum(right) - self.prefix_sum(left - 1); } } }