{"problem":{"name":"One Square in a Triangle","description":{"content":"A triangle $ABC$ on the $xy$\\-plane is said to be a good triangle when it satisfies all of the following conditions. *   Each of the vertices $A$, $B$, and $C$ is a lattice point whose $x$\\- and $y$\\","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc167_e"},"statements":[{"statement_type":"Markdown","content":"A triangle $ABC$ on the $xy$\\-plane is said to be a good triangle when it satisfies all of the following conditions.\n\n*   Each of the vertices $A$, $B$, and $C$ is a lattice point whose $x$\\- and $y$\\-coordinates are between $0$ and $10^{8}$, inclusive.\n*   The triangle $ABC$ (**including** the perimeter and vertices) wholly contains exactly one square of area $1$ whose vertices are all lattice points.\n\nYou are given a positive integer $S$.\nDetermine if there is a good triangle of area $\\frac{S}{2}$, and construct one if it exists.\nFor each input file, you have $T$ test cases to solve.\n\n## Constraints\n\n*   $1\\leq T\\leq 10^{5}$\n*   $1\\leq S\\leq 10^{8}$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_{1}$\n$\\text{case}_{2}$\n$\\vdots$\n$\\text{case}_{T}$\n\nEach case is given in the following format:\n\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc167_e","tags":[],"sample_group":[["3\n1\n4\n15","No\nYes\n1 1 1 3 3 3\nYes\n5 1 7 8 4 5\n\n![image](https://img.atcoder.jp/arc167/d6986726412312ca9a6e022bc8e722ce.png)\nIn the figure, the left and right triangles correspond to the second and third test cases, respectively."]],"created_at":"2026-03-03 11:01:14"}}