#![recursion_limit = "2048"]
#![allow(unused_variables)]
#![allow(unused_assignments)]
#![allow(unused_macros)]
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_must_use)]
#![allow(non_upper_case_globals)]
#![allow(non_camel_case_types)]
#![allow(unused_comparisons)]
// crate import
// use std::io::*;
use std::cmp::*;
// use std::collections::*;
// use std::mem;
// use std::ops::Bound::*;
// use std::ops::RangeBounds;
// use std::str::FromStr;
// use std::fmt::Debug;
// use std::fmt::Display;
// use std::fmt::Write;
// use std::fmt::Result;
// use std::fmt::Formatter;
// use std::fmt::Error;
// use std::f32::consts::PI;
// use std::f64::consts::PI;

// 整数 1 つ読み込み (macro)
macro_rules! read {
    ($($t:ty),*) => {
        {
            let mut input = String::new();
            std::io::stdin().read_line(&mut input).ok();
            let mut iter = input.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap()),*)
        }
    };
}

// 整数 1 つ読み込み (macro)(u128)
macro_rules! read_u128 {
    () => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).ok();
        input.trim().parse::<u128>().unwrap()
    }};
}

// 整数 1 つ読み込み (macro)(i128)
macro_rules! read_i128 {
    () => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).ok();
        input.trim().parse::<i128>().unwrap()
    }};
}

// 文字列 1 つ読み込み (macro)
macro_rules! read_str {
    () => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).ok();
        input.trim().to_string()
    }};
}

// 整数の 1 次元ベクトル読み込み (macro)
macro_rules! read_vec {
    ($t:ty) => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).ok();
        input
            .trim()
            .split_whitespace()
            .map(|x| x.parse::<$t>().unwrap())
            .collect::<Vec<$t>>()
    }};
}

// 文字列の 1 次元ベクトル読み込み (macro)
macro_rules! read_str_vec {
    () => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).ok();
        input
            .trim()
            .split_whitespace()
            .map(|x| x.to_string())
            .collect::<Vec<String>>()
    }};
}

// 整数の 2 次元ベクトル読み込み (macro)
// 2 次元ベクトル読み込み (macro)
macro_rules! read_2d_vec {
    ($t:ty, $rows:expr, $cols:expr) => {{
        let mut v = Vec::with_capacity($rows);
        for _ in 0..$rows {
            v.push(read_vec!($t));
        }
        v
    }};
}

// char の 2 次元ベクトル読み込み (macro)
macro_rules! read_2d_char_vec {
    ($rows:expr, $cols:expr) => {{
        let mut v = Vec::with_capacity($rows);
        for _ in 0..$rows {
            v.push(read_char_vec!());
        }
        v
    }};
}

macro_rules! read_vecdeque {
    ($t:ty) => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).ok();
        let mut iter = input.split_whitespace();
        let mut vecdeque = VecDeque::new();
        while let Some(token) = iter.next() {
            if let Ok(num) = token.parse::<$t>() {
                vecdeque.push_back(num);
            } else {
                eprintln!("Invalid number: {}", token);
            }
        }
        vecdeque
    }};
}

// バイト列 1 つ読み込み (macro)
macro_rules! read_bytes {
    () => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).ok();
        input.trim().as_bytes().to_vec()
    }};
}

// chmin, chmax (macro)
macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_min = min!($($cmps),+);
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            false
        }
    }};
}

macro_rules! chmax {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_max = max!($($cmps),+);
        if $base < cmp_max {
            $base = cmp_max;
            true
        } else {
            false
        }
    }};
}

macro_rules! min {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+))
    }};
}

macro_rules! max {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::max($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::max($a, max!($($rest),+))
    }};
}

// 文字の 1 次元ベクトル読み込み (macro)
macro_rules! read_char_vec {
    () => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).ok();
        input
            .trim()
            .chars()
            .map(|c| c.to_string())
            .collect::<Vec<String>>()
    }};
}

macro_rules! print_space_separated {
    ($coll:expr) => {
        println!(
            "{}",
            $coll
                .iter()
                .map(|&x| x.to_string())
                .collect::<Vec<String>>()
                .join(" ")
        );
    };
}

macro_rules! print_space_separated_hashmap {
    ($map:expr) => {
        println!(
            "{}",
            $map.iter()
                .map(|(k, v)| format!("{} {}", k, v))
                .collect::<Vec<String>>()
                .join(" ")
        );
    };
}

macro_rules! print_2d_vec {
    ($vec:expr) => {
        for v in $vec.iter() {
            println!(
                "{}",
                v.iter()
                    .map(|&x| x.to_string())
                    .collect::<Vec<String>>()
                    .join(" ")
            );
        }
    };
}

const MIN_USIZE: usize = std::usize::MIN;

const MAX_USIZE: usize = std::usize::MAX;

const MIN_ISIZE: isize = std::isize::MIN;

const MAX_ISIZE: isize = std::isize::MAX;

// macro gcd
macro_rules! gcd {
    ($a:expr, $b:expr) => {{
        let mut a = $a;
        let mut b = $b;
        while b > 0 {
            let tmp = b;
            b = a % b;
            a = tmp;
        }
        a
    }};
}

// macro lcm
macro_rules! lcm {
    ($a:expr, $b:expr) => {{
        let a = $a;
        let b = $b;
        a / gcd!(a, b) * b
    }};
}

// macro mod_pow
macro_rules! mod_pow {
    ($a:expr, $b:expr, $m:expr) => {{
        let mut a = $a;
        let mut b = $b;
        let m = $m;
        let mut ret = 1;
        while b > 0 {
            if b & 1 == 1 {
                ret = ret * a % m;
            }
            a = a * a % m;
            b >>= 1;
        }
        ret
    }};
}

// macro mod_comb
macro_rules! mod_comb {
    ($n:expr, $k:expr, $m:expr) => {{
        let n = $n;
        let k = $k;
        let m = $m;
        let mut ret = 1;
        for i in 0..k {
            ret = ret * (n - i) % m;
            ret = ret * mod_pow!(i + 1, m - 2, m) % m;
        }
        ret
    }};
}

// macro mod_fact
macro_rules! mod_fact {
    ($n:expr, $m:expr) => {{
        let n = $n;
        let m = $m;
        let mut ret = 1;
        for i in 1..n + 1 {
            ret = ret * i % m;
        }
        ret
    }};
}

// macro mod_inv
macro_rules! mod_inv {
    ($a:expr, $m:expr) => {{
        let mut a = $a;
        let m = $m;
        let mut b = m;
        let mut u = 1;
        let mut v = 0;
        while b > 0 {
            let t = a / b;
            a -= t * b;
            std::mem::swap(&mut a, &mut b);
            u -= t * v;
            std::mem::swap(&mut u, &mut v);
        }
        u %= m;
        if u < 0 {
            u += m;
        }
        u
    }};
}

// 縦に整数の読み込み（引数に型と個数）
macro_rules! read_vec_vertical {
    ($t:ty, $n:expr) => {{
        let mut v = Vec::with_capacity($n);
        for _ in 0..$n {
            v.push(read!($t));
        }
        v
    }};
}

// 縦に文字列の読み込み（引数に個数）
macro_rules! read_str_vec_vertical {
    ($n:expr) => {{
        let mut v = Vec::with_capacity($n);
        for _ in 0..$n {
            v.push(read_str!());
        }
        v
    }};
}

// 縦に byte 型の読み込み（引数に個数）
macro_rules! read_bytes_vec_vertical {
    ($n:expr) => {{
        let mut v = Vec::with_capacity($n);
        for _ in 0..$n {
            v.push(read_bytes!());
        }
        v
    }};
}

macro_rules! read_2d_str_vec {
    ($rows:expr) => {{
        let mut v = Vec::with_capacity($rows);
        for _ in 0..$rows {
            v.push(read_str_vec!());
        }
        v
    }};
}

// 二分探索 (binary search)
macro_rules! binary_search {
    ($arr:expr, $target:expr) => {{
        let mut left = 0;
        let mut right = $arr.len();
        while left < right {
            let mid = (left + right) / 2;
            if $arr[mid] < $target {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }};
}

// 最長増加部分列 (LIS: Longest Increasing Subsequence)
macro_rules! longest_increasing_subsequence {
    ($arr:expr) => {{
        let mut lis_end: Vec<usize> = vec![0; $arr.len()];
        let mut lis_len = 0;

        for &num in $arr {
            let index = binary_search!(&lis_end[..lis_len], num);
            lis_end[index] = num;
            if index == lis_len {
                lis_len += 1;
            }
        }

        lis_len
    }};
}

// LCS(Longest Common Subsequence)
macro_rules! longest_common_subsequence {
    ($s1:expr, $s2:expr) => {{
        let n = $s1.len();
        let m = $s2.len();
        let mut dp = vec![vec![0; m + 1]; n + 1];

        for i in 1..=n {
            for j in 1..=m {
                if $s1[i - 1] == $s2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
                }
            }
        }

        let mut lcs_length = dp[n][m];
        let mut lcs = Vec::with_capacity(lcs_length);
        let (mut i, mut j) = (n, m);

        while i > 0 && j > 0 {
            if $s1[i - 1] == $s2[j - 1] {
                lcs.push($s1[i - 1]);
                i -= 1;
                j -= 1;
            } else if dp[i - 1][j] > dp[i][j - 1] {
                i -= 1;
            } else {
                j -= 1;
            }
        }

        lcs.reverse();
        (lcs_length, lcs)
    }};
}

const MOD: usize = 1_000_000_007;
const INF: isize = 2_000_000_000;

pub type Graph = Vec<Vec<usize>>;

#[cfg(target_pointer_width = "64")]
pub type fsize = f64;
#[cfg(target_pointer_width = "32")]
pub type fsize = f32;

pub fn lower_bound<T: Ord>(arr: &[T], x: &T) -> usize {
    let mut l = 0;
    let mut r = arr.len();
    while l < r {
        let m = (l + r) / 2;
        if &arr[m] < x {
            l = m + 1;
        } else {
            r = m;
        }
    }
    l
}

pub fn upper_bound<T: Ord>(arr: &[T], x: &T) -> usize {
    let mut l = 0;
    let mut r = arr.len();
    while l < r {
        let m = (l + r) / 2;
        if &arr[m] <= x {
            l = m + 1;
        } else {
            r = m;
        }
    }
    l
}

pub fn print_type_of<T>(_: T) {
    println!("{}", std::any::type_name::<T>());
}

// 2 次元の char 型のベクタを出力する
pub fn print_2d_char_vec(v: &Vec<Vec<char>>) {
    for i in 0..v.len() {
        for j in 0..v[i].len() {
            print!("{}", v[i][j]);
        }
        println!();
    }
}

// vector の merge_sort 関数
pub fn merge_sort<T: Ord + Clone>(arr: &mut Vec<T>) {
    let n = arr.len();
    if n <= 1 {
        return;
    }
    let mid = n / 2;
    let mut left = arr[..mid].to_vec();
    let mut right = arr[mid..].to_vec();
    merge_sort(&mut left);
    merge_sort(&mut right);
    let (mut i, mut j, mut k) = (0, 0, 0);
    while i < left.len() && j < right.len() {
        if left[i] < right[j] {
            arr[k] = left[i].clone();
            i += 1;
        } else {
            arr[k] = right[j].clone();
            j += 1;
        }
        k += 1;
    }
    while i < left.len() {
        arr[k] = left[i].clone();
        i += 1;
        k += 1;
    }
    while j < right.len() {
        arr[k] = right[j].clone();
        j += 1;
        k += 1;
    }
}

// vector の quick_sort 関数
pub fn quick_sort<T: Ord + Clone>(arr: &mut Vec<T>) {
    if arr.len() <= 1 {
        return;
    }
    let pivot = arr[0].clone();
    let mut left = Vec::new();
    let mut right = Vec::new();
    for i in 1..arr.len() {
        if arr[i] < pivot {
            left.push(arr[i].clone());
        } else {
            right.push(arr[i].clone());
        }
    }
    quick_sort(&mut left);
    quick_sort(&mut right);
    let mut k = 0;
    for x in left {
        arr[k] = x;
        k += 1;
    }
    arr[k] = pivot;
    k += 1;
    for x in right {
        arr[k] = x;
        k += 1;
    }
}

// dfs
macro_rules! dfs {
    ($graph:expr, $node:expr, $visited:expr, $action:block) => {{
        let mut stack = vec![$node];
        while let Some(node) = stack.pop() {
            if !$visited[node] {
                $visited[node] = true;
                $action
                for &next_node in &$graph[node] {
                    if !$visited[next_node] {
                        stack.push(next_node);
                    }
                }
            }
        }
    }};
}

// bfs
macro_rules! bfs {
    ($graph:expr, $node:expr, $visited:expr, $action:block) => {{
        let mut queue = VecDeque::new();
        queue.push_back($node);
        while let Some(node) = queue.pop_front() {
            if !$visited[node] {
                $visited[node] = true;
                $action
                for &next_node in &$graph[node] {
                    if !$visited[next_node] {
                        queue.push_back(next_node);
                    }
                }
            }
        }
    }};
}

// dijkstra
macro_rules! dijkstra {
    ($graph:expr, $start:expr) => {{
        let mut dist = vec![std::usize::MAX; $graph.len()];
        let mut heap = BinaryHeap::new();
        dist[$start] = 0;
        heap.push(std::cmp::Reverse((0, $start)));
        while let Some(std::cmp::Reverse((cost, node))) = heap.pop() {
            if cost > dist[node] {
                continue;
            }
            for &(next_node, next_cost) in &$graph[node] {
                let next_cost = cost + next_cost;
                if next_cost < dist[next_node] {
                    heap.push(std::cmp::Reverse((next_cost, next_node)));
                    dist[next_node] = next_cost;
                }
            }
        }
        dist
    }};
}

// ワーシャルフロイド法
macro_rules! warshall_floyd {
    ($graph:expr) => {{
        let mut dist = $graph.clone();
        let n = dist.len();
        for k in 0..n {
            for i in 0..n {
                for j in 0..n {
                    dist[i][j] = dist[i][j].min(dist[i][k] + dist[k][j]);
                }
            }
        }
        dist
    }};
}

// ベルマンフォード法
macro_rules! bellman_ford {
    ($graph:expr, $start:expr) => {{
        let n = $graph.len();
        let mut dist = vec![std::usize::MAX; n];
        dist[$start] = 0;
        for _ in 0..n {
            for i in 0..n {
                for &(next_node, next_cost) in &$graph[i] {
                    if dist[i] != std::usize::MAX && dist[next_node] > dist[i] + next_cost {
                        dist[next_node] = dist[i] + next_cost;
                        if i == n - 1 {
                            return None;
                        }
                    }
                }
            }
        }
        Some(dist)
    }};
}

// プリム法
macro_rules! prim {
    ($graph:expr) => {{
        let n = $graph.len();
        let mut used = vec![false; n];
        let mut heap = BinaryHeap::new();
        let mut cost = 0;
        heap.push((0, 0));
        while let Some((c, v)) = heap.pop() {
            if used[v] {
                continue;
            }
            used[v] = true;
            cost += c;
            for &(to, c) in &$graph[v] {
                heap.push((c, to));
            }
        }
        cost
    }};
}

// クラスカル法
macro_rules! kruskal {
    ($graph:expr) => {{
        let mut edges = vec![];
        for (i, vec) in $graph.iter().enumerate() {
            for &(j, cost) in vec {
                edges.push((cost, i, j));
            }
        }
        edges.sort();
        let mut uf = UnionFind::new($graph.len());
        let mut cost = 0;
        for &(c, a, b) in &edges {
            if !uf.same(a, b) {
                uf.unite(a, b);
                cost += c;
            }
        }
        cost
    }};
}

// ユニオンファインド
pub struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    pub fn new(n: usize) -> UnionFind {
        let mut parent = vec![0; n];
        for i in 0..n {
            parent[i] = i;
        }
        UnionFind {
            parent: parent,
            rank: vec![0; n],
        }
    }

    pub fn root(&mut self, x: usize) -> usize {
        if self.parent[x] == x {
            x
        } else {
            let parent = self.parent[x];
            let root = self.root(parent);
            self.parent[x] = root;
            root
        }
    }

    pub fn same(&mut self, x: usize, y: usize) -> bool {
        self.root(x) == self.root(y)
    }

    pub fn unite(&mut self, x: usize, y: usize) {
        let x = self.root(x);
        let y = self.root(y);
        if x == y {
            return;
        }
        if self.rank[x] < self.rank[y] {
            self.parent[x] = y;
        } else {
            self.parent[y] = x;
            if self.rank[x] == self.rank[y] {
                self.rank[x] += 1;
            }
        }
    }
}

// 二部グラフ判定
macro_rules! is_bipartite_graph {
    ($graph:expr) => {{
        let n = $graph.len();
        let mut color = vec![0; n];
        let mut stack = Vec::new();
        for i in 0..n {
            if color[i] != 0 {
                continue;
            }
            stack.push(i);
            color[i] = 1;
            while let Some(node) = stack.pop() {
                for &next_node in &$graph[node] {
                    if color[next_node] == 0 {
                        color[next_node] = -color[node];
                        stack.push(next_node);
                    } else if color[next_node] == color[node] {
                        return false;
                    }
                }
            }
        }
        true
    }};
}

// トポロジカルソート
macro_rules! topological_sort {
    ($graph:expr) => {{
        let n = $graph.len();
        let mut indeg = vec![0; n];
        for vec in &$graph {
            for &to in vec {
                indeg[to] += 1;
            }
        }
        let mut stack = Vec::new();
        for i in 0..n {
            if indeg[i] == 0 {
                stack.push(i);
            }
        }
        let mut res = Vec::new();
        while let Some(node) = stack.pop() {
            res.push(node);
            for &next_node in &$graph[node] {
                indeg[next_node] -= 1;
                if indeg[next_node] == 0 {
                    stack.push(next_node);
                }
            }
        }
        res
    }};
}

// 二部マッチング
macro_rules! bipartite_matching {
    ($graph:expr) => {{
        let n = $graph.len();
        let m = $graph[0].len();
        let mut match_to = vec![None; m];
        let mut res = 0;
        for i in 0..n {
            let mut visited = vec![false; n];
            if dfs_bipartite_matching!($graph, i, &mut visited, &mut match_to) {
                res += 1;
            }
        }
        res
    }};
}

// 高速フーリエ変換
// fft
macro_rules! convolution_macro {
    ($a:expr, $b:expr) => {{
        let mut a = $a;
        let mut b = $b;
        let m: i64 = 998244353;

        let mut n = 1;

        let na = a.len();
        let nb = b.len();

        while 2 * n < na + nb - 1 {
            n *= 2;
        }
        n *= 2;

        let mut p3 = vec![1_i64; 23]; // p3[i] = rn^(2^i) (1,rn,rn^2,rn^4,...,rn^(2^22))
        let mut invp3 = vec![1_i64; 23]; // invp3[i] = p3[i]の逆元
        let rn = pow_mod_macro!(3, (m - 1) / n as i64, m);
        p3[1] = rn;

        for i in 2..23 {
            p3[i] = p3[i - 1] * p3[i - 1] % m;
        }
        for i in 1..23 {
            invp3[i] = pow_mod_macro!(p3[i], m - 2, m);
        }

        for i in na..n {
            a.push(0);
        }
        for i in nb..n {
            b.push(0);
        }

        let a_fft = ntt_macro!(n, &a, &p3, 1);
        let b_fft = ntt_macro!(n, &b, &p3, 1);

        let mut c_fft = vec![0; n];

        for i in 0..n {
            c_fft[i] = a_fft[i] * b_fft[i] % m;
        }

        let mut c = ntt_macro!(n, &c_fft, &invp3, 1);

        for i in 0..n {
            c[i] = c[i] * pow_mod_macro!(n as i64, m - 2, m) % m;
        }
        c
    }};
}

macro_rules! ntt_macro {
    ($n:expr, $v:expr, $root:expr, $depth:expr) => {{
        let m = 998244353;
        if $n == 1 {
            $v.to_vec()
        } else {
            let mut even = vec![];
            let mut odd = vec![];
            for i in 0..$n {
                if i % 2 == 0 {
                    even.push($v[i]);
                } else {
                    odd.push($v[i]);
                }
            }
            let fft_even = ntt_macro!($n / 2, &even, &$root, $depth + 1);
            let fft_odd = ntt_macro!($n / 2, &odd, &$root, $depth + 1);

            let mut now = 1;

            let mut b = vec![0; $n];
            for i in 0..$n {
                if i < $n / 2 {
                    b[i] = (fft_even[i] + now * fft_odd[i] % m) % m;
                    now = now * $root[$depth] % m;
                } else {
                    b[i] = (fft_even[i - $n / 2] + now * fft_odd[i - $n / 2] % m) % m;
                    now = now * $root[$depth] % m;
                }
            }
            b
        }
    }};
}

macro_rules! pow_mod_macro {
    ($a:expr, $b:expr, $m:expr) => {{
        let mut a = $a;
        let mut b = $b;
        let mut res: i64 = 1;
        while b > 0 {
            if b & 1 == 1 {
                res = res * a % $m;
            }
            a = a * a % $m;
            b >>= 1;
        }
        res
    }};
}

// Z algorithm
macro_rules! z_algorithm {
    ($s:expr) => {{
        let bytes = $s.as_bytes();
        let length = bytes.len();
        let mut z = vec![0; length];
        z[0] = length;

        let mut l = 0;
        let mut r = 0;
        for i in 1..length {
            if i > r {
                l = i;
                r = i;
                while r < length && bytes[r - l] == bytes[r] {
                    r += 1;
                }
                z[i] = r - l;
                r -= 1;
            } else {
                let k = i - l;
                if z[k] < r - i + 1 {
                    z[i] = z[k];
                } else {
                    l = i;
                    while r < length && bytes[r - l] == bytes[r] {
                        r += 1;
                    }
                    z[i] = r - l;
                    r -= 1;
                }
            }
        }

        z
    }};
}

// fenwick tree (usize)
pub struct FenwickTree {
    n: usize,
    data: Vec<usize>,
}

impl FenwickTree {
    pub fn new(n: usize) -> FenwickTree {
        FenwickTree {
            n: n,
            data: vec![0; n + 1],
        }
    }

    pub fn add(&mut self, i: usize, x: usize) {
        let mut i = i as i32;
        while i <= self.n as i32 {
            self.data[i as usize] += x;
            i += i & -i;
        }
    }

    pub fn sum(&self, i: usize) -> usize {
        let mut i = i as i32;
        let mut res = 0;
        while i > 0 {
            res += self.data[i as usize];
            i -= i & -i;
        }
        res
    }
}

// DSU (Disjoint Set Union)
pub struct DSU {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl DSU {
    pub fn new(n: usize) -> DSU {
        let mut parent = vec![0; n];
        for i in 0..n {
            parent[i] = i;
        }
        DSU {
            parent: parent,
            rank: vec![0; n],
        }
    }

    pub fn root(&mut self, x: usize) -> usize {
        if self.parent[x] == x {
            x
        } else {
            let parent = self.parent[x];
            let root = self.root(parent);
            self.parent[x] = root;
            root
        }
    }

    pub fn same(&mut self, x: usize, y: usize) -> bool {
        self.root(x) == self.root(y)
    }

    pub fn unite(&mut self, x: usize, y: usize) {
        let x = self.root(x);
        let y = self.root(y);
        if x == y {
            return;
        }
        if self.rank[x] < self.rank[y] {
            self.parent[x] = y;
        } else {
            self.parent[y] = x;
            if self.rank[x] == self.rank[y] {
                self.rank[x] += 1;
            }
        }
    }
}

fn power(a: i64, b: i64, modulo: i64) -> i64 {
    let mut power = a;
    let mut remain = 1_i64;
    for i in 0..30 {
        if b & (1_i64 << i) > 0 {
            remain *= power;
            remain %= modulo;
        }
        power *= power % modulo;
        power %= modulo;
    }
    remain
}

fn factorial(a: i64, modulo: i64) -> i64 {
    let mut remain: i64 = 1_i64;
    for i in 2..=a {
        remain *= i % modulo;
        remain %= modulo;
    }
    remain
}

// 最大マッチング
fn maximum_matching(graph: &Vec<Vec<usize>>) -> usize {
    let n = graph.len();
    let mut match_to = vec![None; n]; // マッチング先を格納する配列
    let mut res = 0;

    for i in 0..n {
        let mut visited = vec![false; n];
        if dfs_maximum_matching(graph, i, &mut visited, &mut match_to) {
            res += 1;
        }
    }

    res
}

fn dfs_maximum_matching(graph: &Vec<Vec<usize>>, node: usize, visited: &mut Vec<bool>, match_to: &mut Vec<Option<usize>>) -> bool {
    if visited[node] {
        return false;
    }
    visited[node] = true;

    for &next_node in &graph[node] {
        if match_to[next_node].is_none() || dfs_maximum_matching(graph, match_to[next_node].unwrap(), visited, match_to) {
            match_to[next_node] = Some(node);
            return true;
        }
    }

    false
}

// 最大マッチング
fn maximum_matching_bipartite(graph: &Vec<Vec<usize>>) -> usize {
    let n = graph.len();
    let m = graph[0].len();
    let mut match_to = vec![None; m]; // マッチング先を格納する配列
    let mut res = 0;

    for i in 0..n {
        let mut visited = vec![false; n];
        if dfs_maximum_matching_bipartite(graph, i, &mut visited, &mut match_to) {
            res += 1;
        }
    }

    res
}

fn dfs_maximum_matching_bipartite(graph: &Vec<Vec<usize>>, node: usize, visited: &mut Vec<bool>, match_to: &mut Vec<Option<usize>>) -> bool {
    if visited[node] {
        return false;
    }
    visited[node] = true;

    for &next_node in &graph[node] {
        if match_to[next_node].is_none() || dfs_maximum_matching_bipartite(graph, match_to[next_node].unwrap(), visited, match_to) {
            match_to[next_node] = Some(node);
            return true;
        }
    }

    false
}

fn sqrt(n: isize) -> fsize {
    (n as f64).sqrt()
}

fn main() {
    let n = read!(isize);
    let mut sum = 0.0;
    for i in 0..n {
        let x = read!(isize);
        sum += sqrt(x);
        println!("{}", sum);
    }
}