一名玩家来到赌场,发现一台老虎机,一切都取决于他如何玩。规则如下。
屏幕上最初出现一个正整数 $$$a$$$。玩家可以将一枚硬币放入机器中,然后将 $$$1$$$ 添加到或减去 $$$1$$$ 的任意两个相邻数字。执行此操作后,所有数字必须保持在 $$$0$$$ 到 $$$9$$$ 之间,并且前导数字不得为零。换句话说,禁止将 $$$1$$$ 添加到 $$$9$$$、从 $$$0$$$ 减去 $$$1$$$ 以及从前导 $$$1$$$ 减去 $$$1$$$。一旦屏幕上的数字等于 $$$b$$$,玩家就赢得了大奖。 $$$a$$$ 和 $$$b$$$ 具有相同的位数。
帮助玩家确定赢得头奖所需花费的最少硬币数量并告诉玩家如何玩。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) 代表数字 $$$a$$$ 和 $$$b$$$ 的长度。
接下来的两行包含数字 $$$a$$$ 和 $$$b$$$,每个数字位于单独的行上 ($$$10^{n-1} \le a, b < 10^n$$$)。
输出
如果不可能赢得大奖,则打印单个整数 $$$-1$$$。
否则,第一行必须包含玩家必须花费的最小可能数量 $$$c$$$ 的硬币。
$$$\min(c, 10^5)$$$ 行,其中 $$$i$$$ 行包含两个整数 $$$d_i$$$ 和 $$$s_i$$$ ($$$1\le d_i\le n - 1$$$, $$$s_i = \pm 1$$$) 表示第 $$$i$$$ 行步骤中,玩家应将 $$$s_i$$$ 添加到左侧的第 $$$d_i$$$ 和第 $$$(d_i + 1)$$$ 位数字(例如 $$$d_i = 1$$$ 表示两个前导数字发生变化,而 $$$d_i = n - 1$$$ 表示有两个尾随数字发生变化)。
请注意,答案可能非常大,如果 $$$c > 10^5$$$,您应该只打印前 $$$10^5$$$ 动作。如果能够以尽可能少的硬币完成打印的动作并赢得大奖,则您的答案被认为是正确的。特别是,如果有多种方法可以执行此操作,则可以输出其中任何一种。
示例
输入 #1
3 223 322
输出 #1
2 1 1 2 -1
输入 #2
2 20 42
输出 #2
2 1 1 1 1
输入 #3
2 35 44
输出 #3
-1
注意
在第一个示例中,我们可以对前两位进行 +1 运算,将数字 $$$\textbf{22}3$$$ 转换为 $$$\textbf{33}3$$$,然后对最后两位进行 -1 运算,将 $$$3\textbf{33}$$$ 转换为 $$$3\textbf{22}$$$。
也可以以相反的顺序执行这些操作,这给出了另一个正确答案。
在最后一个示例中,可以表明不可能将 $$$35$$$ 转换为 $$$44$$$。