#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(unused_variables)]
#![allow(unused_mut)]
#![allow(non_snake_case)]
// use proconio::input;
// use proconio::marker::{Chars, Isize1, Usize1, Bytes};
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque, BinaryHeap};
use std::f64::consts::PI;
use std::io::{Read, Write};
use std::mem::swap;
use std::ops::Bound::{Excluded, Included, Unbounded};
use std::cmp::Reverse;
//----------------------------------------------------------------------------
fn read<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
fn readvec<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}
//----------------------------------------------------------------------------
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
//----------------------------------------------------------------------------
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),+))
    }};
}
//----------------------------------------------------------------------------
#[derive(Debug, PartialEq, PartialOrd)]
struct FloatCmp(f64);

impl Eq for FloatCmp {}

impl Ord for FloatCmp {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.0.partial_cmp(&self.0).unwrap()
    }
}
//----------------------------------------------------------------------------
// const MOD: i64 = 998_244_353; // 998244353
const MOD: i64 = 1_000_000_007; // 10**9 + 7

#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Mint {
    val: i64,
}

impl Mint {
    pub fn new(n: i64) -> Self {
        let mut new_val = n % MOD + MOD;
        if new_val >= MOD {
            new_val -= MOD;
        }
        Self { val: new_val }
    }

    pub fn pow(&self, n: i64) -> Self {
        if n == 0 {
            Self { val: 1 }
        } else {
            let mut ret = self.pow(n >> 1);
            ret *= ret;
            if (n & 1) != 0 {
                ret *= *self;
            }
            ret
        }
    }

    pub fn inv(&self) -> Self {
        self.pow(MOD - 2)
    }
}

impl std::fmt::Display for Mint {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.val)
    }
}

impl std::fmt::Debug for Mint {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.val)
    }
}

impl std::ops::Add for Mint {
    type Output = Self;
    fn add(self, other: Self) -> Self::Output {
        let mut new_val = self.val + other.val;
        if new_val >= MOD {
            new_val -= MOD;
        }
        Self { val: new_val }
    }
}

impl std::ops::Sub for Mint {
    type Output = Self;
    fn sub(self, other: Self) -> Self::Output {
        let mut new_val = self.val + MOD - other.val;
        if new_val >= MOD {
            new_val -= MOD;
        }
        Self { val: new_val }
    }
}

impl std::ops::Mul for Mint {
    type Output = Self;
    fn mul(self, other: Self) -> Self::Output {
        Self {
            val: (self.val * other.val) % MOD,
        }
    }
}

impl std::ops::Div for Mint {
    type Output = Self;
    fn div(self, other: Self) -> Self::Output {
        if other.val == 0 {
            panic!("0 division occured.");
        }
        self * other.inv()
    }
}

impl std::ops::AddAssign for Mint {
    fn add_assign(&mut self, other: Self) {
        *self = *self + other;
    }
}

impl std::ops::SubAssign for Mint {
    fn sub_assign(&mut self, other: Self) {
        *self = *self - other;
    }
}

impl std::ops::MulAssign for Mint {
    fn mul_assign(&mut self, other: Self) {
        *self = *self * other;
    }
}

impl std::ops::DivAssign for Mint {
    fn div_assign(&mut self, other: Self) {
        *self = *self / other;
    }
}
//----------------------------------------------------------------------------
pub struct MintComb {
    fact: Vec<Mint>,
    ifact: Vec<Mint>,
}

impl MintComb {
    pub fn new(n: usize) -> Self {
        let mut obj = Self {
            fact: vec![Mint::new(1); n + 1],
            ifact: vec![Mint::new(1); n + 1],
        };
        assert!(n < (MOD as usize));
        obj.fact[0] = Mint::new(1);
        for i in 1..=n {
            obj.fact[i] = obj.fact[i - 1] * Mint::new(i as i64);
        }
        obj.ifact[n] = obj.fact[n].inv();
        for i in (1..=n).rev() {
            obj.ifact[i - 1] = obj.ifact[i] * Mint::new(i as i64);
        }
        obj
    }
    pub fn permutation(&self, n: usize, k: usize) -> Mint {
        if n < k {
            Mint::new(0)
        } else {
            self.fact[n] * self.ifact[n - k]
        }
    }
    pub fn combination(&self, n: usize, k: usize) -> Mint {
        if n < k {
            Mint::new(0)
        } else {
            self.fact[n] * self.ifact[k as usize] * self.ifact[n - k]
        }
    }
}
//----------------------------------------------------------------------------
// 有理数（分数）
#[derive(PartialEq, Debug, Copy, Clone, Eq, PartialOrd, Ord)]
struct Ratio {
    numerator: i64,   // 分子
    denominator: i64, // 分母
}

// ユークリッドの互除法
fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

impl std::fmt::Display for Ratio {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        if self.denominator == 1 {
            write!(f, "{}", self.numerator)
        } else {
            write!(f, "{}/{}", self.numerator, self.denominator)
        }
    }
}

impl Ratio {
    fn new(p: i64, q: i64) -> Ratio {
        if q == 0 {
            panic!("Ratio: divide by zero");
        }
        let g = gcd(p.abs(), q.abs());
        let s = if q < 0 { -1 } else { 1 };
        Ratio {
            numerator: s * p / g,
            denominator: s * q / g,
        }
    }

    fn from_integer(n: i64) -> Ratio {
        Ratio {
            numerator: n,
            denominator: 1,
        }
    }

    fn as_int(&self) -> i64 {
        self.numerator / self.denominator
    }
    fn as_float(&self) -> f64 {
        self.numerator as f64 / self.denominator as f64
    }

    fn numer(&self) -> i64 {
        self.numerator
    }
    fn denom(&self) -> i64 {
        self.denominator
    }

    fn is_integer(&self) -> bool {
        self.denominator == 1
    }
}

impl std::ops::Add for Ratio {
    type Output = Ratio;
    fn add(self, other: Ratio) -> Ratio {
        let p = self.numerator * other.denominator + other.numerator * self.denominator;
        let q = self.denominator * other.denominator;
        Ratio::new(p, q)
    }
}

impl std::ops::Sub for Ratio {
    type Output = Ratio;
    fn sub(self, other: Ratio) -> Ratio {
        let p = self.numerator * other.denominator - other.numerator * self.denominator;
        let q = self.denominator * other.denominator;
        Ratio::new(p, q)
    }
}

impl std::ops::Mul for Ratio {
    type Output = Ratio;
    fn mul(self, other: Ratio) -> Ratio {
        let p = self.numerator * other.numerator;
        let q = self.denominator * other.denominator;
        Ratio::new(p, q)
    }
}

impl std::ops::Div for Ratio {
    type Output = Ratio;
    fn div(self, other: Ratio) -> Ratio {
        let p = self.numerator * other.denominator;
        let q = self.denominator * other.numerator;
        Ratio::new(p, q)
    }
}
//----------------------------------------------------------------------------
pub trait BinarySearch<T> {
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}

impl<T: Ord> BinarySearch<T> for [T] {
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                std::cmp::Ordering::Less => {
                    low = mid + 1;
                }
                std::cmp::Ordering::Equal | std::cmp::Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                std::cmp::Ordering::Less | std::cmp::Ordering::Equal => {
                    low = mid + 1;
                }
                std::cmp::Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}
//----------------------------------------------------------------------------
pub trait LexicalPermutation {
    /// Return `true` if the slice was permuted, `false` if it is already
    /// at the last ordered permutation.
    fn next_permutation(&mut self) -> bool;
    /// Return `true` if the slice was permuted, `false` if it is already
    /// at the first ordered permutation.
    fn prev_permutation(&mut self) -> bool;
}

impl<T> LexicalPermutation for [T]
where
    T: Ord,
{
    /// Original author in Rust: Thomas Backman <serenity@exscape.org>
    fn next_permutation(&mut self) -> bool {
        // These cases only have 1 permutation each, so we can't do anything.
        if self.len() < 2 {
            return false;
        }

        // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
        let mut i = self.len() - 1;
        while i > 0 && self[i - 1] >= self[i] {
            i -= 1;
        }

        // If that is the entire vector, this is the last-ordered permutation.
        if i == 0 {
            return false;
        }

        // Step 2: Find the rightmost element larger than the pivot (i-1)
        let mut j = self.len() - 1;
        while j >= i && self[j] <= self[i - 1] {
            j -= 1;
        }

        // Step 3: Swap that element with the pivot
        self.swap(j, i - 1);

        // Step 4: Reverse the (previously) weakly decreasing part
        self[i..].reverse();

        true
    }

    fn prev_permutation(&mut self) -> bool {
        // These cases only have 1 permutation each, so we can't do anything.
        if self.len() < 2 {
            return false;
        }

        // Step 1: Identify the longest, rightmost weakly increasing part of the vector
        let mut i = self.len() - 1;
        while i > 0 && self[i - 1] <= self[i] {
            i -= 1;
        }

        // If that is the entire vector, this is the first-ordered permutation.
        if i == 0 {
            return false;
        }

        // Step 2: Reverse the weakly increasing part
        self[i..].reverse();

        // Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
        let mut j = self.len() - 1;
        while j >= i && self[j - 1] < self[i - 1] {
            j -= 1;
        }

        // Step 4: Swap that element with the pivot
        self.swap(i - 1, j);

        true
    }
}
//----------------------------------------------------------------------------
// Binary Indexed Tree（BIT, Fenwick Tree）
#[derive(Clone)]
struct FenwickTree {
    n: usize,
    data: Vec<i64>,
}
impl FenwickTree {
    fn new(n: usize) -> FenwickTree {
        FenwickTree {
            n: n,
            data: vec![0; n + 1],
        }
    }
    // --- sum ---
    fn add(&mut self, i: usize, x: i64) {
        let mut i = i + 1;
        while i <= self.n {
            self.data[i] += x;
            i += i & i.wrapping_neg();
        }
    }
    fn sum(&self, i: usize) -> i64 {
        let mut i = i + 1;
        let mut s = 0;
        while i > 0 {
            s += self.data[i];
            i -= i & i.wrapping_neg();
        }
        s
    }
    // --- max ---
    fn update(&mut self, i: usize, x: i64) {
        let mut i = i + 1;
        while i <= self.n {
            self.data[i] = self.data[i].max(x);
            i += i & i.wrapping_neg();
        }
    }
    fn max(&self, i: usize) -> i64 {
        let mut i = i + 1;
        let mut s = 0;
        while i > 0 {
            s = s.max(self.data[i]);
            i -= i & i.wrapping_neg();
        }
        s
    }
}
//----------------------------------------------------------------------------
// multiset
#[derive(Clone, Debug)]
struct MultiSet<T> {
    map: BTreeMap<T, usize>,
    len: usize,
}

struct MultiSetIterator<'a, T> {
    iter: std::collections::btree_map::Iter<'a, T, usize>,
    remaining: usize,
    current: Option<&'a T>,
}

impl<'a, T: Ord> Iterator for MultiSetIterator<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining > 0 {
            self.remaining -= 1;
            self.current
        } else {
            let (key, count) = self.iter.next()?;
            self.current = Some(key);
            self.remaining = count - 1;
            self.current
        }
    }
}

impl<'a, T: Ord> DoubleEndedIterator for MultiSetIterator<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.remaining > 0 {
            self.remaining -= 1;
            self.current
        } else {
            let (key, count) = self.iter.next_back()?;
            self.current = Some(key);
            self.remaining = count - 1;
            self.current
        }
    }
}

impl<T: Ord + Clone> MultiSet<T> {
    fn new() -> MultiSet<T> {
        MultiSet {
            map: BTreeMap::new(),
            len: 0,
        }
    }

    fn insert(&mut self, value: T) {
        *self.map.entry(value.clone()).or_insert(0) += 1;
        self.len += 1;
    }

    fn remove(&mut self, value: &T) -> bool {
        if let Some(count) = self.map.get_mut(value) {
            if *count > 1 {
                *count -= 1;
            } else {
                self.map.remove(value);
            }
            self.len -= 1;
            true
        } else {
            false
        }
    }

    fn contains(&self, value: &T) -> bool {
        self.map.contains_key(value)
    }

    fn count(&self, value: &T) -> usize {
        *self.map.get(value).unwrap_or(&0)
    }

    fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    fn len(&self) -> usize {
        self.len
    }

    fn iter(&self) -> MultiSetIterator<'_, T> {
        MultiSetIterator {
            iter: self.map.iter(),
            remaining: 0,
            current: None,
        }
    }

    fn pop_front(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let value = self.front().unwrap().clone();
        self.remove(&value);
        Some(value)
    }

    fn front(&self) -> Option<&T> {
        self.map.iter().next().map(|(key, _)| key)
    }

    fn pop_back(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let value = self.back().unwrap().clone();
        self.remove(&value);
        Some(value)
    }

    fn back(&self) -> Option<&T> {
        self.map.iter().next_back().map(|(key, _)| key)
    }
}
//----------------------------------------------------------------------------
// 区間Set
#[derive(Clone, Debug)]
struct IntervalSet {
    st: std::collections::BTreeSet<(i64, i64)>,
}
impl IntervalSet {
    fn new() -> Self {
        Self {
            st: std::collections::BTreeSet::new(),
        }
    }
    // Add [l, r)
    fn add(&mut self, kukan: (i64, i64)) {
        let mut kukan = kukan;
        loop {
            let mut rng = self.st.range(kukan..);
            if let Some(it) = rng.next() {
                if it.0 <= kukan.1 {
                    kukan.1 = kukan.1.max(it.1);
                    let it = it.clone();
                    self.st.remove(&it);
                } else {
                    break;
                }
            } else {
                break;
            }
        }
        loop {
            let mut rng = self.st.range(..kukan);
            if let Some(it) = rng.next_back() {
                if kukan.0 <= it.1 {
                    kukan.0 = kukan.0.min(it.0);
                    kukan.1 = kukan.1.max(it.1);
                    let it = it.clone();
                    self.st.remove(&it);
                } else {
                    break;
                }
            } else {
                break;
            }
        }
        self.st.insert(kukan);
    }
}
//----------------------------------------------------------------------------
struct LazySegmentTree {
    n: usize,
    val: Vec<i64>,
    lazy: Vec<i64>,
}
impl LazySegmentTree {
    pub fn new(n: usize) -> Self {
        let mut m = 1;
        while m < n {
            m *= 2;
        }
        Self {
            n: m,
            val: vec![0; 2 * m],
            lazy: vec![0; 2 * m],
        }
    }
    // k 番目のノードの値を直接 x に更新する
    pub fn update_val(&mut self, k: usize, x: i64) {
        self.val[self.n + k] = x;
    }
    // 配列の値を元にセグメント木を構築する
    pub fn initialize(&mut self) {
        for k in (1..self.n).rev() {
            self.val[k] = self.val[2 * k] + self.val[2 * k + 1];
        }
    }
    // k 番目のノードについて遅延評価を行う
    pub fn eval(&mut self, k: usize, l: usize, r: usize) {
        // 遅延配列が空でない場合、自ノード及び子ノードへの
        // 値の伝播が起こる
        //@> self.lazy[k] %= (r as i64 - l as i64) * 2;
        if self.lazy[k] != 0 {
            self.val[k] += self.lazy[k];
            //@> self.val[k] = self.lazy[k] - self.val[k];

            // 最下段かどうかのチェックをしよう
            // 子ノードは親ノードの 1/2 の範囲であるため、
            // 伝播させるときは半分にする
            if r - l > 1 {
                self.lazy[2 * k] += self.lazy[k] / 2;
                self.lazy[2 * k + 1] += self.lazy[k] / 2;
            }

            // 伝播が終わったので、自ノードの遅延配列を空にする
            self.lazy[k] = 0;
        }
    }
    // 区間 [a, b) に x を加算する
    pub fn add(&mut self, a: usize, b: usize, x: i64) {
        self.add_sub(a, b, x, 1, 0, self.n);
    }
    pub fn add_sub(&mut self, a: usize, b: usize, x: i64, k: usize, l: usize, r: usize) {
        // k 番目のノードに対して遅延評価を行う
        self.eval(k, l, r);

        // 範囲外なら何もしない
        if r <= a || b <= l {
            return;
        }

        // 完全に被覆しているならば、遅延配列に値を入れた後に評価
        if a <= l && r <= b {
            self.lazy[k] += (r as i64 - l as i64) * x;
            self.eval(k, l, r);
        }
        // そうでないならば、子ノードの値を再帰的に計算して、
        // 計算済みの値をもらってくる
        else {
            self.add_sub(a, b, x, 2 * k, l, (l + r) / 2);
            self.add_sub(a, b, x, 2 * k + 1, (l + r) / 2, r);
            self.val[k] = self.val[2 * k] + self.val[2 * k + 1];
        }
    }
    // 区間 [a, b) の総和を求める
    pub fn getsum(&mut self, a: usize, b: usize) -> i64 {
        self.getsum_sub(a, b, 1, 0, self.n)
    }
    pub fn getsum_sub(&mut self, a: usize, b: usize, k: usize, l: usize, r: usize) -> i64 {
        if r <= a || b <= l {
            return 0;
        }
        // 関数が呼び出されたら評価！
        self.eval(k, l, r);
        if a <= l && r <= b {
            return self.val[k];
        }
        let vl = self.getsum_sub(a, b, 2 * k, l, (l + r) / 2);
        let vr = self.getsum_sub(a, b, 2 * k + 1, (l + r) / 2, r);
        vl + vr
    }
}
//----------------------------------------------------------------------------
// トポロジカルソート
fn tsort_dfs(n: usize, to: &Vec<Vec<usize>>, visited: &mut Vec<u8>, result: &mut Vec<usize>) -> bool {
    if visited[n] == 1 { // 一時的の印がついている
        // 閉路がある
        return false;
    }
    else if visited[n] == 0 { // まだ印がついていない
        visited[n] = 1;
        for &t in &to[n] {
            if !tsort_dfs(t, to, visited, result) {
                return false;
            }
        }
        visited[n] = 2;
        result.push(n);
    }
    true
}
fn tsort(n: usize, to: &Vec<Vec<usize>>) -> Vec<usize> {
    let mut visited = vec![0u8; n];
    let mut result = vec![];
    for i in 0..n {
        if !tsort_dfs(i, to, &mut visited, &mut result) {
            return vec![];
        }
    }
    result.reverse();
    result
}
//----------------------------------------------------------------------------
#[derive(Clone)]
struct UnionFind {
    n: usize,
    parent: Vec<i64>,
}
impl UnionFind {
    fn new(n: usize) -> Self {
        Self {
            n,
            parent: vec![-1; n + 1],
        }
    }
    fn root(&mut self, a: usize) -> usize {
        if self.parent[a] < 0 {
            return a;
        }
        self.parent[a] = self.root(self.parent[a] as usize) as i64;
        return self.parent[a] as usize;
    }
    fn size(&mut self, a: usize) -> usize {
        let r = self.root(a);
        return -self.parent[r] as usize;
    }
    fn connect(&mut self, a: usize, b: usize) -> bool {
        let a = self.root(a);
        let b = self.root(b);
        if a == b {
            return false;
        }
        if self.size(a) > self.size(b) {
            self.parent[a] += self.parent[b];
            self.parent[b] = a as i64;
        } else {
            self.parent[b] += self.parent[a];
            self.parent[a] = b as i64;
        }
        return true;
    }
    fn same(&mut self, a: usize, b: usize) -> bool {
        return self.root(a) == self.root(b);
    }
}
//----------------------------------------------------------------------------
// Z algorithm
fn z_algorithm(s: &[u8]) -> Vec<usize> {
    let slen = s.len();
    let mut z = vec![0; slen];
    z[0] = slen;
    let mut i = 1;
    let mut j = 0;
    while i < slen {
        while i + j < slen && s[j] == s[i + j] {
            j += 1;
        }
        z[i] = j;
        if j == 0 {
            i += 1;
            continue;
        }
        let mut k = 1;
        while k < j && k + z[k] < j {
            z[i + k] = z[k];
            k += 1;
        }
        i += k;
        j -= k;
    }
    z
}
//----------------------------------------------------------------------------
macro_rules! printvec {
    ($vec:expr) => {{
        print!(
            "{}",
            $vec.iter()
                .map(|&x| x.to_string())
                .collect::<Vec<_>>()
                .join(" ")
        );
    }};
}
macro_rules! printvecln {
    ($vec:expr) => {{
        printvec!($vec);
        println!();
    }};
}
//----------------------------------------------------------------------------
const INF: i64 = 2222222222222222222;
//----------------------------------------------------------------------------
fn main() {
    // let T: usize = read();
    let T = 1;
    for _ in 0..T {
        solve();
    }
}
fn solve() {
    let N: usize = read();
    let M: usize = read();
    let A: Vec<i64> = readvec(M);
    let mut ans = vec![];
    for i in 2..=N {
        let mut bit = FenwickTree::new(N+1);
        for j in 0..M {
            if A[j] < i as i64 {
                let max0 = bit.max(i - A[j] as usize - 1);
                let max1 = bit.max(i - A[j] as usize);
                if max0 + 1 > max1 {
                    bit.update(i - A[j] as usize, max0 + 1);
                }
            }
        }
        ans.push(i as i64 - 1 - bit.max(i) as i64);
    }
    printvecln!(ans);
}