問題文

文字列 $t$ が文字列 $s$ の border であるとは，$t$ が $s$ の prefix かつ suffix であることとする．長さ $n$ の文字列 $s$ と整数 $1 \le k \le n$ に対し，$f(s, k)$ を，$s$ の長さ $k$ の prefix の border であって，長さが $k$ 未満のもののうち最長のものの長さとする (空文字列は任意の文字列の border であるから，これは well-defined である)．また，$f(s, 0) = -1$ と定める．

しろうさは，長さ $n$ の文字列 $s$ が与えられたとき $f(s, 0), f(s, 1), \ldots, f(s, n)$ を計算するアルゴリズムを実装しようとしたが，間違えてしまった．以下の C++ コード片で表される関数 Xmas に $s$ を引数として与えたときに計算される整数列 g を $(g(s, 0), g(s, 1), \ldots, g(s, n))$ とする．

#include <string>
#include <vector>
std::vector<int> Xmas(std::string s) {
  int n = s.size();
  std::vector<int> g(n + 1);
  int j = g[0] = -1;
  for (int i = 0; i < n; ++i) {
    for (; j >= 0 && s[j] == s[i]; j = g[j]) {}
    g[i + 1] = ++j;
  }
  return g;
}

正整数 $A, B$ が与えられる．$A$ 個の文字 a と $B$ 個の文字 b からなる長さ $A + B$ の文字列 $s$ に対する， $\displaystyle\sum_{k=0}^{A+B} \bigl\lvert f(s, k) - g(s, k) \bigr\rvert$ の最小値，および最小値を達成する $s$ を $1$ つ求めよ．

制約

• $1 \le A, B \le 10^5$．

入力例 1Copy

2 1

出力例 1Copy

2
aba

$f(\mathtt{aba}, 0) = -1,\, f(\mathtt{aba}, 1) = 0,\, f(\mathtt{aba}, 2) = 0,\, f(\mathtt{aba}, 3) = 1$ である．

$g(\mathtt{aba}, 0) = -1,\, g(\mathtt{aba}, 1) = 0,\, g(\mathtt{aba}, 2) = 1,\, g(\mathtt{aba}, 3) = 2$ である．