해리 포터와 회문 반지름

젊은 마법사 해리 포터에게 슬픈 소식이 전해졌다. 가문의 가장 큰 어른인 마르쿠스 래디우스 팔린드로머스 블랙 삼촌이 세상을 떠났다. 마르쿠스 삼촌은 복잡한 이진 마법을 쓰는 괴짜로 알려져 있었고, 아주 큰 부자이기도 했다.

블랙의 유언장에는 해리가 그의 신비한 보물 방을 물려받는다고 적혀 있다. 그러나 방에 들어가 보물을 차지하려면 올바른 암호 $H$를 말해야 한다. $H$는 0과 1로만 이루어진 길이 $n$의 문자열이다. 마르쿠스 삼촌은 암호를 해리에게 알려 주지 않았다. 대신 $x = 1, 2, \ldots, n$ 각각에 대해 회문 반지름 $p_x$를 계산했다. $p_x$는 $H[x]$를 가운데 두고 길이가 $2p_x + 1$인 구간 $H[x - p_x .. x + p_x]$가 존재하고 회문이 되는 가장 큰 정수이다. 해리가 받은 것은 $p_1, \ldots, p_n$ 값뿐이다. 예를 들어 암호가 10111010이면 해리는 $(0, 1, 0, 3, 0, 1, 1, 0)$을 받는다.

해리는 삼촌이 죽어서까지 자신의 알고리즘 실력을 시험하지 않기를 바란다. 다행히 그를 도와줄 좋은 친구들이 있다. 유언장에 남은 수열이 주어졌을 때, 이에 맞는 암호를 모두 구하라. 유언장이 얼룩져 있어서 해가 전혀 없을 수도 있다.

첫 줄에 테스트 케이스의 개수 $z$가 주어진다 ($1 \le z \le 200000$). 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 암호의 길이이자 블랙의 수열의 길이인 정수 $n$이 주어진다 ($2 \le n \le 1000000$). 둘째 줄에는 회문 반지름 $p_1, p_2, \ldots, p_n$ ($0 \le p_i \le n$)이 주어진다. 모든 테스트 케이스의 $n$을 합한 값은 $5 \times 10^7$을 넘지 않는다.

각 테스트 케이스마다 먼저 가능한 암호의 개수 $k$를 출력한다. $k$가 0보다 크면 다음 $k$줄에 가능한 암호를 모두 0과 1로 이루어진 수열로 사전 순으로 출력한다. $k$는 100을 넘지 않는다고 가정해도 된다.