結果

問題 No.2858 Make a Palindrome
ユーザー ゆうきゆうき
提出日時 2024-08-25 14:35:50
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 21,765 bytes
コンパイル時間 3,714 ms
コンパイル使用メモリ 96,468 KB
実行使用メモリ 77,608 KB
最終ジャッジ日時 2024-08-25 14:36:11
合計ジャッジ時間 20,879 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 593 ms
62,756 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 338 ms
59,656 KB
testcase_19 WA -
testcase_20 AC 428 ms
75,360 KB
testcase_21 AC 352 ms
75,904 KB
testcase_22 AC 257 ms
65,344 KB
testcase_23 AC 445 ms
75,072 KB
testcase_24 AC 294 ms
72,404 KB
testcase_25 AC 325 ms
67,936 KB
testcase_26 AC 304 ms
67,372 KB
testcase_27 AC 386 ms
74,740 KB
testcase_28 AC 296 ms
72,788 KB
testcase_29 AC 384 ms
75,952 KB
testcase_30 AC 369 ms
75,044 KB
testcase_31 AC 485 ms
77,564 KB
testcase_32 AC 487 ms
77,608 KB
testcase_33 AC 387 ms
75,548 KB
testcase_34 AC 376 ms
75,140 KB
testcase_35 AC 375 ms
75,368 KB
testcase_36 AC 488 ms
77,508 KB
testcase_37 AC 397 ms
75,432 KB
testcase_38 AC 415 ms
74,944 KB
testcase_39 AC 486 ms
77,356 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

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

import java.io.*;
import java.lang.reflect.*;
import java.util.*;
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 = true;

  public Object solve(){
    int N = in.it();
    int M = in.it();
    String S = in.str();

    int c1 = calc(S);
    if (M <= c1)
      return 1;
    int c2 = calc(S +S);
    long a = c2 -c1;
    long b = c1 -a;
    if (a == 0)
      return -1;
    return ceil(M -b,a);
  }

  private int calc(String s){

    var rh = new RollingHash(s.toCharArray(),false);
    int ret = 1;
    for (int i = 0;i < s.length();i++) {
      int l = (ret -1) /2;
      while (0 <= i -(l +1) && i +l +2 <= s.length() && rh.get(i -(l +1),i) == rh.get(i +l +2,i +1))
        l++;
      ret = max(ret,l *2 +1);

      l = ret /2;
      while (0 <= i -l && i +l +2 <= s.length() && rh.get(i -l,i +1) == rh.get(i +l +2,i +1))
        l++;
      ret = max(ret,l *2);
    }

    return ret;
  }

  int[][] trans(int[]... T){ return Util.arr(new int[T[0].length][],i -> Util.arrI(T.length,j -> T[j][i])); }

  //  void add(SegmentTree<Data, Long> seg,int a,long[] map){ seg.upd(a,map[a]); }
  //
  //  void rem(SegmentTree<Data, Long> seg,int a,long[] map){ seg.upd(a,-map[a]); }
  //
  //  long[] mo(int N,int[] A,int[][] T,long[] map,SegmentTree<Data, Long> seg,long[] ans){
  //    int k = 32 -Integer.numberOfLeadingZeros((int) (Math.sqrt(1.5 /T.length) *N) +1);
  //    sort(T,(a,b) -> (a[0] >>k != b[0] >>k ? a[0] -b[0] : (a[0] >>k &1) == 1 ? a[1] -b[1] : b[1] -a[1]));
  //    int l = T[0][0];
  //    int r = l -1;
  //    for (var t:T) {
  //      while (t[0] < l)
  //        add(seg,A[--l],map);
  //      while (r < t[1])
  //        add(seg,A[++r],map);
  //      while (l < t[0])
  //        rem(seg,A[l++],map);
  //      while (t[1] < r)
  //        rem(seg,A[r--],map);
  //      ans[t[2]] = seg.get(0,100_000 +1).v;
  //    }
  //    return ans;
  //  }
}

class RollingHash{
  private static long MOD = (1L <<61) -1,MASK30 = (1L <<30) -1,MASK31 = (1L <<31) -1,
      base = ThreadLocalRandom.current().nextLong(Util.infI,MOD);
  private static long[] pow = {1};
  int n;
  private long[] hash,S;
  private boolean updatable;
  private RollingHash rev;

  public RollingHash(char[] S,boolean updatable){ this(Util.arrL(S.length,i -> S[i]),updatable); }

  public RollingHash(int[] S,boolean updatable){ this(Util.arrL(S.length,i -> S[i]),updatable); }

  public RollingHash(long[] S,boolean updatable){
    this.S = new long[n = S.length];
    this.updatable = updatable;
    hash = new long[n +1];
    if (pow.length <= n) {
      int s = pow.length;
      pow = copyOf(pow,max(pow.length <<1,n +1));
      for (int i = s;i < pow.length;i++)
        pow[i] = mul(pow[i -1],base);
    }
    for (int i = 0;i < n;i++)
      set(i,S[i]);
  }

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

  public long get(int l,int r){
    if (l > r)
      return (rev == null ? rev = rev() : rev).get(n -l,n -r);
    return mod(hash(r) -mul(hash(l),pow[r -l]));
  }

  public void upd(int i,long v){
    assert updatable;
    set(i,v);
    if (rev != null)
      rev.set(n -i -1,v);
  }

  private void set(int i,long v){
    if (updatable)
      for (int x = i +1;x <= n;x += x &-x)
        hash[x] = mod(hash[x] +mul(v -S[i],pow[x -i -1]));
    else
      hash[i +1] = mod(mul(hash[i],base) +v);
    S[i] = v;
  }

  private long hash(int i){
    long ret = 0;
    if (updatable)
      for (int x = i;x > 0;x -= x &-x)
        ret = mod(ret +mul(hash[x],pow[i -x]));
    else
      ret = hash[i];
    return ret;
  }

  private RollingHash rev(){
    long[] s = new long[n];
    for (int i = 0;i < n;i++)
      s[i] = S[n -1 -i];
    return new RollingHash(s,updatable);
  }

  private static long mul(long a,long b){
    long au = a >>31;
    long ad = a &MASK31;
    long bu = b >>31;
    long bd = b &MASK31;
    long mid = ad *bu +au *bd;
    return mod((au *bu <<1) +(mid >>30) +((mid &MASK30) <<31) +ad *bd);
  }

  private static long mod(long val){
    return val < 0 ? val +MOD : (val = (val &MOD) +(val >>61)) < MOD ? val : val -MOD;
  }
}

class Matrix{
  public static long[] mul(long[] a,long[][] b){
    assert a.length == b.length;
    int H = b[0].length,W = a.length;
    long[] ret = new long[H];

    for (int i = 0;i < H;i++)
      for (int j = 0;j < W;j++)
        ret[i] = (ret[i] +a[j] *b[j][i]) %Util.mod;

    return ret;
  }

  public static long[][] mul(long[][] a,long[][] b){
    assert a[0].length == b.length;
    int H = a.length,W = b[0].length,Z = b.length;
    long[][] ret = new long[H][W];

    for (int z = 0;z < Z;z++)
      for (int i = 0;i < H;i++)
        for (int j = 0;j < W;j++)
          ret[i][j] = (ret[i][j] +a[i][z] *b[z][j]) %Util.mod;

    return ret;
  }

  public static long[][] pow(long[][] x,long n){
    long[][] ret = new long[x.length][x.length];
    for (int i = 0;i < x.length;i++)
      ret[i][i] = 1;

    for (;0 < n;x = (n >>= 1) > 0 ? mul(x,x) : x)
      if ((n &1) == 1)
        ret = mul(ret,x);

    return ret;
  }
}

class Grid{
  private int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  private int H,W;

  public Grid(int H,int W){
    this.H = H;
    this.W = W;
  }

  public int[] sur(int p){
    MyList<int[]> tmp = sur(toi(p),toj(p));
    int[] ret = new int[tmp.size()];
    for (int i = 0;i < tmp.size();i++)
      ret[i] = top(tmp.get(i)[0],tmp.get(i)[1]);
    return ret;
  }

  public MyList<int[]> sur(int i,int j){
    MyList<int[]> ret = new MyList<>();
    for (var d:dirs) {
      int ni = i +d[0];
      int nj = j +d[1];
      if (valid(ni,H) && valid(nj,W))
        ret.add(new int[]{ni, nj});
    }

    return ret;
  }

  private boolean valid(int i,int N){ return 0 <= i && i < N; }

  public int top(int i,int j){ return i *W +j; }

  public int toi(int p){ return p /W; }

  public int toj(int p){ return p %W; }
}

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); }
}

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> {
  public int n;
  public 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<>();
  }

  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]; }
}

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 MySet implements Iterable<Integer>{
  private Set<Integer> set;
  private BitSet bit;

  public MySet(){ set = new HashSet<>(); }

  public int size(){ return set != null ? set.size() : bit.cardinality(); }

  public void add(int x){
    if (set != null) {
      set.add(x);
      if (set.size() == 100) {
        bit = new BitSet();
        for (int i:set)
          bit.set(i);
        set = null;
      }
    } else
      bit.set(x);
  }

  public boolean contains(int x){ return set == null ? bit.get(x) : set.contains(x); }

  @Override
  public Iterator<Integer> iterator(){
    return set != null ? set.iterator() : new Iterator<>(){
      int w = bit.nextSetBit(0);

      @Override
      public Integer next(){
        int ret = w;
        w = bit.nextSetBit(w +1);
        return ret;
      }

      @Override
      public boolean hasNext(){ return w != -1; }
    };
  }
}

class Data extends BaseV{
  long v;

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

  @Override
  public String toString(){ return v +""; }
}

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)];
  }
}

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

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

  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);
    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);
    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];
  }

  public long[][] toArray(){
    long[][] ret = new long[set.size() -2][];
    long[] x = {set.first()[0]};
    for (int i = 0;i < ret.length;i++)
      x[0] = (ret[i] = set.higher(x))[0];
    return ret;
  }

  public long cardinality(long l,long r){
    long ret = 0;
    long[] key = {r};
    while (l < r) {
      var t = set.lower(key);
      if (t[1] <= l)
        break;
      ret += min(r,t[1]) -max(l,t[0]);
      key = t;
    }
    return ret;
  }

  public long first(){ return set.higher(new long[]{-Util.infL})[0]; }
}

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 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 < 200;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(){ 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 ln(){
    write((byte) '\n');
    if (autoflush)
      flush();
  }

  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);
      ln();
    }
  }

  public void printlns(Object... o){
    print(o);
    ln();
  }
}
0