Background

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”.

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.

Problem Description

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<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}$$

Given $a,A,b,B$, find $c,C$.

Input Format

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 Format

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.

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

Hint

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<4000,1\le M\le10^8$.

Large Samples

This problem provides test cases that satisfy the constraints of Subtask $2,3,5$.

Compile and run the code below, and you will get E01.in, E02.in, E03.in, which are testdata satisfying the constraints of Subtask $2,3,5$ respectively.

#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();
}

The following Special Judge is also provided. You can compile it and call spj E.in E.out E.ans to get feedback.

#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!");
}

In addition, the attachments include the actual method used to generate the official data. If you have stronger and meaningful testdata, feel free to suggest it in the discussion area and @ the problem setter.

Translated by ChatGPT 5