問題文

文字列 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．

入力例 1

2 1

出力例 1

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 である．