题目描述

给定长度为 $N$ 的序列 $A=[A_1,A_2,\cdots,A_N]$ 和长度为 $M$ 的序列 $B=[B_1,B_2,\cdots,B_M]$。

序列 $A$ 是由整数 $1,2,\cdots,N$ 各恰好出现一次构成的序列。序列 $B$ 的每个元素都在 $1$ 到 $N$ 之间，且所有元素两两不同。

将要进行运算的序列记为 $X$。初始时，序列 $X$ 与序列 $A$ 相同。你可以对序列 $X$ 执行以下两种运算任意多次（也可以一次都不执行）。

• 交换运算

  设 $X=[X_1,X_2,\cdots,X_K]$。

  选择一个满足 $1 \le i \le K-1$ 且 $X_i<X_{i+1}$ 的整数 $i$，交换相邻两个元素 $X_i$ 和 $X_{i+1}$ 的值。

• 合并运算

  设 $X=[X_1,X_2,\cdots,X_K]$。

  选择一个满足 $1 \le i \le K-1$ 的整数 $i$，将相邻两个元素 $X_i$ 和 $X_{i+1}$ 合并为一个元素 $\min(X_i,X_{i+1})$。

  也就是说，执行该运算后，序列 $X$ 的长度减少 $1$。

请判断能否使用给定运算将序列 $X$ 变成序列 $B$。若可以，请找出任意一个将序列 $X$ 变为序列 $B$ 的运算序列。

请注意，不需要最小化运算次数。

输入格式

第一行依次给出两个以空格分隔的整数 $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$，则可以证明，一定存在满足上述全部条件的输出。

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

提示

样例 1 解释

序列 $X$ 发生如下变化：

$[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]$

因此，可以将序列 $X$ 变成序列 $B$。

限制条件

• 给出的所有数均为整数。
• $1 \le M \le N \le 3\,000$
• 序列 $A$ 是 $1,2,\cdots,N$ 的一个排列，即 $\{A_1,A_2,\cdots,A_N\}=\{1,2,\cdots,N\}$。
• 对于每个整数 $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$ 的整数 $p_1,p_2,\cdots,p_M$，使得对于每个整数 $i$（$1 \le i \le M$），$B_i=A_{p_i}$。
7. （$30$ 分）$N \le 300$。
8. （$5$ 分）没有额外限制。