黄牛の争
题目背景
Source：天空之城
本题背景中「黄牛」仅代指某游戏中的一种怪物，与一般含义的「[**黄牛**](https://baike.baidu.com/item/黄牛党/285883)」无关。
本题「推荐题目」三灰一黑，但不太能说明本题难度和他们差不多（
相传在很久很久之前梅兰德大陆上空漂浮着一座天空之城，是当时财富、力量、荣誉中心，突然有一天再也不见踪影。
如今已多个世纪不见痕迹的天空之城突然出现，王国的勇士去探索一番，但是飞船船票可不是那么好得到的。
**飞艇码头的船长是梅德龙 · 杜鲁夫，船长为了牟利要求大家必须 *买* *票* *上* *船*，没有票的旅行者无法登船。**
დ琢喵 作为一届黄牛的首领——黄牛党，派出了 $q$ 组黄牛买断了梅德龙 · 杜鲁夫的船票。
她以高价卖出这些船票，并通过差价获取巨额利润。
为维护飞艇码头的治安，梅德龙 · 杜鲁夫规定不允许人类和黄牛打架，当然船长并没有规定黄牛之间不可以打架。
题目描述
დ琢喵 的手下有两种黄牛：
1. I 类黄牛「攻击」为 $a$，「血量」为 $A$；
2. II 类黄牛「攻击」为 $b$，「血量」为 $B$。
黄牛之间的作战，满足以下条件：
1. 任意时刻，某一方「血量」$\le 0$ 时，其对手胜利；
2. 每一回合，「攻击」高者先手；
3. 每回合每方出手一次，造成的伤害即其「攻击」值。
构造的 III 类黄牛应当满足下面条件：
1. 「攻击」数值与 I 类黄牛和 II 类黄牛都不同；
2. I 类黄牛和 II 类黄牛作战 II 类黄牛胜利；（若输入不满足该条件则应直接输出 `-1 -1`）
3. II 类黄牛和 III 类黄牛作战 III 类黄牛胜利；
4. III 类黄牛和 I 类黄牛作战 I 类黄牛胜利。
请给出一种合法的构造。
---
**题意简述**
解方程：（若 $x=\text{true}$ 则 $[x]=1$ 反之 $=0$）
$$\begin{aligned}\left\lceil\frac{A}{b}\right\rceil&+[b<a]\le\left\lceil\frac{B}{a}\right\rceil\\\left\lceil\frac{B}{c}\right\rceil&+[c<b]\le\left\lceil\frac{C}{b}\right\rceil\\\left\lceil\frac{C}{a}\right\rceil&+[a<c]\le\left\lceil\frac{A}{c}\right\rceil\\c&\ne a~\text{and}~c\ne b\end{aligned}$$
已知 $a,A,b,B$，解 $c,C$。
输入输出格式
输入格式
**本题多测。**
第一行一个正整数 $q$。
接下来 $q$ 行，每行四个正整数 $a,A,b,B$。
数据满足 $a\ne b$。
输出格式
一共 $q$ 行，每行两个正整数表示你构造的 III 类黄牛的「攻击」数值和「血量」数值，无解时输出 `-1 -1`。
**本题采用 Special Judge，所有满足要求的解均给分。**
输入输出样例
输入样例 #1
3
1 5 2 3
2 3 4 1
4 1 1 5输出样例 #1
4 1
1 5
2 3输入样例 #2
4
14 1 10 15
14 1 10 15
14 1 10 15
14 1 10 15输出样例 #2
11 11
11 12
11 13
11 14输入样例 #3
1
1 1 999 999输出样例 #3
-1 -1说明
### 样例说明
对于样例 #1，可设 A 是 $(1,5)$，B 是 $(2,3)$，C 是 $(4,1)$。
其中二元组 $(x,y)$ 表示一个「攻击」为 $x$，「血量」为 $y$ 的黄牛。
下面的表格展现了 A、B、C 的对战情况，括号中的数字表示每回合开始时它们的「血量」数值。
| A 和 B 单挑 | B 和 C 单挑 | C 和 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}$ |
因此输出剩下一类黄牛即给分。
对于样例 #2：钦定 III 类黄牛攻击力为 $11$，已经足以击倒 II 类黄牛，血量为 $11\sim14$ 都可以输给 I 类黄牛。
因此任意输出一组均给分。
对于样例 #3：II 类黄牛十分强大，难以再构造又能击败 II 类黄牛又能输给 I 类黄牛的 III 类黄牛品种。
因此输出 `-1 -1` 即给分。
### 数据规模
设 $M=\max\left(a,A,b,B\right)$：
- Subtask1(10pts)：$M\le10,q=399\underline0$。
- Subtask2(20pts)：$M\le100,q=399\underline1$，数据随机。
- Subtask3(10pts)：$M\le10^5,q=99\underline2$，数据随机。
- Subtask4(20pts)：$M\le10^5,q=99\underline3$。
- Subtask5(10pts)：$q=399\underline4$，数据随机。
- Subtask6(30pts)：$q=399\underline5$，无特殊限制。
- 本题根据数据强度设置了不同梯度的时间限制，如果有合理的满分做法被卡了请联系我。
提示：数据组数 $q$ **结尾** 的数字（$\underline0,\underline1,\underline2,\underline3,\underline4,\underline5$）可能有助于你判断 Subtask 的类型。
对于 $100\%$ 的数据：$1\le q<4000,1\le M\le10^8$。
### 大样例
本题提供符合 Subtask $2,3,5$ 限制的测试用例。
直接编译并运行下面代码，即可得到 `E01.in` `E02.in` `E03.in` 分别是满足 Subtask $2,3,5$ 限制的测试数据。
```cpp
#include<ctime>
#include<cstdio>
#include<random>
#include<string>
#include<cassert>
#include<cstdlib>
#include<iostream>
#define int long long
void print(int x){
if (x < 0) x = -x, putchar('-');
if (x > 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 <= subtaskID && subtaskID <= 4)
t -= 3000;
println(t);
if (subtaskID == 2 || subtaskID == 3 || subtaskID == 5) {
int MOD = 0;
if (subtaskID == 2) MOD = 100;
if (subtaskID == 3) MOD = 100000;
if (subtaskID == 5) MOD = 100000000;
while (t--) {
a = rand(1, MOD), A = rand(1, MOD);
b = rand(1, MOD), B = rand(1, MOD);
while (b == a)
b = rand(1, MOD);
printsp(a), printsp(A), printsp(b), println(B);
}
}
}
void File(int Test) {
str[1] = Test / 10 + '0';
str[2] = Test % 10 + '0';
freopen(str, "w", stdout);
}
void Subtask2() {
for (int Test = 1; Test <= 1; ++Test) {
File(Test); maker(2);
}
}
void Subtask3() {
for (int Test = 2; Test <= 2; ++Test) {
File(Test); maker(3);
}
}
void Subtask5() {
for (int Test = 3; Test <= 3; ++Test) {
File(Test); maker(5);
}
}
}
using namespace Data_Maker;
signed main(){
Subtask2();
Subtask3();
Subtask5();
}
```
另外还提供了下面的 Special Judge，可以编译并通过调用 `spj E.in E.out E.ans` 来获取返回信息。
```cpp
#include "testlib.h"
#define int long long
#define inf inf.readLong()
#define ouf ouf.readLong()
#define ans ans.readLong()
bool win(int a, int A, int b, int B){
int x = 0, f = 1;
if (a < b)
a ^= b ^= a ^= b, A ^= B ^= A ^= B, f *= -1;
while (1) {
if (B - a <= 0) {
x = 1;
break;
}
if (A - b <= 0) {
x = -1;
break;
}
B -= a, A -= b;
}
x *= f;
return x < 0;
}
signed main (signed argc, char**argv) {
registerTestlibCmd(argc, argv);
int q = inf;
for (int t = 1; t <= q; ++t) {
int a = inf, A = inf, b = inf, B = inf, c = ouf, C = ouf, d = ans, D = ans;
if (d == -1 && c == -1 && C == -1)
continue;
if (c == a)
quitf (_wa, "Test #%lld, a cannot equal to c!", t);
if (c < 1 || C < 1)
quitf (_wa, "Test #%lld, cannot print negative numbers!", t);
if (!win(c, C, a, A))
quitf (_wa, "Test #%lld, A cannot beat C!", t);
if (!win(b, B, c, C))
quitf (_wa, "Test #%lld, C cannot beat B!", t);
if (!win(a, A, b, B))
quitf (_wa, "Test #%lld, B cannot beat A!", t);
}
quitf (_ok, "Good job!");
}
```
题目附件中的是本题实际数据的脚造方式，如有更强有意义的数据欢迎在讨论区中提出并 at 出题人。