The original version of this problem was proposed by members of KEYENCE Corp.

It is sufficient to solve the following problem \(N\) times: “do there exist \(a\) and \(b\) such that the area is equal to some given \(S\)?” Let us brute force over every \(a\) and \(b\).

If \(a > S\) or \(b > s\), then the area \(4ab+3a+3b\) is obviously greater than \(S\). Therefore, we may brute force over \(a\le S\) and \(b\leq S\).

The complexity is \(O(N \max(S_i)^2)\).

Sample code (C)
Sample code (Python)

• Bonus 1：Solve for \(N\leq 10^6\)、\(S_i\leq 10^3\). (Worth 300 points?)
• Bonus 2：Solve for \(N\leq 10^6\)、\(S_i\leq 10^5\) (Worth 400 points?)
• Bonus 3：Solve for \(N\leq 10^3\)、\(S_i\leq 10^8\) (Worth 400 points?)