一次庆祝活动结束后,尼基塔的厨房里有一堆脏盘子。尼基塔必须将它们清洗并放入烘干机中。在干燥机中,盘子也应堆叠放置,并且盘子尺寸应从下到上增加。所有盘子的尺寸都是不同的。
Nikita 没有那么多可用空间,具体来说,他只能再容纳一叠盘子。因此,他只能进行这样两个操作:
- 从脏堆顶部取出 1 到 a 任意数量的盘子,清洗它们并将它们放入中间堆。
- 从中间堆顶部取出 1 到 b 任意数量的盘子,并将它们放入烘干机中的堆中。
请注意,执行每项操作后,板的放置顺序与操作前相同。
给定了脏堆栈中按从下到上的顺序排列的盘子 s1、s2、...、sn 的大小,以及整数 a 和 b。所有尺寸都是不同的。编写一个程序来确定 Nikita 是否可以将盘子按照从上到下递增的顺序放入烘干机中。如果他能够做到这一点,程序应该找到一些操作序列(不一定是最佳的)来实现它。
输入
第一行包含三个整数 n、a 和 b (1 ≤ n ≤ 2000, 1 ≤ a, b ≤ n)。第二行包含整数 s1、s2、...、sn (1 ≤ si ≤ n) — 按从下到上的顺序排列的板的尺寸。所有尺寸都是不同的。
输出
如果有解决方案,请在第一行打印“YES”。在本例中,在第二行中打印整数 k — 操作次数。然后在 k 行中打印操作,每行一个。每个操作由两个整数 tj 和 cj 描述,其中 tj = 1,如果操作是从脏堆叠中清洗顶部 cj 位置并将它们放入中间堆叠上,并且 tj = 2,如果操作是将顶部 cj 板从中间堆叠移动到干燥机。
如果没有解决方案,请打印单行“NO”。
如果有多个解决方案,请打印其中任何一个。请注意,没有必要最小化操作数量。
示例
输入 #1
6 2 3 2 3 6 4 1 5
输出 #1
YES 8 1 2 1 1 2 1 1 2 1 1 2 1 2 1 2 3
输入 #2
7 7 7 1 2 3 4 5 6 7
输出 #2
YES 2 1 7 2 7
输入 #3
7 1 1 1 2 3 4 5 6 7
输出 #3
YES 14 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
输入#4
4 2 2 3 2 1 4
输出#4
NO
注意
在第一个示例中,板的初始顺序是 2, 3, 6, 4, 1, 5。以下是每次操作后堆栈的样子:
- [1 2]:脏堆栈:6、 4、 1、 5。中间堆栈:2、 3。烘干机已空。
- [1 1]:脏堆栈:4、 1、 5。中间堆栈:6、 2、 3。烘干机已空。
- [2 1]:脏烟囱:4、 1、 5。中间烟囱:2、 3。干燥烟囱:6。
- [1 2]:脏烟囱:5。中间烟囱:4、 1、 2、 3。烘干机烟囱:6。
- [1 1]:没有脏盘子。中间烟囱:5、 4、 1、 2、 3。烘干机烟囱:6。
- [2 1]:没有脏盘子。中间烟囱:4、 1、 2、 3。干燥烟囱:5、 6。
- [2 1]:没有脏盘子。中间烟囱:1、 2、 3。干燥烟囱:4、 5、 6。
- [2 3]:所有板都在干燥器中:1、 2、 3、 4、 5、 6。
这在第三个示例中是不可能的,因为不允许同时移动多个板。可以一张一张地清洗印版,以便将它们以相反的顺序放置到中间堆上,然后将印版一张一张地移至干燥机。最后的顺序是正确的。