문제
Bessie는 간단한 프로그래밍 언어를 사용하여 코딩하는 법을 배우고 있습니다. 이 언어에서 프로그램은 하나 이상의 문장으로 구성된 순서 있는 나열입니다. 문장은 다음 두 형태 중 하나를 가집니다:
PRINT c: 여기서 c는 정수입니다.
REP o: 그 뒤에 프로그램이 오고 마지막에 END가 옵니다. 여기서 o는 1 이상의 정수입니다.
프로그램을 실행하면, 문장들이 순서대로 실행됩니다. PRINT c 문장을 실행하면 c가 출력 시퀀스에 추가되며, REP o 문장은 내부에 포함된 프로그램을 총 o번 순차적으로 실행합니다.
예를 들어, 다음 프로그램을 보세요:
REP 3
PRINT 1
REP 2
PRINT 2
END
END
이 프로그램은 출력 시퀀스 [1, 2, 2, 1, 2, 2, 1, 2, 2]를 생성합니다.
Bessie는 이제 N개의 양의 정수 (1 ≤ N ≤ 100)로 구성된 시퀀스를 출력하고자 합니다. Elsie는 Bessie에게 최대 K개의 PRINT 문장 (1 ≤ K ≤ 3)만을 사용하여 프로그램을 작성하라는 도전을 합니다. Bessie는 원하는 만큼 REP 문장을 사용할 수 있으며, 출력되는 시퀀스의 각 정수는 최대 K 이하입니다. 여러 개의 독립된 테스트 케이스 (T, 1 ≤ T ≤ 100)가 주어질 때, 주어진 시퀀스를 최대 K개의 PRINT 문장만으로 출력할 수 있는지 판별하세요.
입력
첫 번째 줄에는 테스트 케이스의 수 T가 주어집니다.
각 테스트 케이스에 대해:
첫 번째 줄에는 두 개의 정수 N과 K가 공백으로 구분되어 주어집니다.
두 번째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어지며, 각 정수는 최대 K 이하입니다. 이 시퀀스는 Bessie가 출력하고자 하는 시퀀스입니다.
출력
각 테스트 케이스마다, 가능한 경우 "YES"를, 불가능한 경우 "NO"를 (대소문자 구분하여) 한 줄에 하나씩 출력하세요.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | |
| #2 | 30점 | |
| #3 | 50점 | 추가 제약 조건 없음 |
예제1
2
1 1
1
4 1
1 1 1 1
YES
YES
예제2
11
4 2
1 2 2 2
4 2
1 1 2 1
4 2
1 1 2 2
6 2
1 1 2 2 1 1
10 2
1 1 1 2 2 1 1 1 2 2
8 3
3 3 1 2 2 1 2 2
9 3
1 1 2 2 2 3 3 3 3
16 3
2 2 3 2 2 3 1 1 2 2 3 2 2 3 1 1
24 3
1 1 2 2 3 3 3 2 2 3 3 3 1 1 2 2 3 3 3 2 2 3 3 3
9 3
1 2 2 1 3 3 1 2 2
6 3
1 2 1 2 2 3
YES
NO
YES
NO
YES
YES
YES
YES
YES
NO
NO