수열 연산

길이가 $N$인 수열 $A = \left[ A_1, A_2, \cdots, A_N \right]$과 길이가 $M$인 수열 $B = \left[ B_1, B_2, \cdots, B_M \right]$이 주어진다.

수열 $A$는 $N$개의 정수 $1, 2, \cdots, N$을 각각 정확히 한 번씩 원소로 가지는 순열이다. 수열 $B$의 각 원소는 $1$ 이상 $N$ 이하이고, 모든 원소가 서로 다르다.

여러분이 연산을 가할 수열을 $X$라고 하자. 처음에 수열 $X$는 수열 $A$와 동일하다. 여러분은 수열 $X$에 다음 두 종류의 연산을 $0$회 이상 원하는 만큼 수행할 수 있다.

• 교환 연산

$X = \left[ X_1, X_2, \cdots, X_K \right]$라고 하자.

$1 \le i \le K - 1$이고 $X_i < X_{i + 1}$인 정수 $i$를 골라, 인접한 두 원소 $X_i$와 $X_{i + 1}$의 값을 서로 바꿀 수 있다.

• 합치기 연산

$X = \left[ X_1, X_2, \cdots, X_K \right]$라고 하자.

$1 \le i \le K - 1$인 정수 $i$를 골라, 인접한 두 원소 $X_i$와 $X_{i + 1}$을 하나의 원소 $\min \left( X_i, X_{i + 1} \right)$로 합칠 수 있다.

즉, 이 연산을 수행하면 수열 $X$의 길이가 $1$ 감소한다.

주어진 연산들을 이용하여 수열 $X$를 수열 $B$와 같게 만들 수 있는지 판정하라. 만약 가능하다면, 수열 $X$를 수열 $B$로 바꾸는 연산열을 아무거나 하나 찾아라.

연산의 개수를 최소화할 필요는 없음에 유의하라.

• 주어지는 모든 수는 정수이다.
• $1 \le M \le N \le 3\,000$
• 수열 $A$는 $1, 2, \cdots, N$의 순열이다. 즉, $\left\{ A_1, A_2, \cdots, A_N \right\} = \left\{ 1, 2, \cdots, N \right\}$
• 정수 $i$ ($1 \le i \le M$)에 대하여 $1 \le B_i \le N$
• $B_1, B_2, \cdots, B_M$의 값은 모두 서로 다르다.

1. (7점) $N \le 8$
2. (8점) $M = 1$
3. (12점) $M = N$
4. (10점) 정수 $i$ ($1 \le i \le N$)에 대하여 $A_i = i$
5. (13점) $M = N - 1$
6. (15점) 수열 $B$는 수열 $A$의 부분수열이다. 즉, $1 \le p_1 < p_2 < \cdots < p_M \le N$을 만족하면서 모든 정수 $i$ ($1 \le i \le M$)에 대하여 $B_i = A_{p_i}$인 정수 $p_1, p_2, \cdots, p_M$이 존재한다.
7. (30점) $N \le 300$
8. (5점) 추가 제약 조건 없음.

첫 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 $M$개의 정수 $B_1, B_2, \cdots, B_M$이 공백으로 구분되어 차례대로 주어진다.

수열 $X$를 수열 $B$로 만들 수 없다면, 첫 줄에 NO를 출력한다.

수열 $X$를 수열 $B$로 만들 수 있다면, 아래와 같이 출력한다.

첫 줄에 YES를 출력한다.

그다음 줄에 수행할 연산의 개수 $Q$를 출력한다. $Q$는 다음 조건을 만족해야 한다.

$$ 0 \le Q \le N^2 $$

그다음 $Q$개의 줄에 수행할 연산을 순서대로 출력한다. 각 연산은 다음 두 형식 중 하나이다.

• 1 i

수열 $X$의 $i$번째 원소와 $(i + 1)$번째 원소에 대해 교환 연산을 수행한다.

이 연산을 수행하기 직전의 수열 $X$의 길이를 $K$라고 할 때, $1 \le i \le K - 1$이고, 수열 $X$의 $i$번째 원소의 값이 $(i+1)$번째 원소보다 작아야 한다.

• 2 i

수열 $X$의 $i$번째 원소와 $(i + 1)$번째 원소에 대해 합치기 연산을 수행한다.

이 연산을 수행하기 직전의 수열 $X$의 길이를 $K$라고 할 때, $1 \le i \le K - 1$여야 한다.

모든 위치는 해당 연산을 수행하기 직전의 수열 $X$를 기준으로 하며, 수열의 첫 번째 위치는 $1$번으로 한다.

출력한 모든 연산을 순서대로 수행한 결과는 수열 $B$와 정확히 같아야 한다.

가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.

주어진 연산들을 이용하여 수열 $X$를 수열 $B$로 만들 수 있다면, 위 조건을 모두 만족하는 출력이 존재함을 증명할 수 있다.