题目背景

Source：天空之城

本题背景中「黄牛」仅代指某游戏中的一种怪物，与一般含义的「黄牛」无关。

本题「推荐题目」三灰一黑，但不太能说明本题难度和他们差不多（

相传在很久很久之前梅兰德大陆上空漂浮着一座天空之城，是当时财富、力量、荣誉中心，突然有一天再也不见踪影。

如今已多个世纪不见痕迹的天空之城突然出现，王国的勇士去探索一番，但是飞船船票可不是那么好得到的。

飞艇码头的船长是梅德龙 · 杜鲁夫，船长为了牟利要求大家必须 买 票 上 船，没有票的旅行者无法登船。

დ琢喵 作为一届黄牛的首领——黄牛党，派出了 $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，所有满足要求的解均给分。

3
1 5 2 3
2 3 4 1
4 1 1 5

4 1
1 5
2 3

4
14 1 10 15
14 1 10 15
14 1 10 15
14 1 10 15

11 11
11 12
11 13
11 14

1
1 1 999 999

-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$ 限制的测试数据。

#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 来获取返回信息。

#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 出题人。