Problem Description

You are given a sequence $A=[A_1,A_2,\cdots,A_N]$ of length $N$ and a sequence $B=[B_1,B_2,\cdots,B_M]$ of length $M$.

Sequence $A$ is a sequence formed by each of the integers $1,2,\cdots,N$ appearing exactly once. Each element of sequence $B$ is between $1$ and $N$, and all elements are pairwise distinct.

Let the sequence to be operated on be $X$. Initially, sequence $X$ is the same as sequence $A$. You may perform the following two operations on $X$ any number of times (possibly zero times).

• Swap operation

  Let $X=[X_1,X_2,\cdots,X_K]$.

  Choose an integer $i$ such that $1 \le i \le K-1$ and $X_i<X_{i+1}$, and swap the values of the adjacent elements $X_i$ and $X_{i+1}$.

• Merge operation

  Let $X=[X_1,X_2,\cdots,X_K]$.

  Choose an integer $i$ such that $1 \le i \le K-1$, and merge the adjacent elements $X_i$ and $X_{i+1}$ into a single element $\min(X_i,X_{i+1})$.

  In other words, after performing this operation, the length of sequence $X$ decreases by $1$.

Determine whether it is possible to transform sequence $X$ into sequence $B$ using the given operations. If it is possible, output any sequence of operations that transforms $X$ into $B$.

Note that you do not need to minimize the number of operations.

Input Format

The first line contains two integers $N$ and $M$ separated by spaces.

The second line contains $N$ integers $A_1,A_2,\cdots,A_N$ separated by spaces.

The third line contains $M$ integers $B_1,B_2,\cdots,B_M$ separated by spaces.

Output Format

If it is impossible to transform sequence $X$ into sequence $B$, output NO on the first line.

If it is possible to transform sequence $X$ into sequence $B$, output in the following format.

Output YES on the first line.

Output the number of operations $Q$ on the second line. $Q$ must satisfy:

$0 \le Q \le N^2$

In the next $Q$ lines, output each operation in the order performed. Each operation must use one of the following two formats.

• 1 i

  Perform the swap operation on the $i$-th and $(i+1)$-th elements of sequence $X$.

  Let the length of sequence $X$ before this operation be $K$. Then it must satisfy $1 \le i \le K-1$, and the value of the $i$-th element of sequence $X$ must be less than the value of the $(i+1)$-th element.

• 2 i

  Perform the merge operation on the $i$-th and $(i+1)$-th elements of sequence $X$.

  Let the length of sequence $X$ before this operation be $K$. Then it must satisfy $1 \le i \le K-1$.

All positions are based on sequence $X$ before performing the corresponding operation, and the first position in the sequence is numbered $1$.

After executing all operations in the given output in order, the resulting sequence must be exactly the same as sequence $B$.

If multiple valid outputs exist, any one of them is accepted.

If sequence $X$ can be transformed into sequence $B$ using the given operations, it can be proven that there always exists an output satisfying all the conditions above.

4 2
1 4 2 3
3 1

YES
6
1 1
1 2
1 3
2 1
1 1
2 2

2 1
1 2
2

NO

4 4
3 2 1 4
3 1 2 4

NO

4 2
1 3 2 4
1 3

NO

Hint

Sample 1 Explanation

Sequence $X$ changes as follows:

$[1,4,2,3]\to[4,1,2,3]\to[4,2,1,3]\to[4,2,3,1]\to[2,3,1]\to[3,2,1]\to[3,1]$

Therefore, sequence $X$ can be transformed into sequence $B$.

Constraints

• All given numbers are integers.
• $1 \le M \le N \le 3\,000$
• Sequence $A$ is a permutation of $1,2,\cdots,N$, i.e. $\{A_1,A_2,\cdots,A_N\}=\{1,2,\cdots,N\}$.
• For each integer $i$ ($1 \le i \le M$), $1 \le B_i \le N$.
• $B_1,B_2,\cdots,B_M$ are pairwise distinct.

Subtasks

1. ($7$ points) $N \le 8$.
2. ($8$ points) $M=1$.
3. ($12$ points) $M=N$.
4. ($10$ points) For each integer $i$ ($1 \le i \le N$), $A_i=i$.
5. ($13$ points) $M=N-1$.
6. ($15$ points) Sequence $B$ is a subsequence of sequence $A$. In other words, there exist integers $p_1,p_2,\cdots,p_M$ satisfying $1 \le p_1<p_2<\cdots<p_M \le N$ such that for each integer $i$ ($1 \le i \le M$), $B_i=A_{p_i}$.
7. ($30$ points) $N \le 300$.
8. ($5$ points) No additional constraints.

Translated by ChatGPT 5