Once in a casino
Contest: Technocup 2019 - Final
Difficulty rating: 2700
Tags: constructive algorithms, math

One player came to a casino and found a slot machine where everything depends only on how he plays. The rules follow.

A positive integer $$$a$$$ is initially on the screen. The player can put a coin into the machine and then add $$$1$$$ to or subtract $$$1$$$ from any two adjacent digits. All digits must remain from $$$0$$$ to $$$9$$$ after this operation, and the leading digit must not equal zero. In other words, it is forbidden to add $$$1$$$ to $$$9$$$, to subtract $$$1$$$ from $$$0$$$ and to subtract $$$1$$$ from the leading $$$1$$$. Once the number on the screen becomes equal to $$$b$$$, the player wins the jackpot. $$$a$$$ and $$$b$$$ have the same number of digits.

Help the player to determine the minimal number of coins he needs to spend in order to win the jackpot and tell how to play.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) standing for the length of numbers $$$a$$$ and $$$b$$$.

The next two lines contain numbers $$$a$$$ and $$$b$$$, each one on a separate line ($$$10^{n-1} \le a, b < 10^n$$$).

Output format:
If it is impossible to win the jackpot, print a single integer $$$-1$$$.

Otherwise, the first line must contain the minimal possible number $$$c$$$ of coins the player has to spend.

$$$\min(c, 10^5)$$$ lines should follow, $$$i$$$-th of them containing two integers $$$d_i$$$ and $$$s_i$$$ ($$$1\le d_i\le n - 1$$$, $$$s_i = \pm 1$$$) denoting that on the $$$i$$$-th step the player should add $$$s_i$$$ to the $$$d_i$$$-th and $$$(d_i + 1)$$$-st digits from the left (e. g. $$$d_i = 1$$$ means that two leading digits change while $$$d_i = n - 1$$$ means that there are two trailing digits which change).

Please notice that the answer may be very big and in case $$$c > 10^5$$$ you should print only the first $$$10^5$$$ moves. Your answer is considered correct if it is possible to finish your printed moves to win the jackpot in the minimal possible number of coins. In particular, if there are multiple ways to do this, you can output any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, we can make a +1 operation on the two first digits, transforming number $$$\textbf{22}3$$$ into $$$\textbf{33}3$$$, and then make a -1 operation on the last two digits, transforming $$$3\textbf{33}$$$ into $$$3\textbf{22}$$$.

It's also possible to do these operations in reverse order, which makes another correct answer.

In the last example, one can show that it's impossible to transform $$$35$$$ into $$$44$$$.

Example input:
3
223
322

Example output:
2
1 1
2 -1

Example input:
2
20
42

Example output:
2
1 1
1 1

Editorial:
Since each operation saves the alternating series of the digits, if it's different for $$$a$$$ and $$$b$$$, then the answer is '-1'. Now we prove that otherwise it's possible to win.
Let's imagine that digits can be negative or bigger than 9 (that is, for example, number 19 can become the number with digits 2 and 10). Denote by $$$a_i$$$ the $$$i$$$-th digit of $$$a$$$ (and similarly for $$$b$$$). Now there is no difference between any two orders of the same set of operations, so we can do allowed operations from left to right. After we do all operations with first digit (there are at least $$$|a_1 - b_1|$$$ such operations), $$$a_2$$$ will become equal to $$$a_2 + b_1 - a_1$$$. After we do all operations with $$$a_2$$$ and $$$a_3$$$ (there are at least $$$|a_2 + b_1 - a_1 - b_2|$$$ such operations), $$$a_3$$$ will be equal to $$$a_3 + b_2 - a_2 - b_1 + a_1$$$, and so on. Thus we can calculate the minimal total number of operations and find their set. The goal is to prove that it's possible to perform them in some order and never break the rules about the correctness of intermediate numbers.
Indeed, let's just perform these operations from left to right. Assume that we can't perform the current operation. Without loss of generality assume that we can't decrease two digits: one of $$$a_k$$$ and $$$a_{k + 1}$$$ is 0 now. It's easy to see that $$$a_k > 0$$$ because after we perform the set of our operations ignoring the rules, $$$a_k$$$ will become $$$b_k$$$, which is nonnegative. Hence $$$a_{k + 1} = 0$$$. Then we must increase $$$a_{k + 1}$$$ and $$$a_{k + 2}$$$ at least once (again because we can ignore the rules and get $$$b_{k + 1}$$$ in the end). If we can do it then we do it and then decrease $$$a_k$$$ and $$$a_{k + 1}$$$ just as planned and then continue performing the operations. Otherwise, $$$a_{k + 2} = 9$$$. Reasoning similarly, either we can decrease $$$a_{k + 2}$$$ and $$$a_{k + 3}$$$, or $$$a_{k + 3} = 0$$$, et cetera. As it can't continue infinitely, we can perform some operations from our set and decrease $$$a_k$$$ and $$$a_{k + 1}$$$, so we can reach the goal doing the minimal number of operations.