{"problem":{"name":"C. Constructing Tests","description":{"content":"Let's denote a _m_\\-free matrix as a binary (that is, consisting of only 1's and 0's) matrix such that every square submatrix of size _m_ × _m_ of this matrix contains at least one zero. Consider the","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF938C"},"statements":[{"statement_type":"Markdown","content":"Let's denote a _m_\\-free matrix as a binary (that is, consisting of only 1's and 0's) matrix such that every square submatrix of size _m_ × _m_ of this matrix contains at least one zero.\n\nConsider the following problem:\n\n_You are given two integers _n_ and _m_. You have to construct an _m_\\-free square matrix of size _n_ × _n_ such that **the number of 1's in this matrix is maximum possible**. Print the maximum possible number of 1's in such matrix._\n\nYou don't have to solve this problem. Instead, you have to construct a few tests for it.\n\nYou will be given _t_ numbers _x_1, _x_2, ..., _x__t_. For every , find two integers _n__i_ and _m__i_ (_n__i_ ≥ _m__i_) such that the answer for the aforementioned problem is exactly _x__i_ if we set _n_ = _n__i_ and _m_ = _m__i_.\n\n## Input\n\nThe first line contains one integer _t_ (1 ≤ _t_ ≤ 100) — the number of tests you have to construct.\n\nThen _t_ lines follow, _i_\\-th line containing one integer _x__i_ (0 ≤ _x__i_ ≤ 109).\n\n**Note that in hacks you have to set _t_ = 1**.\n\n## Output\n\nFor each test you have to construct, output two positive numbers _n__i_ and _m__i_ (1 ≤ _m__i_ ≤ _n__i_ ≤ 109) such that the maximum number of 1's in a _m__i_\\-free _n__i_ × _n__i_ matrix is exactly _x__i_. If there are multiple solutions, you may output any of them; and if this is impossible to construct a test, output a single integer  - 1.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"我们定义一个 #cf_span[m]-free 矩阵为一个二进制矩阵（仅由 #cf_span[1] 和 #cf_span[0] 组成），使得该矩阵的每一个大小为 #cf_span[m × m] 的子方阵都至少包含一个零。\n\n考虑以下问题：\n\n_给你两个整数 #cf_span[n] 和 #cf_span[m]。你需要构造一个大小为 #cf_span[n × n] 的 #cf_span[m]-free 矩阵，使得该矩阵中 #cf_span[1] 的数量尽可能多。请输出此类矩阵中 #cf_span[1] 的最大可能数量。_\n\n你不需要解决这个问题。相反，你需要为这个问题构造一些测试用例。\n\n你将得到 #cf_span[t] 个数 #cf_span[x1], #cf_span[x2], ..., #cf_span[xt]。对于每个 #cf_span[xi]，找出两个整数 #cf_span[ni] 和 #cf_span[mi]（#cf_span[ni ≥ mi]），使得当我们将 #cf_span[n = ni] 和 #cf_span[m = mi] 代入上述问题时，答案恰好为 #cf_span[xi]。\n\n第一行包含一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 100]）——你需要构造的测试用例数量。\n\n接下来 #cf_span[t] 行，第 #cf_span[i] 行包含一个整数 #cf_span[xi]（#cf_span[0 ≤ xi ≤ 10^9]）。\n\n*注意：在 Hack 中，你必须设置 #cf_span[t = 1]*。\n\n对于每个你需要构造的测试用例，输出两个正整数 #cf_span[ni] 和 #cf_span[mi]（#cf_span[1 ≤ mi ≤ ni ≤ 10^9]），使得在 #cf_span[mi]-free 的 #cf_span[ni × ni] 矩阵中，#cf_span[1] 的最大数量恰好为 #cf_span[xi]。如果有多个解，你可以输出任意一个；如果无法构造这样的测试用例，则输出单个整数 #cf_span[-1]。\n\n## Input\n\n第一行包含一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 100]）——你需要构造的测试用例数量。然后 #cf_span[t] 行，第 #cf_span[i] 行包含一个整数 #cf_span[xi]（#cf_span[0 ≤ xi ≤ 10^9]）。*注意：在 Hack 中，你必须设置 #cf_span[t = 1]*。\n\n## Output\n\n对于每个你需要构造的测试用例，输出两个正整数 #cf_span[ni] 和 #cf_span[mi]（#cf_span[1 ≤ mi ≤ ni ≤ 10^9]），使得在 #cf_span[mi]-free 的 #cf_span[ni × ni] 矩阵中，#cf_span[1] 的最大数量恰好为 #cf_span[xi]。如果有多个解，你可以输出任意一个；如果无法构造这样的测试用例，则输出单个整数 #cf_span[-1]。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ X = \\{x_1, x_2, \\dots, x_t\\} \\subseteq \\mathbb{Z}_{\\geq 0} $ be the given target values.  \n\n**Constraints**  \n1. $ 1 \\leq t \\leq 100 $  \n2. For each $ i \\in \\{1, \\dots, t\\} $, $ 0 \\leq x_i \\leq 10^9 $  \n\n**Objective**  \nFor each $ x_i \\in X $, find integers $ n_i, m_i \\in \\mathbb{Z} $ such that:  \n- $ 1 \\leq m_i \\leq n_i \\leq 10^9 $,  \n- The maximum number of $ 1 $'s in an $ m_i $-free $ n_i \\times n_i $ binary matrix equals $ x_i $.  \n\nIf no such $ (n_i, m_i) $ exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF938C","tags":["binary search","brute force","constructive algorithms"],"sample_group":[["3\n21\n0\n1","5 2\n1 1\n-1"]],"created_at":"2026-03-03 11:00:39"}}