import static java.lang.Math.*;
import static java.util.Arrays.*;

import java.io.*;
import java.lang.reflect.*;
import java.util.*;
import java.util.ArrayList;
import java.util.concurrent.*;
import java.util.function.*;

public final class Main{
  public static void main(String[] args) throws Exception{
    MyReader in = new MyReader(System.in);
    MyWriter out = new MyWriter(System.out,false),log = new MyWriter(System.err,true);
    int T = Solver.multi ? in.it() : 1;
    while (T-- > 0)
      Optional.ofNullable(new Solver(in,out,log).solve()).ifPresent(out::println);
    out.flush();
  }
}

class Solver extends BaseSolver{
  public Solver(MyReader in,MyWriter out,MyWriter log){ super(in,out,log); }

  public static boolean multi = false;

  public Object solve(){
    int N = in.it();
    int[] H = in.it(N);

    RangeSet rs = new RangeSet();

    for (int i = 0;i < N;i++) {
      if (i %2 == 0)
        rs.add(0,H[i]);
      else
        rs.remove(0,H[i]);
      out.println(rs.size());
    }
    return null;
  }

  char[][] trans(char[]... T){
    char[][] ret = new char[T[0].length][T.length];
    for (int i = 0;i < T.length;i++)
      for (int j = 0;j < T[0].length;j++)
        ret[j][i] = T[i][j];

    return ret;
  }

  int max(int... arr){
    int ret = -infI;
    for (var a:arr)
      ret = Math.max(ret,a);
    return ret;
  }

  long min(long... arr){
    long ret = infL;
    for (var a:arr)
      ret = Math.min(ret,a);
    return ret;
  }

  long max(long... arr){
    long ret = -infL;
    for (var a:arr)
      ret = Math.max(ret,a);
    return ret;
  }

  void reverse(Object arr){
    if (!arr.getClass().isArray())
      throw new UnsupportedOperationException("reverse");

    int l = 0;
    int r = Array.getLength(arr) -1;

    while (l < r) {
      Object t = Array.get(arr,l);
      Array.set(arr,l,Array.get(arr,r));
      Array.set(arr,r,t);
      l++;
      r--;
    }

  }
}

class Data extends BaseV{
  long v;

  public Data(long v){ this.v = v; }
}

class SCC extends Graph<Object>{
  private Graph<?> g;
  private MyList<MyList<Integer>> scc;
  private int counter;
  private int[] label;
  private boolean[] seen;

  public SCC(Graph<?> g){
    super(g.n,true);
    this.g = g;
    scc = new MyList<>();
    counter = n;
    label = new int[n];
    seen = new boolean[n];

    for (int i = 0;i < n;i++)
      dfs(i);

    seen = new boolean[n];

    for (var t:label) {
      if (seen[t])
        continue;
      MyList<Integer> list = new MyList<>();
      dfs2(list,t);
      scc.add(list);
    }

    int[] map = new int[n];
    for (int i = 0;i < scc.size();i++)
      for (var j:scc.get(i))
        map[j] = i;

    Set<Long> set = new HashSet<>();
    for (var e:g.es) {
      var u = map[e.u];
      var v = map[e.v];
      if (u != v && set.add((long) u <<30 |v))
        addEdge(u,v);
    }

    n = scc.size();
  }

  private void dfs(final int i){
    if (seen[i])
      return;

    seen[i] = true;
    for (var e:g.go(i))
      dfs(e.v);

    label[--counter] = i;
  }

  private void dfs2(MyList<Integer> set,int i){
    if (seen[i])
      return;

    set.add(i);
    seen[i] = true;
    for (var e:g.bk(i))
      dfs2(set,e.v);
  }

  public MyList<Integer> us(int u){ return scc.get(u); }
}

class RangeSet{
  private long sz;
  private TreeSet<long[]> set;

  public RangeSet(){
    set = new TreeSet<>(Comparator.comparing(t -> t[0]));
    long inf = Solver.infL;
    set.add(new long[]{-inf, -inf});
    set.add(new long[]{inf, inf});
  }

  public long size(){ return sz; }

  public long add(long x){ return add(x,x +1); }

  public long add(long l,long r){
    long ret = r -l;
    long[] t = {l, r};
    for (var s = set.floor(t);t[0] <= s[1];s = set.floor(t))
      ret -= add(t,s);
    for (var s = set.ceiling(t);s[0] <= t[1];s = set.ceiling(t))
      ret -= add(t,s);
    sz += ret;
    set.add(t);
    return ret;
  }

  public long remove(long x){ return remove(x,x +1); }

  public long remove(long l,long r){
    long ret = 0;
    long[] t = {l, r};
    for (var s = set.floor(t);l < s[1];s = set.floor(t))
      ret += remove(t,s);
    for (var s = set.ceiling(t);s[0] < r;s = set.ceiling(t))
      ret += remove(t,s);
    sz -= ret;
    return ret;
  }

  private long add(long[] t,long[] s){
    long ret = min(t[1],s[1]) -max(t[0],s[0]);
    set.remove(s);
    t[0] = min(t[0],s[0]);
    t[1] = max(t[1],s[1]);
    return ret;
  }

  private long remove(long[] t,long[] s){
    set.remove(s);
    long ret = min(t[1],s[1]) -max(t[0],s[0]);
    if (s[0] < t[0])
      set.add(new long[]{s[0], t[0]});
    if (t[1] < s[1])
      set.add(new long[]{t[1], s[1]});
    return ret;
  }

  public long[] get(long x){
    long[] ret = set.floor(new long[]{x});
    return x < ret[1] ? ret : null;
  }

  public long mex(){
    var t = get(0);
    return t == null ? 0 : t[1];
  }

  @Override
  public String toString(){
    List<String> list = new ArrayList<>();
    for (var s:set)
      list.add(Arrays.toString(s));
    return list.toString();
  }
}

class Permutation{
  private int n;
  int[] arr;

  public Permutation(int n){ arr = Util.arrI(this.n = n,i -> i); }

  public Permutation(int[] arr){ this.arr = copyOf(arr,n = arr.length); }

  public boolean increment(){ return crement(1); }

  public boolean decrement(){ return crement(-1); }

  private boolean crement(int d){
    int l = n -2;
    while (0 <= l && arr[l] *d >= arr[l +1] *d)
      l--;

    if (l < 0)
      return false;

    int r = n -1;
    while (arr[l] *d >= arr[r] *d)
      r--;
    swap(l,r);

    l++;
    r = n -1;
    while (l < r)
      swap(l++,r--);

    return true;
  }

  private void swap(int l,int r){
    arr[l] ^= arr[r];
    arr[r] ^= arr[l];
    arr[l] ^= arr[r];
  }
}

abstract class SegmentTree<V extends BaseV, F> extends Seg<V, F>{
  public SegmentTree(int n){ super(n); }

  @Override
  protected F comp(F f,F g){ return null; }

  @Override
  public void upd(int i,F f){
    super.upd(i,f);
    up(i,i +1);
  }
}

abstract class Seg<V extends BaseV, F> {
  private int n,log;
  private V[] val;
  private F[] lazy;

  protected Seg(int n){
    this.n = n;
    while (1 <<log <= n)
      log++;
    val = Util.cast(new BaseV[n <<1]);
    lazy = Util.cast(new Object[n]);

    for (int i = -1;++i < n;)
      (val[i +n] = init(i)).sz = 1;
    for (int i = n;--i > 0;merge(i))
      (val[i] = e()).sz = val[i <<1].sz +val[i <<1 |1].sz;
  }

  public void upd(int i,F f){ prop(i +n,f); }

  public void upd(int l,int r,F f){
    for (l += n,r += n;l < r;l >>= 1,r >>= 1) {
      if ((l &1) == 1)
        prop(l++,f);
      if ((r &1) == 1)
        prop(--r,f);
    }
  }

  public V get(int i){ return val[i +n]; }

  public V get(int l,int r){
    V[] ret = Util.cast(new BaseV[]{e(), e()});
    int i = 0;
    for (var v:getList(l,r)) {
      agg(ret[i],ret[i ^1],v);
      ret[i].sz = ret[i ^= 1].sz +v.sz;
    }
    return ret[i ^1];
  }

  public V[] getList(int l,int r){
    int sz = 0;
    for (int li = l += n,ri = r += n;li < ri;li = li +1 >>1,ri >>= 1)
      sz += (li &1) +(ri &1);
    V[] arr = Util.cast(Array.newInstance(e().getClass(),sz));
    for (int i = 0;l < r;l >>= 1,r >>= 1) {
      if ((l &1) > 0)
        arr[i++] = val[l++];
      if ((r &1) > 0)
        arr[--sz] = val[--r];
    }
    return arr;
  }

  public V[] getPath(int i){
    int sz = 32 -Integer.numberOfLeadingZeros(i +n);
    V[] arr = Util.cast(Array.newInstance(e().getClass(),sz));
    for (i += n;0 < i;i >>= 1)
      arr[--sz] = val[i];
    return arr;
  }

  protected V init(int i){ return e(); }

  protected abstract V e();
  protected abstract void agg(V v,V a,V b);
  protected abstract void map(V v,F f);
  protected abstract F comp(F f,F g);

  protected void up(int l,int r){
    for (l = oddPart(l +n),r = oddPart(r +n);l != r;)
      merge(l > r ? (l >>= 1) : (r >>= 1));
    while (1 < l)
      merge(l >>= 1);
  }

  protected void down(int l,int r){
    int i = log;
    for (l = oddPart(l +n),r = oddPart(r +n);i > 0;i--) {
      push(l >>i);
      push(r >>i);
    }
  }

  private void merge(int i){ agg(val[i],val[i <<1],val[i <<1 |1]); }

  private void push(int i){
    if (lazy[i] != null) {
      prop(i <<1,lazy[i]);
      prop(i <<1 |1,lazy[i]);
      lazy[i] = null;
    }
  }

  private void prop(int i,F f){
    map(val[i],f);
    if (i < n) {
      lazy[i] = lazy[i] == null ? f : comp(lazy[i],f);
      if (val[i].fail) {
        push(i);
        merge(i);
      }
    }
  }

  private int oddPart(int i){ return i /(i &-i); }

  public int bSearchllr(int l,Predicate<V> judge){

    V cur = e(),tmp = e();
    down(l,n);
    V[] list = getList(l,n);
    int ri = -1;
    for (var d:list) {
      agg(tmp,cur,d);
      if (judge.test(tmp)) {
        agg(cur,cur,d);
        cur = tmp;
        tmp = e();

      } else {
        ri = (l +cur.sz +n) /d.sz;
        push(ri);
        break;
      }
    }

    if (ri == -1)
      return n;

    ri <<= 1;
    while (ri < val.length) {
      agg(tmp,cur,val[ri]);
      if (judge.test(tmp))
        return l +cur.sz +val[ri].sz;
      else {
        push(ri);
        ri = ri <<1;
      }
    }

    return n;
  }
}

class DualBIT{
  private int n;
  private long[] val;

  public DualBIT(int n){
    this.n = n +1;
    val = new long[n +2];
  }

  public long agg(long a,long b){ return a +b; }

  public long inv(long v){ return -v; }

  public long get(int i){ return sum(i +1); }

  public void upd(int l,int r,long v){
    upd(l,v);
    upd(r,inv(v));
  }

  private void upd(int x,long v){
    for (x++;x <= n;x += x &-x)
      val[x] = agg(val[x],v);
  }

  private long sum(int x){
    long ret = 0;
    for (;x > 0;x -= x &-x)
      ret = agg(ret,val[x]);
    return ret;
  }
}

class Combin{
  int n = 2;
  long[] f,fi;
  long mod = Util.mod;

  public Combin(int n){
    this();
    grow(n);
  }

  public Combin(){ f = fi = new long[]{1, 1}; }

  public void grow(int n){
    n = min((int) mod,n);
    f = copyOf(f,n);
    fi = copyOf(fi,n);
    for (int i = this.n;i < n;i++)
      f[i] = f[i -1] *i %mod;
    fi[n -1] = pow(f[n -1],mod -2);
    for (int i = n;--i > this.n;)
      fi[i -1] = fi[i] *i %mod;
    this.n = n;
  }

  private long pow(long x,long n){
    long ret = 1;
    for (x %= mod;0 < n;x = x *x %mod,n >>= 1)
      if ((n &1) == 1)
        ret = ret *x %mod;
    return ret;
  }

  public long nHr(int n,int r){ return r < 0 ? 0 : nCr(n +r -1,r); }

  public long nCr(int n,int r){
    if (r < 0 || n -r < 0)
      return 0;

    if (this.n <= n)
      grow(max(this.n <<1,n +1));
    return f[n] *(fi[r] *fi[n -r] %mod) %mod;
  }
}

abstract class AVLSegmentTree<V extends BaseV, F> {
  private V e = e();
  private Node root;
  private V[] ret = Util.cast(new BaseV[2]);
  private int ri;

  public AVLSegmentTree(int n){
    this();
    root = new Node(e(),n);
  }

  public AVLSegmentTree(){
    ret[ri] = e();
    ri = 1;
  }

  public void build(int n,IntFunction<V> init){ root = build(0,n,init); }

  private Node build(int l,int r,IntFunction<V> init){
    if (r -l == 1)
      return new Node(init.apply(l),1);
    var ret = new Node(e(),r -l);
    ret.lft = build(l,l +r >>1,init);
    ret.rht = build(l +r >>1,r,init);
    return ret.update();
  }

  public void add(V v){ add(v,1); }

  public void add(V v,int k){ ins(size(),v,k); }

  public void ins(int i,V v){ ins(i,v,1); }

  public void ins(int i,V v,int k){ root = root == null ? new Node(v,k) : ins(root,i,v,k); }

  private Node ins(Node nd,int i,V v,int k){
    if (nd.lft == null && (i == 0 || i == nd.sz))
      split(nd,i == 0 ? 1 : -1,v,k,nd.sz +k);
    else {
      if (nd.lft == null)
        split(nd,1,ag(e(),e,nd.val),i,nd.sz);
      else
        nd.push();
      if (i < nd.lft.sz)
        nd.lft = ins(nd.lft,i,v,k);
      else
        nd.rht = ins(nd.rht,i -nd.lft.sz,v,k);
    }
    return balance(nd);
  }

  public void del(int i){ root = del(root,i); }

  private Node del(Node nd,int i){
    if (nd.lft == null)
      return 0 < --nd.sz ? nd : null;
    nd.push();
    int c = i < nd.lft.sz ? -1 : 1;
    Node del = c < 0 ? del(nd.lft,i) : del(nd.rht,i -nd.lft.sz);
    if (del == null)
      return nd.cld(-c);
    nd.cld(c,del);
    return balance(nd);
  }

  public void upd(int i,F f){ upd(i,i +1,f); }

  public void upd(int l,int r,F f){
    if (size() < r)
      add(e(),r -size());
    root = upd(root,l,r,f);
  }

  private Node upd(Node nd,int l,int r,F f){
    if (l == 0 && r == nd.sz)
      nd.prop(f);
    else if (l < r) {
      if (nd.lft == null)
        split(nd,1,ag(e(),e,nd.val),0 < l ? l : r,nd.sz);
      else
        nd.push();
      if (l < nd.lft.sz)
        nd.lft = upd(nd.lft,l,min(nd.lft.sz,r),f);
      if (nd.lft.sz < r)
        nd.rht = upd(nd.rht,max(0,l -nd.lft.sz),r -nd.lft.sz,f);
      nd = balance(nd);
    }
    return nd;
  }

  public void toggle(int l,int r){ root = l < r ? toggle(root,l,r) : root; }

  private Node toggle(Node nd,int l,int r){
    nd.push();
    if (0 < l) {
      split(nd,l);
      nd = merge(nd.lft,nd,toggle(nd.rht,0,r -l));
    } else if (r < nd.sz) {
      split(nd,r);
      nd = merge(toggle(nd.lft,l,r),nd,nd.rht);
    } else
      nd.toggle();
    return nd;
  }

  private void split(Node nd,int i){
    if (nd.lft == null)
      split(nd,1,ag(e(),e,nd.val),i,nd.sz);
    else {
      nd.push();
      if (i < nd.lft.sz) {
        split(nd.lft,i);
        var lft = nd.lft;
        nd.lft = lft.lft;
        nd.rht = merge(lft.rht,lft,nd.rht);
      } else if (nd.lft.sz < i) {
        split(nd.rht,i -nd.lft.sz);
        var rht = nd.rht;
        nd.rht = rht.rht;
        nd.lft = merge(nd.lft,rht,rht.lft);
      }
    }
  }

  private Node merge(Node lft,Node nd,Node rht){
    if (abs(lft.rnk -rht.rnk) < 2) {
      nd.lft = lft;
      nd.rht = rht;
    } else if (lft.rnk > rht.rnk) {
      lft.push();
      lft.rht = merge(lft.rht,nd,rht);
      nd = lft;
    } else if (lft.rnk < rht.rnk) {
      rht.push();
      rht.lft = merge(lft,nd,rht.lft);
      nd = rht;
    }
    return balance(nd);
  }

  public V get(int i){ return get(root,i); }

  private V get(Node nd,int i){
    if (nd.lft == null)
      return nd.val;
    nd.push();
    return i < nd.lft.sz ? get(nd.lft,i) : get(nd.rht,i -nd.lft.sz);
  }

  public V get(int l,int r){
    ret[ri] = e();
    ri ^= 1;
    if (root != null)
      get(root,l,min(r,size()));
    return ret[ri ^= 1];
  }

  private void get(Node nd,int l,int r){
    if (0 == l && r == nd.sz)
      ag(ret[ri],ret[ri ^= 1],nd.val());
    else if (nd.lft == null)
      ag(ret[ri],ret[ri ^= 1],pw(nd.val,r -l));
    else {
      nd.push();
      if (l < nd.lft.sz)
        get(nd.lft,l,min(nd.lft.sz,r));
      if (nd.lft.sz < r)
        get(nd.rht,max(0,l -nd.lft.sz),r -nd.lft.sz);
    }
  }

  public V all(){ return root == null ? e : root.val(); }

  public int size(){ return root == null ? 0 : root.sz; }

  protected abstract V e();
  protected abstract void agg(V v,V a,V b);
  protected abstract void map(V v,F f);
  protected abstract F comp(F f,F g);
  protected abstract void tog(V v);

  private V ag(V v,V a,V b){
    agg(v,a,b);
    v.sz = a.sz +b.sz;
    return v;
  }

  protected V pow(V a,int n){
    V ret = e();
    for (V t = ag(e(),e,a);0 < n;n >>= 1,t = ag(e(),t,t))
      if (0 < (n &1))
        ret = ag(e(),ret,t);
    return ret;
  }

  private V pw(V a,int n){
    V ret = pow(a,n);
    ret.sz = n;
    return ret;
  }

  private void split(Node nd,int c,V vl,int i,int sz){
    nd.cld(-c,new Node(vl,i));
    nd.cld(c,new Node(nd.val,sz -i));
    nd.val = e();
  }

  private Node balance(Node nd){ return (1 < abs(nd.bis = nd.rht.rnk -nd.lft.rnk) ? (nd = rotate(nd)) : nd).update(); }

  private Node rotate(Node u){
    var v = u.cld(u.bis);
    v.push();
    if (u.bis *v.bis < -1)
      v = rotate(v);
    u.cld(u.bis,v.cld(-u.bis));
    v.cld(-u.bis,u);
    u.update();
    return v;
  }

  private class Node{
    private int sz,bis,rnk,tog;
    private V val;
    private F laz;
    private Node lft,rht;

    private Node(V val,int sz){
      this.sz = sz;
      this.val = val;
      val.sz = 1;
    }

    private Node update(){
      bis = rht.rnk -lft.rnk;
      rnk = max(lft.rnk,rht.rnk) +1;
      ag(val,lft.val(),rht.val());
      sz = val.sz;
      return this;
    }

    private void push(){
      if (laz != null) {
        lft.prop(laz);
        rht.prop(laz);
        laz = null;
      }
      if (0 < tog) {
        lft.toggle();
        rht.toggle();
        tog = 0;
      }
    }

    private void prop(F f){
      map(val,f);
      if (lft != null)
        laz = laz == null ? f : comp(laz,f);
    }

    private Node toggle(){
      bis *= -1;
      var tn = lft;
      lft = rht;
      rht = tn;
      tog(val);
      if (lft != null)
        tog ^= 1;
      return this;
    }

    private Node cld(int c){ return c < 0 ? lft : rht; }

    private void cld(int c,Node nd){ nd = c < 0 ? (lft = nd) : (rht = nd); }

    private V val(){ return lft == null && 1 < sz ? pw(val,sz) : val; }
  }
}

class FunctionalGraph extends Graph<Integer>{
  public boolean[] closed;
  public int[] roots;

  public FunctionalGraph(int n){
    super(n,true);
    closed = new boolean[n];
    roots = new int[n];
  }

  public void build(int[] P){

    int[] cnt = new int[n];
    for (int i = 0;i < n;i++)
      cnt[P[i]]++;

    int[] stk = new int[n];
    int sp = 0;
    for (int i = 0;i < n;i++)
      if (cnt[i] == 0)
        stk[sp++] = i;

    fill(closed,true);
    while (0 < sp) {
      int u = stk[--sp];
      closed[u] = false;
      if (0 < cnt[P[u]] && --cnt[P[u]] == 0)
        stk[sp++] = P[u];
    }

    int[] root = Util.arrI(n,i -> -1);
    int rp = 0;
    for (int i = 0;i < n;i++) {
      if (root[i] != -1 || !closed[i])
        continue;

      int u = i;
      while (root[u] == -1) {
        root[u] = i;
        u = P[u];
      }
      roots[rp++] = i;
    }

    for (int i = 0;i < n;i++)
      if (!closed[i])
        addEdge(closed[P[i]] ? root[P[i]] : P[i],i);

    roots = Arrays.copyOf(roots,rp);
  }

  @Override
  public int size(){ return n >>1; }

  public Graph<Integer> createTree(){
    UnionFind uf = new UnionFind(n);
    for (var e:es)
      uf.unite(e.u,e.v);

    if (uf.num != 1)
      return null;

    Graph<Integer> ret = new Graph<>(n,false);
    for (var e:es)
      if (e.u < e.v)
        ret.addEdge(e.u,e.v);

    return ret;
  }
}

class MinCostFlow extends Dijkstra<long[], Long>{
  private long[] h;

  public MinCostFlow(int n){
    super(n,false);
    h = new long[n];
  }

  @Override
  protected Long zero(){ return 0L; }

  @Override
  protected Long inf(){ return Util.infL; }

  @Override
  protected Long f(Long l,Edge<long[]> e){ return e.val[1] == 0 ? inf() : l +e.val[0] +h[e.u] -h[e.v]; }

  @Override
  protected long[] inv(long[] l){ return new long[]{-l[0], 0}; }

  public void addEdge(int u,int v,long cost,long cap){ addEdge(u,v,new long[]{cost, cap}); }

  public long[] flow(int s,int t,long flow){
    long[] ret = new long[2];
    while (0 < flow) {
      calc(s);
      var path = path(t);
      if (path.isEmpty())
        break;

      long cost = 0;
      long f = flow;
      for (var e:path)
        f = min(f,e.val[1]);
      for (var e:path) {
        cost += e.val[0];
        e.val[1] -= f;
        e.re.val[1] += f;
      }
      flow -= f;
      ret[0] += cost *f;
      ret[1] += f;
      for (int i = 0;i < n;i++)
        h[i] += get(i);
    }
    return ret;
  }
}

class UnionFind{
  int num;
  protected int[] dat;
  protected int[] nxt;

  public UnionFind(int n){
    dat = new int[n];
    nxt = new int[n];
    setAll(nxt,i -> i);
    fill(dat,-1);
    num = n;
  }

  public int root(int x){ return dat[x] < 0 ? x : (dat[x] = root(dat[x])); }

  public boolean same(int u,int v){ return root(u) == root(v); }

  public boolean unite(int u,int v){
    if ((u = root(u)) == (v = root(v)))
      return false;

    if (dat[u] > dat[v]) {
      u ^= v;
      v ^= u;
      u ^= v;
    }
    dat[u] += dat[v];
    dat[v] = u;
    num--;
    nxt[u] ^= nxt[v];
    nxt[v] ^= nxt[u];
    nxt[u] ^= nxt[v];
    return true;
  }

  public int size(int x){ return -dat[root(x)]; }

  public int[] getGroup(int x){
    int[] ret = new int[size(x)];
    for (int i = 0,c = root(x);i < ret.length;i++)
      ret[i] = c = nxt[c];
    return ret;
  }
}

class BIT{
  public int n;
  private long[] bit;

  public BIT(int n){ this(new long[n]); }

  public BIT(long[] A){
    n = A.length;
    bit = new long[n +1];
    for (int i = 1;i <= n;i++) {
      bit[i] += A[i -1];
      if (i +(i &-i) <= n)
        bit[i +(i &-i)] += bit[i];
    }
  }

  public void upd(int x,long v){
    for (x++;x <= n;x += x &-x)
      bit[x] += v;
  }

  public long sum(int x){
    long ret = 0;
    for (;x > 0;x -= x &-x)
      ret += bit[x];
    return ret;
  }

  public long get(int i){ return get(i,i +1); }

  public long get(int l,int r){ return sum(r) -sum(l); }
}

class DynamicUnionFind<K> {
  int num;
  private Map<K, K> par,nxt;
  private Map<K, Integer> size;

  public DynamicUnionFind(){
    par = new HashMap<>();
    nxt = new HashMap<>();
    size = new HashMap<>();
    num = 0;
  }

  public boolean add(K x){
    if (par.containsKey(x))
      return false;
    par.put(x,x);
    nxt.put(x,x);
    size.put(x,1);
    num++;
    return true;
  }

  public K root(K x){
    add(x);

    if (x.equals(par.get(x)))
      return x;

    K r = root(par.get(x));
    par.put(par.get(x),r);
    return r;
  }

  boolean same(K u,K v){ return root(u).equals(root(v)); }

  boolean unite(K u,K v){
    if ((u = root(u)).equals(v = root(v)))
      return false;

    if (size.get(u) < size.get(v)) {
      var t = u;
      u = v;
      v = t;
    }

    par.put(v,u);
    size.merge(u,size.get(v),Integer::sum);
    var nu = nxt.get(u);
    nxt.put(u,nxt.get(v));
    nxt.put(v,nu);

    num--;
    return true;
  }

  int size(K x){ return size.get(root(x)); }

  public K[] getGroup(K x){
    x = root(x);
    K[] ret = Util.cast(Array.newInstance(x.getClass(),size.get(x)));
    for (int i = 0;i < ret.length;i++)
      ret[i] = x = nxt.get(x);
    return ret;
  }
}

class HLD extends Graph<Object>{
  private int[] p,hp,l,r;

  public HLD(int n){
    super(n,false);
    p = new int[n];
    hp = new int[n];
    l = new int[n];
    r = new int[n];
  }

  public MyList<int[]> auxiliary(MyList<Integer> lis){
    lis = new MyList<>(lis);
    lis.add(0);
    MyList<int[]> ret = new MyList<>();
    lis.sort(Comparator.comparing(i -> l[i]));
    for (int i = lis.size() -1;i > 0;i--)
      lis.add(lca(lis.get(i -1),lis.get(i)));
    lis.sort(Comparator.comparing(i -> l[i]));
    MyStack<Integer> stk = new MyStack<>();
    stk.add(lis.get(0));
    for (var y:lis) {
      while (r[stk.peek()] <= l[y])
        stk.pop();
      if (!stk.peek().equals(y))
        ret.add(new int[]{stk.peek(), y});
      stk.add(y);
    }
    return ret;
  }

  public MyList<int[]> getPath(int u,int v,int incLca){
    MyList<int[]> ret = new MyList<>();
    var lst = itr(u,v,(a,b) -> {
      ret.add(new int[]{l[a], l[b] +1});
      return p[a];
    });
    ret.add(new int[]{l[lst[0]] +1 -incLca, l[lst[1]] +1});
    return ret;
  }

  public int lca(int u,int v){ return itr(u,v,(a,b) -> p[a])[0]; }

  private int[] itr(int u,int v,IntBinaryOperator f){
    while (true) {
      if (l[u] > l[v]) {
        var t = u;
        u = v;
        v = t;
      }

      var h = hp[v];
      if (l[h] <= l[u])
        return new int[]{u, v};

      v = f.applyAsInt(h,v);
    }
  }

  public int ei(int e){ return l[es.get(e).v]; }

  public int l(int u){ return l[u]; }

  public int r(int u){ return r[u]; }

  public void makeTree(int s){
    MyStack<Integer> stk = new MyStack<>();
    fill(hp,-1);
    p[s] = s;
    stk.add(s);
    stk.add(s);
    while (!stk.isEmpty()) {
      var u = stk.pop();
      if (r[u] < 1) {
        r[u] = 1;
        for (var e:go(u)) {
          if (e.v == p[u])
            continue;
          es.set(e.id,e);
          p[e.v] = u;
          stk.add(e.v);
          stk.add(e.v);
        }
      } else if (u != s)
        r[p[u]] += r[u];
    }

    for (int u = 0;u < n;u++) {
      var go = go(u);
      for (int i = 1;i < go.size();i++)
        if (r[u] < r[go.get(0).v] || r[go.get(0).v] < r[go.get(i).v] && r[go.get(i).v] < r[u])
          go.swap(0,i);
    }

    stk.add(s);
    for (int hid = 0;!stk.isEmpty();) {
      var u = stk.pop();
      r[u] += l[u] = hid++;
      if (hp[u] < 0)
        hp[u] = u;
      var go = go(u);
      for (int i = go.size();i-- > 0;) {
        var v = go.get(i).v;
        if (v == p[u])
          continue;
        if (i == 0)
          hp[v] = hp[u];
        stk.add(v);
      }
    }
  }
}

abstract class Dijkstra<E, L> extends Graph<E>{
  private Comparator<L> cmp;
  private L[] len;
  private int[] hep,idx;
  private Edge<E>[] pre;
  private int sz;

  public Dijkstra(int n,boolean dir){ this(n,dir,Util.cast(Comparator.naturalOrder())); }

  public Dijkstra(int n,boolean dir,Comparator<L> cmp){
    super(n,dir);
    hep = new int[n];
    idx = new int[n];
    this.cmp = cmp;
  }

  protected abstract L zero();
  protected abstract L inf();
  protected abstract L f(L l,Edge<E> e);

  public L[] calc(int s){ return calc(s,-1); }

  public L[] calc(int s,int g){
    len = Util.arr(Util.cast(Array.newInstance(inf().getClass(),sz = n)),i -> inf());
    pre = Util.cast(new Edge[n]);
    setAll(hep,i -> i);
    setAll(idx,i -> i);
    len[s] = zero();
    heapfy(idx[s]);
    for (int cur;0 < sz && (cur = poll()) != g;)
      for (var e:go(cur))
        move(cur,e);
    return len;
  }

  public L get(int t){ return len[t]; }

  public Deque<Edge<E>> path(int t){
    Deque<Edge<E>> ret = new ArrayDeque<>();
    for (;pre[t] != null;t = pre[t].u)
      ret.addFirst(pre[t]);

    return ret;
  }

  private void move(int cur,Edge<E> e){
    L l = f(len[cur],e);
    if (idx[e.v] < sz && cmp.compare(l,len[e.v]) < 0) {
      len[e.v] = l;
      pre[e.v] = e;
      heapfy(idx[e.v]);
    }
  }

  private int poll(){
    int ret = hep[0];
    heapfy(swap(0,--sz));
    return ret;
  }

  private void heapfy(int k){
    int p = k -1 >>1;
    if (0 <= p && cmp.compare(len[hep[p]],len[hep[k]]) > 0) {
      heapfy(swap(p,k));
      return;
    }

    int c = k <<1 |1;
    if (sz <= c)
      return;

    if (c +1 < sz && cmp.compare(len[hep[c]],len[hep[c +1]]) > 0)
      c++;

    if (cmp.compare(len[hep[c]],len[hep[k]]) < 0)
      heapfy(swap(c,k));
  }

  private int swap(int i,int j){
    hep[i] ^= hep[j];
    hep[j] ^= hep[i];
    hep[i] ^= hep[j];
    idx[hep[i]] = i;
    idx[hep[j]] = j;
    return i;
  }
}

abstract class SparseTable{
  private int n;
  private long[] tbl;

  public SparseTable(int n){
    int K = max(1,32 -Integer.numberOfLeadingZeros(n -1));
    this.n = 1 <<K;

    tbl = new long[K *this.n];
    for (int i = 0;i < this.n;i++)
      tbl[i] = i < n ? init(i) : e();
    for (int k = 1;k < K;k++)
      for (int s = 1 <<k;s < this.n;s += 2 <<k) {
        int b = k *this.n;
        tbl[b +s] = s < n ? init(s) : e();
        tbl[b +s -1] = s < n ? init(s -1) : e();
        for (int i = 1;i < 1 <<k;i++) {
          tbl[b +s +i] = agg(tbl[b +s +i -1],tbl[s +i]);
          tbl[b +s -1 -i] = agg(tbl[b +s -i],tbl[s -1 -i]);
        }
      }
  }

  protected abstract long e();
  protected abstract long init(int i);
  protected abstract long agg(long a,long b);

  public long get(int l,int r){
    r--;
    if (l == r)
      return tbl[l];
    int k = 31 -Integer.numberOfLeadingZeros(l ^r);
    long ret = e();
    ret = agg(tbl[k *n +l],tbl[k *n +r]);
    return ret;
  }
}

class NTT{
  private static long[][] sum = sum();

  public static long[] convolution(long[] a,long[] b,int l){ return convolution(a,0,a.length,b,0,b.length,l); }

  public static long[] convolution(long[] a,long[] b){
    return convolution(a,0,a.length,b,0,b.length,a.length +b.length -1);
  }

  public static long[] convolution(long[] a,int al,int ar,long[] b,int bl,int br,int l){
    return copyOf(convolution(a,al,ar,b,bl,br),l);
  }

  public static long[] convolution(long[] a,int al,int ar,long[] b,int bl,int br){
    int n = ar -al;
    int m = br -bl;
    int z = max(1,Integer.highestOneBit(n +m -2) <<1);
    long[] ta = new long[z];
    long[] tb = new long[z];
    System.arraycopy(a,al,ta,0,ar -al);
    System.arraycopy(b,bl,tb,0,br -bl);
    a = ta;
    b = tb;

    butterfly(a,sum[0]);
    butterfly(b,sum[0]);
    for (int i = 0;i < z;i++)
      a[i] = a[i] *b[i] %998_244_353;
    butterflyInv(a,sum[1]);

    long iz = pow(z,998_244_351);
    for (int i = 0;i < a.length;i++)
      a[i] = a[i] *iz %998_244_353;
    return a;
  }

  private static void butterflyInv(long[] a,long[] sum){
    int n = a.length;
    int h = 32 -Integer.numberOfLeadingZeros(n -1);

    for (int ph = h;ph >= 1;ph--) {
      int w = 1 <<ph -1,p = 1 <<h -ph;
      long now = 1;
      for (int s = 0;s < w;s++) {
        int offset = s <<h -ph +1;
        for (int i = 0;i < p;i++) {
          long l = a[i +offset];
          long r = a[i +offset +p];
          a[i +offset] = (l +r) %998_244_353;
          a[i +offset +p] = (998_244_353 +l -r) *now %998_244_353;
        }
        int x = Integer.numberOfTrailingZeros(~s);
        now = now *sum[x] %998_244_353;
      }
    }
  }

  private static void butterfly(long[] a,long[] sum){
    int n = a.length;
    int h = 32 -Integer.numberOfLeadingZeros(n -1);
    long ADD = 998_244_351L *998_244_353;

    for (int ph = 1;ph <= h;ph++) {
      int w = 1 <<ph -1,p = 1 <<h -ph;
      long now = 1;
      for (int s = 0;s < w;s++) {
        int offset = s <<h -ph +1;
        for (int i = 0;i < p;i++) {
          long l = a[i +offset];
          long r = a[i +offset +p] *now;
          a[i +offset] = (l +r) %998_244_353;
          a[i +offset +p] = (l -r +ADD) %998_244_353;
        }
        int x = Integer.numberOfTrailingZeros(~s);
        now = now *sum[x] %998_244_353;
      }
    }
  }

  private static long[][] sum(){
    long[][] sum = new long[2][21];
    long[] es = new long[22];
    long[] ies = new long[22];
    long e = 15311432;
    long ie = 469870224;
    for (int i = 22;i-- > 0;) {
      es[i] = e;
      ies[i] = ie;
      e = e *e %998_244_353;
      ie = ie *ie %998_244_353;
    }
    long se = 1;
    long sie = 1;
    for (int i = 0;i < 21;i++) {
      sum[0][i] = es[i] *se %998_244_353;
      se = se *ies[i] %998_244_353;
      sum[1][i] = ies[i] *sie %998_244_353;
      sie = sie *es[i] %998_244_353;
    }
    return sum;
  }

  private static long pow(long x,long n){
    x %= 998_244_353;
    long ret = 1;
    do {
      if ((n &1) == 1)
        ret = ret *x %998_244_353;
      x = x *x %998_244_353;
    } while (0 < (n >>= 1));

    return ret;
  }
}

class PrefixSum{
  private long[] sum;
  private int i;

  public PrefixSum(int n){ sum = new long[n +1]; }

  public PrefixSum(long[] a){
    this(a.length);
    for (int i = 0;i < a.length;i++)
      sum[i +1] = sum[i] +a[i];
  }

  public void add(long a){ sum[i +1] = sum[i++] +a; }

  public long get(int l,int r){ return sum[r] -sum[l]; }

  public long get(int i){ return get(i,i +1); }
}

abstract class Trie<V> {
  private int b;
  public Node root;

  public Trie(){ this('z' +1); }

  public Trie(int b){
    this.b = b;
    root = new Node();
  }

  abstract V e();

  public MyList<Node> path(char[] s){
    MyList<Node> q = new MyList<>(s.length +1);
    var nd = root;
    q.add(nd);
    for (char c:s) {
      if (nd.ch[c] == null)
        nd.ch[c] = new Node();
      q.add(nd = nd.ch[c]);
    }
    return q;
  }

  class Node{
    private Node[] ch = Util.cast(Array.newInstance(this.getClass(),b));
    public V v = e();
  }
}

class LowLink extends Graph<Long>{
  private int[] low,ord,inc;

  public LowLink(int n){ super(n,false); }

  public void build(){
    low = new int[n];
    ord = new int[n];
    inc = new int[n];
    fill(ord,-1);
    Iterator<Edge<Long>>[] itr = Util.cast(new Iterator[n]);
    for (int v = 0;v < n;v++)
      itr[v] = go(v).iterator();
    int[] stk = new int[n +2];
    stk[0] = -1;
    for (int root = 0,s = 0,count = 0;root < n;root++) {
      if (ord[root] != -1)
        continue;
      ord[root] = low[root] = count++;
      inc[root]--;
      stk[s = 1] = root;
      while (0 < s) {
        int v = stk[s],p = stk[s -1];
        if (itr[v].hasNext()) {
          int w = itr[v].next().v;
          if (ord[w] == -1) {
            ord[w] = low[w] = count++;
            stk[++s] = w;
          } else if (w != p && low[v] > ord[w])
            low[v] = ord[w];
        } else {
          s--;
          if (p != -1) {
            if (low[p] > low[v])
              low[p] = low[v];
            if (ord[p] <= low[v])
              inc[p]++;
          }
        }
      }
    }
  }

  public boolean isBridge(int x,int y){ return ord[x] < low[y] || ord[y] < low[x]; }

  public boolean isArticulation(int x){ return inc[x] > 0; }

  public int articulationValue(int x){ return inc[x]; }
}

class Edge<L> {
  public int id,u,v;
  public L val;
  public Edge<L> re;

  public Edge(int id,int u,int v,L val){
    this.id = id;
    this.u = u;
    this.v = v;
    this.val = val;
  }
}

class Graph<L> {
  protected int n;
  protected MyList<Edge<L>> es;
  private MyList<Edge<L>>[] go,bk;

  public Graph(int n,boolean dir){
    this.n = n;
    go = Util.cast(new MyList[n]);
    bk = dir ? Util.cast(new MyList[n]) : go;
    for (int i = 0;i < n;i++) {
      go[i] = new MyList<>();
      bk[i] = new MyList<>();
    }
    es = new MyList<>();
  }

  public int size(){ return n; }

  protected L inv(L l){ return l; }

  public void addEdge(int u,int v){ addEdge(u,v,null); }

  public void addEdge(int u,int v,L l){
    var e = new Edge<>(es.size(),u,v,l);
    var re = new Edge<>(e.id,e.v,e.u,inv(e.val));
    es.add(e);
    go[u].add(re.re = e);
    bk[v].add(e.re = re);
  }

  public MyList<Edge<L>> go(int u){ return go[u]; }

  public MyList<Edge<L>> bk(int u){ return bk[u]; }
}

abstract class Sum3D{
  private long[] sum;
  private int w,d;

  public Sum3D(int h,int w,int d){
    this.w = w;
    this.d = d;
    sum = new long[(h +1) *(w +1) *(d +1)];
    for (int i = 0;i < h;i++)
      for (int j = 0;j < w;j++)
        for (int k = 0;k < d;k++)
          sum[top(i +1,j +1,k +1)] = a(i,j,k)
              +sum[top(i,j +1,k +1)] +sum[top(i +1,j,k +1)] +sum[top(i +1,j +1,k)]
              -sum[top(i +1,j,k)] -sum[top(i,j +1,k)] -sum[top(i,j,k +1)]
              +sum[top(i,j,k)];
  }

  abstract long a(int i,int j,int k);

  private int top(int i,int j,int k){ return i *(w +1) *(d +1) +j *(d +1) +k; }

  long get(int il,int ir,int jl,int jr,int kl,int kr){
    return sum[top(ir,jr,kr)]
        -sum[top(il,jr,kr)] -sum[top(ir,jl,kr)] -sum[top(ir,jr,kl)]
        +sum[top(ir,jl,kl)] +sum[top(il,jr,kl)] +sum[top(il,jl,kr)]
        -sum[top(il,jl,kl)];
  }
}

abstract class BaseV{
  public int sz;
  public boolean fail;
}

class MyStack<T> extends MyList<T>{
  public T pop(){ return remove(size() -1); }

  public T peek(){ return get(size() -1); }
}

class MyList<T> implements Iterable<T>{
  private T[] arr;
  private int sz;

  public MyList(){ this(16); }

  public MyList(int n){ arr = Util.cast(new Object[max(16,n)]); }

  public MyList(MyList<T> org){
    this(org.sz);
    System.arraycopy(org.arr,0,arr,0,sz = org.sz);
  }

  public boolean isEmpty(){ return sz == 0; }

  public int size(){ return sz; }

  public T get(int i){ return arr[i]; }

  public T last(){ return sz == 0 ? null : arr[sz -1]; }

  public void add(T t){ (arr = sz < arr.length ? arr : copyOf(arr,sz *5 >>2))[sz++] = t; }

  public void addAll(MyList<T> list){
    for (var t:list)
      add(t);
  }

  public T remove(int i){
    var ret = arr[i];
    sz--;
    for (int j = i;j < sz;j++)
      arr[j] = arr[j +1];
    return ret;
  }

  public T removeFast(int i){
    var ret = arr[i];
    arr[i] = arr[--sz];
    return ret;
  }

  public void sort(){ sort(Util.cast(Comparator.naturalOrder())); }

  public void sort(Comparator<T> cmp){ Arrays.sort(arr,0,sz,cmp); }

  public <U> MyList<U> map(Function<T, U> func){
    MyList<U> ret = new MyList<>(sz);
    forEach(t -> ret.add(func.apply(t)));
    return ret;
  }

  public MyList<T> rev(){
    MyList<T> ret = new MyList<>(sz);
    for (int i = sz;i-- > 0;)
      ret.add(get(i));
    return ret;
  }

  public T[] toArray(){
    if (sz == 0)
      return Util.cast(new Object[0]);
    T[] ret = Util.cast(Array.newInstance(arr[0].getClass(),sz));
    System.arraycopy(arr,0,ret,0,sz);
    return ret;
  }

  public void swap(int i,int j){
    var t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }

  public void set(int i,T t){ arr[i] = t; }

  public void clear(){ sz = 0; }

  @Override
  public Iterator<T> iterator(){
    return new Iterator<>(){
      int i = 0;

      @Override
      public boolean hasNext(){ return i < sz; }

      @Override
      public T next(){ return arr[i++]; }
    };
  }
}

class BaseSolver extends Util{
  public MyReader in;
  public MyWriter out,log;

  public BaseSolver(MyReader in,MyWriter out,MyWriter log){
    this.in = in;
    this.out = out;
    this.log = log;
  }

  public int[][] addId(int[][] T){
    return arr(new int[T.length][],i -> {
      int[] t = copyOf(T[i],T[i].length +1);
      t[t.length -1] = i;
      return t;
    });
  }

  public long inv(long x){ return pow(x,mod -2); }

  public long inv(long x,long mod){ return (extendGcd(x,mod)[0] +mod) %mod; }

  public long pow(long x,long n){ return pow(x,n,Util.mod); }

  public long pow(long x,long n,long mod){
    long ret = 1;
    for (x %= mod;0 < n;x = x *x %mod,n >>= 1)
      if ((n &1) == 1)
        ret = ret *x %mod;
    return ret;
  }

  public int bSearchI(int o,int n,IntPredicate judge){
    for (int m = 0;1 < abs(n -o);)
      m = judge.test(m = o +n >>1) ? (o = m) : (n = m);
    return o;
  }

  public long bSearchL(long o,long n,LongPredicate judge){
    for (long m = 0;1 < abs(n -o);)
      m = judge.test(m = o +n >>1) ? (o = m) : (n = m);
    return o;
  }

  public double bSearchD(double o,double n,DoublePredicate judge){
    for (double m,c = 0;c < 100;c++)
      m = judge.test(m = (o +n) /2) ? (o = m) : (n = m);
    return o;
  }

  public long gcd(long a,long b){
    while (0 < b) {
      long t = a;
      a = b;
      b = t %b;
    }
    return a;
  }

  public long[] extendGcd(long a,long b){
    long x0 = 1,y0 = 0,x1 = 0,y1 = 1;
    while (b != 0) {
      long q = a /b,t = a %b,tx = x1,ty = y1;
      a = b;
      b = t;
      x1 = x0 -q *x1;
      y1 = y0 -q *y1;
      x0 = tx;
      y0 = ty;
    }
    return new long[]{x0, y0, a};
  }

  public long lcm(long a,long b){ return b /gcd(a,b) *a; }

  public long ceil(long a,long b){ return (a +b -1) /b; }

  public int lis(int[] arr){
    int[] lis = new int[arr.length];
    fill(lis,infI);
    for (var a:arr) {
      int i = bSearchI(0,arr.length,ii -> lis[ii] < a) +1;
      lis[i] = a;
    }
    return bSearchI(0,arr.length,i -> lis[i] < infI) +1;
  }
}

class Util{
  public static String yes = "Yes",no = "No";
  public static int infI = (1 <<30) -1;
  public static long infL = (1L <<61 |1 <<30) -1,
      mod = 998244353;
  public static Random rd = ThreadLocalRandom.current();
  private long st = System.currentTimeMillis();

  protected long elapsed(){ return System.currentTimeMillis() -st; }

  protected void reset(){ st = System.currentTimeMillis(); }

  public static int[] arrI(int N,IntUnaryOperator f){
    int[] ret = new int[N];
    setAll(ret,f);
    return ret;
  }

  public static long[] arrL(int N,IntToLongFunction f){
    long[] ret = new long[N];
    setAll(ret,f);
    return ret;
  }

  public static double[] arrD(int N,IntToDoubleFunction f){
    double[] ret = new double[N];
    setAll(ret,f);
    return ret;
  }

  public static <T> T[] arr(T[] arr,IntFunction<T> f){
    setAll(arr,f);
    return arr;
  }

  @SuppressWarnings("unchecked")
  public static <T> T cast(Object obj){ return (T) obj; }
}

class MyReader{
  private byte[] buf = new byte[1 <<16];
  private int ptr,tail;
  private InputStream in;

  public MyReader(InputStream in){ this.in = in; }

  private byte read(){
    if (ptr == tail)
      try {
        tail = in.read(buf);
        ptr = 0;
      } catch (IOException e) {}
    return buf[ptr++];
  }

  private boolean isPrintable(byte c){ return 32 < c && c < 127; }

  private byte nextPrintable(){
    byte ret = read();
    while (!isPrintable(ret))
      ret = read();
    return ret;
  }

  public int it(){ return toIntExact(lg()); }

  public int[] it(int N){ return Util.arrI(N,i -> it()); }

  public int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); }

  public int idx(){ return it() -1; }

  public int[] idx(int N){ return Util.arrI(N,i -> idx()); }

  public int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); }

  public long lg(){
    byte i = nextPrintable();
    boolean negative = i == 45;
    long n = negative ? 0 : i -'0';
    while (isPrintable(i = read()))
      n = 10 *n +i -'0';
    return negative ? -n : n;
  }

  public long[] lg(int N){ return Util.arrL(N,i -> lg()); }

  public long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); }

  public double dbl(){
    String str = str();
    return Double.parseDouble(str);
  }

  public double[] dbl(int N){ return Util.arrD(N,i -> dbl()); }

  public double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); }

  public char[] ch(){ return str().toCharArray(); }

  public char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); }

  public String line(){
    StringBuilder sb = new StringBuilder();
    for (byte c;(c = read()) != '\n';)
      sb.append((char) c);
    return sb.toString();
  }

  public String str(){
    StringBuilder sb = new StringBuilder();
    sb.append((char) nextPrintable());
    for (byte c;isPrintable(c = read());)
      sb.append((char) c);
    return sb.toString();
  }

  public String[] str(int N){ return Util.arr(new String[N],i -> str()); }

  public String[][] str(int H,int W){ return Util.arr(new String[H][],i -> str(W)); }
}

class MyWriter{
  private OutputStream out;
  private byte[] buf = new byte[1 <<16],ibuf = new byte[20];
  private int tail;
  private boolean autoflush;

  public MyWriter(OutputStream out,boolean autoflush){
    this.out = out;
    this.autoflush = autoflush;
  }

  public void flush(){
    try {
      out.write(buf,0,tail);
      tail = 0;
    } catch (IOException e) {
      e.printStackTrace();
    }
  }

  private void write(byte b){
    buf[tail++] = b;
    if (tail == buf.length)
      flush();
  }

  private void write(long n){
    if (n < 0) {
      n = -n;
      write((byte) '-');
    }
    int i = ibuf.length;
    do {
      ibuf[--i] = (byte) (n %10 +'0');
      n /= 10;
    } while (n > 0);
    while (i < ibuf.length)
      write(ibuf[i++]);
  }

  private void print(Object obj){
    if (obj instanceof Boolean)
      print((boolean) obj ? Util.yes : Util.no);
    else if (obj instanceof Integer)
      write((int) obj);
    else if (obj instanceof Long)
      write((long) obj);
    else if (obj instanceof char[])
      for (char b:(char[]) obj)
        write((byte) b);
    else if (obj.getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++) {
        print(Array.get(obj,i));
        if (i +1 < l)
          write((byte) ' ');
      }
    } else
      print(Objects.toString(obj).toCharArray());
  }

  public void println(Object obj){
    if (obj == null)
      obj = "null";
    if (obj instanceof Iterable<?>)
      for (Object e:(Iterable<?>) obj)
        println(e);
    else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && Array.get(obj,0).getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++)
        println(Array.get(obj,i));
    } else {
      print(obj);
      write((byte) '\n');
      if (autoflush)
        flush();
    }
  }

  public void printlns(Object... obj){
    print(obj);
    write((byte) '\n');
    if (autoflush)
      flush();
  }
}