1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int ile;
	cin>>ile;
	while(ile--){
		int n,k;
		cin>>n>>k;
		if(n==1){
			if(k==1) cout<<"A\n"; else cout<<"NIE\n";
		}
		else if(n==2){
			if(k==1) cout<<"PA\n"; else if(k==2) cout<<"AA\n"; else cout<<"NIE\n";
		}
		else{
			if(k<3 || k>n){
				cout<<"NIE\n";
			}
			else{
				string wyn(n,'A');
				int pol=(k+1)/2;
				for(int i=0;i<pol;i++){
					char c=(i%2==0?'A':'P');
					wyn[i]=c;
					wyn[k-1-i]=c;
				}
				for(int i=k;i<n;i++){
					wyn[i]=((i-k)%2==0?'P':'A');
				}
				vector<int> a(n),b(n);
				int l=0,r=-1;
				for(int i=0;i<n;i++){
					int nn=1;
					if(i<=r) nn=min(a[l+r-i],r-i+1);
					while(i-nn>=0 && i+nn<n && wyn[i-nn]==wyn[i+nn]) nn++;
					a[i]=nn;
					if(i+nn-1>r){ l=i-nn+1; r=i+nn-1; }
				}
				l=0; r=-1;
				for(int i=0;i<n;i++){
					int nn=0;
					if(i<=r) nn=min(b[l+r-i+1],r-i+1);
					while(i-nn-1>=0 && i+nn<n && wyn[i-nn-1]==wyn[i+nn]) nn++;
					b[i]=nn;
					if(i+nn-1>r){ l=i-nn; r=i+nn-1; }
				}
				int mx=0;
				for(int i=0;i<n;i++)
{
					mx=max(mx,2*a[i]-1);
					mx=max(mx,2*b[i]);
				}
				if(mx==k) cout<<wyn<<"\n"; else cout<<"NIE\n";
			}
		}
	}
	return 0;
}