【MX-X4-T3】「Jason-1」数对变换

对于一个**正整数**数对 $(x, y)$，定义一次变换为：选择其中一个数 $a$，记另一个数为 $b$，同时选择一个正整数 $k \leq a$，然后将 $a$ 除以 $k$ 向下取整，同时将 $b$ 乘以 $k$。 形式化地说，对于数对 $(x,y)$，你可以执行以下两种变换： - 类型 1：取 $1 \le k \le x$，令 $(x,y) \gets (\lfloor \frac{x}{k} \rfloor, y \cdot k)$。 - 类型 2：取 $1 \le k \le y$，令 $(x,y) \gets (x \cdot k, \lfloor \frac{y}{k} \rfloor)$。 显然，变换后的数对仍然是正整数数对。 给出两组正整数数对 $(a, b)$ 与 $(c, d)$，你需要执行**不超过 $\bm{65}$ 次**变换将 $(a, b)$ 变为 $(c, d)$，或者报告无解。**注意：你不需要最小化执行变换的次数**。 需要注意数对是有序的，即若 $x \neq y$，则 $(x,y) \neq (y,x)$。 本题使用**自定义校验器**检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出**任意一种**。

**本题输入包含多组数据。** 第一行，一个正整数 $T$，表示数据组数。对于每组数据： - 仅一行，四个正整数 $a, b, c, d$，表示两组数对。

对于每组数据： - 若无解， - 仅一行一个字符串 `-1`。 - 否则， - 第一行，一个非负整数 $m$，表示你执行变换的次数。**你需要保证 $\bm{0 \le m \le 65}$，但不需要最小化 $\bm m$**。 - 接下来 $m$ 行，第 $i$ 行两个整数 $\mathit{op}, k$，表示你执行的第 $i$ 次变换。其中 $\mathit{op} \in \{1, 2\}$ 表示变换类型，$k$ 即为本次变换中选择的 $k$。 本题使用**自定义校验器**检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出**任意一种**。

7
1 1 1 1
1 2 1 1
2 2 1 2
10 10 2 50
5 5 4 10
80 43 52 64
987654321 123456789 313814116 388538872

0
-1
3
1 2
2 3
1 2
1
1 5
-1
2
1 3
2 2
2
1 31415
2 9982

**【样例解释】** 对于第 1 组数据，不需要进行任何操作，因为初始时 $a = c$ 且 $b = d$。 对于第 2 组数据，可以证明无解。 对于第 3 组数据，第一次变换后 $(a,b)=(1,4)$，第二次变换后 $(a,b)=(3,1)$，第三次变换后 $(a,b)=(1,2)$。 对于第 4 组数据，一次变换即可使 $a = c$ 且 $b = d$。 对于第 5 组数据，可以证明无解。 对于第 6 组数据，第一次变换后 $(a,b)=(26,129)$，第二次变换后 $(a,b)=(52,64)$。 对于第 7 组数据，第一次变换后 $(a,b)=(31438,3878395026435)$，第二次变换后 $(a,b)=(313814116,388538872)$。 **【数据范围】** **本题采用捆绑测试。** 令 $n=\max(a,b,c,d)$。 | 子任务 | $n\le$| 特殊性质 | 分值 | | :--------------: | :-----: |:-----:| :--------: | | 1 | $6$ | 无 | $7$ | | 2 | $10^5$ | A | $11$ | | 3 | $10^5$ | C | $13$ | | 4 | $10^6$ | B | $23$ | | 5 | $10^9$ | C | $19$ | | 6 | $10^9$ | 无 | $27$ | - 特殊性质 A：保证 $\dfrac{a}{c}=\dfrac{d}{b}$。 - 特殊性质 B：保证 $a=b$ 且 $c=d$。 - 特殊性质 C：保证 $a,b,c,d$ 在值域内独立均匀随机生成。 对于 $100\%$ 的数据，$1 \le T \le 10^4$，$1 \le a,b,c,d \le 10^9$。