만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

아무나 풀어주세요

시간 제한2초메모리 제한1024 MB

요약
1부터 9까지의 수로 이루어진 수열 A에서 시작해 수를 끝에 덧붙여 수열 B를 만들 수 있는지 판단합니다. 짝수를 붙이기 전에는 마지막 세 수를 오름차순으로 정렬합니다.
난이도

보통10점 중 6점

유형
동적 계획법, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

건모는 수열을 가지고 놀다가 재밌는 게임을 하기로 결정했다.

게임은 다음과 같이 진행된다.

  1. 건모는 처음에 수열 AA를 가지고 시작한다.
  2. 건모는 11부터 99 사이에서 원하는 숫자를 골라 수열의 맨 뒤에 추가한다. 단, 추가하려는 수가 짝수라면 수열의 마지막 수 세 개를 오름차순으로 정렬한 뒤에 추가해야 한다.
  3. 수열 BB를 만들면 건모는 게임에서 승리한다. 어떻게 해도 만들 수 없다면 게임에서 패배한다.

건모는 '되면 한다'는 마인드를 갖고 있어서, 불가능하다면 시도조차 하지 않을 생각이다.

건모가 게임에서 승리하는지 아닌지를 출력하라.

입력

첫째 줄에 테스트 케이스의 수 TT가 주어진다. (1≤T≤5 0001 \le T \le 5\,000)

각 테스트 케이스의 첫 줄에는 수열 AA의 길이 NN과 수열 BB의 길이 MM이 공백으로 구분되어 주어진다. (3≤N≤M≤5 0003 \le N \le M \le 5\,000)

각 테스트 케이스의 둘째 줄에는 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 공백으로 구분되어 주어진다. (1≤Ai≤91 \le A_i \le 9)

각 테스트 케이스의 셋째 줄에는 B1,B2,⋯ ,BMB_1, B_2, \cdots, B_M이 공백으로 구분되어 주어진다. (1≤Bi≤91 \le B_i \le 9)

모든 테스트 케이스에서 MM의 합은 15 00015\,000을 넘지 않는다.

주어지는 모든 수는 정수이다.

출력

각 테스트 케이스마다 정답을 한 줄에 하나씩 출력한다. 건모가 게임에서 승리하면 YES를, 패배하면 NO를 출력한다. 대소문자는 구분하지 않아도 되므로 yEs, yes, YES 모두 정답으로 인정된다.

예제1

  1. 예제 1

    입력
    3
    5 8
    1 4 7 3 4
    1 4 3 4 3 7 8 2
    3 5
    1 2 3
    1 2 3 4 5
    3 5
    5 4 3
    5 4 3 2 1
    
    예상 출력
    YES
    YES
    NO