C. Middle Point
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bobo is exploring a set of lattice points on a two-dimensional plane. Initially, the set of points is defined as $$$S = \{(0,0),(A,0),(0,B),(A,B)\}$$$. Bobo's goal is to include a specific lattice point $$$(X,Y)$$$ in $$$S$$$. To achieve the goal, Bobo may perform the following operation:

  • Select two lattice points $$$P,Q \in S$$$ such that $$$\frac{P+Q}{2}$$$ is also a lattice point, and add $$$\frac{P+Q}{2}$$$ to $$$S$$$.

Your task is to help Bobo find a sequence of operations that minimizes the number of steps to achieve the goal or determine if it is impossible to do so.

Input

The first line of the input contains two integers $$$A$$$ and $$$B$$$ ($$$0 \le A,B \le 10^9$$$), describing the parameters of the initial lattice points.

The second line of the input contains two integers $$$X$$$ and $$$Y$$$ ($$$0 \le X \le A$$$, $$$0 \le Y \le B$$$), denoting the coordinates of the target lattice point.

Output

If it is impossible to achieve the goal, output $$$-1$$$ in one line. Otherwise, output a single integer $$$k$$$ ($$$0 \le k \le 10^5$$$) in one line, denoting the total number of operations to perform. Then $$$k$$$ lines follow. The $$$i$$$-th line contains four integers $$$U_i,V_i,S_i,T_i$$$ ($$$0 \le U_i,V_i,S_i,T_i \le 10^9$$$), describing the lattice points $$$P=(U_i,V_i)$$$ and $$$Q=(S_i,T_i)$$$ chosen in the $$$i$$$-th operation. If there exist multiple solutions, output any.

Examples
Input
2 2
1 1
Output
1
0 0 2 2
Input
8 8
5 0
Output
3
0 0 8 0
4 0 8 0
4 0 6 0
Input
0 0
0 0
Output
0
Input
2024 0
1012 0
Output
1
0 0 2024 0
Input
2024 2024
2023 2023
Output
-1
Input
8 6
7 3
Output
3
0 0 8 0
4 0 8 0
6 0 8 6