This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/string/manacher.hpp"
vector<int> brute(const string& s) {
const int n = (int)s.size();
if(n == 0) return {};
vector<int> res(2 * n - 1);
for(int c = 0; c < 2 * n - 1; ++c) {
for(int len = (c % 2 == 0);; len += 2) {
const int l = (c - len + 1) / 2;
const int r = (c + len + 1) / 2;
if(l < 0 or n < r) break;
bool ok = true;
for(int i = l, j = r - 1; i < j; ++i, --j) {
if(s[i] != s[j]) {
ok = false;
break;
}
}
if(ok) res[c] = len;
}
}
return res;
}
int main() {
assert(manacher(string()).empty());
assert(manacher(string("ab")) == vector<int>({1, 0, 1}));
assert(manacher(string("aa")) == vector<int>({1, 2, 1}));
assert(manacher(string("abba")) == vector<int>({1, 0, 1, 4, 1, 0, 1}));
for(int n = 0; n <= 9; ++n) {
for(int bit = 0; bit < (1 << n); ++bit) {
string s(n, 'a');
for(int i = 0; i < n; ++i) {
if((bit >> i) & 1) s[i] = 'b';
}
assert(manacher(s) == brute(s));
}
}
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}#line 1 "verify/unit_test/string/manacher.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
SetupIO() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(30);
}
} setup_io;
#line 3 "src/string/manacher.hpp"
template <typename T>
vector<int> manacher(const T& s) {
const int n = (int)s.size();
if(n == 0) return {};
vector<int> odd(n), even(n), res(2 * n - 1);
for(int i = 0, l = 0, r = -1; i < n; ++i) {
int k = (i > r ? 1 : min(odd[l + r - i], r - i + 1));
while(0 <= i - k and i + k < n and s[i - k] == s[i + k]) ++k;
odd[i] = k;
if(i + k - 1 > r) {
l = i - k + 1;
r = i + k - 1;
}
}
for(int i = 0, l = 0, r = -1; i < n; ++i) {
int k = (i > r ? 0 : min(even[l + r - i + 1], r - i + 1));
while(0 <= i - k - 1 and i + k < n and s[i - k - 1] == s[i + k]) ++k;
even[i] = k;
if(i + k - 1 > r) {
l = i - k;
r = i + k - 1;
}
}
for(int i = 0; i < n; ++i) {
res[2 * i] = 2 * odd[i] - 1;
if(i) res[2 * i - 1] = 2 * even[i];
}
return res;
}
#line 4 "verify/unit_test/string/manacher.test.cpp"
vector<int> brute(const string& s) {
const int n = (int)s.size();
if(n == 0) return {};
vector<int> res(2 * n - 1);
for(int c = 0; c < 2 * n - 1; ++c) {
for(int len = (c % 2 == 0);; len += 2) {
const int l = (c - len + 1) / 2;
const int r = (c + len + 1) / 2;
if(l < 0 or n < r) break;
bool ok = true;
for(int i = l, j = r - 1; i < j; ++i, --j) {
if(s[i] != s[j]) {
ok = false;
break;
}
}
if(ok) res[c] = len;
}
}
return res;
}
int main() {
assert(manacher(string()).empty());
assert(manacher(string("ab")) == vector<int>({1, 0, 1}));
assert(manacher(string("aa")) == vector<int>({1, 2, 1}));
assert(manacher(string("abba")) == vector<int>({1, 0, 1, 4, 1, 0, 1}));
for(int n = 0; n <= 9; ++n) {
for(int bit = 0; bit < (1 << n); ++bit) {
string s(n, 'a');
for(int i = 0; i < n; ++i) {
if((bit >> i) & 1) s[i] = 'b';
}
assert(manacher(s) == brute(s));
}
}
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}