P7905 The Battle of the Scalpers

Source: Sky City. In this problem, “scalpers” (黄牛) only refers to a type of monster in a certain game, and has nothing to do with the usual meaning of “[**ticket scalpers**](https://baike.baidu.com/item/黄牛党/285883)”. This problem is labeled as “3 grays and 1 black” in the recommended list, but that does not really mean its difficulty is similar to those problems. Legend says that a very long time ago, there was a Sky City floating above the mainland of Meland. It was the center of wealth, power, and honor. Then one day, it suddenly disappeared without a trace. Now, after being missing for centuries, Sky City has suddenly appeared again. Warriors from the kingdom want to explore it, but airship tickets are not easy to obtain. **The captain of the airship dock is Medlon · Duruf. To profit, the captain requires everyone to *buy* *a* *ticket* *to* *board*. Travelers without tickets cannot board.** As the leader of the scalpers—“Huangniu Party” (黄牛党)—d琢喵 sent $q$ groups of scalpers to buy out Medlon · Duruf’s tickets. She then sold these tickets at high prices and made huge profits from the price difference. To maintain order at the airship dock, Medlon · Duruf forbids humans and scalpers from fighting. Of course, the captain did not say that scalpers are not allowed to fight each other.

d琢喵 has two types of scalpers under her command: 1. Type I scalper: “attack” is $a$, “health” is $A$. 2. Type II scalper: “attack” is $b$, “health” is $B$. Battles between scalpers follow these rules: 1. At any time, if one side’s “health” $\le 0$, the opponent wins. 2. Each round, the side with higher “attack” acts first. 3. In each round, both sides act once, and the damage dealt equals their “attack” value. The constructed Type III scalper must satisfy the following: 1. Its “attack” value is different from both Type I and Type II. 2. In a battle between Type I and Type II, Type II wins. (If the input does not satisfy this, output `-1 -1` directly.) 3. In a battle between Type II and Type III, Type III wins. 4. In a battle between Type III and Type I, Type I wins. Please provide one valid construction. --- **Brief statement** Solve the system (if $x=\text{true}$ then $[x]=1$, otherwise $=0$): $$\begin{aligned}\left\lceil\frac{A}{b}\right\rceil&+[b

**This problem has multiple test cases.** The first line contains a positive integer $q$. The next $q$ lines each contain four positive integers $a,A,b,B$. The data guarantees $a\ne b$.

Output $q$ lines. Each line contains two positive integers: the constructed Type III scalper’s “attack” value and “health” value. If there is no solution, output `-1 -1`. **This problem uses Special Judge; any solution that satisfies the requirements will be accepted.**

### Sample Explanation For sample #1, we can set $A$ to be $(1,5)$, $B$ to be $(2,3)$, and $C$ to be $(4,1)$. Here, the pair $(x,y)$ represents a scalper with “attack” $x$ and “health” $y$. The table below shows the battle results among $A$, $B$, and $C$. The numbers in parentheses indicate their “health” at the start of each round. | A vs. B | B vs. C | C vs. A | | :----------: | :----------: | :----------: | | $\begin{aligned}&\texttt{A(5)~B(3)}\overset{\texttt{A-2~B-1}}{\Rightarrow\Rightarrow}\\&\texttt{A(3)~B(2)}\overset{\texttt{A-2~B-1}}{\Rightarrow\Rightarrow}\\&\texttt{A(1)~B(1)}\overset{\texttt{A-2}}{\Rightarrow}\\&\texttt{A}\le\texttt{0~\color{red}B win}\end{aligned}$ | $\begin{aligned}&\texttt{B(3)~C(1)}\overset{\texttt{B-4}}{\Rightarrow}\\&\texttt{B}\le\texttt{0~\color{red}C win}\end{aligned}$ | $\begin{aligned}&\texttt{A(5)~C(1)}\overset{\texttt{A-4~C-1}}{\Rightarrow\Rightarrow}\\&\texttt{C}\le\texttt{0~\color{red}A win}\end{aligned}$ | Therefore, outputting such a Type III scalper will be accepted. For sample #2: fixing the Type III scalper’s attack to be $11$ is already enough to defeat the Type II scalper, and a health value in $11\sim14$ can still lose to the Type I scalper. So any output of one valid pair will be accepted. For sample #3: the Type II scalper is very strong, making it hard to construct a Type III scalper that can both defeat Type II and lose to Type I. So outputting `-1 -1` will be accepted. ### Constraints Let $M=\max\left(a,A,b,B\right)$: - Subtask1(10pts): $M\le10,q=399\underline0$. - Subtask2(20pts): $M\le100,q=399\underline1$, data is random. - Subtask3(10pts): $M\le10^5,q=99\underline2$, data is random. - Subtask4(20pts): $M\le10^5,q=99\underline3$. - Subtask5(10pts): $q=399\underline4$, data is random. - Subtask6(30pts): $q=399\underline5$, no special restrictions. - This problem uses different time limits based on testdata strength. If a reasonable full-score solution is being time-hacked, please contact me. Hint: the last digit of the number of test cases $q$ (namely $\underline0,\underline1,\underline2,\underline3,\underline4,\underline5$) may help you judge the Subtask type. For $100\%$ of the data: $1\le q 9) print(x / 10); putchar(x % 10 + '0'); } void printsp(int x){ print(x), putchar(' '); } void println(int x){ print(x), putchar('\n'); } char str[] = "E .in"; const int Buff = 3989; std::string string; namespace Data_Maker{ std::mt19937 rnd(time(0)); int rand(int l, int r) { int x = r - l + 1; return (rnd() % x + x) % x + l; } int a, A, b, B; void maker(int subtaskID) { int t = Buff + subtaskID; if (3