For a triangle containing the square with vertices at \((0,0),(0,1),(1,0),(1,1)\), it holds that \(M\leq S\), where \(M\) is the maximum absolute value of the coordinates of the triangle’s vertices and \(\frac{S}{2}\) is the area of the triangle.

Therefore, it is possible to perform a brute-force search when \(S\) is small.

Then, it can be confirmed that there are no good triangles when \(S=1,2,3,5,7\).

When \(S=4\), there is a good triangle, as shown in the sample.

For other \(S\), a good triangle can be constructed as follows.

For coprime positive integers \(p,q\) greater than or equal to \(2\), there are positive integers \(s\) and \(t\) that satisfy the following conditions:

• \(1\leq s\lt p\)
• \(1\leq t\lt q\)
• \(sq-tp=1\)

Using such \(p,q,s,t\), the triangle with vertices at \((0,0),(p,q),(s+1,t-1)\) is a good triangle with an area of \(\frac{p+q+1}{2}\).

The area is derived from \((s+1)q-(t-1)p=sq-tp+q+p=1+p+q\).

The triangle contains a square with \((s,t)\) and \((s+1,t-1)\) as the endpoints of a diagonal.

Among the lattice points contained in the triangle, \((s,t)\) is the only one closest to the line connecting \((0,0)\) and \((p,q)\), excluding \((0,0)\) and \((p,q)\), and \((s+1,t-1)\) is the only farthest one.

Since \((1,-1)\) and \((p+1,q-1)\) are not contained in the triangle, \((s,t)\) is the only pair of integers \((a,b)\) such that both \((a,b)\) and \((a+1,b-1)\) are contained in the triangle.

Therefore, there are no squares other than the one with \((s,t)\) and \((s+1,t-1)\) as the endpoints of a diagonal.

If you can find one pair of \(p\) and \(q\) such that \(S=p+q+1\), you can find \(s\) and \(t\) using Euclid’s algorithm and print a good triangle.

For \(p=2,3,\dots\) in this order, you should check whether \(p\) and \(q=S-p-1\) are coprime.

Each test case can be solved in time complexity \(O(\log(S))\).

Also, by case distinction based on multiples of \(8\) or multiples of \(2\), it can be solved in \(O(1)\).