저렴하지만 비슷한

메모리 제한에 유의하세요.

2077년, 신경계에 연결해 움직임을 빠르게 하는 기계 장치 '산데비스탄'이 개발되었다. 산데비스탄을 만들려면 광물 X가 꼭 필요하지만, 이 광물은 매우 비싸다. 어느 날 광물 X 대신 훨씬 저렴한 광물 Y를 사용해 같은 장치를 만드는 방법이 발견되었고, 여러 회사가 광물 Y를 채굴하기 위해 뛰어들었다.

광물 Y가 묻힌 광맥은 좌우로 길게 뻗은 일직선이다. 광맥은 총 $N$개의 칸으로 이루어져 있고, 왼쪽에서 $i$번째 칸에는 $A_i$만큼의 광물이 매장되어 있다. 첫 번째 칸($i=1$)은 이미 통로로 개발되어 더 이상 광물이 없으므로 $A_1=0$이다.

광물을 채굴하려면 장비가 필요하다. 장비 하나는 설치된 칸의 바로 오른쪽에서 시작하는 연속한 1개 이상 3개 이하의 칸에 있는 광물을 모두 채굴할 수 있다. 장비는 반드시 채굴 구간의 맨 왼쪽 칸 바로 왼쪽 칸에 설치해야 한다. 안전 규정상 장비가 설치된 칸의 광물은 채굴할 수 없고, 이미 다른 장비가 채굴하는 칸 위에도 장비를 설치할 수 없다.

총 광물 매장량을 $S=\sum_{i=1}^{N} A_i$라고 하자. $0.75S$ 이상의 광물을 채굴할 수 있는지 판별하고, 가능하다면 장비를 어떻게 설치하고 어떤 칸을 채굴할지 출력하라.

첫 번째 예시를 시각화한 그림이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T \le 100,000)$

각 테스트 케이스마다 첫째 줄에 광맥의 길이 $N$이 주어진다. $(1 \le N \le 20,772,077)$

둘째 줄에는 각 칸에 묻힌 광물의 양 $A_1,A_2,\dots,A_N$이 공백으로 구분되어 주어진다. $(0 \le A_i \le 100, A_1=0)$

모든 테스트 케이스에서 $N$의 합은 $20,772,077$을 넘지 않는다.

각 테스트 케이스마다 $0.75S$ 이상의 광물을 채굴할 방법이 없다면 첫 줄에 NO를 출력한다.

방법이 있다면 첫 줄에 YES를 출력한다. 둘째 줄에는 0, 1, 2, 3으로 이루어진 길이 $N$의 문자열을 출력한다.

$i$번째 칸이 채굴되지 않았다면 문자열의 $i$번째 문자는 0이다. $i$번째 칸이 채굴되었고, 그 칸을 채굴한 장비의 채굴 구간 길이가 $k$라면 문자열의 $i$번째 문자는 $k$이다.

이 문제는 SNUPC 2024의 히든 문제였다. 대회 포스터의 오른쪽 아래를 참고하라.