struct PAM {
	int ch[N][26], fail[N], len[N];
	int tot, las;
	PAM() {
		len[0] = 0; len[1] = -1; fail[0] = 1; tot = 1; las = 0;
	}
	inline int gtfail(int x, int id) {
		while(s[id - len[x] - 1] != s[id]) x = fail[x]; return x;
	}
	inline int New(int x) { len[++ tot] = x; return tot; }
	inline void ins(int c, int id) {
		int p = gtfail(las, id);
		if(! ch[p][c]) {
			int q = New(len[p] + 2);
			fail[q] = ch[gtfail(fail[p], id)][c];
			ch[p][c] = q;
		}
		las = ch[p][c];
	}
}a, b;