Transforming Integer Pairs

Given two ordered pairs of positive integers ( (a, b) ) and ( (c, d) ), you are allowed to perform at most (65) transformations in order to convert ( (a, b) ) into ( (c, d) ). Note that the pairs are ordered, i.e. ( (x, y) ) is different from ( (y, x) ) if ( x \neq y ).

In one transformation, you can choose one of the two numbers in the current pair ( (x, y) ) and denote it by (a) while the other is (b). Then, choose a positive integer (k) satisfying (1 \le k \le a). After that, perform one of the following two moves:

• Type 1: Replace \( (x, y) \) with \( \Big(\left\lfloor \frac{x}{k}\right\rfloor,\, y \cdot k\Big) \).
• Type 2: Replace \( (x, y) \) with \( \Big( x \cdot k,\, \left\lfloor \frac{y}{k}\right\rfloor \Big) \) (here you choose \(k\) with \(1 \le k \le y\)).

The floor operation is denoted by \(\lfloor \cdot \rfloor\). It is clear that after every transformation, the pair remains a pair of positive integers. It is not required to minimize the number of moves; any valid sequence of at most \(65\) moves is accepted if it transforms \( (a, b) \) to \( (c, d) \). If it is impossible to do so, output -1.

Input Format: Four positive integers \(a, b, c, d\) on one line.
Output Format: If a sequence of moves exists, output an integer \(n\) (the number of moves, where \(0 \le n \le 65\)) on the first line, followed by \(n\) lines each containing two integers. Each of these lines should have the form type k, where type is either 1 or 2 indicating the type of transformation, and k is the parameter chosen. If \( (a, b) = (c, d) \), output 0 and no further lines. Otherwise, if no sequence of at most \(65\) moves exists, output -1.

inputFormat

The input consists of a single line containing four space-separated positive integers: (a), (b), (c), and (d).

outputFormat

If a sequence of at most (65) moves exists to transform ( (a, b) ) into ( (c, d) ), then output the number of moves on the first line, followed by that many lines each describing a move in the format: type k. If ( (a, b) = (c, d) ), output 0. If no such sequence exists, output -1.

sample

5 7 5 7

0