Vitya 喜欢编程和解决问题,但有时,为了分散自己的注意力,他会玩电脑游戏。有一次他发现了一款新的有趣的坦克游戏,他非常喜欢它,以至于一天之内几乎通关了所有的关卡。只剩下最后一层了,太难了。然后Vitya想起他是一名程序员,并编写了一个程序帮助他通过了这个困难的关卡。尝试做同样的事情。
比赛组织如下。有一条很长的路,有两个牢房宽 n 细胞长。有些细胞有障碍。您控制一辆占据一个单元的坦克。最初,坦克位于道路起点之前的一个带有坐标的单元格中 (0, 1)。你的任务是将坦克移动到路的尽头,到牢房 (n + 1, 1) or (n + 1, 2).
坦克每秒向右移动一个单元格:坐标 x 增加 1。当按下向上或向下箭头键时,坦克立即改变车道,即 y 坐标。当你按下空格键时,坦克会射击,坦克行驶的车道上最近的障碍物会立即被摧毁。为了给火炮装弹,坦克需要 t 秒。最初,枪未装弹,这意味着只有在 坦克开始移动后 t 秒。
如果在某个时刻,坦克与尚未摧毁的障碍物位于同一个牢房中,它就会烧毁。如果恰好在坦克前进的瞬间按下箭头,坦克会先前进,然后再变道,所以就不可能斜行了。
你的任务是找出是否有可能通过关卡,如果可能的话,找出玩家需要采取的行动顺序。
输入
第一行包含四个整数 n, m1, m2 和 t,分别为场地长度、第一车道障碍物数量、第二车道障碍物数量和装弹前坦克步数(1 ≤ n ≤ 109; 0 ≤ m1, m2 ≤ n; 0 ≤ m1 + m2 ≤ 106; 1 ≤ t ≤ n).
接下来的两行包含障碍物的描述。这些行中的第一行包含 m1 号码 xi — 第一车道的障碍物坐标(1 ≤ xi ≤ n; xi < xi + 1)。的 y 所有这些障碍物的坐标将是 1.
第二行包含 m2 以相同格式描述第二车道障碍物的数字。的 y 所有这些障碍物的坐标将是 2.
输出
在第一行打印 «是»,如果可以通过关卡,或者 «No»,否则。
如果可能,则在第二行中打印坦克从一个车道移动到另一个车道的次数,并在下一行中打印转换的坐标,每个转换一个数字:坐标 x (0 ≤ x ≤ n + 1)。所有过渡坐标坐标必须是不同的,并且应严格按递增顺序输出。过渡的数量不应超过 2·106。如果水箱可以通过液位,那么它可以使用不超过 2·106 转换。
在第四行中打印坦克在移动过程中的射击次数,在接下来的行中打印两个数字, x 和 y 点的坐标 (1 ≤ x ≤ n, 1 ≤ y ≤ 2),坦克从中发射一枪,射击次数不得超过 m1 + m2。射击必须按照射击顺序输出。
如果有多个解,则输出任意一个。
示例
输入复制
6 2 3 2
2 6
3 5 6
输出复制
Yes
2
0 3
2
2 2
4 1
输入复制
1 1 1 1
1
1
输出复制
No
输入复制
9 5 2 5
1 2 7 8 9
4 6
输出复制
Yes
4
0 3 5 10
1
5 2
注意
第一个样本测试的图片。