문제
어린 마법사인 헨리 포터는 방금 슬픈 소식을 들었다 - 그의 가족 중 가장 나이가 많은 사촌 마르코스 라디우스 팰린드로무스 블랙이 세상을 떠났다는 것이다. 사촌 마르코스는 상당히 괴짜인 사람으로 알려져 있는데, 매우 복잡하고 다양한 이진 마법을 사용하기 때문이다.
블랙의 의지는 헨리가 그의 신비한 보물 동굴을 상속받으라는 것을 나타내고 있다. 동굴에 들어가려면, 그 어린 마법사는 올바른 비밀번호 H를 말해야만 하는데, 이것은 0과 1로만 이루어진 길이 n의 단어이다. 사촌 마르코스는 헨리에게 비밀번호를 말하지 않았다 - 이것은 그의 스타일이 아니기 때문이다. 그 대신, 그는 모든 x = 1, 2, ... , n에 대해, 팰린드로믹 라디우스(palindromic radius) px를 계산하여 알려주었다. 여기서 px는, 길이 2px+1이고 중심이 H[x]인 단어 H[x-px … x+px]가 팰린드롬이 되도록 하는 px들 중 가장 큰 수이다. 헨리는 p1, …, pn만을 받았다. 예를 들어, 비밀번호가 10111010이면, 헨리는 (0, 1, 0, 3, 0, 1, 1, 0)을 받을 것이다.
헨리는 사촌 마르코스가 죽을 때 그의 알고리즘 기술을 시험하지 않는 것을 선호하지만, 하지만, 아무튼, 항의 할 대상은 없다. 그리고 그는 자신을 도와줄 좋은 친구가 있다! 마르코스의 의지가 담긴 순열이 주어졌을 때, 그것과 일치하는 모든 가능한 비밀번호를 찾아야 한다. 의지는 낡고 얼룩져있기 때문에, 가능한 비밀번호가 없을 수 있는 일이 발생할 수도 있다.
입력
첫 번째 줄에는 테스트케이스의 개수 z(1 ≤ z ≤ 200 000)가 주어진다. 각 테스트케이스는 다음과 같이 주어진다.
각 테스트케이스는 2개의 줄에 주어진다.
첫 번째 줄은 블랙이 남긴 순열을 의미하는 숫자 n (2 ≤ n ≤ 1,000,000)이 주어진다.
두 번째 줄에는 팰린드로믹 라디우스 pi (0 ≤ pi ≤ n)를 의미하는 숫자 n개가 공백을 사이에 두고 주어진다.
모든 테스트케이스에서 n의 합은 5 x 107을 넘지 않는다.
출력
모든 테스트케이스에 대해, 첫 번째 줄에 가능한 비밀번호의 개수 k를 출력한다.
만약 k > 0이라면, 다음 k개의 줄에 비밀번호의 후보들을 출력한다.
순열은 사전 순서로 출력되어야만 한다.
모든 테스트케이스에 대해, k는 100 이하임이 보장된다.
예제
1
8
0 1 0 3 0 1 1 0
4
00010000
01000101
10111010
11101111
로그인해야 코드를 작성할 수 있어요.