让我们将无 m 矩阵表示为二进制(即仅包含 1 和 0)矩阵,使得该矩阵的每个大小为 m × m 的方形子矩阵都包含至少一个零。
考虑以下问题:
给定两个整数 n 和 m。您必须构造一个大小为 n × n 的无 m 方阵,以使该矩阵中 1 的数量尽可能多。打印该矩阵中 1 的最大可能数量。
你不必解决这个问题。相反,您必须为其构建一些测试。
您将获得 t 个数字 x1, x2, ..., xt。对于 [1,t]$$ 中的每个 $$i \in,找到两个整数 ni 和 mi (ni ≥ mi),如果我们设置 n = ni 和 m = mi,则上述问题的答案正是 xi。
输入
第一行包含一个整数 t (1 ≤ t ≤ 100) — 您必须构建的测试数量。
接下来是 t 行,第 i 行包含一个整数 xi (0 ≤ xi ≤ 109)。
请注意,在 hacks 中你必须设置 t = 1。
输出
对于您必须构造的每个测试,输出两个正数 ni 和 mi (1 ≤ mi ≤ ni ≤ 109),使得无 mi ni × ni 矩阵中 1 的最大数量恰好为 xi。如果有多个解,可以输出任意一个;如果无法构建测试,则输出单个整数 - 1。
示例
输入 #1
3 21 0 1
输出 #1
5 2 1 1 -1